决策树学习笔记（二）：剪枝，ID3，C4.5

本篇将详细介绍决策树常用的三种算法，剪枝处理，缺失值，决策树优缺点，以及常见的应用场景。

• 决策树的生成
  
• 决策树的剪枝
  
• 决策树三种算法概况
  
• 总结
  

▍决策树的生成

决策树的生成其实就是不断地向下构建决策树节点，最终形成一颗完整的决策树模型。其中，节点建立的度量标准可以是信息增益，增益率，基尼指数等。那么如何通过已有的度量标准不断地构建决策树节点呢？

我们可以用数学上的递归方法解决，就如数据结构二叉树一样。设置判断标准，设置递归的停止条件，归纳并实现决策树的不断生成。递归方面的内容也可以参考：如何用Python递归地思考问题？下图就是用递归生成一颗完整决策树的过程。

递归生成决策树的伪代码如下：

Input:  训练集D={(x1, y1), (x2, y2), ..., (xm, ym)};
        属性集A={a1, a2, ..., ad}.
Output: 以node为根节点的一个决策树
Process:
## 通过给定样本集D和属性集A构建决策树
TreeGenerate(D, A){
    1: 生成结点node;
    2: if D 中样本全属于同一类别C then
    3:      将node标记为 C类 叶节点; return
    4: end if
    5: if A = ∅ OR D中样本在A上取值相同 then
    6:      将node标记为叶节点，其类别标记为D中样本数最多的类; return 
    7: end if
    8: 从 A 中选择最优化分属性 a*
    9: for a* 的每一值a[i] do
   10:      为node生成一个分支; 令Dv表示D中在 a* 上取值为 a[i] 的样本子集;
   11:      if Dv is empty then
   12:          将分支结点标记为叶节点，其类别为D中样本最多的类; return
   13:      else
   14:          以 TreeGenerate(Dv, A\{a*}) 为分支结点;
   15:      end if
   16: end for
}

使用Python实现的递归构建决策树如下：

deftreeGrow(dataset,features):
   # 停止条件(1)(2)
   if  len(classList) == classList.count(classList[0]):  #no more feature
       return classifyMaxLabel(classList)
   if  len(dataSet[0]) == 1:  # pure dataset
       return classList[0]
   
   #特征选择    
   bestFeature = findBestSplit(dataset)
   delbestFeature
   
   #划分特征并递归调用    
   SplitData = SplitDataset(dataset, bestFeature)
   tree = treeGrow(SplitData，features)
   return tree

上面递归函数的过程是：

• 先定义停止条件：(1)没有更多特征供选择了；(2)数据集本身就已经分类好了，纯数据集。满足这两个中任何一个条件树生成就停止。
  
• 特征选择：根据自己选择的度量标准来选择特征。
  
• 递归地调用treeGrowth函数并根据选择特征不断地生成子树，直到达到停止条件。
  

注：上面代码只是一个决策树递归生成的框架示例，细节部分不完整，具体实现还需要补充。

▍决策树的剪枝

决策树是一个非常容易发生过拟合的模型，因为如果没有任何限制，在生成的阶段，它将会穷尽所有的特征，直到停止条件。这时叶子节点的数目最多，而叶子节点越多则越容易发生过拟合缺少泛化能力。如下图所示，右图就是未剪枝后的过拟合情况，显然对于新的数据集效果将会很差。

那么如何对一颗决策树进行一些限制呢？

可以通过正则化来解决，我们之前提到过正则化的问题：【机器学习笔记】：解读正则化，LASSO回归，岭回归。在决策树中被称为剪枝，就是将树生成的不必要子树剪掉，减少叶子节点数量，降低树模型复杂度。

总的来说，剪枝可分为：预剪枝，后剪枝两类。

预剪枝(pre-pruning)

预剪枝的重点在 ”预“ 字。它是指在完全正确分类之前，决策树会较早地停止树的生长。而终止树继续向下生长的方法有很多，我把停止生长的方法总结为通用的停止和更严格的停止两种。

通用的停止

通用的停止其实就是前面递归生成示例中的终止判定条件：

• 如果所有样本均属同一类，终止递归。
  
• 如果样本的所有的特征值都相同，终止递归。
  

更严格的终止

• 如果树到达一定高度
  
