决策树算法研究及应用

电脑应用技术二零零八总第七十二期1决策树算法研究及应用∗王桂芹黄道华东理工大学实验十五楼206室摘要：信息论是数据挖掘技术的重要指导理论之一，是决策树算法实现的理论依据。决策树算法是一种逼近离散值目标函数的方法，其实质是在学习的基础上，得到分类规则。本文简要介绍了信息论的基本原理，重点阐述基于信息论的决策树算法，分析了它们目前主要的代表理论以及存在的问题，并用具体的事例来验证。关键词：决策树算法分类应用StudyandApplicationinDecisionTreeAlgorithmWANGGuiqinHUANGDaoCollegeofInformationScienceandEngineering,EastChinaUniversityofScienceandTechnologyAbstract：TheinformationtheoryisoneofthebasictheoriesofDataMining，andalsoisthetheoreticalfoundationoftheDecisionTreeAlgorithm．DecisionTreeAlgorithmisamethodtoapproachthediscrete-valuedobjectivefunction．Theessentialofthemethodistoobtainaclas-sificationruleonthebasisofexample-basedlearning．Anexampleisusedtosustainthetheory.Keywords：DecisionTree;Algorithm;Classification;Application1引言决策树分类算法起源于概念学习系统CLS(ConceptLearningSystem)，然后发展到ID3方法而为高潮，最后又演化为能处理连续属性的C4．5，有名的决策树方法还有CART和Assistant，Sliq、Sprint等等[2]。最初利用信息论中信息增益方法寻找数据库中具有最大信息量的字段，作决策树的一个结点字段的某些值作门限建立树的分支；在分支下建立下层结点和子分支，生成一棵决策树。再剪枝，优化，然后把决策树转化为规则，利用这些规则可以对新事例进行分类。作者介绍：王桂芹，女，汉族，1983年5月生于山东省嘉祥县，2005年本科毕业于太原理工大学自动化系，现就读于华东理工大学信息科学与工程学院，攻读硕士学位，研究方向为数据挖掘；黄道，男，汉族，华东理工大学信息科学与工程学院博士生导师、教授。电脑应用技术二零零八总第七十二期22算法分类2.1ID3算法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算法中采用的信息增益并非最优启发式这一缺点，吴艳艳电脑应用技术二零零八总第七十二期3提出了将决策树的基本建树思想ID3算法与对象决策属性化简的粗集理论相结合的一种新型的决策树建树方法，该方法的提出使数据挖掘的效果更简单、更容易理解。以徐爱琴为代表的学者提出了基于神经网络的分类决策树构造[6]，该方法通过神经网络训练建立各属性与分类结果之间的关系，进而通过提取各属性与分类结果之间的导数关系来建立分类决策树，同时为了提高神经网络所隐含关系的提取效果，提出了关系强化约束的概念并建立了具体的模型，并通过经验证明了算法的有效性。2.2C4.5算法在ID3算法的基础上，J．R．Quinlan于1993年在其“ProgramsforMachineLearning”一书中，对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]；Quinlan⑤经典的展示C4.5算法结果的方法，是将结果树逆时针旋转90度。以文本形式输出，很不直观[3]。C4.5算法特别适用于挖掘数据量多，且对效率和性能要求高的场合。C5.0算法是C4.5的商业改进版，它利用boosting技术把多个决策树合并到一个分类器，使得在大数据量情况下，效率和生成规则的数量与正确性都有显著的提高。2.3IBLE算法国内于90年代初，研究出基于信道容量的IBLE(Information-BasedLearningfromEx-ample)算法。，较之ID3每次只选一个特征作为决策树的结点的方法，IBLE算法选一组重要特征建立规则，更有效地正确判别，克服了ID3依赖正反例比例的缺点[4]。IBLE算法的基本思想是利用信道容量，寻找数据集中信息量从大到小的多个字段，并由这些字段取值来建立决策规则树的一个结点。根据该结点中指定字段取值的权值之和与两个阈值比较，建立左、中、右三个分枝。在各分枝子集中重复建树结点和分枝过程，这样就建立了决策规则树。IBLE算法的优点在于它不依赖类别先验概率，特征间为强相关，具有直观的知识表，电脑应用技术二零零八总第七十二期4获得的知识与专家知识在表示和内容上有较高的一致性。因此，IBLE算法特别适合于处理大规模的学习问题，其形成系统可作专家系统的知识获取工具[5]。2.4SPRINT算法为了减少需要驻留于内存的数据量。提出了SPRINT算法，进一步改进了决策树算法实现时的数据结构，去掉在SLIQ中需要驻留在内存的类别列表。将它的类别列合并到每个属性列表中。其优点是：在寻找每个结点的最优分裂标准时变得相对简单一些：其缺点是：对非裂属性的属性列表进行分裂变得很困难。解决的办法是对分裂属性进行分裂时用哈希表记录下每个记录属于哪个孩子结点，若内存能够容纳下整个哈希表，其它属性列表的分裂只需参照该哈希表即可。2.5SLIQ算法SLIQ算法是IBMAlmadenResearchCenter于1996年提出的一种高速可伸缩的数据挖掘分类算法．它通过“预排序技术”和“广度优先技术”，着重解决当训练集数据量巨大，无法全部放人内存时，如何高速准确地生成更快的，更小的决策树[6]。此外，SLIQ采用的是Gini分割系数的方法，不限制训练数据属性的数量，能同时处理离散字段和连续字段。对数据集包含n个类的数据集S，Gini(S)定义为：21()1njjGiniSP==−∑，jP是S中第j类数据的频率。Gini越小，InformationGain越大，如果集合S分成两部分，1N和2N，那么这个分割的Gini就是：12()(1)(2)splitNNGinitginiSginiSNN=+区别于一般的决策树，SLIQ采用二分查找树结构，对于每个节点都需要先计算最佳方案，然后执行分裂。对于数值型连续字段(numbericattribute)分裂的形式Av=。所以，可以先对数值型字段排序，假设排序后的结果为12,,,mvvv⋅⋅⋅，因为分裂只会发生在两个节点之间，所以有1n−种可能性。通常取中点1()/2iivv++作为分裂点．从小到大依次取不同的splitpoint，取InformationGain指标最大(gini最小)的一个就是分裂点。因为每个节点都需要排序，所以这项操作的代价极大，降低排序成本成为一个重要的问题，SLIQ算法对排序有很好的解决方案，使用一个重要的结构：类直方图(classhistogram)经过一次对所有属性表的遍历，可以找出所有叶子节点的最佳分裂方案。对于离散型字段(categoricalattrib-ute)，设()SA为A的所有可能的值，分裂测试将要取遍。S的所有子集'S，寻找当分裂成'S和'SS−两块时的gini指标，取到gini最小的时候，就是最佳分裂方法。显然，主要开销是寻找最佳的子集，这是一个对集合。S的所有子集进行遍历的过程，共需要计算2S次，代价也是很大的。SLIQ的可伸缩性受限于它所使用的常驻内存的数据结构，随着训练集的增长，可能变得代价昂贵．SPRINT算法使用不同的属性表数据结构，并易于并行化，进一步增强了可伸缩性。上面讨论的各类算法，各有优缺点．在实际工作中，必须根据数据类型的