决策树算法研究及应用

决策树算法研究及应用

王桂芹 黄道

华东理工大学实验十五楼206室

摘 要：信息论是数据挖掘技术的重要指导理论之一，是决策树算法实现的理论依据。决策树算法是一种逼近离散值目标函数的方法，其实质是在学习的基础上，得到分类规则。本文简要介绍了信息论的基本原理，重点阐述基于信息论的决策树算法，分析了它们目前主要的代表理论以及存在的问题，并用具体的事例来验证。 关键词：决策树 算法 分类 应用

Study and Application in Decision Tree Algorithm

WANG Guiqin HUANG Dao

College of Information Science and Engineering, East China University of Science and Technology Abstract：The information theory is one of the basic theories of Data Mining，and also is the theoretical foundation of the Decision Tree Algorithm．Decision Tree Algorithm is a method to approach the discrete-valued objective function．The essential of the method is to obtain a clas-sification rule on the basis of example-based learning．An example is used to sustain the theory. Keywords：Decision Tree; Algorithm; Classification; Application

1 引 言

决策树分类算法起源于概念学习系统CLS(Concept Learning System)，然后发展到ID3方法而为高潮，最后又演化为能处理连续属性的C4．5，有名的决策树方法还有CART和Assistant，Sliq、Sprint等等[2]。最初利用信息论中信息增益方法寻找数据库中具有最大信息量的字段，作决策树的一个结点字段的某些值作门限建立树的分支；在分支下建立下层结点和子分支，生成一棵决策树。再剪枝，优化，然后把决策树转化为规则，利用这些规则可以对新事例进行分类。

作者介绍：王桂芹，女，汉族，1983年5月生于山东省嘉祥县，2005年本科毕业于太原理工大学自动化系，现就读于华东理工大学信息科学与工程学院，攻读硕士学位，研究方向为数据挖掘；黄道，男，汉族，华东理工大学信息科学与工程学院博士生导师、教授。 1

决策树算法研究及应用

2 算法分类

2.1 ID3算法

Quinlan提出的ID3算法是决策树算法的代表，具有描述简单、分类速度快的优点，适合于大规模数据的处理，绝大数决策树算法都是在它的基础上加以改进而实现的．它采用分治策略，通过选择窗口来形成决策树，是利用信息增益寻找数据库中具有最大信息量的属性字段建立决策树的一个节点，再根据该属性字段的不同取值建立树的分枝；在每个分枝子集中重复建立树的下层节点和分枝过程。

ID3算法的基础理论清晰，使得算法较简单，学习能力较强，且构造的决策树平均深度较小，分类速度较快，特别适合处理大规模的学习问题。ID3算法采用信息增益最为单一属性的度量，试图减少树的平均深度，忽略了叶子数目的研究，主要存在的问题有[1]:

(1)ID3算法注意力集中在特征的选择上，且偏向于选择特征值数目较多的特征，而特征值数目较多的特征却不总是最优的特征，这样不太合理；

(2)用互信息作为特征选择量上存在一个假设，即训练例子集中的正、反例的比例应该与实际问题领域里正、反例的比例相同。一般情况下，不能保证相同，这样计算训练集的互信息就存在偏差；

(3)ID3对噪声较为敏感，训练集中正例与反例的比例很难控制； (4)学习简单的逻辑表达能力差；

(5)当训练集增加时，ID3的决策树会随之变化。这对渐进学习是不方便的； (6)ID3在建树时，每个节点仅含一个特征，特征之间的相关性强调不够。

ID3算法适用于数量较大的决策判断系统和大型的数据库系统。在这些系统中，其优势将会得到更好的体现。ID3引入后不久，Schlimmer和Fisher在ID3的基础上构造了ID4算法，允许递增式地构造决策树。1988年，Utgoff也提出ID5算法，它允许通过修改决策树来增加新的训练实例，而无需重建决策树。

以ID3为代表构造决策树的算法把研究重点放在属性的选择上，这一研究方式受到了许多有关学者的关注与怀疑。针对这一情况，人们都在此基础上提出了自己的改进思想。

