决策树C4.5算法属性取值优化研究

在决策树算法中，属性取值种类的多少决定着决策树分支数量的多少。基于此，提出了一种新的属性取 *通讯作者。

决策树算法是一种最简单、最直接、最有效的文本分类算法。最早的决策树算法是ID3 算法[1]，于1986 年由Quinlan 提出，该算法是一种基于信息熵的决策树分类算法。由于该算法是以信息熵作为属性选择的标准，偏向于选择属性取值较多的属性，而属性取值较多的属性往往分类的贡献不大。因此，于1993 年Quinlan 在ID3 算法的基础上又提出了一种改进算法， 即C4.5 算法[2]。

该算法采用信息增益率作为属性选择的标准，继承了ID3 算法的所有优点，克服了ID3 算法中偏向于选择属性取值较多的属性作为测试属性的不足，同时还能对连续属性与未知属性进行处理，在剪枝方面也有很大的改进。

C4.5 算法作为经典的决策树分类算法，已被广泛的应用到各个领域。但其仍然存在以下不足之处：1) 在计算信息增益的过程中(包括：分类所需信息量、信息熵、分割信息量)涉及的复杂的对数运算，计算机每一次计算都需要调用库函数， 增大了生成决策树所需的时间开销；2) 生成决策树中分支数量过多， 部分分支还能进行合并，进一步精简生成决策树的结构。

针对以上不足，已有很多学者提出了改进优化算法。文献[3]，作者通过引入高等数学中等价无穷的原理，对C4.5 算法中的计算公式进行了改进，用简单的四则混合运算取代了复杂的对数运算，减少了生成决策树所需的时间开销。文献[4]，作者提出了一种对属性取值进行优化合并的方法，该方法通过将属性的不同取值分成多个样本子集，并计算各个样本子集的熵以及样本子集的平均熵值，并将熵值大于平均熵值的样本子集进行合并，并重新定义一个属性取值替代原数据表中的属性取值，实例证明该方法确实能起到精简生成决策树结构的作用。

本文针对生成决策树分支数量过多的不足，提出了一种新的属性取值优化方法，并用实例分析验证了该方法的有效性。

2. C4.5 算法介绍 C4.5 算法是一种基于信息熵的决策分类算法，该算法的核心思想是根据信息熵原理，选择样本集中信息增益率最大的属性作为分类属性，并根据该属性的不同取值构造决策树的分支，再对子集进行递归构造，直到完成决策树的构造[5]。

假设样本空间D 中有正例集P 个、反例集N 个，且D = P + N，则一棵决策树能对待分类数据集做出正确类别判断所需的信息量为： ()22, loglogPPNNI P NDDDD= −− (1) 如果以属性A 作为决策树的根节点，且A 具有V 个值()123, , , , vV V VV，它将H 分为V 个样本子集()123, , , , vH HHH，设iH 中共有d 个数据集，其中有p 个正例和n 个反例，则子集iH 的信息熵()iE H可由下式计算： ()22loglogippnnE Hdddd= −− (2)