数学建模常见算法的通俗理解（更新中）

1.层次分析法（结合某些属性及个人倾向，做出某种决定）

1.1 粗浅理解

举一个例子：我们想选择一个旅游地，对于不用的旅游地有不同属性，而且我们对于不同的属性也有不同的倾向（比如旅游地有景点和旅途两个属性，每个旅游地的属性好坏不同，而且我们可能在选择旅游地时更倾向于景点或旅途，这样得出的决策就会更符合自身实际）

层次分析法就是将一个决策事件分解为目标层（例如选择旅游地），准则层（影响决策的因素，例如景点、旅途等）以及方案层（指的是方案，例如去某地旅游）

层次分析法大致有如下过程：

?1.2 算法过程

1.2.1 构造判断矩阵

构造判断矩阵就是通过各要素之间相互两两比较，并确定各准则层对目标层的权重。

简单地说，就是把准则层的指标进行两两判断，通常我们使用Santy的1-9标度方法给出。

初始表格如下（每个属性对于自身的重要性为1）：?

?如果我们认为属性2比属性1明显重要，那么：

以此类推，当我们填完这个表格，判断矩阵A就构造出来了

1.2.2 计算权重向量

简单来说，就是将判断矩阵A的列向量归一化，然后求行和得出矩阵后再归一化，这时我们得到一个n行1列的权重向量矩阵W?

1.2.3 计算最大特征根

根据公式：

1.2.4 计算C.I.值

根据公式：

?1.2.5 求解C.R.值

根据公式：

其中R.I.值我们可以查表得知

?1.2.6 判断一致性

C.R.<0.1 时，表明判断矩阵 A 的一致性程度被认为在容许的范围内，此时可用 A 的特征向量开展权向量计算；若 C.R.≥0.1, 说明我们在构建判断矩阵时出现了逻辑错误，这个时候，我们需要对判断矩阵 A 进行修正。

1.2.7 计算总得分

利用权重及得分矩阵来计算，最后得分最高的即为决策方案

2 神经网络（正向流通反向反馈，调整系数，预测结果）

2.1 粗浅理解

1. 设计一个神经网络时，输入层与输出层的节点数往往是固定的，中间层则可以自由指定；
2. 神经网络结构图中的拓扑与箭头代表着预测过程时数据的流向，跟训练时的数据流有一定的区别；
3. 结构图里的关键不是圆圈（代表“神经元”），而是连接线（代表“神经元”之间的连接）。每个连接线对应一个不同的权重（其值称为权值），这是需要训练得到的。??

?大致过程：

2.2 算法过程

2.2.1 划分数据集

大部分用来做训练集训练模型，小部分用来做验证集和测试集证明模型的完备性（可以没有验证集，只不过准确度会稍差一点）

2.2.2?前向传播及反向调整系数（利用梯度下降法）

?

注：这里的S函数是激活函数

?3 决策树（通过若干属性，并进行合理排序，最快做出分类）

3.1 粗浅理解

决策树（Decision Tree）是一种分类和回归方法，是基于各种情况发生的所需条件构成决策树，以实现期望最大化的一种图解法。由于这种决策分支画成图形很像一棵树的枝干，故称决策树。它的运行机制非常通俗易懂，因此被誉为机器学习中，最“友好”的算法。下面通过一个简单的例子来阐述它的执行流程。假设根据大量数据（含 3 个指标：天气、温度、风速）构建了一棵“可预测学校会不会举办运动会”的决策树（如下图所示）。
?

接下来，当我们拿到某个数据时，就能做出对应预测。

在对任意数据进行预测时，都需要从决策树的根结点开始，一步步走到叶子结点（执行决策的过程）。如，对下表中的第一条数据（ [ 阴天，寒冷，强 ] ）：首先从根结点出发，判断 “天气” 取值，而该数据的 “天气” 属性取值为 “阴天”，从决策树可知，此时可直接输出决策结果为 “举行”。这时，无论其他属性取值为什么，都不需要再执行任何决策（类似于 “短路” 现象）。
?

