2.2.2 C4.5算法

C4.5算法的核心思想与ID3完全相同，但在实现方法上做了更好的改进，并增加了新的功能。主要包括：采用“增益比例”来选择分裂属性、对连续属性的处理、对样本属性值缺失情况的处理、规则的产生、交叉验证等。

(1)    用“增益比例”来选择分裂属性

如前所述，ID3是采用“信息增益”来选择分裂属性的。虽然这是一种有效地方法，但其具有明显的倾向性，即它倾向于选择具有大量不同取值的属性，从而产生许多小而纯的子集。尤其是关系数据库中作为主键的属性，比如用户交友数据集中每个用户的一个唯一标识ID，每个样本都有会一个不同的取值。如果以这样的属性作为分裂属性，那么将产生非常多的分支，而且每一个分支产生的子集的熵均为0（因为子集中只有一个样本）。显然，这样的决策树是没有实际意义的。因此，Quinlan提出使用增益比例来代替信息增益。

设S是由s个样本组成的数据集。A是S的某个属性，有v个不同的取值，这样可以把S划分为v个自己，Si表示第i个子集，i=1,2,…,v。|Si|表示子集Si中的样本数量，定义：

Split_info(S,A)用来衡量 属性A分裂属性集的广度性和均匀性。样本在属性A上的取值分布越均匀，Split_info(S,A)值越大。增益比例定义为：

C4.5选择增益比例最大的作为分裂属性。

显然，属性A分裂数据集的广度越大，均匀性越强，其Split_info就越大，增益比例就越小。因此通过该分裂度量计算方法可以消除选择那些值较多且均匀分布的属性作为分裂属性的倾向性。

(2)    连续属性的处理

ID3最初的定义假设数据集的各属性都必须是离散的。如果有连续属性，则可以采用划分区间的方法来离散化。假如在前面的交友偏好例子中，属性“年龄”由于是连续型属性，被划分为“<20”、“[20,30]”、“>30”3个区间，这样属性“年龄” 的不同取值就只有3个了，这就是被离散化的过程。在C4.5中，算法采用另外一种方法来实现连续属性的离散化。

设数据集中有一连续属性Y，现要测试是否可以选用该属性来对数据集进行分裂以及如何分裂（即通过计算信息增益或增益比例来确认Y是否可以作为分裂属性，如果可以，还要确定分裂谓词）。

例如在表3-3所示的训练数据集中，如果要计算“年龄”属性的信息增益，则首先将不同的属性值排序{20，25，28，40，46，55，56，58，60，65，70}，那么可能的阈值集合为{20，25，28，40，46，55，56，58，60，65，70}，从中一一取出，并形成分裂谓词，例如取出“20”，形成谓词“<=20”和“>20”，用它们划分训练数据集，然后计算信息增益或增益比例。

(3)    处理有缺失值的样本

ID3是基于所有属性值都已经确定这一假设的。但是在实际应用中，经常会因为搜集样本时有的样本数据不完整，或者输入数据是有人为的误差等原因，一个数据集中会有某些样本缺少一些属性值。

在用一个属性对数据集进行划分时，必须知道一个样本属于哪一类（以便于计算每类有多少个样本，进而计算该属性的信息增益），这是根据这个样本的属性值来决定的，但是由于属性值缺失，那么该如何判断这个样本属于哪一类呢？

 C4.5并不会武断地将一个有缺省值的样本抛弃（当然，样本数量很大的时候可以这么做），也不会随意地将它分配到某个类别中去。C4.5会根据其他已知属性值来计算一个有缺失值的样本属于某个类别的概率，这个样本可以属于每一个类，只是概率不同而已。

(4)    树的修剪

C4.5采用的修剪方法是所谓的“后剪枝”，即待决策树完全生长结束之后，再来修剪掉那些对分类精度贡献不大的叶子节点。

对于某个节点，计算该节点分裂之前的误分类损失（由于错误地预测了样本的类别而导致的损失）和分裂成子树之后的误分类损失，如果分裂后的误分类损失没有得到显著降低，就可以考虑修剪掉这棵子树。

在计算分类精度之前，用户可以自行定义各种误分类损失的权重，例如“A类样本被误分类为B类导致的损失”比“B类样本误分类为A类导致的损失”要大得多，在这种情况下就可以通过设置误分类损失的权重来加以区分。

