进击数据挖掘十大算法(四):C4.5决策树
一、从分类问题开始
分类（Classification）任务就是确定对象属于哪个预定义的目标类。 分类问题不仅是一个普遍存在的问题，而且是其他更加复杂的决策问题的基础，更是机器学习和数据挖掘技术中最庞大的一类算法家族。我们前面介绍过的朴素贝叶斯就可以用来解决分类问题。作为本文的开始，我们首先来简单回顾一下什么是分类。
分类问题的本质就是当给定这样一个数据集后，要求我们训练出（或建立）一个模型\(f\)。当出现一组新的特征向量时，要求我们预测（或判断）拥有这样一组特征向量的对象应当属于哪个类别。
分类问题的类别数目可以是两类也可以是多类。二分类问题是最简单的分类问题，而多分类问题模型可以在二分类模型的基础上进行构建。我们在前面文章中一直使用的鸢尾花数据集就是一个典型的多分类问题，问题的最终目标是判断给定一朵花，它应该属于setosa、versicolor和virginica中的哪一类。 ****** ### 二、决策树基础 #### 2.1 什么是决策树 决策树是一种用于对实例进行分类的树形结构。决策树由节点（node）和有向边（directed edge）组成。节点的类型有两种：内部节点和叶子节点。其中，内部节点表示一个特征或属性的测试条件（用于分开具有不同特性的记录），叶子节点表示一个分类。
一旦我们构造了一个决策树模型，以它为基础来进行分类将是非常容易的。具体做法是，从根节点开始，对实例的某一特征进行测试，根据测试结构将实例分配到其子节点（也就是选择适当的分支）；沿着该分支可能达到叶子节点或者到达另一个内部节点。如果到达内部节点，那么就使用新的测试条件递归执行下去，直到抵达一个叶子节点。当到达叶子节点时，我们便得到了最终的分类结果。
下图是一个决策树的示例（注意我们仅用了两个feature就对数据集中的5个记录实现了准确的分类）：
我们可以把决策树看作是一个if-then规则的集合。将决策树转换成if-then规则的过程是这样的： + 由决策树的根节点到叶节点的每一条路径构建一条规则 + 路径上中间节点的特征对应着规则的条件，叶节点的类标签对应着规则的结论
决策树的路径或者其对应的if-then规则集合有一个重要的性质：互斥并且完备。也就是说，每一个实例都被有且仅有一条路径或者规则所覆盖。这里的覆盖是指实例的特征与路径上的特征一致，或实例满足规则的条件。
2.2 决策树的构建准备工作
使用决策树做分类的每一个步骤都很重要，首先我们要收集足够多的数据，如果数据收集不到位，将会导致没有足够的特征去构建错误率低的决策树。数据特征充足，但是不知道用哪些特征好，也会导致最终无法构建出分类效果好的决策树。从算法方面来看的话，决策树的构建就是我们的核心内容。 决策树如何构建呢？通常，这一过程可以概括为3个步骤：特征选择、决策树的生成和决策树的剪枝。
2.2.1 特征选择
特征选择就是决定用哪个特征来划分特征空间，其目的在于选取对训练数据具有分类能力的特征。这样可以提高决策树学习的效率。如果利用一个特征进行分类的结果与随机分类的结果没有很大的差别，则称这个特征是没有分类能力的，经验上扔掉这些特征对决策树学习的精度影响不会很大。 那如何来选择最优的特征来划分呢？一般而言，随着划分过程不断进行，我们希望决策树的分支节点所包含的样本尽可能属于同一类别，也就是节点的纯度（purity）越来越高。
在实际使用中，我们衡量的常常是不纯度。度量不纯度的指标有很多种，比如：熵、增益率、基尼值数。这里我们使用的是熵，也叫作香农熵，这个名字来源于信息论之父：克劳德·香农。
(1) 香浓熵
熵定义为信息的期望值。在信息论与概率统计中，熵是表示随机变量不确定性的度量。 假定当前样本集合D中一共有n类样本，第i类样本为\(x_i\)，那么\(x_i\)的信息定义为：
\[l(x_i)=-log_2{p(x_i)}\]
其中 \(p(x_i)\) 是选择该分类的概率。
通过上式，我们可以得到所有类别的信息。为了计算熵，我们需要计算所有类别所有可能值包含的信息期望值(数学期望)，通过下面的公式得到：
\[Ent(D)=-\sum_{i=1}^{n}p(x_i)log_2p(x_i)\]
\(Ent(D)\) 的值越小，则D的不纯度就越低。
(2) 信息增益
信息增益（Information Gain）的计算公式其实就是父节点的信息熵与其下所有子节点总信息熵之差。但这里要注意的是，此时计算子节点的总信息熵不能简单求和，而要求在求和汇总之前进行修正。
假设离散属性A有V个可能的取值 \(\{A^1,A^2,\ldots,A^V\}\)，若使用A对样本数据集D进行划分，则会产生V个分支节点，其中第v个分支节点包含了D中所有在属性A上取值为\(A^v\)的样本，记为\(D^v\).我们可根据信息熵的计算公式计算出\(D^v\)的信息熵，再考虑到不同的分支节点所包含的样本数不同，给分支节点赋予权重 \(|D^v|/D\) ，这就是所谓的的修正。
所以信息增益的计算公式为：
\[Gain(D,A)=Ent(D)-\sum_{v=1}^{V}\frac{|D^v|}{|D|}Ent(D^v)\]
(3) 信息增益率
信息增益率 = 惩罚参数 * 信息增益 公式：\[IGR(D,A)=\frac{Gain(D,A)}{H_A(D)}\]
\[H_A(D)=-\sum_{i=1}^{n}\frac{|D_i|}{|D|}log_2\frac{|D_i|}{|D|}\]
信息增益率本质： 是在信息增益的基础之上乘上一个惩罚参数。特征个数较多时，惩罚参数较小；特征个数较少时，惩罚参数较大。
使用信息增益率：并不是直接选择信息增益率最大的特征，而是先在候选特征中找出信息增益高于平均水平的特征，然后在这些特征中再选择信息增益率最高的特征。 ****** ### 三、C4.5决策树基本思想 下面以一个例子来详细说明C4.5的基本思想
上述数据集有四个属性，属性集合A={天气，温度，湿度，风速}， 类别标签有两个，类别集合L={进行，取消}。
3.1 计算类别信息熵
类别信息熵表示的是所有样本中各种类别出现的不确定性之和。根据熵的概念，熵越大，不确定性就越大，把事情搞清楚所需要的信息量就越多。
Ent(D) = -9/14 * log2(9/14)-5/14 * log2(5/14) =
0.940
3.2 计算每个属性的信息熵
每个属性的信息熵相当于一种条件熵。他表示的是在某种属性的条件下，各种类别出现的不确定性之和。属性的信息熵越大，表示这个属性中拥有的样本类别越不“纯”。
Ent(天气) = 5/14 * [-2/5 * log2(2/5) - 3/5 * log2(3/5)] + 4/14
* [-4/4 * log2(4/4)] + 5/14 * [-3/5 * log2(3/5) - 2/5 * log2(2/5)] =
0.694
Ent(温度) = 4/14 * [-2/4 * log2(2/4) - 2/4 * log2(2/4)] + 6/14
* [-4/6 * log2(4/6) - 2/6 * log2(2/6)] + 4/14 * [-3/4 * log2(3/4) - 1/4
* log2(1/4)] = 0.911
Ent(湿度) = 7/14 * [-3/7 * log2(3/7) - 4/7 * log2(4/7)] + 7/14
* [-6/7 * log2(6/7) - 1/7 * log2(1/7)] = 0.789
Ent(风速) = 6/14 * [-3/6 * log2(3/6) - 3/6 * log2(3/6)] + 8/14
* [-6/8 * log2(6/8) - 2/8 * log2(2/8)] = 0.892
3.3 计算信息增益
信息增益 = 熵 - 条件熵，在这里就是 类别信息熵 - 属性信息熵，它表示的是信息不确定性减少的程度。如果一个属性的信息增益越大，就表示用这个属性进行样本划分可以更好的减少划分后样本的不确定性，当然，选择该属性就可以更快更好地完成我们的分类目标。
信息增益就是ID3算法的特征选择指标。
Gain(天气) = Ent(D) - Ent(天气) = 0.940 - 0.694 = 0.246
Gain(温度) = Ent(D) - Ent(温度) = 0.940 - 0.911 = 0.029
Gain(湿度) = Ent(D) - Ent(湿度) = 0.940 - 0.789 = 0.150
Gain(天气) = Ent(D) - Ent(风速) = 0.940 - 0.892 = 0.048
但是我们假设这样的情况，每个属性中每种类别都只有一个样本，那这样属性信息熵就等于零，根据信息增益就无法选择出有效分类特征。所以，C4.5选择使用信息增益率对ID3进行改进。
3.4 计算属性分裂信息度量
用分裂信息度量来考虑某种属性进行分裂时分支的数量信息和尺寸信息，我们把这些信息称为属性的内在信息（instrisic information）。信息增益率用信息增益 / 内在信息，会导致属性的重要性随着内在信息的增大而减小（也就是说，如果这个属性本身不确定性就很大，那我就越不倾向于选取它），这样算是对单纯用信息增益有所补偿。
H(天气) = -5/14 * log2(5/14) - 5/14 * log2(5/14) - 4/14 *
log2(4/14) = 1.577 H(温度) = -4/14 * log2(4/14) - 6/14 *
log2(6/14) - 4/14 * log2(4/14) = 1.556 H(湿度) = -7/14 *
log2(7/14) - 7/14 * log2(7/14) = 1.0 H(风速) = -6/14 *
log2(6/14) - 8/14 * log2(8/14) = 0.985
3.5 计算信息增益率
IGR(天气) = Gain(天气) / H(天气) = 0.246/1.577 = 0.155
IGR(温度) = Gain(温度) / H(温度) = 0.029/1.556 = 0.0186
IGR(湿度) = Gain(湿度) / H(湿度) = 0.151/1.000 = 0.151
IGR(风速) = Gain(风速) / H(风速) = 0.048/0.985 = 0.048
天气的信息增益率最高，选择天气为分裂属性。发现分裂了之后，天气是“阴”的条件下，类别是”纯“的，所以把它定义为叶子节点，选择不“纯”的结点继续分裂。
在子结点当中重复过程1~5。 至此，这个数据集上C4.5的计算过程就算完成了，一棵树也构建出来了。
3.6 算法流程
1 | while (当前节点”不纯“) |
四、Python代码
完整源码: QzmVc1/Data-Mining/C4.5决策树/
这个程序还是有些瑕疵的，比如什么RuntimeWarning: invalid value
encountered in
double_scalars，看了很久也没发现程序哪里错了，也没找到相应的解决方法…暂且先鸽着吧…但还是可以跑起来的emmm…
#### 运行结果 
****** ### 五、优点与缺点 优点：产生的分类规则易于理解，准确率较高。
缺点：在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。
****** 参考链接： 数据挖掘领域十大经典算法之—C4.5算法