洪家荣等从事例学习最优化的角度分析了决策树归纳学习的优化原则，提出了一种新的基于概率的决策树构造算法PID[7] 。PID在决策树的规模和精度方面优于ID3，但是在训练速度和测试速度上比ID3慢，并且PID决策树上的某些属性可能重复使用。针对ID3算法选择属性较多的属性这一缺点，针对ID3算法的不足，刘小虎等提出的MID3算法是对ID3算法的优化[1][8]。MID3算法改进了选择新属性的启发式函数，能取得比ID3更好的分类效果。当选择一个新属性时，MID3算法不仅考虑该属性带来的信息增益，而且考虑选择该属性后继的属性带来的信息增益，即同时考虑树的两层节点，从而弥补了ID3算法的不足。而曲开社等人就Quinlan的ID3算法中信息熵标准有倾向于取值较多的属性的缺陷，在计算信息熵时引入了用户兴趣度，改进了ID3算法，使决策树减少了对取值较多的属性的依赖性[9]。同样，王静红和李笔为了克服ID3算法偏向于选择取值多的，但在实际问题中对分类意义并不大的属性作为测试属性的缺点，引入了选取优值法的概念来对ID3算法进行改进[10][11]

。此外，对于Quinlan的ID3算法中采用的信息增益并非最优启发式这一缺点，吴艳艳

2

决策树算法研究及应用

提出了将决策树的基本建树思想ID3算法与对象决策属性化简的粗集理论相结合的一种新型的决策树建树方法，该方法的提出使数据挖掘的效果更简单、更容易理解。以徐爱琴为代表的学者提出了基于神经网络的分类决策树构造[6]，该方法通过神经网络训练建立各属性与分类结果之间的关系，进而通过提取各属性与分类结果之间的导数关系来建立分类决策树， 同时为了提高神经网络所隐含关系的提取效果，提出了关系强化约束的概念并建立了具体的模型，并通过经验证明了算法的有效性。 2.2 C4.5算法

在ID3算法的基础上，J．R．Quinlan于1993年在其“Programs for Machine Learning”一书中，对ID3算法进行了补充和改进，提出了又一流行的C4.5算法。C4.5算法继承了ID3全部优点，且克服了ID3在应用中的不足，主要体现在以下几方面[2]：

(1)用信息增益率来选择属性，克服了ID3用信息增益选择属性时偏向于选择取值多的属性的不足；

(2)在树构造过程中或者构造完成之后，使用不同的修剪技术以避免树的不平衡； (3)能够完成对连续属性的离散化处理； (4)能够对不完整数据进行处理； (5)K次迭代交叉验证；

(6)C4.5采用的知识表示形式为决策树，并能最终可以形成产生规则。

此外，C4.5算法可通过使用不同的修剪技术以避免树的不平衡。即通过剪枝操作删除部分节点和子树以避免“过度适合”，以此消除训练集中的异常和噪声。

C4.5算法代表着基于决策树的方法的里程碑。但是，C4.5算法同样存在不足：①C4.5算法采用分而治之的策略所得到决策树不一定是最优的；②采用一边构造决策树，一边进行评价的方法，使决策树的结构调整、性能改善比较困难；③仅考虑决策树的错误率，未考虑树的节点、深度，而树的结点个数代表了树的规模，树的平均深度对应着决策树的预测速度；没有一种使用启发式搜索的机制，分组效率较低[1] ；④对属性值分组时逐个探索，

是将结果树逆时针旋转90度。以文本形式输出，⑤Quinlan经典的展示C4.5算法结果的方法，

很不直观[3]。C4.5算法特别适用于挖掘数据量多，且对效率和性能要求高的场合。C5.0算法是C4.5的商业改进版，它利用boosting技术把多个决策树合并到一个分类器，使得在大数据量情况下，效率和生成规则的数量与正确性都有显著的提高。 2.3 IBLE算法

国内于90年代初，研究出基于信道容量的IBLE(Information-Based Learning from Ex-ample)算法。，较之ID3每次只选一个特征作为决策树的结点的方法，IBLE算法选一组重要特征建立规则，更有效地正确判别，克服了ID3依赖正反例比例的缺点[4] 。IBLE算法的基本思想是利用信道容量，寻找数据集中信息量从大到小的多个字段，并由这些字段取值来建立决策规则树的一个结点。根据该结点中指定字段取值的权值之和与两个阈值比较，建立左、中、右三个分枝。在各分枝子集中重复建树结点和分枝过程，这样就建立了决策规则树。

IBLE算法的优点在于它不依赖类别先验概率，特征间为强相关，具有直观的知识表，

3

决策树算法研究及应用

获得的知识与专家知识在表示和内容上有较高的一致性。因此，IBLE算法特别适合于处理大规模的学习问题，其形成系统可作专家系统的知识获取工具[5]。 2.4 SPRINT算法

