深度学习500问——Chapter02：机器学习基础（4）

2.12 决策树

2.12.1 决策树的基本原理

决策树（Decision Tree）是一种分为治之的决策过程。一个困难的预测问题，通过树的分支节点，被划分成两个或多个较为简单的子集，从结构上划分为不同的子问题。将依规则分割数据集的过程不断递归下去（Recursive Partitioning）。随着树的深度不断增加，分支节点的子集越来越小，所需要提的问题数也逐渐简化。当分支节点的深度或者问题的简单程度满足一定的停止规则（Stopping Rule）时，该分支节点会停止分裂，此为自上而下的停止阈值（Cutoff Threshold）法；有些决策树也使用自上而下的剪枝（Pruning）法。

2.12.2 决策树的三要素

一棵决策树的生成过程主要分为以下3个部分：

1、特征选择：从训练数据中众多的特征中选择一个特征作为当前节点的分裂标准，如果选择特征有着很多不同量化评估标准，从而衍生处不同的决策树算法。

2、决策树的生成：根据选择的特征评估标准，从上至下递归地生成子节点，直到数据集不可分则决策树停止生长。树结构来说，递归结构是最容易理解的方式。

3、剪枝：决策树容易过拟合，一般来需要剪枝，缩小树结构规模、缓解过拟合。剪枝技术有预剪枝和后剪枝两种。

2.12.3 决策树学习基本算法

2.12.4 决策树算法优缺点

决策树算法的优点：

1、决策树算法易于理解，机理解释起来简单。

2、决策树算法可以用于小数据集。

3、决策树算法的时间复杂度较小，为用于训练决策树的数据点的对数。

4、相比于其他算法智能分析一种类型变量，决策树算法可处理数字和数据的类别。

5、能够处理多输出的问题。

6、对缺失值不敏感。

7、可以处理不相关特征数据。

8、效率高，决策树只需要一次构建，反复使用，每一次预测的最大计算次数不超过决策树的深度。

决策树算法的缺点：

1、对连续性的字段比较难预测。

2、容易出现过拟合。

3、当类别太多时，错误可能就会增加的比较快。

4、在处理特征关联性比较强的数据时表现得不是太好。

5、对于各类别样本数量不一致的数据，在决策树中，信息增益的结果偏向于那些具有更多数值的特征。

2.12.5 熵的概念以及理解

熵：度量随机变量的不确定性。

定义：假设随机变量X的可能取值有 ，对于每一个可能的取值 ，其概率为 。随机变量的熵为： 。对于样本集合，假设样本有k个类别，每个类别的概率为 ，其中 为类别为k的样本个数， 为样本总数。样本集合D的熵为： 。

2.12.6 信息增益的理解

定义：以某种特征划分数据集前后的熵的差值。熵可以表示样本集合的不确定性，熵越大，样本的不确定性就越大。因此可以使用划分前后集合熵的差值来衡量使用当前特征对于样本集合D划分效果的好坏。

假设划分前样本集合D的熵为H(D)。使用某个特征A划分数据集D，计算划分后的数据子集的熵为H(D|A)。

则信息增益为：

注：在决策树构建的过程中我们总是希望集合往最快到达纯度更高的子集方向发展，因此我们总是选择使得信息增益最大的特征来划分当前数据集D。

思想：计算所有特征划分数据集D，得到多个特征划分数据集D的信息增益，从这些信息增益中选择最大的，因而当前结点的划分特征便是使信息增益最大的划分所使用的特征。

另外这里提一下信息增益比相关知识：信息增益比=惩罚参数 X 信息增益。

信息增益比本质：在信息增益的基础之上乘上一个惩罚参数。特征个数较多时，惩罚参数较小；特征个数较少时，惩罚参数较大。

惩罚参数：数据集D有以特征A作为随机变量的熵的倒数。

2.12.7 剪枝处理的作用及策略

剪枝处理是决策树学习算法用来解决过拟合问题的一种办法。

在决策树算法中，为了尽可能正确分类训练样本，节点划分过程不断重复，有时候会造成决策树分支过多，以至于将训练样本集自身特点当作泛化特点，而导致过拟合。因此可以采用剪枝处理来去掉一些分支来降低过拟合的风险。

剪枝的基本策略有预剪枝（pre-pruning）和后剪枝（post-pruning）。

预剪枝：在决策树生成过程中，在每个节点划分前后先估计其划分后的泛化性能，如果不能提升，则停止划分，将当前节点标记为叶结点。

后剪枝：生成决策树以后，再自下而上对非叶结点进行考察，若将此节点标记为叶结点可以带来泛化性能提升，则修改之。

2.13 支持向量机

2.13.1 什么是支持向量机

支持向量：在求解过程中，会发现只根据部分数据就可以确定分类器，这些数据称为支持向量。

支持向量机（Support Vector Machine，SVM）：其含义是通过支持向量运算的分类器。

在一个二维环境中，其中点R，S，G点和其他靠近中间黑线的点可以看作为支持向量，它们可以决定分类器，即黑线的具体参数。

