资源描述：
《基于决策树的经典算法综述.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第22卷第2期宿州学院学报Vol.22,No.22007年4月JournalofSuzhouCollegeApr.2007基于决策树的经典算法综述1,2路红梅(1.合肥工业大学计算机与信息学院,安徽合肥230009;2.宿州学院人工智能与数据挖掘研究室,安徽宿州234000)摘要:决策树是一种重要的数据挖掘方法。本文对几种经典的决策树算法进行了综述,并对其进行了分析比较,为决策树的优化研究提供了借鉴。关键词:决策树;数据挖掘;分类中图分类号:TP312文献标识码:A文章编号:1673-2006(2007)02-0091-05人工智能已经发
2、展了多种技术来建造分类模1966年由Hunt等人提出了第一个用于构造决[2]型,其中决策树是一种常用的模型。决策树曾在相当策树的概念学习系统CLS,后来的许多决策树学长的时间内是一种非常流行的人工智能技术。20世习算法都可以看作是对CLS算法的改进与更新。纪80年代,它是构建人工智能系统的主要方法之CLS算法的主要思想是从一个空的决策树出一。20世纪90年代初,这一技术随着人工智能遭遇发,通过添加新的判定结点来完善原来的决策树,直低潮而逐渐不为人所注意。然而,20世纪90年代后至该决策树能够正确分类训练实例为止。期,随着数据挖掘技术的兴起
3、,决策树作为一个构建CLS算法的主要步骤如下:决策系统的强有力的技术而重新浮出水面。随着数(1)令决策树T的初始状态只含有一个树根据挖掘技术在商业智能等方面的应用,决策树技术(X,Q),其中X是全体训练实例的集合,Q是全体[1]测试属性的集合;将在未来发挥越来越强大的作用。(2)若T的所有叶结点(X′,Q′)都有如下状态:1决策树与分类或者第一个分量X′中的训练实例都属于同一个类,决策树因其形状像树且能用于决策而得名。从或者第二个分量Q′为空,则停止执行学习算法,学习的结果为T;技术上讲,一个决策树由一系列结点和分枝组成,树(3)否则,选
4、取一个不具有步骤(2)所述状态的中的每个非叶结点(包括根结点)对应于训练集中一叶结点(X′,Q′);个非类别属性的测试,非叶结点的每一个分枝对应(4)对于Q′按照一定规则选取测试属性b,设X′属性的一个测试结果,每个叶子结点则代表一个类被b的不同取值分为m个不相交的子集X′i,1≤i≤或类分布。从根结点到叶子结点的一条路径形成一m,从(X′,Q′)伸出m个分叉,每个分叉代表b的一条分类规则,决策树可以很方便地转化为分类规则,个不同取值,从而形成m个新的叶结点(X′i,Q′-是一种非常直观的分类模式表示形式。{b}),1≤i≤m;决策树的构
5、建是一种自上而下、分而治之的归(5)转步骤(2)。纳过程,其中,测试属性的选择和如何划分样本集是从CLS算法的描述可以看出,决策树的构造过构建决策树的关键环节。不同的决策树算法在此使程是一个假设特化的过程,CLS算法可以看作是只用的技术不尽相同。带一个操作符的学习算法,此操作符可以表示为:通2几种典型的决策树算法过添加一个新的判定条件(新的判定结点),特化当前假设。CLS算法递归调用这个操作符,作用在每2.1CLS算法个叶结点,来构造决策树。在CLS算法中,没有明确给出测试属性的选取收稿日期:2006209222基金支持:安徽省教育厅自然
6、科学基金项目(2006kj091B)。标准,所以CLS有很大的改进空间。作者简介:路红梅(1965-),女,山东聊城人,副教授,在职硕2.2ID3算法士,研究方向:人工智能、数据挖掘和计算机控制。在CLS的基础上,后人陆续提出了多种决策树91v学习算法,其中最为有影响的是Quinlan于1986年piE(A)=õI(Ei)(2.5)[3]∑m提出的ID3算法。ID3名称的由来是因为它是一系j列的“交互式二分法”程序的第3版(InteractiveID3算法是最经典的决策树算法,应用非常广Dichotomizer23)。泛,但它存在着很多不
7、足:(1)存在种类偏见问题,即ID3对CLS主要做了两方面的修改:(1)增加了信息增益的计算倾向于选择取值较多的属性,但取窗口技术;(2)提出以信息熵作为选取测试属性的标值多的属性不一定是最优的;(2)ID3算法构造的决准。策树是单变量决策树,忽略了属性间的相互联系;在CLS算法中,每次运行算法时要知道所有训(3)ID3算法不能直接处理连续性属性;(4)不能处练实例,若训练实例集过大,无法一次全部放人内理属性值空缺的样本。也正是因为ID3算法存在着存,则算法运行时会发生一些问题。Quinlan在ID3以上不足,Quinlan于1993年又
8、研制了C4.5系统。算法中通过引入窗口(windows)的方法进行增量式2.3C4.5算法[4]学习解决了这个问题。C4.5算法是以ID3算法为核心的完整的决信息熵的下降速度是ID3中关键的选
