C4.5算法

0. 引言

C4.5是一系列用在机器学习和数据挖掘的分类问题中的算法。它的目标是监督学习：给定一个数据集，其中的每一个元组都能用一组属性值来描述，每一个元组属于一个互斥的类别中的某一类。C4.5的目标是通过学习，找到一个从属性值到类别的映射关系，并且这个映射能用于对新的类别未知的实体进行分类。
C4.5由J.Ross Quinlan在ID3的基础上提出的。ID3算法用来构造决策树。决策树是一种类似流程图的树结构，其中每个内部节点（非树叶节点）表示在一个属性上的测试，每个分枝代表一个测试输出，而每个树叶节点存放一个类标号。一旦建立好了决策树，对于一个未给定类标号的元组，跟踪一条有根节点到叶节点的路径，该叶节点就存放着该元组的预测。决策树的优势在于不需要任何领域知识或参数设置，适合于探测性的知识发现。

1. 决策树的模型

决策树呈树形结构，在分类问题中，表示基于特征对实例进行分类的过程。学习时，利用训练数据，根据损失函数最小化的原则建立决策树模型；预测时，对新的数据，利用决策模型进行分类。

1.1 决策树的分类

离散性决策树：离散性决策树，其目标变量是离散的，如性别：男或女等；
连续性决策树：连续性决策树，其目标变量是连续的，如工资、价格、年龄等；

1.2 决策树模型

决策树是一种通过对特征属性的分类对样本进行分类的树形结构，包括有向边以及三类节点：

根节点（root node），表示第一个特征属性，只有出边没有入边；
内部节点（internal node），表示特征属性，有一条入边至少两条出边
叶子节点（leaf node），表示类别，只有一条入边没有出边。

决策树模型.png

上图给出了（二叉）决策树的示例。决策树具有以下特点：

对于二叉决策树而言，可以看作是if-then规则集合，由决策树的根节点到叶子节点对应于一条分类规则；
分类规则是互斥并且完备的，所谓互斥即每一条样本记录不会同时匹配上两条分类规则，所谓完备即每条样本记录都在决策树中都能匹配上一条规则；
分类的本质是对特征空间的划分，如下图所示：

决策树模型解析——特征空间划分.png

1.4 决策树学习

决策树学习的本质是从训练集中归纳出一组分类规则。但随着分裂属性次序的不同，所得到的决策树也会不同。如何得到一棵决策树既对训练数据有较好的拟合，又对未知数据有很好的预测呢？

首先，我们要解决两个问题：

如何选择较优的特征属性进行分裂？每一次特征属性的分裂，相当于对训练数据集进行再划分，对应于一次决策树的生长。ID3算法定义了目标函数来进行特征选择。
什么时候应该停止分裂？有两种自然情况应该停止分裂，一是该节点对应的所有样本记录均属于同一类别，二是该节点对应的所有样本的特征属性值均相等。但除此之外，是不是还应该其他情况停止分裂呢？

2. 决策树算法

一般的，一颗决策树包含一个根节点、若干个内部结点和若干个叶结点；叶结点则对应于一个属性册书；每个叶结点包含的样本集合根据属性测试的结果被划分到子结点中；根结点包含样本全集，从根结点到每个叶结点的路径对饮过了一个判定测试序列。决策树学习的目的是为了产生一颗泛化能力强的决策树，其基本流程遵循简单且只管的“分而治之”（divide-and-conquer）策略，如下图所示：

输入： 训练集 $D=\{ (x_1,y_1),(x_2,y_2),...,(x_m,y_m)\}$ ;属性集 $A=\{ a_1,a_2,...,a_d\}$
过程： 函数 $TreeGenerate(D,A)$
1: 　生成节点node
2：　if $D$ 中样本全属于同一类别 $C$ then
3：　　将node标记为 $C$ 类叶节点； return
4：　end if
5：　if $A=\varnothing \ \ \ \ OR\ D$ 中样本在 $A$ 中取值相同then
6：　　　将node标记为叶节点，其类别标记为 $D$ 中样本数最多的类；return
7:　　end if
8：　从 $A$ 中选择最有划分属性 $a_*$ ;
9:　　for $a_*$ 的每一个值 $a^v_*$ 　　do
10:　　　为node生成一个分支；令 $D_v$ 表示 $D$ 中在 $a_*$ 上取值为 $a^v_*$ 的样本子集；
11：　　　if $D_v$ 为空then
12:　　　　将分支节点标记为叶节点，其类别标记为 $D$ 中样本最多的类；return
13:　　　　else
14:　　　　　以 $TreeGenerate(D_v,A\backslash\{ a_*\})$ 为分支结点
15：　　　end if
16：　end for
输出：以node为根节点的一颗决策树