支持向量机是一种二分类模型，它的目的是寻找一个超平面来对样本进行分割，分割的原则是边界最大化，最终转化为一个凸二次规划问题来求解。由简至繁的模型包括：

当训练样本线性可分时，通过硬边界（hard margin）最大化，学习一个线性可分支持向量机；

当训练样本近似线性可分时，通过软边界（soft margin）最大化，学习一个线性支持向量机；

当训练样本线性不可分时，通过核技巧和软边界最大化，学习一个非线性支持向量机。

2.13.2 支持向量机能解决哪些问题

线性分类

在训练数据中，每个数据都有n个的属性和一个二分类类别的标志，我们可以认为这些数据在一个n维空间里。我们的目标是找到一个n-1维的超平面，这个超平面可以将数据分成两部分，每部分数据都属于同一个类别。

这样的超平面有很多，假如我们要找到一个最佳的超平面。此时，增加一个约束条件：要求这个超平面到每边最近数据点的距离是最大的，成为最大边距超平面。这个分类器即为最大边距分类器。

非线性分类

SVM的一个优势是支持非线性分类。它结合使用拉格朗日乘子法（Lagrange Multiplier）和KKT（Karush Kuhn Tucker）条件，以及核函数可以生成非线性分类器。

2.13.3 核函数特点及其作用

引入核函数目的：把原坐标系里的线性不可分的数据用核函数Kernel投影到另一个空间，尽量使得数据在新的空间里线性可分。

核函数方法的广泛应用，与其特点是分不开的：

1）核函数的引入避免了“维数灾难”，大大减小了计算量。而输入空间的维数n对核函数矩阵无影响。因此，核函数方法可以有效处理高维输入。

2）无需知道非线性变换函数 的形式和参数。

3）核函数的形式和参数的变化会隐式地改变从输入空间到特征空间的映射，进而对特征空间的性质产生影响，最终改变各种核函数方法的性能。

4）核函数方法可以和不同的算法相结合，形成多种不同的基于核函数技术的方法，且这两部分的设计可以单独进行，并可以为不同的应用选择不同的核函数和算法。

2.13.4 SVM为什么引入对偶问题

1、对偶问题将原始问题中的约束转为了对偶问题中的等式约束，对偶问题往往更加容易求解。

2、可以很自然的引用核函数（拉格朗日表达式里面有内积，而核函数也是通过内积进行映射的）。

3、在优化理论中，目标函数 f(x) 会有多种形式：如果目标函数和约束条件都为变量 x 的线性函数，称该问题为线性规划；如果目标函数为二次函数，约束条件为线性函数，称该最优化问题为二次规划；如果目标函数或者约束条件均为非线性函数，称该最优化问题为非线性规划。每个线性规划问题都有一个与之对应的对偶问题，对偶问题有非常良好的性质，以下列举几个：

• a, 对偶问题的对偶是原问题；
• b, 无论原始问题是否是凸的，对偶问题都是凸优化问题；
• c, 对偶问题可以给出原始问题一个下界；

2.13.5 如何理解SVM中的对偶问题

在硬边界支持向量机中，问题的求解可以转化为凸二次规划问题。

假设优化目标为： （1）

step 1. 转化问题：  (2)

上式等价于原问题，因为若满足(1)中不等式约束，则(2)式求max时， 必须取0，与（1）等价；若不满足（1）中不等式约束，，(2)中求max会得到无穷大。 交换min和max获得其对偶问题: 交换之后的对偶问题和原问题并不相等，上式的解小于等于原问题的解。

step 2.现在的问题是如何找到问题(1) 的最优值的一个最好的下界?

  (3)

若方程组(3)无解， 则v是问题(1)的一个下界。若(3)有解， 则

由逆否命题得：若 则(3)无解。

那么v是问题（1）的一个下界。 要求得一个好的下界，取最大值即可：

step 3. 令 ， 为原问题的最小值，对应的 分别为 ，则对于任意的 ： ，则 是问题（1）的一个下界。

此时，取最大值即可求得好的下界，即 。

2.13.6 常见的核函数有哪些

2.13.7 SVM的主要特点

特点：

(1) SVM方法的理论基础是非线性映射，SVM利用内积核函数代替向高维空间的非线性映射。

(2) SVM的目标是对特征空间划分得到最优超平面，SVM方法核心是最大化分类边界。

(3) 支持向量是SVM的训练结果，在SVM分类决策中起决定作用的是支持向量。

(4) SVM是一种有坚实理论基础的新颖的适用小样本学习方法。它基本上不涉及概率测度及大数定律等，也简化了通常的分类和回归等问题。

(5) SVM的最终决策函数只由少数的支持向量所确定，计算的复杂性取决于支持向量的数目，而不是样本空间的维数，这在某种意义上避免了“维数灾难”。

(6) 少数支持向量决定了最终结果，这不但可以帮助我们抓住关键样本、“剔除”大量冗余样本,而且注定了该方法不但算法简单，而且具有较好的“鲁棒性”。这种鲁棒性主要体现在：

