Decision Tree

梳理 Decision Tree(决策树) 算法原理

foreword

相信所有学习过数据结构这门课的朋友们都学习过树。我们从ID3开始复习下这玩意

ID3

H(C) 代表C的熵，H(C|D) 代表C在D下的熵，所以 gain(D) D对于C的信息增益就是 C的信息增益 - C在D发生时的熵
结合例子说明
以play为root，构建DT，其中 play 的gain(play) 就是如下所示
我们单列所有变量，对其进行分析
非常简单明了，其中 gain(天气) = gain(play) - H(天气)，其他也同理。这说明在 outlook temperature humidity windy 四者中，outlook最重要，选取为第一位的节点
由此生成第一节点，分裂出三个分叉，其中overcast的gain为0，低于随意一个阈值，停止分裂，其他两项继续分裂
ID3伪代码：
ID3 缺点
- ID3 没有剪枝策略，容易过拟合；
- 信息增益准则对可取值数目较多的特征有所偏好，类似“编号”的特征其信息增益接近于 1；
- 只能用于处理离散分布的特征；
- 没有考虑缺失值。

C4.5

可以处理连续数值型属性
- 对于离散值，C4.5和ID3的处理方法相同，对于某个属性的值连续时，假设这这个节点上的数据集合样本为total，C4.5算法进行如下处理：
  - 将样本数据该属性A上的具体数值按照升序排列，得到属性序列值：{A1,A2,A3,…,Atotal}
  - 在上一步生成的序列值中生成total-1个分割点。第i个分割点的取值为Ai和Ai+1的均值，每个分割点都将属性序列划分为两个子集。
  - 计算每个分割点的信息增益(Information Gain),得到total-1个信息增益。
  - 对分裂点的信息增益进行修正：减去log2(N-1)/|D|，其中N为可能的分裂点个数，D为数据集合大小。
  - 选择修正后的信息增益值最大的分类点作为该属性的最佳分类点
  - 计算最佳分裂点的信息增益率(Gain Ratio)作为该属性的Gain Ratio
  - 选择Gain Ratio最大的属性作为分类属性。
- 其实就是把连续值问题转化为多分类问题
信息增益率
- C4.5对信息增益添加了罚项，改为了信息增益比。并且能够处理连续特征了。以及相比于ID3，能够处理缺失值了。但是C4.5仍然只能用于分类。C4.5也可以是多叉树。
- gain 函数被重新定义为
- 以 outlook 为例
- H(outlook) = -(5/14 log2(5/14) + 4/14 log2(4/14) + 5/14 * log2(5/14)) = 1.5774062828523454
- C(outlook) = gain(outlook) / H(outlook) = 0.247 / 1.5774 = 0.156586788
- 在计算信息增益时，C4.5考虑了变量本身的熵，熵越大的变量得到惩罚越高，从而综合考虑得到了新的选择
- 同样的可以得到
- H(temperature) = -(4/14 log2(4/14) + 6/14 log2(6/14) + 4/14 * log2(4/14)) = 1.5566567074628228
- C(temperature) = 0.029 / 1.5567 = 0.018629151
- H(humidity) = -(7/14 log2(7/14) + 7/14 log2(7/14)) = 1
- C(humidity) = 0.152 / 1 = 0.152
- H(windy) = -(8/14 log2(8/14) + 6/14 log2(6/14)) = 0.9852281360342515
- C(windy) = 0.048 / 0.9852 = 0.048721072
- 虽然结果还是选择outlook，但是outlook 和 humidity的差距已经被拉得很近
剪枝
- 预剪枝：在节点划分前来确定是否继续增长，及早停止增长的主要方法有：
  - 节点内数据样本低于某一阈值；
  - 所有节点特征都已分裂；
  - 节点划分前准确率比划分后准确率高。
- 后剪枝：在已经生成的决策树上进行剪枝，从而得到简化版的剪枝决策树，C4.5是采用后剪枝的方法
  - 采用的悲观剪枝方法，用递归的方式从低往上针对每一个非叶子节点，评估用一个最佳叶子节点去代替这课子树是否有益
  - 如果剪枝后与剪枝前相比其错误率是保持或者下降，则这棵子树就可以被替换掉
  - C4.5 通过训练数据集上的错误分类数量来估算未知样本上的错误率。