?决策树的组成：

决策树由结点和有向边组成。结点有两种类型：内部结点（圆）和叶结点（矩形）。其中，内部结点表示一个特征（属性）；叶结点表示一个类别。而有向边则对应其所属内部结点的可选项（属性的取值范围）。

?在用决策树进行分类时，首先从根结点出发，对实例在该结点的对应属性进行测试，接着会根据测试结果，将实例分配到其子结点；然后，在子结点继续执行这一流程，如此递归地对实例进行测试并分配，直至到达叶结点；最终，该实例将被分类到叶结点所指示的结果中。

但是，对于每一个属性做出决定的先后顺序没有进行解释

3.2 算法过程

3.2.1 随机分配属性顺序，计算熵值

构建决策树的实质是对特征进行层次选择，而衡量特征选择的合理性指标，则是熵。为便于说明，下面先给出熵的定义：设 𝑋 是取值在有限范围内的一个离散随机变量，其概率密度为：

3.2.2 条件熵的计算?

根据熵的定义，在构建决策树时我们可采用一种很简单的思路来进行“熵减”：每当要选出一个内部结点时，考虑样本中的所有“尚未被使用”特征，并基于该特征的取值对样本数据进行划分。即有：

对于每个特征，都可以算出“该特征各项取值对运动会举办与否”的影响（而衡量各特征谁最合适的准则，即是熵）。为此，引入条件熵。

我们将“天气”特征展开，以分别求解各取值对应集合的熵。实际上，该式的计算正是在求条件熵。条件熵 𝐻(𝑌 | 𝑋) 表示在已知随机变量 𝑋 的条件下随机变量 𝑌 的不确定性。它的数学定义是：若设随机变量 (𝑋, 𝑌) ，其联合概率密度为

?则定义条件熵 𝐻(𝑌 | 𝑋) ：在给定 𝑋 的条件下 𝑌 的条件概率分布对 𝑋 的数学期望，即

3.2.3?根据不同的评选方法，得出最优决策树

1、信息增益（ ID3 算法选用的评估标准）

信息增益 𝑔(𝐷, 𝑋) ：表示某特征 𝑋 使得数据集 𝐷 的不确定性减少程度，定义为集合 𝐷 的熵与在给定特征 𝑋 的条件下 𝐷 的条件熵 𝐻(𝐷 | 𝑋) 之差，即

?2、信息增益率（ C4.5 算法选用的评估标准）
以信息增益作为划分数据集的特征时，其偏向于选择取值较多的特征。比如，当在学校举办运动会的历史数据中加入一个新特征 “编号” 时，该特征将成为最优特征。因为给定 “编号” 就一定知道那天是否举行过运动会，因此 “编号” 的信息增益很高。

但实际我们知道，“编号” 对于类别的划分并没有实际意义。故此，引入信息增益率。

信息增益率 𝑔𝑅(𝐷, 𝑋) 定义为其信息增益 𝑔(𝐷, 𝑋) 与数据集 𝐷 在特征 𝑋 上值的熵 𝐻𝑋(𝐷) 之比，即：

3、基尼系数（ CART 算法选用的评估标准）
从前面的讨论不难看出，无论是 ID3 还是 C4.5 ，都是基于信息论的熵模型出发而得，均涉及了大量对数运算。能不能简化模型同时又不至于完全丢失熵模型的优点呢？分类回归树（Classification and Regression Tree，CART）便是答案，它通过使用基尼系数来代替信息增益率，从而避免复杂的对数运算。基尼系数代表了模型的不纯度，基尼系数越小，则不纯度越低，特征越好。注：这一点和信息增益（率）恰好相反。

在分类问题中，假设有 𝑘 个类别，且第 𝑘 个类别的概率为 𝑝𝑘 ，则基尼系数为

对于给定数据集 𝐷 ，假设有 𝑘 个类别，且第 𝑘 个类别的数量为 𝐶𝑘?，则该数据集的基尼系数为

