算法

Cherzing2024年8月8日大约 24 分钟

评价决策类

层次分析法

> 将定量分析与定性分析结合起来，用决策者的经验判断各衡量目标之间能否实现的标准之间的相对重要程度 >

层次分析法（AHP简化版）-SPSSPRO帮助中心

层次分析法（AHP专业版）-SPSSPRO帮助中心

概念

面临各种各样的方案，要进行比较、判断、评价、直至最后的决策。这个过程中都是一些主观的因素，这些因素可能由于个人情况的不同，有相应不同的比重，所以这样主观因素给数学方法的解决带来了很多的不便。

层次分析法：（ AnalyticHierarchyProcess，简称AHP）是对一些较为复杂、较为模糊的问题作出决策的简易方法，它特别适用于那些难于完全定量分析的问题它是美国运筹学家 T．L．Saaty 教授于上世纪70年代初期提出的一种简便、灵活而又实用的多准则决策方法

模型原理

应用 AHP 分析决策问题时，首先要把问题条理化、层次化，构造出一个有层次的结构模型。在这个模型下，复杂问题被分解为元素的组成部分。这些元素又按其属性及关系形成若干层次。上一层次的元素作为准则对下一层次有关元素起支配作用。这些层次可以分为三类：

最高层：这一层次中只有一个元素，一般它是分析问题的预定目标或理想结果，因此也称为目标层。
中间层：这一层次中包含了为实现目标所涉及的中间环节，它可以由若干个层次组成，包括所需考虑的准则、子准则，因此也称为准则层。·
最底层：这一层次包括了为实现目标可供选择的各种措施、决策方案等，因此也称为措施层或方案层。

基本步骤：
运用层次分析法建模，大体上可按下面四个步骤进行：
建立递阶层次结构模型
构造出各层次中的所有****判断矩阵
一致性检验
求权重后进行评价

构造判断矩阵

两两比较的过程中忽略了其他因素，导致出现的结果可能出现矛盾
所以需要一致性检验

一致性检验
+ $a_{i j} = \frac{i 的重要程度}{j 的重要程度}$ ， $a_{i k} = \frac{i 的重要程度}{k 的重要程度}$ ， $a_{k j} = \frac{k 的重要程度}{j 的重要程度}$

易得 $a_{i j} = a_{i k} * a_{k j}$ 且矩阵各列（行）城倍数关系，满足这两条的矩阵是一致矩阵，不会出现矛盾的情况

一致矩阵：
若矩阵中的每个元素 $a_{i j} > 0$ 且满足 $a_{i j} * a_{j i} = 1$ ，我们称为该矩阵为正互反矩阵。在层次分析法中，我们构造的判断矩阵均是正互反矩阵。
若正互反矩阵满足 $a_{i k} * a_{k j} = a_{i j}$ ，则我们称其为一致矩阵

一致性检验的步骤

计算一致性指标CI

查找对应的平均随机一致性指标RI

建立一致性比例CR

求权重

算数平均法

TOPSIS--优劣解距离法

:::info **基本概念**：通过各**备选方案**与**理想解**和**负理想解**做比较，若其中有一个方案最接近理想解，而同时又远离负理想解，则该方案是备选方案中最好的方案。

TOPSIS通过最接近理想解且最远离负理想解来确定最优选择

基本原理：通过归一化后(去量纲化)的数据规范化矩阵，找出多个目标中最优目标和最劣目标(分别用理归想一解化和反理想解表示),分别计算各评价目标与理想解和反理想解的距离,获得各目标与理想解的贴近度，按理想解贴近度的大小排序，以此作为评价目标优劣的依据。

贴近度取值在0～1之间，该值愈接近1,表示相应的评价目标越接近最优水平；反之,该值愈接近0,表示评价目标越接近最劣水平。

:::

步骤：

将原始矩阵正向化

将原始矩阵正向化，就是要将所有的指标类型统一转化为极大型指标。

正向矩阵标准化

标准化的方法有很多种，其主要目的就是去除量纲的影响,保证不同评价指标在同一数量级，且数据大小排序不变

计算得分并归一化
+ $S_{i} = \frac{D_{i}^{-}}{D_{i}^{+} + D_{i}^{-}}$ 其中 $S_{i}$ 为得分， $D_{i}^{+}$ 为评价对象与最大值的距离， $D_{i}^{+}$ 为评价对象与最小值的距离
原始矩阵正向化

指标名称	指标特点
极大型指标	越大越好
极小型指标	越小越好
中间型指标	越接近某个值越好
区间型指标	落在某个区间最好