显然，决策树的生成是一个递归的过程。在决策树基本算法中，有三种情形会导致递归返回：

当前结点包含的样本全属于同意类别，无需划分；
当前属性集为空，或是所有样本在所有属性上取值相同，无法划分；
当前结点包含的样本集合为空，不能划分。

在第二种情形下，我们把当前结点标记为叶结点，并且将其类别设定为该结点所含样本最多的类别；在第三种情形下，同样把当前结点标记为叶结点，但将其类别设定为其父结点所含样本最多类别。注意这两种情形的处理实质不同：情形二是在利用当前结点的后验分布，而情形三则是把父结点的样本分布当做当前结点的先验分布。

3. 划分选择

决策树学习的关键在于如何选择最优划分属性。一般而言，随着划分过程的不断进行，我们希望决策树的分支结点所包含的样本尽可能属于同一类别，即结点的“纯度”越来越高。

3.1 信息增益

“信息熵”（information entropy）是度量样本集合纯度最常用的一种指标。假定当前样本集合 $D$ 中第ｋ类样本所占比例为 $p_k(k=1,2,...,|y|)$ ，则 $D$ 的信息熵定义为
$Ent(D)=-\sum_{k=1}^{|y|}p_klog_2p_k$
$Ent(D)$ 的值越小，则 $D$ 的纯度越高。
假定离散属性 $a$ 有 $V$ 个可能的取值 $\{ a^1,a^2,...,a^V\}$ ,若使用 $a$ 来对样本集合 $D$ 进行划分，则会产生 $V$ 个分支结点，其中第ｖ个分支结点包含了 $D$ 中所有在属性 $a$ 上取值为 $a^v$ 的样本，记为 $D^v$ ，我们根据上述公式计算出 $D^v$ 的信息熵，再考虑到不同的分支结点所包含的样本数不同，给分支结点赋予权重 $|D^v|\backslash|D|$ ，即样本越多的分支结点影响越大，于是可以计算出用属性 $a$ 对样本集合 $D$ 进行划分所获得的"信息增益"（information gain）
$Gain(D,a)=Ent(D)-\sum_{v=1}^V\frac{|D^v|}{|D|}Ent(D^v)$
一般而言，信息增益越大，则意味着使用属性ａ来进行划分所获得的“纯度提升越大”。因此，我们可用信息增益来进行决策树的划分属性选择。

3.2 增益率

实际上，信息增益准则对可取值数目较多的属性有所偏好（如何以序号作为划分属性，每一个事物作为一个单独存在的类别的时候，信息增益往往会很高，但是这样进行划分并没有什么意义），为了减少这种偏好可能带来的不利影响，著名的C4.5算法并不是直接使用信息增益，而是使用增益率（gain ratio）来选择最优的划分属性。增益率的定义为：
$Gain\_ratio(D,a)=\frac{Gain(D,a)}{IV(a)}$
$IV(a)=-\sum_{v=1}^V\frac{|D^v|}{|D|}log_2\frac{|D^v|}{|D|}$

值得注意的是：增益率准则对可取值数目较少的属性有所偏好，因此C4.5算法并不是直接选择增益率最大的候选划分属性，而是使用了一个启发式：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的

3.3 基尼指数