为了减少需要驻留于内存的数据量。提出了SPRINT算法，进一步改进了决策树算法实现时的数据结构，去掉在SLIQ中需要驻留在内存的类别列表。将它的类别列合并到每个属性列表中。其优点是：在寻找每个结点的最优分裂标准时变得相对简单一些：其缺点是：对非裂属性的属性列表进行分裂变得很困难。解决的办法是对分裂属性进行分裂时用哈希表记录下每个记录属于哪个孩子结点，若内存能够容纳下整个哈希表，其它属性列表的分裂只需参照该哈希表即可。 2.5 SLIQ算法

SLIQ算法是IBM Almaden Research Center于1996年提出的一种高速可伸缩的数据挖掘分类算法．它通过“预排序技术”和“广度优先技术”，着重解决当训练集数据量巨大，无法全部放人内存时，如何高速准确地生成更快的，更小的决策树[6]。此外，SLIQ采用的是Gini分割系数的方法，不限制训练数据属性的数量，能同时处理离散字段和连续字段。对数据集包含n个类的数据集S，Gini(S)定义为：Gini(S)=1 ∑

nj=1

P

2j

，Pj是S中第j类数据

的频率。Gini越小，Information Gain越大，如果集合S分成两部分，N1和N2，那么这个分割的Gini就是：Gini

split

(t)=

N1N2

gini(S1)+gini(S2) NN

区别于一般的决策树，SLIQ采用二分查找树结构，对于每个节点都需要先计算最佳方案，然后执行分裂。对于数值型连续字段(numberic attribute)分裂的形式A<=v。所以，可以先对数值型字段排序，假设排序后的结果为v1,v2, ,vm，因为分裂只会发生在两个节点之间，所以有n 1种可能性。通常取中点(vi+vi+1)/2作为分裂点．从小到大依次取不同的split point，取Information Gain指标最大(gini最小)的一个就是分裂点。因为每个节点都需要排序，所以这项操作的代价极大，降低排序成本成为一个重要的问题，SLIQ算法对排序有很好的解决方案，使用一个重要的结构：类直方图(class histogram)经过一次对所有属性表的遍历，可以找出所有叶子节点的最佳分裂方案。对于离散型字段(categorical attrib-ute)，设S(A)为A的所有可能的值，分裂测试将要取遍。S的所有子集S'，寻找当分裂成S'和S S'两块时的gini指标，取到gini最小的时候，就是最佳分裂方法。显然，主要开销是寻找最佳的子集，这是一个对集合。S的所有子集进行遍历的过程，共需要计算

2次，代价也是很大的。

SLIQ 的可伸缩性受限于它所使用的常驻内存的数据结构，随着训练集的增长，可能

变得代价昂贵．SPRINT算法使用不同的属性表数据结构，并易于并行化，进一步增强了可伸缩性。

上面讨论的各类算法，各有优缺点．在实际工作中，必须根据数据类型的特点及数据集的大小，选择合适的算法。

4

S

决策树算法研究及应用

3 基于信息增益决策树算法的描述

设S为一个包含s个数据样本的集合，类别属性可以取m个不同的值，对应于m个不同的类别Ci,i∈{1,2,3,…，m}。假设si为类别Ci 中的样本个数，那么要对一个给定数据对象进行分类所需要的信息量为：

m

I(s1,s2, ，sm)= ∑pilog(pi)

i=1

(1)

子集{s1,s2, ，sv}，其中Sj包含了S集合中属性A取aj 值的数据样本，若属性A被选为测试属性(用于对当前样本集进行划分)，设Sij 为子集Sj中属于Ci类别的样本集，利用属性A划分当前样本集合所需要的信息熵：

设一个属性A取v个不同的值{a1,a2, ，av}，利用属性A可以将集合S划分为v个

E(A)=∑

j=1v

v

S1j+S2j+ +Smj

S

m

(S1j+S2j+ +Smj)

=∑∑

j=1i=1

S1j+S2j+ +Smj

S

pijlog(pij)

(2)

其中，pij=

SijSj

，即为子集Sj中任一个数据样本属于类别Ci的概率。这样利用属性A对

当前分支结点进行相应样本集合划分所获得的信息增益是：

Gain(A)=I(s1,s2, ,sm) E(A)

(3)

计算出各属性的信息增益后，选取信息增益最大的属性作为结点向下生成决策树。

4 应用举例

有一个决策树生成的例子，是早晨的天气是否适合晨练的问题。适合的属于正例记