下面介绍一种常见的代价复杂性剪枝（CART剪枝算法）。

 对于树中的每一个非叶子节点，计算它的表面误差率增益值α。

其中|NTt|是子树中包含的叶子节点个数，R(t)是节点t的误差代价，如果该节点被剪枝，则

r(t)是节点t的误差率；p(t)是节点t上的数据占所有数据的比例。R(T_t)是子树Tt的误差代价，如果该节点不被剪枝。它等于子树T_t上所有叶子节点的误差代价之和。

采用该剪枝策略的优点在于1. 避免训练数据过拟合；2.转化的叶子节点相比其他剪枝算法有更高的准确率和支持率。

(5)    交叉验证

用决策树分类是有监督学习的算法，通过学习可以对未知的数据进行预测。在训练过程开始之前，将一部分数据保留下来，在训练之后，利用这部分数据对学习的结果进行验证，这种模型评估方法称为交叉验证。如果将这个“学习-验证”的过程重复k次，就称为k次迭代交叉验证。首先将所有训练数据平均分成k份，每次使用其中一份作为测试样本，其余的k-1份数据作为学习样本，然后选择平均分类精度最高的树作为最后的结果。通常，分类精度最高的树并不是节点最多的树。另外，交叉验证还可以用于决策树的修剪。在树的构建过程中要构建k棵决策树会加大该方法计算量。

3.    决策树在交友产品中的应用

在交友类产品中，每个用户都有着自己的偏好，从而拥有各自不同的交友圈和感兴趣的对象。因此，个性化的用户偏好模型建立在交友平台中往往起着举足轻重的作用。而个性化的用户偏好决策树可以很好地满足以上需求。

用户偏好决策树模型

系统通过学习用户的个性化交友偏好行为（偏向喜欢或厌恶那类用户），运用决策树模型为每个用户生成一个个性化的交友偏好模型，并对候选推荐列表进行分类以及排序。

交友平台中每个用户往往有一系列公开的，即可以被其他用户所看到的属性值，如年龄，所在地，职业，兴趣，头像照片等等。

表3.1中列出了可以用做构建决策树的用户公开属性以及说明。

(1)  正反馈，指的是用户觉得喜欢的对象，在交友平台上产生的表现行为有：点赞、送礼物、收藏、发送消息等等；

(2)  未有显著反馈， 即用户觉得无所谓的对象，在交友平台上产生的表现行为往往表现为：点击该对象之后就没有下文了，或者连点都不点，即所谓的未有显著反馈用户是指仅有点击行为或者未点击的没有正、负反馈的用户

(3)  负反馈，即用户不喜欢的对象，在交友平台上产生的表现行为有将用户拖入不感兴趣列表，直接屏蔽或者拉黑用户等等。

以下实际应用中为某个用户建立的决策树结果图

图中，圆形节点代表分裂节点，各节点标有训练样本的数量，分裂属性以及各类别样本分布，方框节点代表叶子节点，标有样本的数量，叶子节点所属类别，样本的分布以及准确率。

其中，按图中用红线标出的一条从根节点到叶子节点的路径，含义为：对于该用户来说，某个用户若其学历属性在字典项(3,4)中的（第1层），职业属性为字典项(6,9)中的（第2层），身高小于166cm的（第3层），被分为正反馈类型，该次分类训练准确率为100%。

构建完成每个用户的个性偏好决策树模型之后，就可以利用该模型对未知的目标进行分类，从而在推荐或者其他展示模块中，优先展示用户更加喜欢的对象。

实际证明，运用该模型对用户进行候选集的推荐，比仅仅利用活跃度或者热门度等单一指标进行排序推荐有着更高的一次转化率以及二次转化率。

值得注意的是，实际应用中用户的偏好群体往往没有严格固定的统一目标属性，因此决策树的剪枝必不可少，否则很容易建立一棵层次过深的过度拟合的树。

4.    总结

本文主要介绍了决策树在交友类产品中的应用，通过一个用户偏好关系的实例详细阐述了决策树的构建过程，并给出了用决策树建立用户偏好模型以及用户关系模型建立的两大应用。在实际交友平台中，还可以结合决策树的特点有着更多具体的应用，如用户关系模型、潜在消费用户模型、用户标签匹配模型等等一系列相关模型，在此不一一赘述。

相关阅读：

决策树技术在交友类产品中的应用（上篇）