机器学习17：决策树模型

1，决策树生成：按特征选择指标不同分类

决策树分为两大类：分类树和回归树，分类树用于分类标签值，回归树用于预测连续值，常用算法有ID3、C4.5、CART等。

决策树的生成是一个递归的过程：

ID3、C4.5、CART三种算法的最大区别是最优划分属性的选择标准不同，分别是：信息增益、信息增益比、基尼系数。

1.1，ID3(信息增益)：多叉树

主要用于分类树，采用信息增益作为最优划分属性的选择标准,ID3选择信息增益最大的划分属性作为树节点属性。《机器学习5：集成学习--Bagging与随机森林》中详细解释了信息熵和信息增益的含义和计算方法，这里就不在赘述了，直接阐述算法。

构造树的基本想法是随着树深度的增加，节点的熵迅速地降低。熵降低的速度越快越好，这样我们有望得到一棵高度最矮的决策树。当系统的信息熵降为0时 ，就没有必要再往下构造决策树了，此时叶子节点都是纯的--这是理想情况。最坏的情况下，决策树的高度为属性（决策变量）的个数，叶子节点不纯（这意味着我们要以一定的概率来作出决策）。

1.2，C4.5(信息增益比)：多叉树

主要用于分类树，采用信息增益比作为最优划分属性的选择标准。

信息增益准则对可取值数目较多的属性有所偏好，为减少这种偏好可能带来的不利影响，C4.5决策树算法使用增益率(gain ratio)来选择最优划分属性。

可见，信息增益率准则对可取值数目较少的属性有所偏好。因此，C4.5算法并不是直接选择增益率最大的候选划分属性，而是使用了一个启发式：先从候选划分属性中找到信息增益高于平均水平的属性，再从中选择增益率最高的。

1.3，CART(Gini系数)：二叉树

CART(Classification and Regression Tree)算法可用于分类树，也可用于回归树，采用基尼指数公式作为最优划分属性的选择标准。

对于给定的样本集合D，其基尼指数为：

属性a的基尼指数为：

于是，在候选属性集A中，选择那个使得划分后基尼指数最小的属性作为最优划分属性。

1.4，三种算法比较：

1),ID3算法: 内部使用信息熵以及信息增益来进行构建,每次迭代选择信息增益最大的特征属性作为分割属性。只支持离散的特征属性。

优点:决策树构建速度快，实现简单

缺点：算法依赖样本中出现次数较多的特征属性,但是出现次数最多的属性并不一定最优。

2),C4.5算法：使用信息增益率来构建,在树的构建过程中会进行剪枝操作的优化,能够自动完成对连续属性的离散化处理。选择信息增益率大的属性进行分割。

优点:准确率较高,实现简单

缺点：对数据集需要进行多次顺序扫描和排序,效率较低。

3),CART算法:使用基尼系数作为数据纯度的量化指标来构建,选择‘GINI增益率’来分割，越大的即作为当前数据集的分割属性.可用于分类和回归。（二叉树构建）

三种算法主要区别:CART构建的一定是二叉树,ID3,C4.5构建的不一定是二叉树

2，剪枝与过拟合：

决策树容易过拟合，需要剪枝来缩小树的结构和规模（包括预剪枝和后剪枝）。

预剪枝：

预剪枝是要对划分前后泛化性能进行评估。对比决策树某节点生成前与生成后的泛化性能。

后剪枝：

后剪枝先从训练集中生成一颗完整决策树，然后逐步减掉叶子节点。

对比预剪枝与后剪枝生成的决策树，可以看出，后剪枝通常比预剪枝保留更多的分支，其欠拟合风险很小，因此后剪枝的泛化性能往往由于预剪枝决策树。但后剪枝过程是从底往上裁剪，因此其训练时间开销比前剪枝要大。

3，损失函数与剪枝：

决策树剪枝是简化已经生成的复杂的决策树，防止过拟合，使生成的决策更一般化。

决策树的损失函数为：剪枝操作将依据此损失函数进行剪枝。

其中：

t是树的叶节点，Nt表示该叶节点的样本数量，Ht（T）表示结点t上的经验熵，所以右边第一项相当于对决策树的所有叶节点求熵，并以每个叶节点包含的样本数量为权重。又因为熵的含义为随机变量不确定性的度量，所以右边第一项的计算意义为模型对训练集的预测误差。

对于正则化项α|T|：T表示树的叶节点个数，即表示树的复杂度，a为参数，相当于a越大，叶节点的个数对损失函数的影响越大，剪枝之后的决策树更容易选择复杂度较小的树，a越小，表示叶节点的个数对损失函数的影响越小，所以a的大小控制了预测误差与树的复杂度对剪枝的影响

所以当a确定时，损失函数最小的子树越大，表明与训练数据的拟合越好，但是树也越复杂，子树越小，与训练数据的拟合越差，但树的复杂度较小，避免了过拟合，提高决策树的一般性，损失函数正好表示了对两者的平衡

4，code：

code：1，ID3分类树(信息增益)；2，C4.5分类树(信息增益比)；3，CART分类和回归树(Gini index)。

# 由于代码太长，简洁起见，这里给出github地址：https://github.com/Jesselinux/Mining-Algorithms