《决策树算法研究 .doc》由会员分享，可在线阅读，更多相关《决策树算法研究 .doc（15页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、摘 要随着信息科技的高速发展，人们对于积累的海量数据量的处理工作也日益增重，需求是发明之母，数据挖掘技术就是为了顺应这种需求而发展起来的一种数据处理技术。数据挖掘技术又称数据库中的知识发现，是从一个大规模的数据库的数据中有效地、隐含的、以前未知的、有潜在使用价值的信息的过程。决策树算法是数据挖掘中重要的分类方法，基于决策树的各种算法在执行速度、可扩展性、输出结果的可理解性、分类预测的准确性等方面各有千秋，在各个领域广泛应用且已经有了许多成熟的系统，如语音识别、模式识别和专家系统等。本文着重研究和比较了几种典型的决策树算法，并对决策树算法的应用进行举例。关键词：数据挖掘；决策树；比较Abstra
2、ctWiththerapiddevelopmentofInformationTechnology,peoplearefacingmuchmoreworkloadindealingwiththeaccumulatedmassdata.Dataminingtechnologyisalsocalledtheknowledgediscoveryindatabase,datafromalargedatabaseofeffectively,implicit,previouslyunknownandpotentiallyusevalueofinformationprocess. Algorithm of d
3、ecision tree in data mining is an important method of classification based on decision tree algorithms, in execution speed, scalability, output result comprehensibility, classification accuracy, each has its own merits., extensive application in various fields and have many mature system, such as sp
4、eech recognition, pattern recognition and expert system and so on. This paper studies and compares several kinds of typical decision tree algorithm, and the algorithm of decision tree application examples.Keywords: Data mining; decision tree；Compare目录第一章 绪论第二章 文献综述2.1 数据挖掘简述2.2 决策树算法背景知识及研究现状2.2.1 决
5、策树算法描述2.2.2关联分析决策树算法研究现状第三章 决策树算法3.1 CLS算法3.2 ID3算法3.2.1 信息量大小的度量3.2.2 ID3决策树应用举例3.3 C4.5算法3.3.1 用信息增益率选择属性3.3.2 处理连续属性值3.3 树剪枝3.4 weka平台的简述第四章 决策树在学生成绩中的应用4.1数据的预处理4.2数据的训练集处理4.3数据的校验和成绩分析第五章 结论参 考 文 献I第一章 绪论无论在企业应用领域，还是在科学领域，数据挖掘技术有着广泛的应用价值。 在企业应用领域，用于制定好的市场策略以及企业的关键性决策。在商业面，数据挖掘技术可以增强企业的竞争优势，缩短销售
6、周期，降低生产成本，有助制定市场计划和销售策略，并已经成为电子商务中的关键技术。近年来，随着我国高等教育的飞速发展，高校的教学管理信息不断增多。教学工作信息化有了很大的进步，好多高校在管理学生和教师信息方面有了很好的方式。比如我校的教务系统，这些系统为老师和学生提供了很好的帮助。这些系统中积累了大量的数据。目前的这些数据库系统虽然基本上都可以实现数据的录入、修改、统计、查询等功能，但是这些数据所隐藏的价值并没有被充分的挖掘和利用，信息资源的浪费还是比较严重的。为了提高教学质量，将数据挖掘技术引入到高校学生成绩分析中，对这些数据进行深入的挖掘和合理的分析，从而挖掘出传统的分析方法所无法得出的结论
7、。进而利用分析结果引导教学的开展，从而有利于提高教学质量。第二章 文献综述数据挖掘作为一个新兴的多学科交叉应用领域，正在各行各业的决策支持活动扮演着越来越重要的角色。2.1 数据挖掘简述数据挖掘（英语：Data mining），又译为资料探勘、数据采矿。它是数据库知识发现（英语：Knowledge-Discovery in Databases，简称：KDD)中的一个步骤。数据挖掘一般是指从大量的数据中自动搜索隐藏于其中的有着特殊关系性（属于Association rule learning）的信息的过程。数据挖掘通常与计算机科学有关，并通过统计、在线分析处理、情报检索、机器学习、专家系统（依靠
8、过去的经验法则）和模式识别等诸多方法来实现上述目标。数据挖掘是通过分析每个数据，从大量数据中寻找其规律的技术，主要有数据准备、规律寻找和规律表示3个步骤。数据准备是从相关的数据源中选取所需的数据并整合成用于数据挖掘的数据集；规律寻找是用某种方法将数据集所含的规律找出来；规律表示是尽可能以用户可理解的方式（如可视化）将找出的规律表示出来。决策树是判定给定样本与某种属性相关联的决策过程的一种表示方法，从数据中生成分类器的一个特别有效的方法是生成一棵决策树，该方法广泛应用与数据挖掘和机器学习等领域，用来解释用分类相关的问题，决策树表示法是应用最广泛的逻辑方法之一。目前生成决策树方法的算法主要有三种：
9、CART算法、ID3算法和C4.5算法。其中C4.5算法具有分类速度快且精度高的特点，是发展比较完善的一种决策树算法。2.2 决策树算法背景知识及研究现状2.2.1 决策树算法描述决策树，顾名思义就是一个类似于流程图的树型结构。个决策树由根结点、分支和叶结点构成。树的最高层节点称为根结点，是整个决策树的开始。与根结点相连的不同分支，对应这个属性的不同取值，根据不同的回答转向相应的分支，在新到达的结点处做同样的分支判断，持续这一过程直到到达某个叶结点。在决策树中，每个内部结点表示一个测试，该结点的每个分支表示该测试的一个结果，每个叶结点表示一个类别。例如公司需要预测某位客人是否要买计算机，图2.
10、1就是为了解决这个问题而建立的一颗决策树,从中可以看到决策树的基本组成部分：根结点、分支和叶结点。年龄学生信誉买买不买不买买中青老否是优良图2.1 决策树2.2.2关联分析决策树算法研究现状 决策树算法广泛应用于各个领域，已经有了广泛的应用并且有许多成熟的系统，如语音识别、医疗诊断、模式识别和专家系统等。目前，决策树技术面临的挑战表现在以下几个方面：(1)可扩展性亟待提高。在大型数据集中，能从中快速而准确地发现隐藏于其中的主要分类规则，即认为算法具有良好的可扩展性。数据挖掘面临的数据往往是海量的，对实时性要求较高的决策场所，数据挖掘方法的主动性和快速性显得日益重要。 (2)适应多数据类型和容噪
11、性。随着计算机网络和信息的社会化，数据挖掘的对象已不单是关系数据库模型，而是分布、异构的多类型数据库，数据的非结构化程度、噪声等现象越来越突出，这也是决策树技术面临的困难问题。(3)决策树方法的递增性。数据挖掘出来的知识，只是相对于某一时间的某些数据，新的数据可能使发现的新知识与原来的知识冲突。因此，设计具有递增性决策树挖掘方法，也是实用化的基本要求之一。第三章 决策树算法3.1 CLS算法CLS算法是早期的决策树学习算法，是许多决策树学习算法的基础。CLS基本思想：从一棵空决策树开始，选择某一属性作为测试属性。该测试属性对应决策树中的决策结点。根据该属性的值的不同，可将训练样本分成相应的子集
12、，如果该子集为空，或该子集中的样本属于同一个类，则该子集为叶结点，否则该子集对应于决策树的内部结点，即测试结点，需要选择一个新的分类属性对该子集进行划分，直到所有的子集都为空或者属于同一类。例1：如表3.1所示为人员眼睛、头发颜色与所属人种之间的关系：人员眼睛颜色头发颜色所属人种1黑色黑色黄种人2蓝色金色白种人3灰色金色白种人4蓝色红色白种人5灰色红色白种人6黑色金色混血7灰色黑色混血8蓝色黑色混血根据表3.1所提供的信息，选择“眼睛颜色”为测试属性，可将该样本划分为相应的子集如图3.1所示。眼睛颜色1,62,4,83,5,7黑色蓝色灰色根据“眼睛颜色”所划分的子集中的样本不属于同一类，所以选
13、择新的测试属性“头发颜色”对各个子集进行划分，如图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，它们中有
14、且仅有一个发生，则其平均的信息量可如下度量：= ，在决策树分类中，假设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的值后导致的熵的期
15、望压缩。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) 计算决策属性的熵决策属性“买计算机？”，该
16、属性分为两类：买、不买。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=
17、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计算收入的熵：收入共分三个组：高、中、低
18、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：年龄买/不买买/不买买中青老在年龄属性为青年时，分别计算
19、收入信息增益、学生信息增益、信誉信息增益可知，在属性学生处信息增益值最大，因此取学生为分支属性；同理，当年龄属性为老年时，同样的计算可得分支属性为信誉。预测消费者是否会购买电脑的决策树分类构建完成，如图3.4所示：年龄学生信誉买买不买不买买中青老否是优良图3.4 谁在买计算机3.3 C4.5算法C4.5算法是ID3算法的改进，它继承了ID3算法的优点并对ID3算法进行了改进和补充。C4.5算法采用信息增益率作为选择分支属性的标准，克服了ID3算法中信息增益选择属性时偏向选择取值多的属性的不足，并能够完成对连续属性离散化的处理，还能够对不完整数据进行处理。3.3.1 用信息增益率选择属性信息增益
20、率等于信息增益与分裂信息的比值，定义如下：，上式中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.018Sp
21、litInfo2.999SplitInfo1.528GainRatio0.089GainRatio0.012学生信誉Gain0.173Gain0.045Splitinfo0.998SplitInfo0.929GainRatio0.173GainRatio0.048利用C4.5算法构建决策树中选取各属性中信息增益率最大的属性作为分裂点，以后的做法与ID3的相同，唯一的不同之处是判断标准由信息增益变成了信息增益率。3.3.2 处理连续属性值C4.5既可以处理离散型描述属性，也可以处理连续性描述属性。在选择某结点上的分枝属性时，对于离散型描述属性，C4.5的处理方法与ID3相同，按照该属性本身的取值
22、个数进行计算；对于某个连续性描述属性， C4.5将作以下处理：(1) 对属性的取值由小到大进行排序。(2) 两个属性取值之间的中点作为可能的分裂点，将该结点上的数据集分成两部分，计算每个可能的分裂点的信息增益。 (3) 计算每一种分割所对应的信息增益率，选择最大的分割点来划分数据集。3.3 树剪枝剪枝方法的主要目的是去掉那些噪声或异常数据，使决策树具有更泛化能力。剪枝常采用统计度量，剪掉最不可靠的分枝，从而带来较快的分类，提高树独立于测试数据进行正确分类的能力。剪枝按其实施的时间分为两种方法：事前修剪法和事后修剪法。C4.5算法采用一种后剪枝方法。事后剪枝是由完全生长的树剪去分枝。通过删除结点
23、的分枝，剪掉树结点。它在允许决策树得到最充分生长的基础上，再根据一定的规则，剪去决策树中的那些不具有一般代表性的叶结点或分枝。修剪后，被修剪的分枝结点就成为一个叶结点，并将其标记为它所包含样本中类别个数最多的类别。3.4 决策树算法比较分析基于决策树算法自提出至今种类不下几十种。各种算法在执行速度、可扩展性、输出结果的可理解性，分类预测的准确性等方面各有千秋。最早提出的CLS算法只是给出了生成决策树系统的框架，却没有具体说明算法的内容；ID3算法采用信息熵的增益进行属性选择，但只能处理具有离散型属性和属性值齐全的元组，生成形如多叉树的决策树。后来出现的C4.5算法经过改进，能够直接处理连续属性
24、，也能够处理属性值空缺的训练元组，它采用信息增益率进行属性选择。由于ID3算法与C4.5算法生成决策树分支多，规模过于庞大，出现了根据GINI系数来选择测试属性的决策树算法，比如CART。对这几种算法进行一个概要性的比较如表3.4所示。表3.4 典型决策树算法比较属性选择度量处理连续属性剪枝方法是否需要独立测试样本集决策树结构ID3信息增益离散化分类错误是多叉树C4.5信息增益率预排序分类错误否多叉树CARTGINI系数预排序MDL否二叉树第五章 结论本文重点讲了了ID3算法与C4.5算法及其应用举例，比较了几种典型决策树算法的优缺点。对于相当大的范围内的应用来说，决策树分类比其他分类技术能生
25、成更精确的分类结果，但是对决策树分类性能的度量和评价会困难些。即使在树分类器的每一等级上的分类效果是最优的，也不能保证最终的结果是最优的，虽然决策树算法使用最好的特征进行分类，但还是可能存在一些特征对分类很有用，却没有用到。如果能把这些特征选择出来，选择在每个子集上能够有效分类的特征，就能有效地减少树的层数，对于分类结果会有很大的提高。参 考 文 献1黄建军.田长春;把“数据挖掘”作用发挥出来 N;中国国防报;20092王浩;数据挖掘技术及应用 J;华东理工大学;20123张建同.邱玥;数据挖掘技术及其在电子商务中的应用 A;新世界;20104薛红强;浅析数据挖掘在学生体质健康测试中的应用 J
26、;西安航空学院学报;20145徐述;基于大数据的数据挖掘研究 J;科技视界;20146杜丽英;基于数据挖掘的决策树算法 J;吉林建筑工程学院学报;20147孙柏林;高珏;陈开;基于校园一卡通的学生体育锻炼数据挖掘的研究J;中国国防报;20108郭秀娟;数据挖掘方法综述 J;吉林建筑工程学院学报;20049张成叔;决策树分类算法在选课系统中应用研究J;新余学院;201410王全旺,赵兵川;数据挖掘技术在Moodle课程管理系统中的应用研究 J;电化教育研究;201111栾丽华,吉根林;决策树分类技术研究J;计算机工程;200412张儒良,王翰虎;论数据挖掘优化教学管理 J;贵州民族学院学报(哲学社会科学版);200413唐吉深;图书馆数据挖掘技术研究现状述评 J;图书馆界;201114李明江,唐颖,周力军;数据挖掘技术及应用J;中国新信;201215郑宏;数据挖掘可视化技术的研究与实现D;西安电子科技大学;2010