• 如果节点下包含的样本点小于指定的阈值
  
• 如果样本的类分布是独立于可用特征的（使用卡方检验）
  
• 如果扩展当前节点不会改善信息增益，即信息增益小于指定的阈值
  

周志华老师的"机器学习"一书中采用对每个节点划分前用验证集进行估计，通过比较划分前后的验证集精度来判断是否剪枝。若当前节点的划分不能带来决策树泛化能力的提升，则停止划分并标记当前节点为叶子也点。下图是"周志华机器学习"中的西瓜示例，描述了该方法预剪枝过程。

利用验证集对节点进行评估，如果划分后的正确率比划分前还低，那就禁止划分，如图中的 "色泽" 特征。如果划分后的正确率大于划分前，则同意划分，如图中的 "脐部" 特征。

注：很多博客在学习周志华老师的书籍过程中，将预剪枝方法局限于上面这个方法。我个人认为这只是其中的一种，还有很多其它方法可以使用，只要满足这个”预“的含义，都可以算作预剪枝处理。

后剪枝(post-pruning)

与预剪枝不同，后剪枝首先通过完全分裂构造完整的决策树，允许过拟合，然后采取一定的策略来进行剪枝，个人的简单理解就是"先斩后奏"。常用的后剪枝策略包括:

• 降低错误剪枝 REP
  
• 悲观错误剪枝 PEP
  
• 基于错误剪枝 EBP
  
• 代价-复杂度剪枝 CCP
  
• 最小错误剪枝 MEP
  

几种后剪枝算法的对比情况

网上大部分博客都是参考周志华老师的”机器学习“和李航老师的”统计学习方法“来介绍的，并没有从概况上说明属于哪一种。我在本篇对于两本书的方法做个总结。

统计学习方法中的剪枝方法属于CCP，也就是代价-复杂度剪枝方法。就像其他的模型最小化风险结构函数一样，在原有的经验损失函数（经验熵）基础上加入了正则项，正则参数是树的叶子节点个数，公式如下：

机器学习中的剪枝方法属于REP，也就是降低错误剪枝，它是最简单粗暴的一种后剪枝方法，其目的减少误差样本数量。下图是书中西瓜示例的后剪枝过程，通过对比验证集前后的误差精度来判断是否剪枝。

这里仅对这两本书中的方法进行一个总结，其它剪枝方法不在这里展开。如果对这两本书中的剪枝方法感兴趣，建议好好翻一翻，写得很详细。

预剪枝和后剪枝对比

虽然都是剪枝，但预剪枝与后剪枝最终达到的效果是不一样的。了解两种方法并进行比较有助于我们更好地选择。我们来看一下二者的区别：

预剪枝：预剪枝提前使很多分支都没有展开，降低了过拟合的风险，但是这个分支下的后续划分可能是非常有用的。从这点考虑，预剪枝是基于”贪心“的本质来禁止分支以及后续的展开，在降低过拟合的同时也有欠拟合的风险。

后剪枝：相比预剪枝，后剪枝的优点是：1)后剪枝决策树通常比预剪枝决策树保留了更多的分支；2)后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝决策树。后剪枝的缺点是：1)决策树训练时间开销比未剪枝决策树和预剪枝决策树都要大的多。

以上就是决策树中比较关键的三个步骤：特征选择，树生成，树剪枝。当然，决策树还有很多其它方面的问题需要考虑，比如连续值处理，缺失值处理，以及如何用于回归等。这些问题我们将通过决策树的三种算法来深入探讨。

▍决策树算法概况

前面提到的三个步骤其实就基本构成了一个决策树的算法。决策树经典有三种常用的算法有：ID3，C4.5，CART。在对每个算法深入介绍之前，我们先从总体了解一下这几个算法的功能。

每个算法对应着不同的度量准则，其中只有CART算法可以用于回归和分类，分类基于基尼指数，回归基于平方误差最小化。

▍决策树算法：ID3

ID3算法由Ross Quinlan于1986年提出，它的核心是根据信息增益(Information gain)来选取Feature作为决策树分裂的节点。特征对训练数据集的信息增益定义为集合D的经验熵(所谓经验熵，指的是熵是有某个数据集合估计得到的) H(D) 与特征A给定条件下的经验条件熵 H(D|A) 之差，记为：