由于基尼系数 𝐺𝑖𝑛𝑖(𝐷) 表示集合 𝐷 的不确定性，则基尼系数 𝐺𝑖𝑛𝑖(𝐷, 𝑋) 表示 “基于指定特征 𝑋 进行划分后，集合 𝐷 的不确定性”。该值越大，就表示数据集 𝐷 的不确定性越大，也就说明以该特征 进行划分越容易分乱。?

4、基尼增益

同信息增益一样，如果将数据集 𝐷 的基尼系数减去数据集 𝐷 根据特征 𝑋 进行划分后得到的基尼系数

就得到基尼增益（系数）。显然，采用越好的特征进行划分，得到的基尼增益也越大。基于前面各特征对数据集的划分，可得到其对应的基尼增益。

步骤一：先算出初始数据集合 D 的基尼系数

步骤二：计算基尼系数计算基尼增益率

?可见，基尼增益在处理诸如 “编号” 这一类特征时，仍然会认为其是最优特征（此时，可采取类似信息增益率的方式，选用基尼增益率 ）。但对常规特征而言，其评估的合理性还是较优的。

5、基尼增益率

基尼增益率 𝐺𝑅(𝐷, 𝑋) 定义为其尼基增益 𝐺(𝐷, 𝑋) 与数据集 𝐷 在特征 𝑋 上的取值个数之比，即

容易看出，基尼增益率考虑了特征本身的基尼系数（此时，当某特征取值类别较多时， 𝐺𝑅(𝐷, 𝑋) 式中的分母也会增大），从而降低了 “偏向取值较多的特征” 这一影响。

从上面的结果可以看出，基尼增益率能明显降低取值较多的特征偏好现象，从而更合理地评估各特征在划分数据集时取得的效果。?

3.2.4?连续值处理

在前面的数据集中，各项特征（以及标签）均为离散型数据，但有时处理的数据对象可能会含有连续性数值，为了解决这一问题，我们可以对数据进行离散化处理。此时，可把连续取值的数据值域划分为多个区间，并将每个区间视为该特征的一个取值，如此就完成了从连续性数据到离散性数据的转变。?

对于一些有意义的连续值，我们可以通过实际情况来进行划分归类，比如温度：

对于一些无意义的连续值：

62，65，72，86，89，96，102，116，118，120，125，169，187，211，218

?

3.2.5 剪枝处理

对于决策树而言，当你不断向下划分，以构建一棵足够大的决策树时（直到所有叶子结点熵值均为 0），理论上就能将近乎所有数据全部区分开。所以，决策树的过拟合风险非常大。为此，需要对其进行剪枝处理。

常用的剪枝策略主要有两个：

预剪枝；构建决策树的同时进行剪枝处理（更常用）；
后剪枝：构建决策树后再进行剪枝处理。
预剪枝策略可以通过限制树的深度、叶子结点个数、叶子结点含样本数以及信息增量来完成。

这里只讨论预剪枝：

1、限制决策树的深度

下图展示了通过限制树的深度以防止决策树出现过拟合风险的情况。

2、限制决策树中叶子结点的个数

下图展示了通过限制决策树中叶子结点的个数以防止决策树出现过拟合风险的情况。

?

3、限制决策树中叶子结点包含的样本个数

下图展示了通过限制决策树中叶子结点包含的样本个数以防止决策树出现过拟合风险的情况。

?

4、限制决策树的最低信息增益

下图展示了通过限制决策树中叶子结点包含的样本个数以防止决策树出现过拟合风险的情况。

?3.2.6 补充：K折交叉验证

? 交叉验证是在机器学习建立模型和验证模型参数时常用的办法，一般被用于评估一个机器学习模型的表现。更多的情况下，我们也用交叉验证来进行模型选择(model selection)。

? ? ? ? 交叉验证，顾名思义，就是重复的使用数据，把得到的样本数据进行切分，组合为不同的训练集和测试集，用训练集来训练模型，用测试集来评估模型预测的好坏。在此基础上可以得到多组不同的训练集和测试集，某次训练集中的某样本在下次可能成为测试集中的样本，即所谓“交叉”。