CART决策树使用“基尼指数”来选择划分属性。数据集 $D$ 的纯度可用基尼值来度量：
$Gini(D)=\sum_{k=1}^{|y|}\sum_{k^{'}\ne{k}}p_kp_k^{'}=1-\sum_{k=1}^{|y|}p_k^2$
直观来说， $Gini(D)$ 反映了从数据集 $D$ 中随机抽取两个样本，其类别标记不一致的概率，因此 $Gini(D)$ 值越小，则数据集 $D$ 的纯度就越高。属性 $a$ 的基尼指数定义为：
$Gini\_index(D,a)=\sum_{v=1}^V\frac{|D^v|}{|D|}Gini(D^v)$
于是，我们在候选属性集合 $A$ 中，选择那个使得划分后基尼指数最小的属性作为最优划分属性，即 $a_{*}=arg min Gini\_index(D,a)$

3.4 具体例子

例子一(决策树的构成使用)

银行希望能够通过一个人的信息（包括职业、年龄、收入、学历）去判断他是否有贷款的意向，从而更有针对性地完成工作。下表是银行现在能够掌握的信息，我们的目标是通过对下面的数据进行分析建立一个预测用户贷款一下的模型。

决策树例证——银行用户信息表.png

上表中有4个客户的属性，如何综合利用这些属性去判断用户的贷款意向？决策树的做法是每次选择一个属性进行判断，如果不能得出结论，继续选择其他属性进行判断，直到能够“肯定地”判断出用户的类型或者是上述属性都已经使用完毕。比如说我们要判断一个客户的贷款意向，我们可以先根据客户的职业进行判断，如果不能得出结论，再根据年龄作判断，这样以此类推，直到可以得出结论为止。决策树用树结构实现上述的判断流程，如图所示：

银行贷款意向分析决策树示意图.png

通过上图的训练数据，我们可以建议生成决策树，其输入是用户的信息，输出是用户的贷款意向。如果要判断某一客户是否有贷款的意向，直接根据用户的职业、收入、年龄以及学历就可以分析得出用户的类型。如某客户的信息为：{职业、年龄，收入，学历}={工人、39， 1800，小学}，将信息输入上述决策树，可以得到下列的分析步骤和结论。
第一步：　根据该客户的职业进行判断，选择“工人”分支；

决策树例证01.png

第二步：　根据客户的年龄进行选择，选择年龄”<=40”这一分支；

决策树例证02.png

第三步：　根据客户的学历进行选择，选择”小学”这一分支，得出该客户无贷款意向的结论。

决策树例证0３.png

例子二（信息增益）

以熵作为节点复杂度的统计量，分别求出下面例子的信息增益，图3.1表示节点选择属性1进行分裂的结果，图3.2表示节点选择属性2进行分裂的结果，通过计算两个属性分裂后的信息增益，选择最优的分裂属性。

决策树例证04.png

属性一
$Info_1=Ent-\sum_{i=1}^nEnt(y_i)\\ =\frac{16}{28+16}log_2(\frac{16}{28+16})+\frac{28}{28+16} log_2(\frac{16}{28+16})\Rightarrow Entropy\\- (\frac{14}{14+4}log_2(\frac{14}{14+4})+\frac{4}{14+4}log_2(\frac{4}{14+4}))\Rightarrow Entropy1\\- (\frac{14}{14+12}log_2(\frac{14}{14+12})+\frac{12}{14+12}log_2(\frac{12}{14+12}))\Rightarrow Entropy2\\= 0.81$
属性二
$Info_2=Ent-\sum_{i=1}^nEnt(y_i)\\ =\frac{16}{28+16}log_2(\frac{16}{28+16})+\frac{28}{28+16} log_2(\frac{16}{28+16})\Rightarrow Entropy\\- (\frac{8}{8+2}log_2(\frac{8}{8+2})+\frac{2}{8+2}log_2(\frac{2}{8+2}))\Rightarrow Entropy1\\- (\frac{20}{20+14}log_2(\frac{20}{20+14})+\frac{14}{20+14}log_2(\frac{14}{20+14}))\Rightarrow Entropy2\\= 0.75$
由于 $Info_1>Info_2$ ，所以属性1是比属性2更优的分裂属性，故而选择属性1作为分裂属性。

例子三（增益率）

决策树例证04.png

属性一的信息增益率

属性二的信息增益率

由于 $Info\_Ratio_2>Info\_Ratio_1$ ，故而选择属性2作为分裂属性。

4. 剪枝处理

剪枝（pruning）是决策树学习算法对付“过拟合”的主要手段。在决策树学习中，为了尽可能正确分类训练样本，结点划分过程将不断重复，有事会造成决策树分支过多，这是就可能因为训练样本学得太好了，以致把训练集自身的一些特点党组哟所有数据都具有的一般性质而导致过拟合。因此，可通过主动去掉一些分支来降低过拟合的风险。

预剪枝是指在决策树生成过程中，对每一个结点在划分前进行估计，若当前结点的划分不能带来决策树泛化能力的提升，则停止划分并将当前结点标记为叶结点；
后剪枝则是先从训练集生成一颗完整的决策树，然后自底向上对非叶结点进行考察，若将该结点对应的字数替换为叶结点能带来决策树泛化能力的提升，则将该子树替换为叶结点。

4.1 数据集

其中{1,2,3,6,7,10,14,15,16,17}为测试集，{4,5,8,9,11,12,13}为训练集。

西瓜数据——决策树剪枝.png

4.2 预剪枝

预剪枝是要对划分前后泛化性能进行评估。对比决策树某节点生成前与生成后的泛化性能。

在未划分前，根据训练集，类别标记为训练样例数最多的类别，由于训练集中的好瓜与坏瓜是相同多的类别，均为5，因此任选其中一类，书中选择了好瓜作为标记类别。当所有节点集中在根节点，所有训练集属于标记类别的仅有{4,5,8}，因此分类正确的是3/7*100%=42.9%.

2.计算训练集的信息增益，得知脐部的信息增益最大，因此按照脐部进行划分。又因为在训练集中，凹陷特征好瓜的占比多，因此凹陷划分为好瓜，稍凹特征好过占比多，因此将其标记为好瓜，因此按照脐部划分的子树结果如下：

预剪枝02.png

划分后，对比结果如下：

预剪枝03.png

在脐部划分的基础上，进一步计算凹陷、根蒂特征下，其他属性的信息增益，根据计算结果可知，在凹陷的情况下，色泽的信息增益最大，因此对于凹陷的西瓜，进一步确定按照色泽进行划分，划分结果如下：

预剪枝04.png

对于凹陷数据，进一步按照色泽进行划分后，对比划分前后的准确性：

预剪枝05.png

对稍凹数据集，进一步计算其他属性的信息增益，确定根蒂的信息增益最大，因此对稍凹，进一步按照根蒂进行划分：

预剪枝06.png

对于稍凹数据，进一步按照根蒂进行划分后，对比划分前后的准确性：

预剪枝07.png
因此按照预剪枝，最终形成的决策树如下图，其泛化性为71.4%（5/7）。

预剪枝08.png

由图可知，预剪枝使得很多分支没有展开，这不仅降低了过拟合的风险，还显著减少了决策树的训练时间开销和测试时间。但是，有些分支虽当前不能提升泛化性。甚至可能导致泛化性暂时降低，但在其基础上进行后续划分却有可能导致显著提高，因此预剪枝的这种贪心本质，给决策树带来了欠拟合的风险。

4.3 后剪枝

后剪枝表示先从训练集中生成一颗完整决策树。

我在此生成的决策树上将测试集的数据在此树上进行了标记，如下图所示：

后剪枝01.png

对比标记节点的划分类与各数据的真实分类，计算准确率，如下表所示：

后剪枝02.png

生成的决策树，在验证集上的准确度为3/7*100%=42.9%.

后剪枝将从决策树的底部往上进行剪枝，先看最底部的纹理，将其领衔的分支减掉，即将其换成叶子节点。由于在训练集上，替换后，包含的样本号为{7,15}，好瓜坏瓜比例相等，因此选择好瓜进行标记，剪枝后的决策树为：

后剪枝03.png

后剪枝04.png

当减掉底部纹理划分后，准确率提高，因此按照纹理划分需裁剪掉。
接着往上裁剪，此时应该是色泽部分，由于在训练集上，替换后，包含的样本号为{6,7,15}，好瓜（2个）多于坏瓜（1个），因此选择好瓜进行标记，剪枝后的决策树为：

后剪枝05.png

后剪枝06.png

此时决策树验证集精度仍为57.1%，因此可不进行剪枝，即对于脐部稍凹，根蒂稍蜷部分，可保留按照色泽进一步划分。
接下来，我们看脐部凹陷分支。由于在训练集上，将色泽替换为叶节点后，包含的样本号为{1,2,3,14}，好瓜（3个）多于坏瓜（1个），因此选择好瓜进行标记，剪枝后的决策树为：

后剪枝07.png

后剪枝08.png

当减掉最左侧色泽划分后，准确率提高，因此按照色泽划分需裁剪掉。
整棵树遍历基本完成，因此该决策树最终后剪枝的结果如下图所示，其验证精度为71.4%。

后剪枝09.png

4.4 剪枝小结

对比预剪枝与后剪枝生成的决策树，可以看出，后剪枝通常比预剪枝保留更多的分支，其欠拟合风险很小，因此后剪枝的泛化性能往往由于预剪枝决策树。但后剪枝过程是从底往上裁剪，因此其训练时间开销比前剪枝要大。