决策树学习笔记（二）：剪枝，ID3，C4.5开发者社区

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

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实现的递归构建决策树如下：
def treeGrow(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) 
    del bestFeature
    # 划分特征并递归调用    
    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