机器学习2-决策树

1 决策树的特点与数学表达

决策树属于监督学习的一种，起源非常早，符合直觉并且非常直观，模仿人类做决策的过程，早起人工智能模型中有很多应用，现在更多时基于决策树的一些集成学习算法。

把决策树的基础学习好，对后续的集成学习很有帮助。

1.1 决策树的特点

1. 可以处理非线性问题
2. 可解释性强，没有θ
3. 模型简单，预测效率高
4. 不容易显示的使用函数表达，不可微 XGBoost

1.2 决策树模型生成与预测

模型生成：通过大数据生成非常好的树，用这棵树来预测新的数据

预测：输入一条新数据，按照生成好的树的标准，落到某一节点上

1.3 决策树的数学表达形式

• 整体方式表达

  

  可以理解为整个树是由多个路径组成，每个路径（有多少个路径呢？其实是有多少个叶子结点，就有多少路径）有不同的分值。其中的qt(x)要么是1or0，gt(x)是每个叶子结点的分值，这样就可以计算出某个值落在哪个叶子结点上的分值。

• 迭代方式表达

  

  可以将上面的树看成由3棵小树组成，根据G(x)的分值决定该往哪走，走到下一个树，在进行G(x)的分值计算，如此递归下去

1.4 构建决策树表达式

通过上面我们了解了两种表达方式，那么我们构建决策树的目标函数

可以看到需要4个选择，也就是提前定义好4个参数：分支的数量、分支的判断、结束判断、基础假设

1.5 总结决策树流程和待解决问题

1. 将原始数据集进行筛选，分裂成子数据集（每次分几份，以什么条件分）
2. 对生成的子数据集不断分裂，直到停止（停止的条件是什么）
3. 利用最终生成的n份数据的共性来代表这个节点（如何用节点共性代表未来预测值？）

总结，决策树的生成说白了就是数据不断分裂的递归过程，每一次分裂，尽可能让类别一样的数据在树的一遍，当树的叶子节点的数据都是一类的时候，则停止分裂。

2 生成决策树所需分裂指标

2.1 常用的分裂条件

• Gini系数
• 信息增益
• 信息增益率
• MSE（回归问题）

2.2 Gini系数（CART）

基尼系数介绍

基尼系数是国际上通用的、用来衡量一个国家或地区收入差距的常用指标

基尼系数最大为“1”，最小为“0”，越接近0表明收入分配越趋于平等。国际上把0.2以下视为收入绝对平等，0.2-0.3视为收入平均，0.3-0.4视为收入相对合理，0.4-0.5视为收入差距较大，当基尼系数达到0.5以上，则表示收入悬殊。国际上通常把0.4作为贫富差距的警戒线，大于这一数值容易出现社会动荡。

公式：

基尼系数在决策树中的应用

Gini系数越小，代表D集合中的数据越纯，所有我们可以计算分裂前的值在按照某个维度对数据集进行划分，然后计算多个节点的Gini系数

2.3 信息增益（ID3）

介绍

在信息论中熵叫做信息量，即熵是对不确定性的度量。从控制论的角度看，应叫不确定性。信息论创始人香农在其著作《通信的数学理论》中提出建立在概率统计模型上的信息度量。他把信息定义为“用来消除不确定性的东西”。在信息的世界里，熵越高，则能从传输越多的信息，熵越低，则以为着传输的信息越少。

在决策树中的应用

在决策树中，我们用熵来表示不纯度（impurity）

信息增益：分裂前的信息熵减去分裂后的信息熵

一个分裂导致的信息增益越大，代表这次分裂提升的纯度越高

2.4 信息熵与Gini指数关系

将f(x)=-lnx在x=1处进行一阶泰勒展开（忽略高阶无穷小）：

因此，熵可近似转化为：

即用-logP来近似1-P，且P处于[0,1]，从图上来直观理解一下：

基尼指数是信息熵中-logP在P=1处一阶泰勒展开后的结果，所以两者都可以用来度量数据集的纯度，用于描述决策树节点的纯度

2.5 信息增益率（C4.5）

对于多叉树，如果不限制分裂多少支，一次分裂就可以将信息熵降为0，比如ID3,

如何平衡分裂情况与信息增益

信息增益率：信息增益 除以 类别本身的熵

2.6 MSE