? ? ? ? 那么什么时候才需要交叉验证呢？交叉验证用在数据不是很充足的时候。如果数据样本量小于一万条，我们就会采用交叉验证来训练优化选择模型。如果样本大于一万条的话，我们一般随机的把数据分成三份，一份为训练集（Training Set），一份为验证集（Validation Set），最后一份为测试集（Test Set）。用训练集来训练模型，用验证集来评估模型预测的好坏和选择模型及其对应的参数。把最终得到的模型再用于测试集，最终决定使用哪个模型以及对应参数。

? ? ? ? k折交叉验证（ k-Folder Cross Validation），经常会用到的。 k折交叉验证先将数据集 D随机划分为 k个大小相同的互斥子集，即 ，每次随机的选择 k-1份作为训练集，剩下的1份做测试集。当这一轮完成后，重新随机选择 k份来训练数据。若干轮（小于 k ）之后，选择损失函数评估最优的模型和参数。注意，交叉验证法评估结果的稳定性和保真性在很大程度上取决于 k取值。

步骤：
1、首先随机地将数据集切分为 k 个互不相交的大小相同的子集；
2、然后将 k-1 个子集当成训练集训练模型，剩下的 (held out) 一个子集当测试集测试模型；
3、将上一步对可能的 k 种选择重复进行 (每次挑一个不同的子集做测试集)；
4、这样就训练了 k 个模型，每个模型都在相应的测试集上计算测试误差，得到了 k 个测试误差，对这 k 次的测试误差取平均便得到一个交叉验证误差。这便是交叉验证的过程。

k折交叉验证最大的优点：

所有数据都会参与到训练和预测中，有效避免过拟合，充分体现了交叉的思想。

? ? ? ? 交叉验证可能存在 bias 或者 variance。如果我们提高切分的数量 k，variance 会上升但 bias 可能会下降。相反得，如果降低 k，bias 可能会上升但 variance 会下降。bias-variance tradeoff 是一个有趣的问题，我们希望模型的 bias 和 variance 都很低，但有时候做不到，只好权衡利弊，选取他们二者的平衡点。通常使用10折交叉验证，当然这也取决于训练数据的样本数量。

3.2.7 补充：过拟合和欠拟合

?? 欠拟合（Underfitting）是指模型不能获取数据集的主要信息，在训练集及测试集上的表示都十分糟糕。
?? 过拟合（Overfitting）是指模型不仅获取了数据集的信息还提取了噪声数据的信息是的模型在训练集有非常好的表现但在测试集上的表现及其糟糕。
?

4 拟合与插值

问题的引入：
已经测得海洋的某深度的及其对应的水温：

如何根据这些已有的数据如何估计其他深度（比如600,700,800米处）的水温？我们很自然想到深度和水温之间是否存在某种函数关系。

?函数的表达式可能无法给出，只能通过实验或者观察得到有限数量的数据点，那么如何通过数据点得到其他的点函数值？

插值的概念：

在实际问题中，一个函数y=f(x)往往是通过实验观察到的，仅已知函数f(x)在某个区间[a,b]上一系列点的值

当需要这些节点

之间的某点x的函数值时，常用较为简单的，满足一定的条件的函数𝑃(𝑥)去代替真实的，难以得出的𝑓(𝑥)，插值法是一种常用的方法，其插值函数满足

?

拟合的概念：

拟合也是有限个数据点，求近似函数。但是拟合只要求整体上逼近，而不要求一定满足上面的条件，即不要求拟合得到的曲线一定过数据点，但是要求在某种意义上这些点的总偏差最小。

?

?其中样本点较少时（泛指样本点小于30个）采用插值方法，主要有拉格朗日插值算法、牛顿插值、双线性内插和双三次插值
当样本点较多时（泛指样本点大于30个）则采用拟合函数