决策树算法研究.doc

长治学院学士学位论文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.1 CLS算法CLS算法是早期的决策树学习算法，是许多决策树学习算法的基础。CLS基本思想：从一棵空决策树开始，选择某一属性作为测试属性。该测试属性对应决策树中的决策结点。根据该属性的值的不同，可将训练样本分成相应的子集，如果该子集为空，或该子集中的样本属于同一个类，则该子集为叶结点，否则该子集对应于决策树的内部结点，即测试结点，需要选择一个新的分类属性对该子集进行划分，直到所有的子集都为空或者属于同一类。例1：如表3.1所示为人员眼睛、头发颜色与所属人种之间的关系： 表3.1 人员眼睛、头发颜色与所属人种人员眼睛颜色头发颜色所属人种1黑色黑色黄种人2蓝色金色白种人3灰色金色白种人4蓝色红色白种人5灰色红色白种人6黑色金色混血7灰色黑色混血8蓝色黑色混血根据表3.1所提供的信息，选择“眼睛颜色”为测试属性，可将该样本划分为相应的子集如图3.1所示。眼睛颜色1,62,4,83,5,7黑色蓝色灰色图3.1 初步构建决策树根据“眼睛颜色”所划分的子集中的样本不属于同一类，所以选择新的测试属性“头发颜色”对各个子集进行划分，如图3.2所示，所得的样本属于同一类，决策树构建完成。眼睛颜色头发颜色头发颜色头发颜色黑色蓝色灰色白种人4白种人2混血7白种人6黄种人1混血8白种人5白种人3黑色金色金色红色黑色金色红色黑色图3.2 决策树3.2 ID3算法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.2 ID3决策树应用举例例2：公司收集了数据如下表3.2所示，对于任意给定的客人，能否帮助公司将这位客人归类。表3.2 谁在买计算机计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买(1) 计算决策属性的熵决策属性“买计算机？”，该属性分为两类：买、不买。S1(买)=641 S2(不买)=383 S=S1+S2=1024P1=641/1024=0.6260 P2=383/1024=0.3740I(S1，S2)=I(641,383)=-P1log2P1-P2log2P2=0.9537(2) 计算条件属性的熵条件属性共有4个，分别是年龄、收入、学生、信誉。分别计算不同属性的信息增益。计算年龄的熵：年龄共分三个组：青年、中年、老年青年买与不买比例为128/256P1=128/384 P2=256/384I(S1，S2)=I(128,256)=-P1log2P1-P2log2P2=0.9183中年买与不买的比例为256/0P1=256/256 P2=0/256I(S1,S2)=I(256,0)=-P1log2P1-P2log2P2=0老年买与不买的比例为257/127P1=257/384 P2=127/384I(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.6877G(年龄)=0.9537-0.6877=0.266计算收入的熵：收入共分三个组：高、中、低E(收入)=0.9361 G(收入) =0.9537-0.9361=0.0176计算学生的熵：学生共分为两个组：学生、非学生E(学生)=0.7811G(学生) =0.9537-0.7811=0.1726计算信誉的熵：信誉分两个组：良好，优秀E(信誉)=0.9048G(信誉) =0.9537-0.9048=0.0453(3) 计算选择结点：通过以上计算可知，年龄信息增益值最大，因此选择年龄属性进行分支，观察表3.2，当年龄为“中”时，对应的归类都为买，因此该处形成叶结点；而年龄取“青”、“老”时，对应的归类不唯一，因此构造树结构如图3.3：年龄买/不买买/不买买中青老图3.3 树结构在年龄属性为青年时，分别计算收入信息增益、学生信息增益、信誉信息增益可知，在属性学生处信息增益值最大，因此取学生为分支属性；同理，当年龄属性为老年时，同样的计算可得分支属性为信誉。预测消费者是否会购买电脑的决策树分类构建完成，如图3.4所示：年龄学生信誉买买不买不买买中青老否是优良图3.4 谁在买计算机3.3 C4.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.999GainRatio(年龄)=gain(年龄)/split(384,256,384)=0.266/2.999=0.089其他的三个属性可以类似地得出它们的信息增益率，如下表3.3所示：表3.3 属性对应的信息增益率年龄收入Gain0.266Gain0.018SplitInfo2.999SplitInfo1.528GainRatio0.089GainRatio0.012学生信誉Gain0.173Gain0.045Splitinfo0.998SplitInfo0.929GainRatio0.173GainRatio0.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信息增益率预排序分类错误否多叉树CARTGINI系数预排序MDL否二叉树5、总结本文重点阐述了ID3算法与C4.5算法及其应用举例，比较了几种典型决策树算法的优缺点。对于相当大的范围内的应用来说，决策树分类比其他分类技术能生成更精确的分类结果，但是对决策树分类性能的度量和评价会困难些。即使在树分类器的每一等级上的分类效果是最优的，也不能保证最终的结果是最优的，虽然决策树算法使用最好的特征进行分类，但还是可能存在一些特征对分类很有用，却没有用到。如果能把这些特征选择出来，选择在每个子集上能够有效分类的特征，就能有效地减少树的层数，对于分类结果会有很大的提高。参考文献1 冯少荣.决策树算法的研究与改进J.厦门大学学报.2007,46(4):496497.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.Re