为P，不适合的属于反例记为N。天气由四个属性描述，即天气形势、温度、湿度、风。天气形势取值晴朗、有云、下雨；温度取值凉、温、热；湿度取值正常、高；风取值为无、有。共有十四个记录，如表1所示。

样本数据集中有两个不同的类别，即m=2。设c1对应于P类别，共有9个样本，c2对应于N类别，共有5个样本。

为计算每个属性的信息量，根据公式计算出对一个给定样本进行分类 所需要的期望信息：

I(s1,s2)=I(9,5)= 9log29 5log25=0.94

14

14

14

14

对属性“天气”，有{晴，多云，雨}

取值为“晴天”的样本有2个属于P类，3个属于N类，即

5

决策树算法研究及应用

I(s11,s21)=I(2,3)=0.971

取值为“多云”的有：s12=4s22=0I(s12,s22)=I(4,0)=0 取值为“雨”的有：s13=3s23=2I(s13,s23)=I(3,2)=0.971

计算出根据属性“天气” 对样本集合进行划分需要的期望信息：

s11=2s21=3

545

I(s11,s21)+I(s12,s22)+I(s13,s23) 141414

由此获得利用属性“天气”对样本集合进行划分所获得的信息增益为： Gain=(天气）＝I(s1,s2)－E(天气）＝0.245 E(天气）=

同样，Gain=(湿度）＝0.151

Gain=(风）＝0.048

表1 样本数据集

1 2 3 4 5 6 7 8 9 10 11 12 13 14

天气形势 晴 晴 多云 雨 雨 雨 多云 晴 晴 雨 晴 多云 多云 雨

温度

热 热 热 适中 冷 冷 冷 适中 冷 适中 适中 适中 热 适中

适度

高 高 高 高 正常 正常 正常 高 正常 正常 正常 高 正常 高

风

无风 有风 无风 无风 无风 有风 有风 无风 无风 无风 有风 有风 无风 有风

类别 N N P P P N P N P P P P P N

Gain=(温度）＝0.029

因此，天气形势具有最大的信息增益，被选为根结点并向下扩张。依次类推产生的决策树如图1所示。

如果生成决策树时不对属性进行选择，则结果如图2所示。

5 结束语

本文介绍了决策树算法，分析了它们目前主要的代表理论以及存在的问题，并举出了利用基于信息论的决策树算法解决天气分类问题的实例。

决策树算法已经有了广泛的应用，并且已经有了许多成熟的系统，这些系统广泛应用于各个领域，如语音识别、模式识别、专家系统等。但是，解决一个复杂的数据挖掘问题的任何算法都要面临以下问题：从错误的数据中学习、从分布的数据中学习、从有偏的数

6

决策树算法研究及应用

据中学习、学习有弹性的概念、学习那些抽象程度不同的概念、整合定性与定量的发现等，归纳学习当中还有很多未开发的课题等待我们去研究。

图1 基于信息增益的决策树算法描述

图2 不基于信息增益法生成的决策树

参考文献

[1] J.R.Quinlan ．C4.5：Programs for machine leaning[M]．Los Altos，California：Morgan Kaufmann

Publishers，Inc．1993．

[2] 邵峰晶，于忠清．数据挖掘原理[M]．北京：中国水利出版社，2003 [3] HOLLAND J H．Adaptation in Natural and Artificial System[M]．Cambridge，MA：MIT Press，1992． [4] 曲开社，成文丽等．ID3算法的一种改进算法[J]．计算机工程与应用，2OO3，(25)：104—107． [5] 徐凌宇，杜庆东等．一种基于互信息的特征跃迁示例学习法[J]．2001，(6)：653—657．

[6] 洪家荣．丁明峰，李星原等．一种新的决策树归纳学习算法[J]，计算机学报．1995，18(6)：471-475． [7] 洪家荣，丁明峰等．一种新的决策树归纳学习方法[J]．计算机学报，1995，l8(6)：471-474． [8] 刘小虎，李生．决策树的优化算法[J]．软件学报，1998，9(1O)：797—800．

[9] 曲开社，成文丽等．ID3算法的一种改进算法[J]．计算机工程与应用，2OO3，(25)：104-107 [10] 王静红，李笔．基于决策树的一种改进算法[J]．电讯技术．2OO4，(5)：175-178． [11] 王静红，王熙照，等．决策树算法的研究及优化[J]．微机发展．2OO4，(9)：30-32．

7