矩阵正向化就是将所有的指标类型统一转化为极大型指标

将正向化的矩阵标准化

消除不同指标量纲的影响

标准化后，还需给不同指标加上权重，采用的权重确定方法有层次分析法、熵权法、Delphi法、对数最小二乘法等。在这里认为各个指标的权重相同

计算得分并归一化

上一步得到标准化矩阵

熵权法

**基本概念：**

对于某项指标，可以用熵值来判断某个指标的离散程度，其信息熵值越小，指标的离散程度越大，该指标对综合评价的影响（即权重）就越大，如果某项指标的值全部相等，则该指标在综合评价中不起作用。因此，可利用信息熵这个工具，计算出各个指标的权重，为多指标综合评价提供依据。
熵权法是一种客观的赋权方法，它可以靠数据本身得出权重。
依据的原理：指标的变异程度越小，所反映的信息量也越少，其对应的权值也应该越低

基本步骤

模糊综合评价

**模糊集合的表示方法**

模糊集合的分类

模糊集合主要有三类，分别为偏小型，中间型和偏大型。其实也就类似于TOPSIS方法中的极大型、极小型、中间型、区间型指标。

举个例子，“年轻”就是一个偏小型的模糊集合，因为岁数越小，隶属度越大，就越“年轻”；“年老”则是一个偏大型的模糊集合，岁数越大，隶属度越大，越“年老”；而“中年”则是一个中间型集合，岁数只有处在某个中间的范围，隶属度才越大。总结来说，就是考虑“元素”与“隶属度”的关系，再类比一下，就是考虑隶属函数的单调性。

隶属函数的确定

**模糊统计法：**问卷
借助已有的客观尺度

对于某些模糊集合，我们可以用已经有的指标去作为元素的隶属度。

例如“小康家庭”这个模糊集合，就可以用“恩格尔系数（食品支出总额/家庭总支出）”衡量相应的隶属度。显而易见，家庭越接近小康水平，其恩格尔系数应该越低，那“1-恩格尔系数”就越大，我们便可以把“1-恩格尔系数”看作家庭相对于“小康家庭”的隶属度。

对于“质量稳定”这一模糊集合，我们可以使用正品率衡量隶属度。

注意：隶属度是在[0,1]之间的。如果找的指标不在，可以进行归一化处理。

指派法

指派法是一个主观性比较强的方法，即凭主观意愿，在确定模糊集合的所属分类后，给它指派一个隶属函数，得到元素的隶属度。这是比赛中最常用的方法之一，只需进行选择，便可得到隶属函数。

右边是常用的模糊分布：可以看出，对于偏小型模糊集合，隶属函数总体上递减，也就是元素的某个特征越大，隶属度越小；对于偏大型集合，隶属函数总体上递增，也就是元素的某个特征越大，隶属度越大；对于中间型集合，隶属函数总体上先递增后递减，中间一部分或是某个点取到最大值。

灰色关联分析

