决策树算法研究及应用? 王桂芹黄道
华东理工大学实验十五楼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年本科毕业于太原理工大学自动化系,现就读于华东理工大学信息科学与工程学院,攻读硕士学位,研究方向为数据挖掘;黄道,男,汉族,
华东理工大学信息科学与工程学院博士生导师、教授。 2 算法分类 2.1 ID3算法
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算法改进了选择新属性的启发式函数,能取得比ID3更好的分类效果。当选择一个新属性时,MID3算法不仅考虑该属性带来的信息增益,而且考虑选择该属性后继的属性带来的信息增益,即同时考虑树的两层节点,从而弥补了ID3算法的不足。而曲开社等人就Quinlan的ID3算
法中信息熵标准有倾向于取值较多的属性的缺陷,在计算信息熵时引入了用户兴趣度,改进了ID3算法,使决策树减少了对取值较多的属性的依赖性[9]。同样,王静红和李笔为了克服ID3算法偏向于选择取值多的,但在实际问题中对分类意义并不大的属性作为测试属性的缺点,引入了选取优值法的概念来对ID3算法进行改进[10][11]。此外,对于Quinlan的ID3算法中采用的信息增益并非最优启发式这一缺点,吴艳艳
提出了将决策树的基本建树思想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能够对不完整数据进行处理; (5K次迭代交叉验证;
(6C4.5采用的知识表示形式为决策树,并能最终可以形成产生规则。
此外,C4.5算法可通过使用不同的修剪技术以避免树的不平衡。即通过剪枝操作删除部分节点和子树以避免“过度适合”,以此消除训练集中的异常和噪声。
①C4.5算法代表着基于决策树的方法的里程碑。但是,C4.5算法同样存在不足:C4.5算法采用分而治之的策略所得到决策树不一定是最优的;②采用一边构造决策树,一边进行评价的方法,使决策树的结构调整、性能改善比较困难;③仅考虑决策树的错误率,未考虑树的节点、深度,而树的结点个数代表了树的规模,树的平均深度对应着决策树的预测速度;④对属性值分组时逐个探索,没有一种使用启发式搜索的机制,分组效率较低[1]; Quinlan
⑤经典的展示C4.5算法结果的方法,是将结果树逆时针旋转90度。以文本形式输出,很不直观[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算法的优点在于它不依赖类别先验概率,特征间为强相关,具有直观的知识表,
获得的知识与专家知识在表示和内容上有较高的一致性。因此,IBLE 算法特别适合于处理大规模的学习问题,其形成系统可作专家系统的知识获取工具[5]。
决策树算法研究及应用概要