缺失值处理
- 对于某些采样数据，可能会缺少属性值
- 在这种情况下，处理缺少属性值的通常做法是赋予该属性的常见值，或者属性均值
- 另外一种比较好的方法是为该属性的每个可能值赋予一个概率，即将该属性以概率形式赋值
  - 例如给定Boolean属性B，已知采样数据有12个B=0和88个B=1实例，那么在赋值过程中，B属性的缺失值被赋值为B(0)=0.12、B(1)=0.88；所以属性B的缺失值以12%概率被分到False的分支，以88%概率被分到True的分支。这种处理的目的是计算信息增益，使得这种属性值缺失的样本也能处理。
缺点
- 剪枝策略可以再优化；
- C4.5 用的是多叉树，用二叉树效率更高；
- C4.5 使用的熵模型拥有大量耗时的对数运算，连续值还有排序运算；
- C4.5 在构造树的过程中，对数值属性值需要按照其大小进行排序，从中选择一个分割点，所以只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时，程序无法运行。

伪代码

Function C4.5(R:包含连续属性的无类别属性集合,C:类别属性,S:训练集)    
Begin    
   If S为空,返回一个值为Failure的单个节点;    
   If S是由相同类别属性值的记录组成,    
      返回一个带有该值的单个节点;    
   If R为空,则返回一个单节点,其值为在S的记录中找出的频率最高的类别属性值;    
   [注意未出现错误则意味着是不适合分类的记录]；    
  For 所有的属性R(Ri) Do    
        If 属性Ri为连续属性，则    
        Begin    
           sort(Ri属性值)  
           将Ri的最小值赋给A1：    
             将Ri的最大值赋给Am；    
           For j From 1 To m-1 Do Aj=(A1+Aj+1)/2;    
           将Ri点的基于Aj(1<=j<=m-1划分的最大信息增益属性(Ri,S)赋给A；    
        End；    
  将R中属性之间具有最大信息增益的属性(D,S)赋给D;    
  将属性D的值赋给{dj/j=1,2...m}；    
  将分别由对应于D的值为dj的记录组成的S的子集赋给{sj/j=1,2...m};    
  返回一棵树，其根标记为D;树枝标记为d1,d2...dm;    
  再分别构造以下树:    
  C4.5(R-{D},C,S1),C4.5(R-{D},C,S2)...C4.5(R-{D},C,Sm);    
End C4.5

CART

以基尼系数为准则选择最优划分属性，可以应用于分类和回归
CART是一棵二叉树，采用二元切分法，每次把数据切成两份，分别进入左子树、右子树。而且每个非叶子节点都有两个孩子，所以CART的叶子节点比非叶子多1
相比ID3和C4.5，CART应用要多一些，既可以用于分类也可以用于回归
CART 包含的基本过程有分裂，剪枝和树选择。
- 分裂：分裂过程是一个二叉递归划分过程，其输入和预测特征既可以是连续型的也可以是离散型的，CART 没有停止准则，会一直生长下去；
- 剪枝：采用代价复杂度剪枝，从最大树开始，每次选择训练数据熵对整体性能贡献最小的那个分裂节点作为下一个剪枝对象，直到只剩下根节点。CART 会产生一系列嵌套的剪枝树，需要从中选出一颗最优的决策树；
- 树选择：用单独的测试集评估每棵剪枝树的预测性能（也可以用交叉验证）。
CART 在 C4.5 的基础上进行了很多提升。
- C4.5 为多叉树，运算速度慢，CART 为二叉树，运算速度快；
- C4.5 只能分类，CART 既可以分类也可以回归；
- CART 使用 Gini 系数作为变量的不纯度量，减少了大量的对数运算；
- CART 采用代理测试来估计缺失值，而 C4.5 以不同概率划分到不同节点中；
- CART 采用“基于代价复杂度剪枝”方法进行剪枝，而 C4.5 采用悲观剪枝方法。

分类树
- CART作为分类树时，特征属性可以是连续类型也可以是离散类型，但观察属性(即标签属性或者分类属性)必须是离散类型。
- 类似于C4.5，对于连续值，先把连续属性转换为离散属性再进行处理。
- 另外，对于连续属性先进行排序（升序），只有在决策属性（即分类发生了变化）发生改变的地方才需要切开，这可以显著减少运算量。
  1. 对特征的取值进行升序排序
  2. 两个特征取值之间的中点作为可能的分裂点，将数据集分成两部分，计算每个可能的分裂点的GiniGain。优化算法就是只计算分类属性发生改变的那些特征取值
  3. 选择GiniGain最小的分裂点作为该特征的最佳分裂点（注意，若修正则此处需对最佳分裂点的Gini Gain减去log2(N-1)/|D|（N是连续特征的取值个数，D是训练数据数目）
- 必须注意的是：根据离散特征分支划分数据集时，子数据集中不再包含该特征（因为每个分支下的子数据集该特征的取值就会是一样的，信息增益或者Gini Gain将不再变化，这也是C4.5等决策树离散型特征不会被重复选择为节点分裂的属性）；而根据连续特征分支时，各分支下的子数据集必须依旧包含该特征（当然，左右分支各包含的分别是取值小于、大于等于分裂值的子数据集），因为该连续特征再接下来的树分支过程中可能依旧起着决定性作用。
- CART分类时，使用基尼指数（Gini）来选择最好的数据分割的特征，gini描述的是纯度，与信息熵的含义相似。CART中每一次迭代都会降低GINI系数。
- 对于上题
  - G(oulook) = 5/14 (1 - (2/5)2 - (3/5)2) + 4/14 (1 - (4/4)2 - 02) + 5/14 (1 - (3/5)*2 - (2/5)2) = 0.34285714285714286
  - G(temperature) = 4/14 (1 - (2/4)2 - (2/4)2) + 6/14 (1 - (4/6)2 - (2/6)2) + 4/14 (1 - (3/4)*2 - (1/4)2) = 0.44047619047619047
  - G(humidity) = 7/14 (1 - (3/7)2 - (4/7)2) + 7/14 (1 - (6/7)2 - (1/7)2) = 0.3673469387755103
  - G(windy) = 8/14 (1 - (6/8)2 - (2/8)2) + 6/14 (1 - (3/6)2 - (3/6)2) = 0.42857142857142855
  - 仍然选 outlook，但是变量间差异变化较大
1. 缺失值
  - 对于缺失值，cart和c4.5的处理方式类似，缺失特征的gini是在非缺失数据上先划分然后根据非缺失值的比例前面乘上相应系数，降低存在缺失值特征的gini然后和其它特征分裂之后的gini增益进行比较。
  - 如果缺失特征恰好是gini增益最大的特征，那么要在有缺失值的特征上分裂就比较麻烦了：
  - cart使用的方式是：surrogate splits
  - 翻译为中文是代理特征分裂，有两种情况：
    1. 首先，如果某个存在缺失值的特征恰好是当前的分裂增益最大的特征，那么我们需要遍历剩余的特征，剩余的特征中如果有也存在缺失值的特征，那么这些特征忽略，仅仅在完全没有缺失值的特征上进行选择，我们选择其中能够与最佳增益的缺失特征分裂之后增益最接近的特征进行分裂。
    2. 如果我们事先设置了一定的标准仅仅选择仅仅选择差异性在一定范围内的特征作为代理特征进行分裂而导致了没有特征和最佳缺失特征的差异性满足要求，或者所有特征都存在缺失值的情况下，缺失样本默认进入个数最大的叶子节点。
2. 剪枝
  - CART 剪枝算法从完全生长的决策树的底端剪去一些子树，使决策树变小（模型简单），从而能够对未知数据有更准确的预测。CART剪枝算法由两步组成：首先从生成算法产生的决策树T0T0底端开始不断剪枝，直到T0T0的根节点，形成一个子序列T0,T1,T3,…..TnT0,T1,T3,…..Tn,然后通过交叉验证在独立的验证集上对子树序列进行测试，从中选择最优子树。
  - 其中，alpha最大只会是T0的depth，对于分类树交叉验证gini，对于回归树一般交叉验证lsd
回归树
- 回归树要求观察属性是连续类型，由于节点分裂选择特征属性时通常使用最小绝对偏差（LAD）或者最小二乘偏差（LSD）法，因此通常特征属性也是连续类型。
- 也就是 mae mse
- 以最小绝对偏差（LAD）为例
  1. 先令最佳方差为无限大bestVar=inf
  2. 依次计算根据某特征（FeatureCount次迭代）划分数据后的总方差currentVar（，计算方法为：划分后左右子数据集的总方差之和），如果currentVar
  3. 返回最佳分支特征、分支特征值（离散特征则为二分序列、连续特征则为分裂点的值），左右分支子数据集。
- 举个栗子
- 这里是使用了 LSD，也就是MSE作为评估，取代GINI作为分裂标准