用于回归树

3 经典决策树算法

3.1 剪枝

如果什么都不做，只要无限分下去，最终都会将结果分到最好，fully grown tree，但容易过拟合

所以我们需要剪枝，防止其过拟合

剪枝（pruning）分为前剪枝和后剪枝

当树训练的过于茂盛的时候会出现在测试集上效果差，训练集上效果好的现象，这就过拟合了

3.1.1 前剪枝

在构建决策树的过程中，提前停止。那么，会将切分节点的条件设置的很严苛，导致决策树很短小

3.1.2 后剪枝

在决策树构建好后，然后剪枝

常见的三种后剪枝方法：

1. REP—错误率降低剪枝
2. PEP—悲观剪枝（C4.5）
3. CCP—代价复杂度剪枝（CART）

CCP—代价复杂度剪枝（CART）

该算法为子树Tt定义了代价（cost）和复杂度（complexity），以及一个可由用户设置的衡量代价的复杂度之间关系的参数α，其中，代价指在剪枝过程中因子树Tt被叶子节点替代而增加的错分样本，复杂度表示剪枝后子树Tt减少的叶子节点树，α则表示剪枝后树的复杂度降低程度与代价间的关系，定义为

CCP剪枝算法分为两个步骤：

1. 对于完全决策树T的每个非叶节点计算α值，循环减掉具有最小α值的子树，直到剩下根节点。在该步可得到一系列剪枝树｛T0，T1，T2…Tm｝,其中T0为原有的完全决策树，Tm为根结点，Ti+1为对Ti进行剪枝的结果；
2. 从子树序列中，根据真实的误差估计选择最佳决策树

3.2 决策树的优缺点

优点

1. 决策过程接近人的思维习惯。

2. 模型容易解释，比线性模型具有更好的解释性。

3. 能清楚地使用图形化描述模型。

4. 处理定型特征比较容易。

缺点

1. 一般来说，决策树学习方法的准确率不如其他的模型。针对这种情况存在一些解决方案，在后面的文章中为大家讲解。

2. 不支持在线学习。当有新样本来的时候，需要重建决策树。

3. 容易产生过拟合现象。

3.3 经典的决策树算法

ID3和C4.5比较

ID3（Iterative Dichotomiser 3，迭代二叉树3代）由Ross Quinlan于1986年提出，1994年他对ID3进行改进设计出C4.5

ID3是根据信息增益选取特征构造决策树，C4.5是根据信息增益率为核心构造决策树。既然C4.5是在ID3基础上改进，那他们的优缺点是什么？

• 使用信息增益会让ID3算法更偏向于选择值多的属性。信息增益反映给定一个条件后不确定性因素减少程度，那么分的越细，数据确定性越高，也就是信息熵越小，信息增益越大。因此，在一定条件下，值多的属性具有更大的信息增益。而C4.5则使用信息增益率选择属性，信息增益率通过引入分裂信息（Split Information）的项来惩罚取值较多的属性，分裂信息用来衡量属性分裂数据的广度和均匀性。这样就改进了ID3偏向选择值多属性的缺点。

  相对于ID3只能处理离散数据，C4.5还能处理连续属性数据，具体步骤为：

  1. 把需要处理的样本或者样本自己按连续变量从小到大进行排序
  2. 假设该属性对应的不同属性值一共有N个，那么总共有N-1个可能的候选分割阈值点，每个候选的分割阈值点的值为上述排序后的属性值中两两前后连续元素的中点，根据这个分割点把原来连续的属性分成bool属性。实际上可以不用检查所有的N-1个分割点。（连续属性值比较多的时候，由于需要排序和扫描，会使C4.5的性能有所下降。）
  3. 用信息增益比率选择最佳划分

C4.5的其他优点

优点：

1. 在树的构造过程中可进行剪枝，缓解过拟合
2. 能够对连续数据进行离散化处理（二分法）
3. 能够对缺失值进行处理

缺点：

构造树的过程需要对数据集进行多次扫描和排序，导致算法效率低

CART

CART（Classification And Regression Tree，分类回归树）由L.Breiman，J.Friedman，R.Olshen和C.Stone于1984年提出，是一种应用相当广泛的决策树学习方法。值得一提的是，CART和C4.5一同被评为数据挖掘领域十大算法。