实际上就是特征A和D的互信息

# 统计学习方法：ID3生成决策树算法
输入：训练数据集D，特征集A，阈值e
输出：决策树T
1：若D中所有实例属于同一类Ck，则T为单结点树，并将类Ck作为该结点的类标记，返回T；
2：若A=空，则T为单结点树，将D中实例数最多的类Ck作为结点类标记，返回T；
3：否则，计算A中各特征对D的信息增益，选择信息增益值最大的特征Ag；
4：如果Ag的信息增益小于阈值e，则T为单结点树，将D中最多的类Ck作为结点类标记，返回T；
5：否则，对Ag的每一可能值ai，依Ag=ai将D分割为若干子集Di，将Di中实例数最大多的类作为类标记，构建子结点，由结点及其子结点构成树T，返回T；
6：对于第i个子结点，以Di为训练集，以A-Ag为特征集，递归调用步骤（1）~（5），得到子树Ti，返回Ti。

整个代码部分很长，只显示核心信息增益部分：

# 筛选出信息增益最大的特征，返回特征索引,该特征的信息增益    
def Maxinformation_gain(data,labels):
    feature_gain ={}
    data_labels = [y[-1] for y in data]
    entropyD = entropy(data_labels)
    # 计算每一个feature的信息增益
    for f in range(len(labels)):
        featureVal = [value[f] for value in data]
        entropyF = ConditionalEntropy(featureVal,data_labels)
        feature_gain[f] = entropyD-entropyF
    result = max(feature_gain.items(),key=lambda x:x[1])    
    return result[0],result[1]

ID3算法只有树的生成，所以该算法生成的树容易产生过拟合。

▍决策树算法：C4.5

ID3算法有很多局限性，Quinlan针对这些局限性给出了ID3的一个扩展算法：即C4.5算法。C4.5是ID3算法的改进版本，针对四个主要的不足进行改进：

• 不能处理连续特征
  
• 用信息增益作为标准容易偏向于取值较多的特征
  
• 不能处理缺失值
  
• 容易发生过拟合问题
  

不能处理连续特征：C4.5的思路是将连续的特征离散化，采用 ”二分法“ 对连续属性进行处理。具体的做法是：将a特征的连续值从小打大进行排列，生成n-1个切分选择，遍历每个切分，根据增益率(信息增益比)选择最优的切分。下图引自机器学习中的内容。

信息增益作为标准容易偏向于取值较多的特征：引入信息增益比，特征数越多的特征对应的特征熵越大，它作为分母，可以校正信息增益容易偏向于取值较多的特征的问题。

具体代码实现如下：

def Maxinformation_gain_ratio(data,labels):
    # 计算每个特征的信息增益
    result = {}
    data_labels = [y[-1] for y in data]
    entropyD = entropy(data_labels)
    # 计算每一个feature的信息增益
    for f in range(len(labels)):
        featureVal = [value[f] for value in data]
        entropyF = ConditionalEntropy(featureVal,data_labels)
        feature_gain = entropyD-entropyF
        feature_data_en = FeatureDataEntropy(featureVal)
        result[f] = feature_gain/feature_data_en
    return max(result,key=result.get)[0],max(result,key=result.get)[1]

不能处理缺失值：主要需要解决的是两个问题：

1）如何在属性值缺失的情况下进行划分属性选择？

2）给定了划分属性，若样本在该属性上的值缺失，如何对样本进行划分？

引自机器学习的内容，具体解释如下：

容易发生过拟合问题：C4.5引入了正则化系数进行初步的剪枝。剪枝参考前面解释部分。

▍总结

本篇介绍了决策树的生成，剪枝两个步骤，然后介绍了前两种算法ID3，C4.5。下一篇将介绍非常经典的CART算法，它是集成学习常用的基础算法，可以说是十大经典算法中的一员了，因此将它单拿出来介绍。

除此外，还将从整体介绍决策树的优缺点以及一些应用场景。

参考：

[1] 机器学习，周志华，决策树章节

[2] 统计学习方法，李航，决策树章节

[3] https://blog.csdn.net/am290333566/article/details/81187562

[4] https://blog.csdn.net/u012328159/article/details/79413610

[5] http://leijun00.github.io/2014/10/decision-tree-2/