• ①增、删非支持向量样本对模型没有影响;
• ②支持向量样本集具有一定的鲁棒性;
• ③有些成功的应用中，SVM方法对核的选取不敏感

(7) SVM学习问题可以表示为凸优化问题，因此可以利用已知的有效算法发现目标函数的全局最小值。而其他分类方法（如基于规则的分类器和人工神经网络）都采用一种基于贪心学习的策略来搜索假设空间，这种方法一般只能获得局部最优解。

(8) SVM通过最大化决策边界的边缘来控制模型的能力。尽管如此，用户必须提供其他参数，如使用核函数类型和引入松弛变量等。

(9) SVM在小样本训练集上能够得到比其它算法好很多的结果。SVM优化目标是结构化风险最小，而不是经验风险最小，避免了过拟合问题，通过margin的概念，得到对数据分布的结构化描述，减低了对数据规模和数据分布的要求，有优秀的泛化能力。

(10) 它是一个凸优化问题，因此局部最优解一定是全局最优解的优点。

2.13.8 SVM的主要缺点

（1）SVM算法对大规模训练样本难以实施

SVM的空间消耗主要是存储训练样本和核矩阵，由于SVM是借助二次规划来求解支持向量，而求解二次规划将涉及m阶矩阵的计算（m为样本的个数），当m数目很大时该矩阵的存储和计算将耗费大量的机器内存和运算时间。

如果数据量很大，SVM的训练时间就会比较长，如垃圾邮件的分类检测，没有使用SVM分类器，而是使用简单的朴素贝叶斯分类器，或者是使用逻辑回归模型分类。

（2）用SVM解决多分类问题存在困难

经典的支持向量机算法只给出了二类分类的算法，而在实际应用中，一般要解决多类的分类问题。可以通过多个二类支持向量机的组合来解决。主要有一对多组合模式、一对一组合模式和SVM决策树；再就是通过构造多个分类器的组合来解决问题。主要原理是克服SVM固有的缺点，结合其他算法的优势，解决多类问题的分类精度。如：与粗糙集理论结合，形成一种优势互补的多类问题的组合分类器。

（3）对缺失数据敏感，对参数和核函数的选择敏感

支持向量机性能的优劣主要取决于核函数的选取，所以对于一个实际问题而言，如何根据实际的数据模型选择合适的核函数从而构造SVM算法。目前比较成熟的核函数及其参数的选择都是人为的，根据经验来选取的，带有一定的随意性。在不同的问题领域，核函数应当具有不同的形式和参数，所以在选取时候应该将领域知识引入进来，但是目前还没有好的方法来解决核函数的选取问题。

2.13.9 逻辑回归与SVM的异同

相同点：

LR和SVM都说是分类算法。

LR和SVM都是监督学习算法。

LR和SVM都是判别模型。

如果不考虑核函数，LR和SVM都是线性分类算法，也就是说它们的分类决策面都是线性的。说明：LR也可以用核函数，但LR通常不采用核函数的方法（计算量太大）。

不同点：

1. LR采用log损失，SVM采用合页（hinge）损失

逻辑回归的损失函数：

支持向量机的目标函数：

逻辑回归方法基于概率论，假设样本为1的概率可以用sigmoid函数来表示，然后通过极大似然估计的方法估计出参数的值。

2. LR对异常值敏感，SVM对异常值不敏感

支持向量机只考虑局部的边界线附近的点，而逻辑回归考虑全局。LR模型找到的那个超平面，是尽量让所有点都远离他，而SVM寻找的那个超平面，是只让最靠近中间分割线的那些点尽量远离，即只用到那些支持向量的样本。

支持向量机改变非支持向量样本并不会引起决策面的变化。

逻辑回归中改变任何样本都会引起决策面的变化。

3. 计算复杂度不同。对于海量数据，SVM的效率较低，LR效率比较高

当样本较少，特征维数较低时，SVM和LR的运行时间均比较短，SVM较短一些。准确率的话，LR明显比SVM要高。当样本稍微增加些时，SVM运行时间开始增长，但是准确率赶超了LR。SVM时间虽长，但在可接受范围内。当数据量增长到20000时，特征维数增长到200时，SVM的运行时间剧烈增加，远远超过了LR的运行时间。但是准确率却和LR相差无几。(这其中主要原因是大量非支持向量参与计算，造成SVM的二次规划问题)

4. 对非线性问题的处理方式不同

LR主要靠特征构造，必须组合交叉特征，特征离散化。SVM也可以这样，还可以通过核函数kernel（因为只有支持向量参与核计算，计算复杂度不高）。由于可以利用核函数，SVM则可以通过对偶求解高效处理。LR则在特征空间维度很高时，表现较差。

5. SVM的损失函数就自带正则

损失函数中的 项，这就是为什么SVM是结构风险最小化算法的原因！！！而LR必须另外在损失函数上添加正则项！！

6. SVM自带结构风险最小化，LR则是经验风险最小化

7. SVM会用核函数而LR一般不用核函数