决策树的划分依据-信息增益率C4.5

1 背景

• 信息增益准则ID3对可取值数目较多的属性有所偏好，为减少这种偏好可能带来的不利影响，著名的 C4.5 决策树算法[Quinlan， 1993J 不直接使用信息增益，而是使用"增益率" (gain ratio) 来选择最优划分属性.

2 定义

• 增益率：增益率是用前面的信息增益Gain(D, a)和属性a对应的"固有值"(intrinsic value)的比值来共同定义的。

属性 a 的可能取值数目越多(即 V 越大)，则 IV(a) 的值通常会越大.

3 案例

• 第一列为天气，第二列为温度，第三列为湿度，第四列为风速，最后一列该活动是否进行。我们要解决：根据下面表格数据，判断在对应天气下，活动是否会进行？
  
  
  该数据集有四个属性，属性集合A={ 天气，温度，湿度，风速}， 类别标签有两个，类别集合L={进行，取消}。
  a.计算类别信息熵
  类别信息熵表示的是所有样本中各种类别出现的不确定性之和。根据熵的概念，熵越大，不确定性就越大，把事情搞清楚所需要的信息量就越多。
  
  b.计算每个属性的信息熵
  每个属性的信息熵相当于一种条件熵。他表示的是在某种属性的条件下，各种类别出现的不确定性之和。属性的信息熵越大，表示这个属性中拥有的样本类别越不“纯”。
  

c.计算信息增益

信息增益的 = 熵 - 条件熵，在这里就是 类别信息熵 - 属性信息熵，它表示的是信息不确定性减少的程度。如果一个属性的信息增益越大，就表示用这个属性进行样本划分可以更好的减少划分后样本的不确定性，当然，选择该属性就可以更快更好地完成我们的分类目标。

信息增益就是ID3算法的特征选择指标。

d.计算属性分裂信息度量
用分裂信息度量来考虑某种属性进行分裂时分支的数量信息和尺寸信息，我们把这些信息称为属性的内在信息（instrisic information）。信息增益率用信息增益/内在信息，会导致属性的重要性随着内在信息的增大而减小（也就是说，如果这个属性本身不确定性就很大，那我就越不倾向于选取它），这样算是对单纯用信息增益有所补偿。

e.计算信息增益率

天气的信息增益率最高，选择天气为分裂属性。发现分裂了之后，天气是“阴”的条件下，类别是”纯“的，所以把它定义为叶子节点，选择不“纯”的结点继续分裂。

在子结点当中重复过程1~5，直到所有的叶子结点足够"纯"。现在我们来总结一下C4.5的算法流程：

while(当前节点"不纯")：
    1.计算当前节点的类别熵(以类别取值计算)
    2.计算当前阶段的属性熵(按照属性取值吓得类别取值计算)
    3.计算信息增益
    4.计算各个属性的分裂信息度量
    5.计算各个属性的信息增益率
end while
当前阶段设置为叶子节点

4 为什么使用C4.5要好

1.用信息增益率来选择属性
克服了用信息增益来选择属性时偏向选择值多的属性的不足。
2.采用了一种后剪枝方法
避免树的高度无节制的增长，避免过度拟合数据
3.对于缺失值的处理
在某些情况下，可供使用的数据可能缺少某些属性的值。

• 处理缺少属性值的一种策略是赋给它结点n所对应的训练实例中该属性的最常见值；
• 另外一种更复杂的策略是为A的每个可能值赋予一个概率。
  • 例如，给定一个布尔属性A，如果结点n包含6个已知A=1和4个A=0的实例，那么A(x)=1的概率是0.6，而A(x)=0的概率是0.4。于是，实例x的60%60%被分配到A=1的分支，40%40%被分配到另一个分支。C4.5就是使用这种方法处理缺少的属性值。