决策树算法研究报告

1、-. z.摘 要随着信息科技的高速开展，人们对于积累的海量数据量的处理工作也日益增重，需创造之母，数据挖掘技术就是为了顺应这种需求而开展起来的一种数据处理技术。数据挖掘技术又称数据库中的知识发现，是从一个大规模的数据库的数据中有效地、隐含的、以前未知的、有潜在使用价值的信息的过程。决策树算法是数据挖掘中重要的分类方法，基于决策树的各种算法在执行速度、可扩展性、输出结果的可理解性、分类预测的准确性等方面各有千秋，在各个领域广泛应用且已经有了许多成熟的系统，如语音识别、模式识别和专家系统等。本文着重研究和比拟了几种典型的决策树算法，并对决策树算法的应用进展举例。关键词：数据挖掘；决策树；比拟Abs

2、tractWiththerapiddevelopmentofInformationTechnology,peoplearefacingmuchmoreworkloadindealingwiththeaccumulatedmassdata.Dataminingtechnologyisalsocalledtheknowledgediscoveryindatabase,datafromalargedatabaseofeffectively,implicit,previouslyunknownandpotentiallyusevalueofinformationprocess. Algorithm o

3、f decision tree in data mining is an important method of classification based on decision tree algorithms, in e*ecution speed, scalability, output result prehensibility, classification accuracy, each has its own merits., e*tensive application in various fields and have many mature system, such as sp

4、eech recognition, pattern recognition and e*pert system and so on. This paper studies and pares several kinds of typical decision tree algorithm, and the algorithm of decision tree application e*amples.Keywords:Data mining; decision tree；pare目录TOC o 1-3 h z uHYPERLINK l _Toc440569408第一章 绪论 PAGEREF _

5、Toc440569408 h HYPERLINK l _Toc440569409第二章 文献综述 PAGEREF _Toc440569409 h HYPERLINK l _Toc4405694102.1 数据挖掘简述 PAGEREF _Toc440569410 h HYPERLINK l _Toc4405694112.2 决策树算法背景知识及研究现状PAGEREF _Toc440569411 h HYPERLINK l _Toc4405694122.2.1 决策树算法描述 PAGEREF _Toc440569412 h HYPERLINK l _Toc4405694132.2.2关联分析决策树

6、算法研究现状 PAGEREF _Toc440569413 h HYPERLINK l _Toc440569414第三章 决策树算法 PAGEREF _Toc440569414 h HYPERLINK l _Toc4405694153.1 CLS算法 PAGEREF _Toc440569415 h HYPERLINK l _Toc4405694163.2 ID3算法 PAGEREF _Toc440569416 h HYPERLINK l _Toc4405694173.2.1 信息量大小的度量 PAGEREF _Toc440569417 h HYPERLINK l _Toc4405694183.2

7、.2 ID3决策树应用举例 PAGEREF _Toc440569418 h HYPERLINK l _Toc4405694193.3 C4.5算法 PAGEREF _Toc440569419 h HYPERLINK l _Toc4405694203.3.1 用信息增益率选择属性 PAGEREF _Toc440569420 h HYPERLINK l _Toc4405694213.3.2 处理连续属性值 PAGEREF _Toc440569421 h HYPERLINK l _Toc4405694223.3 树剪枝 PAGEREF _Toc440569422 h HYPERLINK l _Toc

8、4405694233.4 weka平台的简述 PAGEREF _Toc440569423 h HYPERLINK l _Toc440569424第四章 决策树在学生成绩中的应用 PAGEREF _Toc440569424 h HYPERLINK l _Toc4405694254.1数据的预处理 PAGEREF _Toc440569425 h HYPERLINK l _Toc4405694264.2数据的训练集处理 PAGEREF _Toc440569426 h HYPERLINK l _Toc4405694274.3数据的校验和成绩分析 PAGEREF _Toc440569427 h HYPE

9、RLINK l _Toc440569428第五章 结论 PAGEREF _Toc440569428 h HYPERLINK l _Toc440569429参 考 文 献 PAGEREF _Toc440569429 h I-. z.第一章 绪论无论在企业应用领域，还是在科学领域，数据挖掘技术有着广泛的应用价值。 在企业应用领域，用于制定好的市场策略以及企业的关键性决策。在商业面，数据挖掘技术可以增强企业的竞争优势，缩短销售周期，降低生产本钱，有助制定市场方案和销售策略，并已经成为电子商务中的关键技术。近年来，随着我国高等教育的飞速开展，高校的教学管理信息不断增多。教学工作信息化有了很大的进步，好

