决策树算法研究.docx
《决策树算法研究.docx》由会员分享,可在线阅读,更多相关《决策树算法研究.docx(14页珍藏版)》请在冰点文库上搜索。
决策树算法研究
2012届学士学位毕业论文
决策树算法研究
学号:
姓名:
指导教师:
专业:
系别:
完成时间:
2012年5月
决策树算法研究
专业:
计算机科学与技术姓名:
学号:
指导教师:
摘要
决策树算法是数据挖掘中重要的分类方法,基于决策树的各种算法在执行速度、可扩展性、输出结果的可理解性、分类预测的准确性等方面各有千秋,在各个领域广泛应用且已经有了许多成熟的系统,如语音识别、模式识别和专家系统等。
本文着重研究和比较了几种典型的决策树算法,并对决策树算法的应用进行举例。
关键词
决策树算法,度量,比较,应用
1、引言
数据挖掘是一个利用分析工具从大量的、不完全的、模糊的数据中,提取隐含在其中的有用的信息和知识的过程。
分类算法是属于预测式数据挖掘的一种数据分析方法,其目的是根据重要样本数据集找出能准确描述并区分数据类的模型,以便对未来的测试数据进行分类。
决策树算法就是一种典型的分类方法,它着眼于从一组无次序、无规则的事例中推理出决策树表示形式的分类规则。
决策树方法的起源是概念学习系统CLS,发展到ID3方法为高潮,最后又演化为能处理连续属性的C4.5,其他典型的决策树方法还有CART,SLIQ和SPRINT等。
本文重点介绍了ID3算法以及C4.5算法,分析比较了几种典型算法的优点和不足,并对算法所面临的问题进行简要阐述,提出今后开展研究的建议。
2、决策树算法背景知识及研究现状
2.1决策树算法描述
决策树,顾名思义就是一个类似于流程图的树型结构。
—个决策树由根结点、分支和叶结点构成。
树的最高层节点称为根结点,是整个决策树的开始。
与根结点相连的不同分支,对应这个属性的不同取值,根据不同的回答转向相应的分支,在新到达的结点处做同样的分支判断,持续这一过程直到到达某个叶结点。
在决策树中,每个内部结点表示一个测试,该结点的每个分支表示该测试的一个结果,每个叶结点表示一个类别。
例如公司需要预测某位客人是否要买计算机,图2.1就是为了解决这个问题而建立的一颗决策树,从中可以看到决策树的基本组成部分:
根结点、分支和叶结点。
图2.1决策树
2.2决策树算法研究现状
决策树算法广泛应用于各个领域,已经有了广泛的应用并且有许多成熟的系统,如语音识别、医疗诊断、模式识别和专家系统等。
目前,决策树技术面临的挑战表现在以下几个方面:
(1)可扩展性亟待提高。
在大型数据集中,能从中快速而准确地发现隐藏于其中的主要分类规则,即认为算法具有良好的可扩展性。
数据挖掘面临的数据往往是海量的,对实时性要求较高的决策场所,数据挖掘方法的主动性和快速性显得日益重要。
(2)适应多数据类型和容噪性。
随着计算机网络和信息的社会化,数据挖掘的对象已不单是关系数据库模型,而是分布、异构的多类型数据库,数据的非结构化程度、噪声等现象越来越突出,这也是决策树技术面临的困难问题。
(3)决策树方法的递增性。
数据挖掘出来的知识,只是相对于某一时间的某些数据,新的数据可能使发现的新知识与原来的知识冲突。
因此,设计具有递增性决策树挖掘方法,也是实用化的基本要求之一。
3、决策树算法简介
3.1CLS算法
CLS算法是早期的决策树学习算法,是许多决策树学习算法的基础。
CLS基本思想:
从一棵空决策树开始,选择某一属性作为测试属性。
该测试属性对应决策树中的决策结点。
根据该属性的值的不同,可将训练样本分成相应的子集,如果该子集为空,或该子集中的样本属于同一个类,则该子集为叶结点,否则该子集对应于决策树的内部结点,即测试结点,需要选择一个新的分类属性对该子集进行划分,直到所有的子集都为空或者属于同一类。
例1:
如表3.1所示为人员眼睛、头发颜色与所属人种之间的关系:
表3.1人员眼睛、头发颜色与所属人种
人员
眼睛颜色
头发颜色
所属人种
1
黑色
黑色
黄种人
2
蓝色
金色
白种人
3
灰色
金色
白种人
4
蓝色
红色
白种人
5
灰色
红色
白种人
6
黑色
金色
混血
7
灰色
黑色
混血
8
蓝色
黑色
混血
根据表3.1所提供的信息,选择“眼睛颜色”为测试属性,可将该样本划分为相应的子集如图3.1所示。
图3.1初步构建决策树
根据“眼睛颜色”所划分的子集中的样本不属于同一类,所以选择新的测试属性“头发颜色”对各个子集进行划分,如图3.2所示,所得的样本属于同一类,决策树构建完成。
图3.2决策树
3.2ID3算法
ID3算法是决策树学习算法中最具有影响和最为典型的算法,它的基本思想是,利用信息熵原理,选择信息增益最大的属性作为分类属性。
3.2.1信息量大小的度量
Shannon1948年提出的信息论理论。
事件ai的信息量I(ai)可如下度量:
,
其中p(ai)表示事件ai发生的概率。
假设有n个互不相容的事件a1,a2,a3,……,an,它们中有且仅有一个发生,则其平均的信息量可如下度量:
=
,
在决策树分类中,假设S是训练样本集合,|S|是训练样本数,样本划分为n个不同的类C1,C2,……Cn,这些类的大小分别标记为|C1|,|C2|,……,|Cn|。
则任意样本S属于类Ci的概率为:
。
假设属性A的所有不同值的集合为XA,Sv是S中属性A的值为v的样本子集,在选择属性A后的每一个分支节点上,对该节点的样本集Sv分类的熵为E(Sv)。
选择A导致的期望熵定义为每个子集Sv的熵的加权和,权值为属于Sv的样本占原始样本S的比例
即期望熵为:
属性A相对样本集合S的信息增益Gain(S,A)定义为:
,
其中Gain(S,A)是指因知道属性A的值后导致的熵的期望压缩。
Gain(S,A)越大,说明选择测试属性A对分类提供的信息越多。
ID3算法就是将每个节点选择信息增益Gain(S,A)最大的属性作为测试属性。
3.2.2ID3决策树应用举例
例2:
公司收集了数据如下表3.2所示,对于任意给定的客人,能否帮助公司将这位客人归类。
表3.2谁在买计算机
计数
年龄
收入
学生
信誉
归类:
买计算机?
64
青
高
否
良
不买
64
青
高
否
优
不买
128
中
高
否
良
买
60
老
中
否
良
买
64
老
低
是
良
买
64
老
低
是
优
不买
64
中
低
是
优
买
128
青
中
否
良
不买
64
青
低
是
良
买
132
老
中
是
良
买
64
青
中
是
优
买
32
中
中
否
优
买
32
中
高
是
良
买
63
老
中
否
优
不买
1
老
中
否
优
买
(1)计算决策属性的熵
决策属性“买计算机?
”,该属性分为两类:
买、不买。
S1(买)=641S2(不买)=383S=S1+S2=1024
P1=641/1024=0.6260P2=383/1024=0.3740
I(S1,S2)=I(641,383)=-P1log2P1-P2log2P2=0.9537
(2)计算条件属性的熵
条件属性共有4个,分别是年龄、收入、学生、信誉。
分别计算不同属性的信息增益。
计算年龄的熵:
年龄共分三个组:
青年、中年、老年
青年买与不买比例为128/256
P1=128/384P2=256/384
I(S1,S2)=I(128,256)=-P1log2P1-P2log2P2=0.9183
中年买与不买的比例为256/0
P1=256/256P2=0/256
I(S1,S2)=I(256,0)=-P1log2P1-P2log2P2=0
老年买与不买的比例为257/127
P1=257/384P2=127/384
I(S1,S2)=I(257,127)=-P1log2P1-P2log2P2=0.9157
所占比例:
青年组:
384/1024=0.375;中年组:
256/1024=0.25;老年组:
384/1024=0.375
计算年龄的平均信息期望:
E(年龄)=0.375*0.9183+0.25*0+0.375*0.9157=0.6877
G(年龄)=0.9537-0.6877=0.266
计算收入的熵:
收入共分三个组:
高、中、低
E(收入)=0.9361
G(收入)=0.9537-0.9361=0.0176
计算学生的熵:
学生共分为两个组:
学生、非学生
E(学生)=0.7811
G(学生)=0.9537-0.7811=0.1726
计算信誉的熵:
信誉分两个组:
良好,优秀
E(信誉)=0.9048
G(信誉)=0.9537-0.9048=0.0453
(3)计算选择结点:
通过以上计算可知,年龄信息增益值最大,因此选择年龄属性进行分支,观察表3.2,当年龄为“中”时,对应的归类都为买,因此该处形成叶结点;而年龄取“青”、“老”时,对应的归类不唯一,因此构造树结构如图3.3:
图3.3树结构
在年龄属性为青年时,分别计算收入信息增益、学生信息增益、信誉信息增益可知,在属性学生处信息增益值最大,因此取学生为分支属性;同理,当年龄属性为老年时,同样的计算可得分支属性为信誉。
预测消费者是否会购买电脑的决策树分类构建完成,如图3.4所示:
图3.4谁在买计算机
3.3C4.5算法
C4.5算法是ID3算法的改进,它继承了ID3算法的优点并对ID3算法进行了改进和补充。
C4.5算法采用信息增益率作为选择分支属性的标准,克服了ID3算法中信息增益选择属性时偏向选择取值多的属性的不足,并能够完成对连续属性离散化的处理,还能够对不完整数据进行处理。
3.3.1用信息增益率选择属性
信息增益率等于信息增益与分裂信息的比值,定义如下:
,
上式中SplitInfo(A)表示属性A的分裂信息,分裂信息用来衡量属性分裂数据的广度和均匀,其定义如下:
。
根据例2中提供的信息,可计算:
SplitInfo([384,256,384])=-(0.375*log20.375+0.25*log20.25+0.375*log20.375)=2.999
GainRatio(年龄)=gain(年龄)/split([384,256,384])=0.266/2.999=0.089
其他的三个属性可以类似地得出它们的信息增益率,如下表3.3所示:
表3.3属性对应的信息增益率
年龄
收入
Gain
0.266
Gain
0.018
SplitInfo
2.999
SplitInfo
1.528
GainRatio
0.089
GainRatio
0.012
学生
信誉
Gain
0.173
Gain
0.045
Splitinfo
0.998
SplitInfo
0.929
GainRatio
0.173
GainRatio
0.048
利用C4.5算法构建决策树中选取各属性中信息增益率最大的属性作为分裂点,以后的做法与ID3的相同,唯一的不同之处是判断标准由信息增益变成了信息增益率。
3.3.2处理连续属性值
C4.5既可以处理离散型描述属性,也可以处理连续性描述属性。
在选择某结点上的分枝属性时,对于离散型描述属性,C4.5的处理方法与ID3相同,按照该属性本身的取值个数进行计算;对于某个连续性描述属性,C4.5将作以下处理:
(1)对属性的取值由小到大进行排序。
(2)两个属性取值之间的中点作为可能的分裂点,将该结点上的数据集分成两部分,计算每个可能的分裂点的信息增益。
(3)计算每一种分割所对应的信息增益率,选择最大的分割点来划分数据集。
3.3.3树剪枝
剪枝方法的主要目的是去掉那些噪声或异常数据,使决策树具有更泛化能力。
剪枝常采用统计度量,剪掉最不可靠的分枝,从而带来较快的分类,提高树独立于测试数据进行正确分类的能力。
剪枝按其实施的时间分为两种方法:
事前修剪法和事后修剪法。
C4.5算法采用一种后剪枝方法。
事后剪枝是由完全生长的树剪去分枝。
通过删除结点的分枝,剪掉树结点。
它在允许决策树得到最充分生长的基础上,再根据一定的规则,剪去决策树中的那些不具有一般代表性的叶结点或分枝。
修剪后,被修剪的分枝结点就成为一个叶结点,并将其标记为它所包含样本中类别个数最多的类别。
4、决策树算法比较分析
基于决策树算法自提出至今种类不下几十种。
各种算法在执行速度、可扩展性、输出结果的可理解性,分类预测的准确性等方面各有千秋。
最早提出的CLS算法只是给出了生成决策树系统的框架,却没有具体说明算法的内容;ID3算法采用信息熵的增益进行属性选择,但只能处理具有离散型属性和属性值齐全的元组,生成形如多叉树的决策树。
后来出现的C4.5算法经过改进,能够直接处理连续属性,也能够处理属性值空缺的训练元组,它采用信息增益率进行属性选择。
由于ID3算法与C4.5算法生成决策树分支多,规模过于庞大,出现了根据GINI系数来选择测试属性的决策树算法,比如CART。
对这几种算法进行一个概要性的比较如表4.1所示。
表4.1典型决策树算法比较
属性选择度量
处理连续属性
剪枝方法
是否需要独立测试样本集
决策树结构
ID3
信息增益
离散化
分类错误
是
多叉树
C4.5
信息增益率
预排序
分类错误
否
多叉树
CART
GINI系数
预排序
MDL
否
二叉树
5、总结
本文重点阐述了ID3算法与C4.5算法及其应用举例,比较了几种典型决策树算法的优缺点。
对于相当大的范围内的应用来说,决策树分类比其他分类技术能生成更精确的分类结果,但是对决策树分类性能的度量和评价会困难些。
即使在树分类器的每一等级上的分类效果是最优的,也不能保证最终的结果是最优的,虽然决策树算法使用最好的特征进行分类,但还是可能存在一些特征对分类很有用,却没有用到。
如果能把这些特征选择出来,选择在每个子集上能够有效分类的特征,就能有效地减少树的层数,对于分类结果会有很大的提高。
参考文献
[1]冯少荣.决策树算法的研究与改进[J].厦门大学学报.2007,46(4):
496—497.
[2]刘小虎,李生.决策树的优化算法[J].软件学报.1998,9(10):
797-800.
[3]洪家荣,丁明峰.一种新的决策树归纳学习算法[J].计算机学报.2011,6:
470-474.
[4]迟庆云.决策树分类算法及应用[J].枣庄学院学报.2005,22:
29-31.
[5]王晓东.《算法设计与分析》[M].北京:
清华大学出版社,2003.75-80.
[6]王光宏,蒋平.数据挖掘综述[J].同济大学学报.2004,32
(2):
246-252.
[7]路红梅.基于决策树的经典算法综述[J].宿州学报.2007,22
(2):
99-95.
[8]杨明,张载鸿.决策树学习算法ID3的研究[J].微机发展.2002,12(5):
89-94.
[9]李启炎.应用c4.5算法构造客户分类决策树的方法[J].计算机工程.2003,(14):
89-91.
[10]吉根林.决策树分类计数研究.计算机工程[J].2004,(9):
91-94.
Researchondecisiontreealgorithm
Name:
ZhangQianliInstructor:
MaQiang
Abstract:
Algorithmofdecisiontreeindataminingisanimportantmethodofclassificationbasedondecisiontreealgorithms,inexecutionspeed,scalability,outputresultcomprehensibility,classificationaccuracy,eachhasitsownmerits.,extensiveapplicationinvariousfieldsandhavemanymaturesystem,suchasspeechrecognition,patternrecognitionandexpertsystemandsoon.Thispaperstudiesandcomparesseveralkindsoftypicaldecisiontreealgorithm,andthealgorithmofdecisiontreeapplicationexamples.
KeyWords:
DecisionTreeAlgorithmMeasureCompareApplication