[灰色关联分析-SPSSPRO帮助中心](https://www.spsspro.com/help/Grey-correlation-analysis/)

什么是灰色系统？

灰色系统理论是1982年由邓聚龙创立的一门边缘性学科（interdisciplinary）。灰色系统用颜色深浅反映信息量的多少。说一个系统是黑色的，就是说这个系统是黑洞洞的，信息量太少；说一个系统是白色的，就是说这个系统是清楚的，信息量充足。而处于黑白之间的系统，或说信息不完全的系统，称为灰色系统或简称灰系统
“灰”的基本含义：
系统因素不完全明确
因素关系不完全清楚系统的结构不完全知道
系统的作用原理不完全明了
什么是关联分析？
所谓关联分析，就是系统地分析因素。回答的问题是：某个包含多种因素的系统中，哪些因素是主要的，哪些是次要的；哪些因素影响大，哪些因素影响小；哪些因素是明显的，哪些因素是潜在的；哪些是需要发展的，那些需要抑

灰色关联度分析：

灰色关联度分析（Grey Relation Analysis，GRA），是一种多因素统计分析的方法。灰色关联分析方法弥补了采用数理统计方法作系统分析所导致的缺憾。它对样本量的多少和样本有无规律都同样适用，而且计算量小,十分方便,更不会出现量化结果与定性分析结果不符的情况。
灰色关联分析的基本思想是根据序列曲线几何形状的相似程度来判断其联系是否紧密。曲线越接近,相应序列之间的关联度就越大,反之就越小。
对一个抽象的系统或现象进行分析,首先要选准反映系统行为特征的数据序列,称为找系统行为的映射量，用映射量来间接地表征系统行为。例如,用国民平均接受教育的年数来反映教育发达程度,用刑事案件的发案率来反映社会治安面貌和社会秩序,用医院挂号次数来反映国民的健康水平等。有了系统行为特征数据和相关因素的数据，即可作出各个序列的图形,从直观上进行分析

关联分析的步骤:

母序列

能反映出系统行为特征的数据序列，类似于因变量 $Y$ 。记为 $Y = [y_{1}, y_{2}, . . ., y_{n}]^{T}$

子序列

X_{n m} = [\begin{matrix} x_{11} & x_{12} & \dots & x_{1 m} \\ x_{21} & x_{22} & \dots & x_{2 m} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ x_{n 1} & x_{n 2} & \dots & x_{n m} \end{matrix}]

数据预处理

由于不同要素具有不同量纲和数据范围，因此我们要对他们进行预处理去量纲，将他们统一到近似的范围内，先求出每个指标的均值，在用指标中的元素除以其均值

$\tilde{y_{k}} = \frac{y_{k}}{\overset{―}{y_{i}}}, \overset{―}{y_{i}} = \frac{1}{n} \sum_{k = 1}^{n} y_{k}$

$\tilde{x_{k i}} = \frac{x_{k i}}{\overset{―}{x_{i}}}, \overset{―}{x_{i}} = \frac{1}{n} \sum_{k = 1}^{n} x_{k i} (i = 1, 2, \dots, m)$

计算灰色关联系数

计算子序列中各个指标与木序列的关联系数

记为： $a = {m i n}_{i} m i n_{k} | x_{0} (k) - x_{i} (k) |$ ,

$b = m a x_{i} m a x_{k} | x_{0} (k) - x_{i} (k) |$ ,

为两极最小差和最大差

构造：

计算关联度

注意：

灰色关联分析时，数据一定需要大于 0，原因在于如果小于 0 进行计算时会出现‘抵消’现象，并不符合灰色关联分析的计算原理。如果出现小于 0 数据，建议作为空值处理或者填补；
在选择量纲处理方式时，一般地，初值化方法适用于稳定递增或递减的数据，而均值化适合没有明显升降趋势现象的数据；
母序列是指标的参照对比项，比如研究 5 个指标与母序列的关联程度，通常研究者需要自己提供母序列数据。

运筹优化类

机理分析类

数理统计类

机器学习

### 线性回归模型原理：使用数据点来寻找最佳拟合线。

公式，V=mx+c，其中v是因变量，x是自变量，利用给定的数据集求m和c 的值。

逻辑回归模型（梯度下降法）

逻辑回归(梯度下降法)-SPSSPRO帮助中心

原理：通过将线性回归模型的输出通过一个逻辑函数进行转换，将连续的预测值映射到和之间，表示属于某一类的概率。

逻辑回归的模型假设因变量服从伯努利分布，近通过最大似然估计来拟合模型参数。

决策树模型

决策树模型是一种常见的机器学习算法，主要用于分类和回归任务。它是一种树形结构，其中每个内部节点代表一个特征或属性，每个分支代表一个测试结果，每个叶节点代表一个类别或决策结果。

原理：决策树通过对数据集进行递归地划分，以建立一个树形结构，每个内部节点表示一个属性上的测试，每个分支代表一个测试输出，每个叶节点代表一个类别标签或者一个连续值。

构建过程

选择最优特征：在构建决策树时，首先需要确定在每个节点上使用哪个特征进行分割。这通常通过一些标准（如信息增益、增益率、基尼不纯度等）来评估每个特征的重要性。
分割数据集：根据选定的特征和阈值，将数据集分割成子集。
重复过程：对每个子集重复上述过程，直到满足停止条件（如子集大小小于预定阈值、没有更多特征可分割、达到最大深度等）。
生成叶节点：当达到停止条件时，生成叶节点，并根据子集中的数据分布来标记类别或回归值。

常用算法

ID3：使用信息增益作为特征选择标准。
C4.5：改进的ID3算法，使用增益率来选择特征，能够处理连续和缺失值。
CART（分类和回归树）：既可用于分类也可用于回归，使用基尼不纯度作为分类标准，使用最小二乘回归作为回归标准。

决策树回归--预测

[xgboost回归-SPSSPRO帮助中心](https://www.spsspro.com/help/trees-regressor/)

决策树分类--分类

[决策树分类-SPSSPRO帮助中心](https://www.spsspro.com/help/tree-classifier/)

朴素贝叶斯分类

朴素贝叶斯分类器-SPSSPRO帮助中心

朴素贝叶斯分类是一种基于贝叶斯定理的简单概率分类器。它在分类问题中假设特征之间相互独立，即一个特征或属性的出现不依赖于其他特征。这种“朴素”的假设使得模型在计算上变得简单且高效，尽管在现实世界中特征之间往往存在一定的依赖关系。

BP神经网络

随机森林

随机森林分类-SPSSPRO帮助中心

随机森林（Random Forest）是一种基于树的集成学习算法，它通过组合多个决策树来进行预测

基本原理

随机森林的基本思想是构建多个决策树，并对它们的预测结果进行投票（在分类问题中）或平均（在回归问题中）。每个决策树都是在随机抽样的数据集上训练的，并且特征的选取也是随机的。

构建过程

以下是构建随机森林的基本步骤：

数据抽样：从原始数据集中进行有放回的抽样（Bootstrapping），生成多个不同的训练数据集。
特征选择：在每个决策树的节点上，随机选择一个特征子集，并从中选择最优特征进行分割。
树的生长：在每个训练数据集上，使用选定的特征构建决策树。树的生长过程不需要剪枝，让每棵树尽可能地生长。
森林的构建：重复步骤1到3多次，生成多棵决策树，组成随机森林。
预测：对于新的实例，每棵树都会给出一个预测结果。在分类问题中，通过投票来选择最终类别；在回归问题中，取所有树的预测结果的平均值作为最终预测。

关键概念

Bootstrap抽样：有放回的随机抽样，用于生成训练数据集。
特征子集：在构建每棵树时，不是考虑所有特征，而是随机选择一个特征子集。
Out-of-Bag (OOB)：由于Bootstrap抽样，大约有1/3的数据没有被选中用于训练特定的树。这些数据称为OOB数据，可以用来估计模型的泛化误差。

优点

准确度高：随机森林通常比单个决策树具有更高的预测准确度。
鲁棒性强：由于随机性的引入，随机森林对噪声和异常值不敏感。
泛化能力强：随机森林不易过拟合，适用于各种数据集。
能够处理高维数据：随机森林能够处理具有大量特征的数据集。
特征重要性评估：随机森林可以提供特征重要性的排序，有助于特征选择。

缺点

计算成本高：相比于单个决策树，随机森林的训练和预测成本较高。
不易解释：随机森林的内部结构比较复杂，不如单个决策树那样直观易懂。

支持向量机

支持向量机(SVM)分类-SPSSPRO帮助中心

支持向量机（Support Vector Machine，简称SVM）是一种用于分类和回归分析的机器学习算法。SVM在分类问题中特别有效，尤其是在高维空间中。

基本原理

SVM的基本思想是找到一个最优的超平面，将不同类别的数据点分开，并且使得类别之间的间隔（margin）尽可能大。间隔最大化可以提供更好的泛化能力，减少模型的过拟合风险。

关键概念

超平面：在二维空间中是一个线，在三维空间中是一个平面，在高维空间中是超平面。
支持向量：距离超平面最近的那些数据点，它们对于确定超平面的位置至关重要。
间隔：超平面到最近的支持向量的距离。

构建过程

以下是构建SVM分类器的基本步骤：

数据预处理：确保数据是数值型的，并且进行标准化或归一化。
选择核函数：根据数据的分布，选择合适的核函数。最简单的是线性核，但还有多项式核、径向基函数（RBF）核等。
优化目标：找到最优的超平面，即使得间隔最大化的超平面。这可以通过解决以下优化问题来实现：

其中，𝑤 是超平面的法向量，𝑏是偏置项，𝑥𝑖 是特征向量，𝑦𝑖__是对应的类别标签（取值 +1 或 -1）。

使用拉格朗日乘子法：引入拉格朗日乘子，将上述约束优化问题转化为无约束优化问题。
求解对偶问题：通过求解对偶问题，找到最优的拉格朗日乘子 𝛼𝑖_α__i_，进而确定 𝑤w 和 𝑏_b_。
构建决策函数：使用支持向量来构建决策函数，用于对新实例进行分类。

优点

泛化能力强：由于间隔最大化，SVM通常具有很好的泛化能力。
适用于高维数据：SVM可以有效处理高维数据，甚至是超过样本数量的维度。
效果好：在许多问题上，SVM都能提供高质量的分类结果。

缺点

计算成本高：对于大规模数据集，SVM的训练时间可能会很长。
难以解释：SVM模型的决策函数比较复杂，不易解释。
对参数敏感：SVM的性能对参数选择比较敏感。

聚类分析--KNN

K近邻(KNN)回归-SPSSPRO帮助中心

K近邻(KNN)分类-SPSSPRO帮助中心

KNN（K-Nearest Neighbors）通常被误认为是聚类模型，但实际上它是一种监督学习算法，用于分类和回归任务。KNN算法的核心思想是基于相似度原则，通过查找最近邻的K个训练样本来确定新样本的类别或回归值

基本原理

在KNN算法中，一个新样本的分类是由其最近邻的K个样本投票决定的。在回归任务中，新样本的值通常是K个最近邻样本值的平均值。

KNN算法步骤

选择距离度量：确定用于计算样本之间距离的度量方法，常见的有欧几里得距离、曼哈顿距离等。
选择K值：确定最近邻的数目K。K值的选择对模型的性能有很大影响。
分类或回归：
- 分类：对于一个新的输入样本，计算它与所有训练样本的距离，找出K个最近邻，然后根据这K个最近邻的多数类别来确定新样本的类别。
- 回归：对于一个新的输入样本，找出K个最近邻，然后取这K个最近邻的输出值的平均值作为新样本的预测值。

优点

简单易懂：KNN算法的概念非常直观，易于理解。
无需训练：KNN没有显式的训练过程，只需存储训练数据。
适应性强：KNN可以适用于任何形状的数据，因为它不依赖于数据的分布假设。

缺点

计算成本高：对于每个新样本，都需要计算它与所有训练样本的距离，这在数据量大时计算成本很高。
对噪声敏感：KNN算法容易受到异常值的影响。
K值选择困难：K值的选择对结果影响很大，但并没有一个明确的方法来确定最佳的K值。

与聚类算法的区别

监督与无监督：KNN是一种监督学习算法，需要使用带有标签的训练数据。而聚类是一种无监督学习算法，不需要预先标记的数据。
目标：KNN的目标是根据训练数据对新的数据点进行分类或回归。而聚类的目标是发现数据中的自然分组或结构。

K-means

聚类分析(K-Means)-SPSSPRO帮助中心

聚类分析(K-Means)是一种基于中心的无监督学习聚类算法（K 均值聚类），通过迭代，将样本分组成k个簇，使得每个样本与其所属类的中心或均值的距离之和最小。与分层聚类等按照字段进行聚类的算法不同的是，K-Means算法是按照样本进行聚类。

基本原理

K-means算法的目标是将相似的数据点归到同一个簇中，而将不相似的数据点归到不同的簇中。算法通过迭代过程来实现这一目标，以下是该算法的基本步骤：

随机初始化：在数据集中随机选择K个数据点作为初始的簇中心（Centroids）。
分配数据点：对于数据集中的每一个数据点，计算它与每个簇中心的距离，并将其分配到最近的簇中心所代表的簇中。
更新簇中心：计算每个簇中所有数据点的均值，将该均值作为新的簇中心。
重复迭代：重复步骤2和步骤3，直到满足停止条件。停止条件可以是簇中心的变化小于某个阈值、达到预设的迭代次数等。
输出结果：当算法停止时，输出最终的簇分配结果和簇中心。

关键概念

簇中心（Centroid）：一个簇中所有数据点的均值，代表该簇的中心位置。
距离度量：通常使用欧几里得距离来计算数据点与簇中心的距离。

优点

简单易实现：K-means算法的原理和实现都比较简单。
适用于大规模数据集：K-means算法能够处理包含大量数据点的数据集。
簇内相似度高：K-means能够使得簇内数据点的相似度尽可能高。

缺点

需要预先指定K值：在实际应用中，K值的选取可能不是那么直观。
对初始中心敏感：算法的性能可能受到初始中心选择的影响。
只能发现球形簇：K-means假设簇是凸形的，并且大小相似，这使得它不适用于发现非球形簇或大小差异很大的簇。
易受噪声和离群点影响：噪声和离群点可能会对簇中心产生较大影响。

其他算法

${\begin{cases} max_{a \in A_{t}} [C o s t (a) + V_{t + 1} (s^{'}, W^{'}, F^{'}, M^{'})], & 若 t < N \\ M, & 若 t = N 且玩家在终点 \end{cases}$

其中， $(A_{t})$ 是在状态 $((s, W, F, M))$ 下第 $(t)$ 天可行的动作集， $(C o s t (a))$ 是执行动作 $(a)$ 的即时成本（通常为0，因为成本已体现在状态转移中）， $((s^{'}, W^{'}, F^{'}, M^{'}))$ 是执行 $(a)$ 后的新状态。