CART算法采用一种二分递归分割的技术，将当前的样本集分为两个子样本集，使得生成的的每个非叶子节点都有两个分支。因此，CART算法生成的决策树是结构简洁的二叉树。

作为一种决策树学习算法，CART与ID3以及C4.5不同，它使用基尼系数（Gini coefficien）对属性进行选择。我们曾提及基尼系数的计算公式：

举个例子，假设我们拥有如下表所示的动物分类信息表：

那么对于非恒温动物，包含爬行类3个、鱼类3个、两栖类2个，因此，

Gini1=1-【（3/8）^2 + （3/8）^2 +（2/8）^2 】

而对于恒温动物，只包含5个哺乳类，同样，

Gini2=1 - 1^2 = 0

同熵一样，如果样本集合D被某个属性A是否取某个值分成两个样本集合D1和D2，则在属性A的条件下，集合D的基尼指数定义为：

对于上述按恒温和非恒温属性划分动物，

Gini(D, A)= 8/13 * Gini1 + 5/13 * Gini2

在一定程度上基尼指数（Gini(D)）反应的是集合D的不确定程度，跟熵类似。Gini(D, A)反应的是经过特征A划分后集合D的不确定程度。基尼系数越大，样本集合的不确定性也就越大。因此最好的属性划分是使得Gini(D, A)最小的划分。

下图显示了二分类问题中基尼系数、熵（单位比特）之半1/2*H§和分类误差率的关系。横坐标表示概率p，纵坐标表示损失。可以看出基尼系数和熵之半曲线很接近，都可以近似的代表分类误差率

每一次选择使基尼系数最小的属性作为切分点直到满足停止条件为止。算法的停止条件是节点中的样本个数小于预定阈值，或者样本集的基尼系数小于预定阈值（样本基本属于同一类），或者没有更多特征。

回归树

除了分类决策之外，CART也可以进行回归决策。

假设X和Y分别为输入和输出变量，Y为连续变量，训练数据集D为：

一个回归树对应着输入空间的一个划分以及在划分的单元上的输出值。假设已经将输入空间划分为M个单元R1,R2,…,RM，在每个单元Rm上有个固定的输出Cm，则回归树表示为：

问题是怎么对输入空间进行划分。一般采用启发式的思路，选择第 j 个Feature Xj和他的取值s分别作为切分变量（splitting variable）和切分点（splitting point），并定义两个区域：

然后采用平方误差损失求解最优的切分变量j和切分点s。具体地，求解

每一个切分变量和切分点对(j,s)都将输入空间分成两个区域，然后分别求每个区域的输出值，使得误差最小，很显然输出值应该是那个区域所有样本值的平均值，即：

举例说明，下面有一个简单的训练数据，根据这个数据集我们生成一棵回归树。

由于x只有一个Feature，我们不用选择j，下面我们考虑如下的切分点s： 1.5，2.5，3.5，4.5，5.5，6.5，7.5，8.5，9.5 然后求出对应的R1,R2,c1,c2，以及总的误差：

经过计算，可以得到如下结果：

很显然应该取s=6.5作为切分点，此时：

R1={1,2,3,4,5,6},R2={7,8,9,10},c1=6.24,c2=8.91

决策树为：

然后每个(j,s)对里找出使总误差最小的对作为最终的切分变量和切分点，对切分后的子区域重复这一步骤，直到满足停止条件为止。这样就生成了一颗回归树。此时的回归树成为最小二乘回归树（least squares regression tree）。

总结

C4.5算法是在ID3算法的基础上采用信息增益率的方法选择决策属性。C4.5改进了ID3偏向选择值多属性以及只能处理离散属性等缺点。ID3算法和C4.5算法虽然在对训练样本集的学习中能尽可能多地挖掘信息，但其生成的决策树分支较大，规模较大。为了简化决策树的规模，提高生成决策树的效率，又出现了根据GINI系数来选择测试属性的决策树算法CART。
CART算法采用一种二分递归分割的技术，与基于信息熵的算法不同，CART算法对每次样本集的划分计算GINI系数，GINI系数越小则划分越合理。CART算法总是将当前样本集分割为两个子样本集，使得生成的决策树的每个非叶结点都只有两个分枝。因此CART算法生成的决策树是结构简洁的二叉树