10、多高校在管理学生和教师信息方面有了很好的方式。比方我校的教务系统，这些系统为教师和学生提供了很好的帮助。这些系统中积累了大量的数据。目前的这些数据库系统虽然根本上都可以实现数据的录入、修改、统计、查询等功能，但是这些数据所隐藏的价值并没有被充分的挖掘和利用，信息资源的浪费还是比拟严重的。为了提高教学质量，将数据挖掘技术引入到高校学生成绩分析中，对这些数据进展深入的挖掘和合理的分析，从而挖掘出传统的分析方法所无法得出的结论。进而利用分析结果引导教学的开展，从而有利于提高教学质量。第二章文献综述数据挖掘作为一个新兴的多学科穿插应用领域，正在各行各业的决策支持活动扮演着越来越重要的角色。2.1数据挖

11、掘简述数据挖掘英语：Data mining，又译为资料探勘、数据采矿。它是数据库知识发现英语：Knowledge-Discovery in Databases，简称：KDD)中的一个步骤。数据挖掘一般是指从大量的数据中自动搜索隐藏于其中的有着特殊关系性属于Association rule learning的信息的过程。数据挖掘通常与计算机科学有关，并通过统计、在线分析处理、情报检索、机器学习、专家系统依靠过去的经历法则和模式识别等诸多方法来实现上述目标。数据挖掘是通过分析每个数据，从大量数据中寻找其规律的技术，主要有数据准备、规律寻找和规律表示3个步骤。数据准备是从相关的数据源中选取所需的数据

12、并整合成用于数据挖掘的数据集；规律寻找是用*种方法将数据集所含的规律找出来；规律表示是尽可能以用户可理解的方式如可视化将找出的规律表示出来。决策树是判定给定样本与*种属性相关联的决策过程的一种表示方法，从数据中生成分类器的一个特别有效的方法是生成一棵决策树，该方法广泛应用与数据挖掘和机器学习等领域，用来解释用分类相关的问题，决策树表示法是应用最广泛的逻辑方法之一。目前生成决策树方法的算法主要有三种：CART算法、ID3算法和C4.5算法。其中C4.5算法具有分类速度快且精度高的特点，是开展比拟完善的一种决策树算法。2.2决策树算法背景知识及研究现状决策树算法描述决策树，顾名思义就是一个类似于流

13、程图的树型构造。个决策树由根结点、分支和叶结点构成。树的最高层节点称为根结点，是整个决策树的开场。与根结点相连的不同分支，对应这个属性的不同取值，根据不同的答复转向相应的分支，在新到达的结点处做同样的分支判断，持续这一过程直到到达*个叶结点。在决策树中，每个部结点表示一个测试，该结点的每个分支表示该测试的一个结果，每个叶结点表示一个类别。例如公司需要预测*位客人是否要买计算机，图2.1就是为了解决这个问题而建立的一颗决策树,从中可以看到决策树的根本组成局部：根结点、分支和叶结点。年龄学生信誉买买不买不买买中青老否是优良图2.1 决策树关联分析决策树算法研究现状决策树算法广泛应用于各个领域，已经

14、有了广泛的应用并且有许多成熟的系统，如语音识别、医疗诊断、模式识别和专家系统等。目前，决策树技术面临的挑战表现在以下几个方面：(1)可扩展性亟待提高。在大型数据集中，能从中快速而准确地发现隐藏于其中的主要分类规则，即认为算法具有良好的可扩展性。数据挖掘面临的数据往往是海量的，对实时性要求较高的决策场所，数据挖掘方法的主动性和快速性显得日益重要。 (2)适应多数据类型和容噪性。随着计算机网络和信息的社会化，数据挖掘的对象已不单是关系数据库模型，而是分布、异构的多类型数据库，数据的非构造化程度、噪声等现象越来越突出，这也是决策树技术面临的困难问题。(3)决策树方法的递增性。数据挖掘出来的知识，只是

15、相对于*一时间的*些数据，新的数据可能使发现的新知识与原来的知识冲突。因此，设计具有递增性决策树挖掘方法，也是实用化的根本要求之一。第三章 决策树算法3.1 CLS算法CLS算法是早期的决策树学习算法，是许多决策树学习算法的根底。CLS根本思想：从一棵空决策树开场，选择*一属性作为测试属性。该测试属性对应决策树中的决策结点。根据该属性的值的不同，可将训练样本分成相应的子集，如果该子集为空，或该子集中的样本属于同一个类，则该子集为叶结点，否则该子集对应于决策树的部结点，即测试结点，需要选择一个新的分类属性对该子集进展划分，直到所有的子集都为空或者属于同一类。例1：如表3.1所示为人员眼睛、头发颜

