决策树汇总——ID3、C4.5、CART

决策树是机器学习中的经典算法之一，十大机器学习算法中就包含决策树算法(Decision Tree). 顾名思义，决策树是基于树结构进行决策的，根据算法不同会使用多叉树或者二叉树。其实人类在日常生活中，遇到问题时也会使用决策树进行判断。例如西瓜书里有列举挑选西瓜的例子。

一颗决策树一般包含一个根结点，若干个内部节点和若干叶节点，根结点是判断的开始，内部节点是一些子判断流程，而叶节点对应于决策的结果。决策树作为机器学习算法的一种，其目的是产生一颗泛化能力强的树，能处理训练集中没有见到的情形，并能正确决策。

ID3

信息增益

信息熵是度量样本集合纯度最常用的一种指标，令D中第k类样本的比例为$p_k$, 则D的信息熵为
$Ent(D)=-\sum_{k=1}^{|y|} p_klog_2{p_k}$

信息增益=信息熵-条件熵
$Gain(D,a)=Ent(D)-\sum_{v=1}^{V} \frac{D^v}{D}Ent(D^v)$

以西瓜书中的列子

17个样本中正例有8个，负例有9个，则根结点的信息熵为:
$Ent(D)=-\sum_{k=1}^{2} p_klog_2{p_k}=-(\frac{8}{17}log_2 \frac{8}{17}+\frac{9}{17}log_2 \frac{9}{17})=0.998$

然后计算相应属性的条件熵，以色泽属性为例，可以分为 $D^1$(色泽=青绿)有6个样本，正反各3个，$D^2$(色泽=乌黑)有6个样本，正4，饭2，$D^3$(色泽=浅白)，有5个样本，正1反4.则3个分支节点的信息熵为：
$Ent(D^1)=-(\frac{3}{6}log_2 \frac{3}{6}+\frac{3}{6}log_2 \frac{3}{6})=1$
$Ent(D^2)=-(\frac{4}{6}log_2 \frac{4}{6}+\frac{2}{6}log_2 \frac{2}{6})=0.918$
$Ent(D^2)=-(\frac{1}{5}log_2 \frac{1}{5}+\frac{4}{5}log_2 \frac{4}{5})=0.722$

则色泽的信息增益为:

$Gain(D,a)=Ent(D)-\sum_{v=1}^{V} \frac{D^v}{D}Ent(D^v)=0.998-(\frac{6}{17}1+\frac{6}{17}0.918+\frac{5}{17}*0.722)=0.109$

也可以得到其他属性的信息增益，在根节点的位置信息增益最大的属性为纹理Gain=0.381.
确定第一个分支后，后面的内部节点和叶节点叶通过类似方式递归判断，则生成的决策树为:

缺点

• ID3没有剪纸的策略，容易过拟合
• 没有考虑缺失值
• 只能处理离散分布的特征

C4.5

C4.5在ID3的基础上做了一些改进:

• 引入后剪枝缓解过拟合
• 可以处理属性中有连续值的情形，具体做法是对于某属性在区间$[a^i, a^{i+1})$，若取任意值产生的划分结果相同，则取该区间的中位点作为划分点
• 对于缺失值，C4.5的做法是用没有缺失的样本子集计算信息增益

剪枝

剪枝的目的是防止决策树过拟合，在构建决策树时，为了能正确分类训练样本。决策树的结点划分过程会不断重复，可能导致分的过细，在训练集拟合的很好，但测试集的效果变得很差。所以需要剪枝帮助模型获得泛化性。
剪枝有预剪枝和后剪枝两种，引用下西瓜书里关于两种剪枝方式的差异

预剪枝是指在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点;后剪枝则是先从训练集生成一棵完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点.

判断上述两种剪枝方式是否能带来性能提升的方式是采用验证集，验证剪枝前后的效果。

预剪枝和后剪枝的例子见下面两图:

缺点

• C4.5使用的是多叉树，二叉树效率更高
• 只能用于分类
• 使用的熵模型有大量耗时的对数运算，连续值还有排序运算
• 在构造树的过程中，对数值属性值需要按照其大小排序，从中选择一个分割点。当训练集打到内存无法容纳时，会无法运行

CART

基尼指数

CART使用基尼指数作为划分属性的度量
$Gini(D)=\sum_{k=1}^{|y|}\sum_{k^{‘} \neq k} p_k p_{k^{‘}}=1- \sum_{k=1}^{|y|}p_k^2$

$Gini(D)$反映了从数据集D中随机抽取两个样本，其类别标记不一致的概率。因此$Gini(D)$越小，则数据集D的纯度越高

将其写成和信息增益等价的形式，则基尼指数为

$ Gini_index(D,a)=\sum_{v=1}^{V} \frac{D^v}{D} Gini(D^v) $

在是否要划分决策树的判断时，CART会选择使得划分后基尼指数最小的属性作为最优划分属性。