【西瓜书笔记二】决策树

一，基本流程

决策树是一类常见的机器学习方法，是基于树结构来进行决策的。决策树学习的目的是为了产生一颗泛化能力强，即处理未见示例能力强的决策树。其基本流程遵循简单而直观的“分而治之”策略，如下所示：

二，划分选择

决策树学习的关键在于如何选择最优划分属性。一般而言，随着划分过程不断进行，我们希望决策树的分支结点所包含的样本尽可能属于同一个类别，即结点的“纯度”越来越高。

1，信息增益

Ent(D)的值越小，则D的纯度越高。

假定离散属性a有V个可能的取值{a1,a,2,...,av}，若使用a来对样本集D进行划分，则会产生V个分支结点，其中V个分支结点包含了D中所有在属性a上取值为av的样本，记为DV。一般来说样本数越多的分支结点影响越大，于是可计算出属性a对样本的集D进行划分所获得的“信息增益”：

其中DV表示的是正反比例。

一般而言，信息增益越大，则意味着使用属性a来进行划分所获得的“纯度提升”越大。因此我们想用信息增益来进行决策树的划分选择。下面使用一个表来计算信息增益的过程。

该样本集中有17个样例用于学习一颗还没剖开的瓜是好的还是坏的。

· 第一步计算出根节点的信息熵：

第二步，计算出当前属性集合{色泽，根蒂，敲声，纹理，脐部，触感}中每个属性的信息增益，

下面以“色泽”为例，计算器信息增益。该属性在D中的划分可以得到3个子集，分别记为：D1=(色泽=青绿)，D2=(色泽=乌黑)，D3=(色泽=浅白)。

于是，根据4.2可计算出属性“色泽”的信息增益为：

2，增益率

在上面的介绍中，并没有考虑“编号”这一属性，若将“编号”作为属性，那么“编号”将产生17个分支，每个分支结点仅包含一个样本，那么由 log1 =0 可知 Ent("编号") = 0 ，那么此时的信息增益为0.998，远大于其他属性。然而这样的决策树显然不具有泛化能力，无法对新样本进行有效预测。

这其实是因为信息增益准备会对取值数目较多的属性有所偏好，为减少可能带来的不利影响，C4.5决策树算法，使用“增益率”来选择最优划分属性。信息率定义为：

其中IV(a)称为属性a的“固有值”。属性a的可能取值数目越多（即V越大），则IV(a)的值通常越大。例如样本数据集有，IV(触感)=0.874 (V=2) , IV(色泽)=1.580 (V=3) , IV(编号)=4.088 (V=17) 。

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

3，基尼系数

设有2种结果：Gini(D) = 2P1P2 = 1 - (p1*p1 + p2*p2) = (p1 + p2)*(p1 + p2)  - (p1*p1 + p2*p2) 

三，剪枝处理

剪枝是决策树学习算法对付“过拟合”的主要手段，这是因为训练样本学习的“太好”，以至于将训练集自身的一些特点当作所有数据都具有的一般性特点而导致的拟合，因此可以主动去掉一些分支来降低过拟合的风险。

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

那么如何判断决策树的泛化能力呢？可以采用留出法，即预留出一部分数据用作“验证集”以进行性能评估。如下表所示，将数据集划成两个部分：

1，预剪枝

由前面所知，基于信息增益作为准则，选取”脐部“来对训练集进行划分，则产生3个分支。然后是否应该进行划分呢?预剪枝要对划分前后的泛化性能进行估计。在划分前，所有样例集中在根节点。若不进行划分，则根据算法流程可知，该结点被标记为叶结点，其类别标记为训练样例中样例数最多的类别，则该结点标记为”好瓜“，那么验证集中有4个样例被分类错误，正确率为42.9%。而若用”脐部“划分之后，则结点2，3，4分别被标记为”好瓜“，”好瓜“，”坏瓜“，此时验证集中有5个被验证正确，因此精度为：71.4%。所以应该用”脐部“进行划分。

划分的结果如下所示：

2，后剪枝

最终得到的后剪枝图如上所示，其验证机精度为71.4%。通过对比可知，后剪枝决策树通常比预剪枝决策树保留更多的分支，一般情况下，后剪枝决策树的欠拟合风险小，泛化性能往往优于预剪枝决策树。但后剪枝决策树的训练时间要比一般的决策树和预剪枝决策树要耗费的时间多得多。

四，多变量决策树

有称为”斜决策树“。决策树所形成的分类边界有一个明显的特征：轴平行，即它的分类边界由若干个与坐标轴平行的分段组成。如下图所示：

这样在学习任务的真实分类边界比较复杂时，必须使用很多段划分，才能获得较好的近似。此时的决策树会相当复杂，由于要进行大量的属性测试，预测时间开销会非常大。