《决策树算法研究》由会员分享，可在线阅读，更多相关《决策树算法研究（15页珍藏版）》请在金锄头文库上搜索。
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的值后导致的熵的期望压缩。Gain(S，A)越大，说明选择测试属性A对分类提供的信息越多。ID3算法就是将每个节点选择信息增益Gain(S，A)最大的属性作为测试属性。3.2.2 ID3决策树应用举例例2：公司收集了数据如下表3.2所示，对于任意给定的客人，能否帮助公司将这位客人归类。表3.2 谁在买计算机计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买