16、色与所属人种之间的关系：人员眼睛颜色头发颜色所属人种1黑色黑色黄种人2蓝色金色白种人3灰色金色白种人4蓝色红色白种人5灰色红色白种人6黑色金色混血7灰色黑色混血8蓝色黑色混血根据表3.1所提供的信息，选择眼睛颜色为测试属性，可将该样本划分为相应的子集如图3.1所示。眼睛颜色1,62,4,83,5,7黑色蓝色灰色根据眼睛颜色所划分的子集中的样本不属于同一类，所以选择新的测试属性头发颜色对各个子集进展划分，如图3.2所示，所得的样本属于同一类，决策树构建完成。眼睛颜色头发颜色头发颜色头发颜色黑色蓝色灰色白种人4白种人2混血7白种人6黄种人1混血8白种人5白种人3黑色金色金色红色黑色金色红色黑色图3

17、.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，这些类的大小分别标记为|C1|，|C2|，|。则任意样本S属于类Ci的概率为：。假设属性A的所有不同

18、值的集合为*A，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所示，对于任意给定的客人，能否帮助公司将

19、这位客人归类。表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

20、) 计算条件属性的熵条件属性共有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-P2log2

21、P2=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.9

22、048G(信誉) =0.9537-0.9048=0.0453(3) 计算选择结点：通过以上计算可知，年龄信息增益值最大，因此选择年龄属性进展分支，观察表3.2，当年龄为中时，对应的归类都为买，因此该处形成叶结点；而年龄取青、老时，对应的归类不唯一，因此构造树构造如图3.3：年龄买/不买买/不买买中青老在年龄属性为青年时，分别计算收入信息增益、学生信息增益、信誉信息增益可知，在属性学生处信息增益值最大，因此取学生为分支属性；同理，当年龄属性为老年时，同样的计算可得分支属性为信誉。预测消费者是否会购置电脑的决策树分类构建完成，如图3.4所示：年龄学生信誉买买不买不买买中青老否是优良图3.4 谁在买

23、计算机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

24、*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.

25、5算法构建决策树中选取各属性息增益率最大的属性作为分裂点，以后的做法与ID3的一样，唯一的不同之处是判断标准由信息增益变成了信息增益率。3.3.2处理连续属性值C4.5既可以处理离散型描述属性，也可以处理连续性描述属性。在选择*结点上的分枝属性时，对于离散型描述属性，C4.5的处理方法与ID3一样，按照该属性本身的取值个数进展计算；对于*个连续性描述属性， C4.5将作以下处理：(1) 对属性的取值由小到大进展排序。(2) 两个属性取值之间的中点作为可能的分裂点，将该结点上的数据集分成两局部，计算每个可能的分裂点的信息增益。 (3) 计算每一种分割所对应的信息增益率，选择最大的分割点来划分数据

26、集。3.3 树剪枝剪枝方法的主要目的是去掉那些噪声或异常数据，使决策树具有更泛化能力。剪枝常采用统计度量，剪掉最不可靠的分枝，从而带来较快的分类，提高树独立于测试数据进展正确分类的能力。剪枝按其实施的时间分为两种方法：事前修剪法和事后修剪法。C4.5算法采用一种后剪枝方法。事后剪枝是由完全生长的树剪去分枝。通过删除结点的分枝，剪掉树结点。它在允许决策树得到最充分生长的根底上，再根据一定的规则，剪去决策树中的那些不具有一般代表性的叶结点或分枝。修剪后，被修剪的分枝结点就成为一个叶结点，并将其标记为它所包含样本中类别个数最多的类别。3.4 决策树算法比拟分析基于决策树算法自提出至今种类不下几十种。各种算法在执行速度、可扩展性、输出结果的可理解性，分类预测的准确性等方面各有千秋。最早提出的CLS算法只是给出了生成决策树系统的框架，却没有具体说明算法的容；ID3算法采用信息熵的增益进展属性选择，但只能处理具有离散型属性和属性值齐全的元组，生成形如多叉树的决策树。后来出现的C4.5算法经过改良，能够直接处理连续属性，也能够处理属性值空缺的训练元组，它采用信息增益率进展属性选择。由于ID3算法与C4.5算法生成决策树分支多，规模过于庞大，出现了根据GINI系数来选择测试属性的决策树算法，比方CART。对