决策树ID3算法的优化*

王利军

(安徽经济管理学院信息工程系,安徽 合肥 230031)

Quinlan J R提出的ID3算法[1]是经典的决策树算法，该算法以信息增益作为属性划分的依据，选取信息增益最大的属性作为分裂节点，从而生成决策树.这样的决策树结构简单，易于理解.但这种选取方式倾向属性值较多的属性，而这个属性不一定是最优的，为了避免这种多值依赖现象，许多学者提出了各种方案，如文献[2]引入属性的相关子集进行分类；文献[3]引用权值来进行改进信息增益公式来解决多值依赖问题；文献[4]提出了属性优先值的概念进行修正；文献[5]引入属性协调度这一概念来度量属性的分类能力，该分类能力其实是属性与类标号属性之间的相关性的体现；文献[6]提出的GINI指数作为衡量阀值，平衡信息增益对属性值个数多的偏好问题.本文拟采用OneR算法计算出每个属性的准确率来修正ID3算法的多值依赖问题.

另外关于信息增益公式简化计算方面的问题，许多学者提出各种简化方法，如文献[7]利用等价无穷小的性质来加快信息增益的计算效率；文献[8]利用凸函数的性质来简化计算；文献[9]利用知识依赖理论对公式进行简化.本文拟采用幂级数展开式来简化计算.

1 相关理论和举例

1.1 决策树ID3算法

ID3算法是决策树中的常用算法，它是以信息论中的信息熵理论为依据的.

