决策树算法研究及应用?王桂芹黄道华东理工大学实验十五楼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年本科毕业于太原理工大学自动化系,现就读于华东理工大学信息科学与工程学院,攻读硕士学位,研究方向为数据挖掘;黄道,男,汉族,华东理工大学信息科学与工程学院博士生导师、教授。2算法分类2.1ID3算法Quinlan提出的ID3算法是决策树算法的代表,具有描述简单、分类速度快的优点,适合于大规模数据的处理,绝大数决策树算法都是在它的基础上加以改进而实现的.它采用分治策略,通过选择窗口来形成决策树,是利用信息增益寻找数据库中具有最大信息量的属性字段建立决策树的一个节点,再根据该属性字段的不同取值建立树的分枝;在每个分枝子集中重复建立树的下层节点和分枝过程。ID3算法的基础理论清晰,使得算法较简单,学习能力较强,且构造的决策树平均深度较小,分类速度较快,特别适合处理大规模的学习问题。ID3算法采用信息增益最为单一属性的度量,试图减少树的平均深度,忽略了叶子数目的研究,主要存在的问题有[1]:(1ID3算法注意力集中在特征的选择上,且偏向于选择特征值数目较多的特征,而特征值数目较多的特征却不总是最优的特征,这样不太合理;(2用互信息作为特征选择量上存在一个假设,即训练例子集中的正、反例的比例应该与实际问题领域里正、反例的比例相同。一般情况下,不能保证相同,这样计算训练集的互信息就存在偏差;(3ID3对噪声较为敏感,训练集中正例与反例的比例很难控制;(4学习简单的逻辑表达能力差;(5当训练集增加时,ID3的决策树会随之变化。这对渐进学习是不方便的;(6ID3在建树时,每个节点仅含一个特征,特征之间的相关性强调不够。ID3算法适用于数量较大的决策判断系统和大型的数据库系统。在这些系统中,其优势将会得到更好的体现。ID3引入后不久,Schlimmer和Fisher在ID3的基础上构造了ID4算法,允许递增式地构造决策树。1988年,Utgoff也提出ID5算法,它允许通过修改决策树来增加新的训练实例,而无需重建决策树。以ID3为代表构造决策树的算法把研究重点放在属性的选择上,这一研究方式受到了许多有关学者的关注与怀疑。针对这一情况,人们都在此基础上提出了自己的改进思想。洪家荣等从事例学习最优化的角度分析了决策树归纳学习的优化原则,提出了一种新的基于概率的决策树构造算法PID[7]。PID在决策树的规模和精度方面优于ID3,但是在训练速度和测试速度上比ID3慢,并且PID决策树上的某些属性可能重复使用。针对ID3算法选择属性较多的属性这一缺点,针对ID3算法的不足,刘小虎等提出的MID3算法是对ID3算法的优化[1][8]。MID3算法改进了选择新属性的启...