定义1 类标号属性的期望信息量：设包含s个数据的训练样本数据集DB，若DB中类标号属性可划分为n个分类，每个分类表示为DBi(1≤i≤n),每个分类包含的样本数据为si，pi表示属于第i个类标志值的概率，即pi=si/s(0

(1)

定义2 属性的期望信息量：假设属性A具有k个不同的值，则样本数据集DB可根据属性A的不同值划分为k个子集{A1,A2,…,Ak}，每个分类为Aj(1≤j≤k)，设子集Aj在类DBi中的样本个数为si,j,sj表示按属性A分类后第j类的样本个数，pi,j表示第j类属于第i个类标志值的概率，即pi,j=si,j/sj(0

(2)

定义3 属性A的信息熵：公式如下：

(3)

定义4 属性A的信息增益：公式如下：

Gain(A)=I(s1,s2,…,sn)-E(A)

(4)

决策树ID3算法以信息熵为基础，选择信息增益最大的属性作为测试属性，这样的选择方法则会产生多值偏向的问题，即属性值较多的属性优先成为测试属性，而与类标号属性关系相对密切的属性不一定会被优先选择，因此需要修改信息增益的计算公式使信息增益不会随着属性值个数的增加而递增.

采用购车数据集来生成决策树见表1.

表1 购车数据集

各个测试属性的信息熵如下所示：

故Gain(收入水平)=I(8,6)-E(收入水平)=0.448 88，Gain(驾车技术)=I(8,6)-E(驾车技术)=0.257 8，Gain(商务人士)=I(8,6)-E(商务人士)=0.048 119，Gain(喜欢季节)=I(8,6)-E(喜欢季节)=0.467 72，则Gain(喜欢季节)最大，使用喜欢季节作为初始节点，是否购车其实跟客户喜欢的季节关联度不是太大，ID3算法存在多值依赖问题，故构建的决策树如图1所示.

图1 ID3算法构建的决策树

1.2 ID3算法的改进

本文将对决策树ID3算法进行两个方面的改进，第一个方面：引入准确率修正信息增益公式解决多值偏向问题；第二个方面：引入幂级数展开式简化计算优化性能.

1.2.1 基于准确率的信息增益修正

以信息增益最大的属性为测试属性的决策树ID3算法存在的多值偏向问题，为了解决这一问题，需要对信息增益公式进行修正，修正公式不仅需要考虑属性的值取个数，还需要考虑属性与类标号属性之间的关系.本文引入OneR(One Rule)算法来解决这一问题.

OneR算法是一种极为简单的分类算法模型，它可以根据训练集中的一个特征实现对数据的分类，而这个特征必须是准确率最高的，这样的特征则会与类标号属性关系密切，这样就可以解决多值偏向的问题

OneR算法步骤描述如下：首先确定类标号属性后，再对每一个属性的每一个值执行统计，统计每一个值在类标号属性上出现的次数，找出出现次数最大的值所属的类，并确定规则；然后计算每一个属性的准确率，最后找出准确率最高的属性集合

下面举例说明如何计算准确率，比如测试数据包含10条数据信息见表2，以性别为类标号属性，除编号外的三个属性(身高、体重和头发)为测试属性.

表2 OneR算法测试数据

对这三个测试属性分别进行统计，统计结果见表3：

表3 测试属性的统计结果

分析统计结果获得每个属性的准确率，从身高的统计数据中发现，身高为高的4个为男士，则设定规则为身高为高为男，则身高为高的4个男士为准确数据，同理获得身高为矮的3个女士为准确数据，故身高的总准确数据为4+3=7，身高的准确率为7/10=70%；同理获得体重的准确率为60%；头发的准确率为90%.因此根据头发来判断性别的准确率是最高的，选择头发作为性别判断的唯一规则.

每个属性的准确率Accuracy一定程度上反映该属性与类标号属性的关联程度，准确度越高关联度越大，本文对公式(4)进行改进，增加有关准确率的权值系数，这样就可以在计算信息增益时考虑属性与类标号属性的关联性，以此来解决多值偏向问题，修改后的信息增益公式(5)如下所示：

Gain(A)=Accuracy·[I(s1,s2,…,sn)-E(A)]

(5)

1.2.2 基于幂级数展开式简化计算

ID3算法每次选择测试属性时，都需要计算每个候选属性的信息增益，计算过程中包含形如:

常见的幂级数公式如(6)所示：

(6)

设pi=(1-ki)/(1+ki)，kj∈[0,1)，可得ki=(1-pi)/(1+pi),pi∈[0,1)，推导过程如下：

因ki的取值范围符合公式(6)的要求，故可以对上式进行幂级数转化，最终得到如下结果：

(7)

考虑精度和运算量，故保留前两项，近似推导过程：

再将ki=(1-pi)/(1+pi)代入可得(8)式：

(8)

再将pi=si/s代入(8)中得到：

(9)

至此，对数运算已转化成公式(9)所包含的简单加减乘除运算，而且si和s都是整数，减少了计算成本，虽然采用幂级数近似计算会产生误差，但本文采用了准确率对信息增益进行了修正，该准确率也会相应地减少误差.

1.2.3 改进前后的决策树比较

基于表1的购车数据集中各个测试属性的准确率分别为Accuracy(收入水平)=12/14，Accuracy(驾车技术)=11/14，Accuracy(商务人士)=9/14和Accuracy(喜欢季节)=11/14.

采用幂级数近似计算得到I(8,6)=0.981 839，采用幂级数近似计算实现公式(5)得到的信息增益分别为Gain(收入水平)= 0.399 357 9，Gain(驾车技术)=0.217 7，Gain(商务人士)=0.0328 14和Gain(喜欢季节)=0.368 84, 这时发现Gain(收入水平)最大，选择收入水平作为决策树的初始节点，更符合客观实际，从而一定程度上解决了ID3算法的多值偏向问题.基于准确率的信息增益近似计算结果构建的决策树如图2所示：

图2 改进后的决策树

比较图1和图2，首先，可以发现初始节点由4个分枝的“喜欢季节”变成了3个分枝的“收入水平”，收入水平对是否购车的影响最大，才是是否购车的主要因素，这才符合客观实际；其次，叶子节点数由原先的8个变成现在的7个，改进后的决策树更加精简.

2 验证实验

采用3种UCI测试数据集如表4，进行仿真实验来验证改进后的决策树的优越性.验证实验的结果如表5所示.

表4 数据集信息

仿真实验从节点数、挖掘精度和建树时间上进行验证，发现改进后生成决策树的节点数明显减少，表明改进后的决策树更加精简，并且挖掘精度上均有提升，另外从建树时间上看，改进后的算法可以加快建树效率.总之，本文提出的两个方面的改进可以对ID3算法进行一定的优化，达到了预期的效果.

3 结语

本文采用OneR算法中的准确率对信息增益公式进行了修正，从而一定程度上解决了ID3算法的多值偏向问题，另外采用幂级数展开式对ID3算法的计算进行了简化，加快了运算效率，在准确率的协助下近似误差也得到一定的减小.最后采用仿真实验对改进前后生成决策树的节点数、挖掘精度和建树时间进行比较，验证了改进后的算法的优越性.下一步的工作是对改进后的决策树进行进一步的修剪，使决策树得到最优最简状态.