数据挖掘技术

数据挖掘技术 南华大学计算机科学与技术学院毕业设计(论文) 目 录 摘要 .................................................... iii Abstract ................................................. iv 第一章 绪论............................................... 1 1.1 数据挖掘技术 ................................................ 1 1.1.1 数据挖掘技术的应用背景................................. 1 1.1.2数据挖掘的定义及系统结构 ............................... 2 1.1.3 数据挖掘的方法......................................... 4 1.1.4 数据挖掘系统的发展..................................... 5 1.1.5 数据挖掘的应用与面临的挑战............................. 61.2 决策树分类算法及其研究现状 .................................. 8 1.3数据挖掘分类算法的研究意义.................................. 10 1.4本文的主要内容.............................................. 11 第二章 决策树分类算法相关知识 ........................... 12 2.1决策树方法介绍.............................................. 12 2.1.1决策树的结构 .......................................... 12 2.1.2决策树的基本原理 ...................................... 13 2.1.3决策树的剪枝 .......................................... 15 2.1.4决策树的特性 .......................................... 16 2.1.5决策树的适用问题 ...................................... 18 2.2 ID3分类算法基本原理........................................ 18 2.3其它常见决策树算法.......................................... 20 2.4决策树算法 总结 初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf 比较.......................................... 24 2.5实现平台简介................................................ 25 2.6本章小结.................................................... 29 第三章 ID3算法的具体分析 ................................ 30 3.1 ID3算法分析................................................ 30 3.1.1 ID3算法流程 .......................................... 30 3.1.2 ID3算法评价 .......................................... 33 3.2决策树模型的建立............................................ 34 3.2.1 决策树的生成.......................................... 34 3.2.2 分类规则的提取....................................... 377 3.2.3模型准确性评估 ....................................... 388 3.3 本章小结 ................................................... 39 i 南华大学计算机科学与技术学院毕业设计(论文) 第四章 实验结果分析 ..................................... 40 4.1 实验结果分析 ............................................... 40 4.1.1生成的决策树 .......................................... 40 4.1.2 分类规则的提取........................................ 40 4.2 本章小结 ................................................... 41 第五章 总结与展望 ....................................... 42 参考文献 ................................................. 44 致谢 ..................................................... 45 附录 ..................................................... 46 ii 南华大学计算机科学与技术学院毕业设计(论文) 摘要:信息高速发展的今天～面对海量数据的出现～如何有效利用海量的原始数据分析现状和预测未来～已经成为人类面临的一大挑战。由此～数据挖掘技术 应运而生并得到迅猛发展。 数据挖掘是信息技术自然演化的结果～是指从大量数据中抽取挖掘出来隐含未知的、有价值的模式或规律等知识的复杂过程。 本文主要介绍如何利用决策树方法对数据进行分类挖掘。文中详细的阐述了决策树的基本知识和相关算法～并对几种典型的决策树算法进行了分析比较～如:核心经典算法——ID3算法;能够处理不完整的数据、对连续属性的数据离散化处理以及克服了ID3算法偏向于选择取值较多的属性作为测试属性的缺点的C4.5算法;利用GINI系数判别数据集中的分裂属性并形成二叉树的CART算法;使数据的分类不受机器主存的限制～有着良好的伸缩和并行性的SLIQ和SPRNIT算法。ID3算法是最核心的技术～所以本文主要对它进行了研究和设计实现。 第四章在JAVA编译器上实现ID3算法～并对结果进行分析～决策树生成～分类规则的提取～以便于以后直接使用这一规则进行数据分析。在论文的最后一章介绍了目前数据挖掘技术的研究前景。 关键词:数据挖掘,决策树,ID3算法,信息增益,熵值 iii 南华大学计算机科学与技术学院毕业设计(论文) Abstract: Today, the massage is passed very quickly. How to investigate current status and forecast the future with good use of tremendous original Data has been becoming the big challenge to human beings when facing the emergence of mass Data in information era. Consequently, Data mining technology emerge and boom quickly. Data mining, is the product of the evolution of information technology, which is a complex process excacting the implicated and valuable pattens, knowledge and rules from a large scale of dataset. This paper mainly introduces the decision tree algorithm for classification. Firstly, the basic knowledge about decision tree and some representative algorithms for inducing decision tree are discussed, including ID3,which is classical;C4.5,which can deal with continuous attributes and some empty attribute ,at the same time, it can overcome the ID3’weakness which is apt to select some attribute with more value; CART, which uses GINI coefficient about attribute selection and induces a binary tree; SLIQ and SPRINT, which are scalable and can be easily parallelized, moreover they don’t have any limitation of main memory. Because ID3 algorithms which is classical, so in the paper I main introduce it. The firth chapter,ID3 algorithm is developed on the java platform by java， and carries on the analysis to the result, the decision tree production, the classified rule extraction, it will be advantageous for us to use this rule to carry on the data analysis directly in the future. I introduce data mining technology research prospect in the paper last chapter. Key words: Data mining; Decision tree; ID3 algorithm ;Information gain; Entropy value iv 南华大学计算机科学与技术学院毕业设计(论文) 第一章 绪论 1.1 数据挖掘技术 1.1.1 数据挖掘技术的应用背景 最近几十年以来，随着互联网的发展和企业信息化程度的日益提高，科研政府部门普遍使用电子事物处理技术，商品条形码被广泛使用，以及电子商务和科学数据库的急剧增长为我们带来了海量的数据。激增的数据背后隐藏着许多重要的信息，人们希望能够对其进行更高层次的分析，以便更好地利用这些数据。而目前的数据库系统可以高效地实现数据的录入、查询、统计等功能，但无法发现数据中存在的关系和规则，无法根据现有的数据预测未来的发展趋势，缺乏挖掘数据背后隐藏的知识的手段，从而导致了“数据爆炸但知识贫乏”的现象。 大量信息在给人们带来方便的同时也带来了一大堆问题:第一是信息过量，难以消化;第二是信息真假难以辨识;第三是信息安全难以保证;第四是信息形式不一致，难以统一处理。人们开始考虑:“如何才能不被信息淹没，而是从中及时发现有用的知识、提高信息利用率,”这就引 发 了 一 门 新 兴 的 自 动 [1]信 息 提 取 技 术 : 数 据 中 的 知 识 发 现 ， 简 称KDD (Knowledge Discovery in Data Base)。其内容主要涉及人工智能领域中的机器学习，模式识别、统计学、智能数据库、知识获取、专家系统、数据库可视化、数据库领域的数据仓库联机分析处理(OLAP)，多维数据库等方面。KDD 已经是解决目前信息系统中普遍面临的“数据爆炸”而“信息缺乏”状况的最有效的手段之一，并且它的研究领域具有较大的研究意义和较多的研究方向一度成为数据库研究界最热的研究方向，拥有人数众多的研究群体，受到学术界和企业界的极大关注。多学科的相互交融和相互促进，使得这一学科得以蓬勃发展，而且已初具规模。并行计算、计算机网络和信息工程等其他领域的国际学会、学刊也把数据挖掘和知识发现列为专题和专刊讨论，甚至到了脍炙人口的程度。数据挖掘是目前研究的热点，它可以说是数据库研究中的一个非常有应用价值的新领域，它融合了数据库、人工智能、机器学习、数理统计学、模糊数学等多个领域的理论和技术。 第 1 页 ,共 52页 南华大学计算机科学与技术学院毕业设计(论文) [2]数据挖掘 DM (Data Mining)是 KDD 的一个最关键步骤，因此实际应用中把 DM 和 KDD 不作区分。数据挖掘是目前研究的热点，它可以说是数据库研究中的一个非常有应用价值的新领域，它融合了数据库、人工智能、机器学习、数理统计学、模糊数学等多个领域的理论和技术。从数据分析的观点来看，数据挖掘分为两类:描述性数据挖掘和预测性数据挖掘。描述性数据挖掘以概要方式描述数据，提供数据所具有的一般性质;预测性数据挖掘分析数据，建立一个或一组模型，产生关于数据的预测。包括分类和回归。分类可用于提取描述重要数据的模型或预测未来的数据趋势。1995 年，在美国计算机年会(ACM)上，提出了数据挖掘的概念。即通过从数据库中抽取隐含的，未知的，具有潜在使用价值信息的过程。数据挖掘应用的普遍性及带来的巨大的经济和社会效益，吸引了许多专家和研究机构从事该领域的研究，许多公司推出了自己的数据库挖掘系统。从 1989 年举行的第十一届国际联合人工智能学术会议上 KDD被提出，到现在不过十多年的时间，但在 Gartner Group 的一次高级技术调查中将数据挖掘和人工智能列为“未来 5 年内将对工业产生深远影响的五大关键技术”之首，并且还将数据挖掘列为未来五年内十大新兴技术投资焦点的第二位。根据最近 Gartner 的 HPC 研究表明，“随着数据捕获、传输和存储技术的快速发展，大型系统用户将更多地需要采用新技术来挖掘市场以外的价值，采用更为广阔的并行处理系统来创建新的商业增长点。” 1.1.2数据挖掘的定义及系统结构 数据挖掘也称为数据库中的知识发现KDD(Knowledge Discovery in Data Base)。指的是从存放在数据库、数据仓库或其他信息库中的大量数据中挖掘出人们感兴趣的知识，这些知识是隐含的、事先未知的潜在有用信息。目的是帮助决策者寻找数据间潜在的关联，发现被忽略的要素，而这些信息对预测趋势和决策行为也许是十分有用的。数据挖掘技术能从DW中自动分析数据，进行归纳性推理，从中发掘出潜在的模式，或产生联想，建立新的业务模型，这是一个高级的处理过程。高级的处理过程是指一个多步骤的处理过程，多步骤之间相互影响、反复调整，形成一种螺旋式上升过程。这个过程与人类问题求解的过程是存在巨大相似性的。决策树分类算法的研究与改进挖掘过程可能需要多次的循环反复，每一个步骤一旦与预期目标不符，都要回到前面的步骤，重新调整，重新执 第 2 页 ,共 52页 南华大学计算机科学与技术学院毕业设计(论文) 行。 从广义角度讲数据、信息是知识的表现形式，但在数据挖掘中更多把概念、规则、模式、规律和约束等看作知识。原始数据可以是结构化的，如关系型数据库中的数据，也可以是半结构化的，如文本、图形、图像数据、甚至是分布在网络上的异构型数据。发现知识的方法可以是数学的或非数学的、演绎的或归纳的。发现的知识可以被用于信息管理、查询优化、决策支持、过程控制等。总之，数据挖掘是一门广义的交叉学科，它的发展和应用涉及到不同的领域尤其是数据库、人工智能、数理统计、可视化、并行计算等。因此，概括起来从广义上来说，数据挖掘是从大型数据集(可能是不完全的，有噪声的，不确定的，各种存储形 [3]式的)中，挖掘隐含在其中的，人们事先不知道的，对决策有用的知识的过程。从狭义上来说，数据挖掘是从特定形式的数据集中提炼知识的过程。 数据挖掘的系统结构可以用以下的图来说明: 图1.1 数据挖掘系统结构图 ?数据库、数据仓库或其他信息库:这是一个或一组数据库、数据仓库、电子表格或其他类型的信息库。可以在数据上进行数据清理和集成。 ?数据库或数据仓库服务器:根据用户的数据挖掘请求负责提取相关数据。 ?知识库:这是领域知识，用于指导、搜索或评估结果模式的兴趣度。 ?数据挖掘引擎:这是数据挖掘系统的基本部分。由一组功能模块组成，用 第 3 页 ,共 52页 南华大学计算机科学与技术学院毕业设计(论文) 于特征化、关联、分类、聚类分析以及演变和偏差分析。 ?模式评估模块:通常，此模块使用兴趣度度量，并与数据挖掘模块交互，以便将搜索聚焦在有趣的模式上。 ?图形用户界面:本模块在用户和数据挖掘系统之间通信，允许用户与系统交互，指定数据挖掘查询或任务，提供信息，帮助搜索聚焦，根据数据挖掘的中间结果进行探索式数据挖掘。此外，此模块还允许用户浏览数据库和数据仓库模式或数据结构，评估挖掘的模式，以不同的形式对模式可视化。 1.1.3 数据挖掘的方法 数据挖掘的功能用于指定数据挖掘任务中要找的模式类型，其任务一般可分为两类:描述和预测。描述性挖掘任务刻画数据库中数据的一般特性，预测性挖掘任务在当前数据上进行推断，以进行预测。在实际应用中，往往根据模式的 [4]实际应用细分为以下 6 种: 1.分类模式 2.回归模式 3.时间序列模式 4.聚类模式 5.关联模式 6.序列模式 本文主要介绍分类算法，所以下面主要介绍分类分析方法，分类分析要分析数据库中的一组对象，找出其共同属性，构造分类模型，然后利用分类模型对其它的数据对象进行分类。要构造分类模型，需要一个训练样本数据集作为输入，训练集由一组数据库记录或元组组成，每个元组包含一些字段值，又称“属性”或“特征”，这些字段和测试集中记录的字段相同，另外，每个训练样本记录有一个类别标识。分类目标是分析训练集中的数据，利用数据中能得到的特征，为每一类建立一个恰当的描述或模型，然后根据这些分类描述对测试数据进行分类或产生更恰当的描述。我们可以举一个简单的例子，信用卡公司的数据库中保存着各持卡人的记录，公司根据信誉程度将持卡人记录分成三类:良好、一般、较差，并且类别标记己赋给了各个记录。分类分析就是分析该数据库的记录数据，对每个信誉等级做出准确描述，如“信誉良好的客户是指那些年收入在5万元以 第 4 页 ,共 52页 南华大学计算机科学与技术学院毕业设计(论文) 上，年龄在40-50岁之间的人士”，然后根据这些描述对其它具有相同属性的数据库记录进行分类。 在分类分析中，分类模型的构造方法有统计方法、神经网络方法及机器学习方法等。统计方法包括贝叶斯法和非参数法(近邻学习或基于事例的学习)，对应的知识表示为判别函数和原型事例。神经网络方法主要是多层前向神经网络的误差反向传播(error back propagation，BP)算法，用模型表示是前向反馈神经网络模型，该算法实质是一种非线性的判别函数。机器学习方法包括决策树法和规则归纳法，前者对应的表示是决策树或判别树，后者则一般为产生式规则。另外， ough set)新的理论方法，它将知识表示为产近年来又出现了一种称为粗糙集(R 生式规则。 在解决实际问题时，经常要同时使用多种模式。分类模式和回归模式是使用最普遍的模式。分类模式、回归模式、时间序列模式也被认为是受监督知识，因为在建立模式前数据的结果是已知的，可以直接用来检测模式的准确性，模式的产生是在受监督的情况下进行的。一般在建立这些模式时，使用一部分数据作为样本，用另一部分数据来检验、校正模式。 1.1.4 数据挖掘系统的发展 根据 R.Grossman 的观点，数据挖掘的发展过程可分为如下所介绍的一到四[5]代: 第一代:第一代的数据挖掘系统仅支持一个或少数几个数据挖掘算法，这些算法只能够挖掘向量数据。如果数据足够大，并且频繁的变化，这就需要利用数据库或者数据仓库技术进行管理，第一代系统显然不能满足需求。 第二代:第二代系统的主要特点是支持与数据库和数据仓库的高性能接口，并有高的可测量性和功能性。第二代系统提供了数据挖掘模式和数据挖掘查询语言，从而具有更高的灵活性。然而第二代系统只注重模型的生成，如何和预言模型系统集成的问题导致了第三代数据挖掘系统的开发。 第三代:第三代数据挖掘系统可挖掘 intranets和 extranets上的分布的和高度异质的数据，并能有效的和操作系统结合。这一代数据挖掘系统的关键技术之一是提高对建立在异质系统上的多个预言模型以及管理这些预言模型的元数据提供第一级别的支持。 第 5 页 ,共 52页 南华大学计算机科学与技术学院毕业设计(论文) 第四代:第四代数据挖掘系统可以挖掘嵌入式、移动式以及一般性的计算设备所产生的各种数据。 1.1.5 数据挖掘的应用与面临的挑战 尽管数据挖掘是一个新兴的研究领域，但是却得到了稳定的发展，每年市场上都会出现新的数据挖掘系统，各大数据库软件公司也分别推出了自己的数据挖掘产品。数据挖掘广泛应用于科学研究、商业应用、以及Web挖掘等很多领域。 (1)科学研究 数据挖掘在天文学上有一个著名的应用系统:SKICAT[27](Sky Image Cataloging and Analysis Tool)。它是加州理工学院喷气推进实验室与天文学家合作开发的用于帮助天文学家发现遥远的类星体的一个工具。SKICAT的任务是构造星体分类器对星体进行分类，使用了决策树方法构造分类器，结果使得能分辨的星体较以前的方法在亮度上要低一个数量级之多，而且新的方法比以往的方法要在效率上要高40倍以上。数据挖掘在生物学上的应用主要集中于分子生物学特别是基因工程的研究上。进几年，通过用计算生物分子系统分析法，尤其是基因数据库搜索技术以在基因研究上做出了很多重大发现，数据挖掘在分子生物学上的工作可分为两种:一是从各种生物体的DNA序列中定位出具有某种功能的基因串;二是在基因数据库中搜索与某种具有高阶结构(不是简单的线形结构)或功能的蛋白质相似的高阶结构序列。 (2)商业应用 数据挖掘技术以及应用此技术所获得知识和信息可以被广泛的应用于信息管理、商务管理、过程控制、市场分析、工程设计和科学研究等众多领域，这些领域的管理决策层可以通过对历史数据的分析，发现诸如市场供需规律、商品价格走势、家庭收入与消费特点、购买商品的习惯等规律，以支持企业的生产、经营和销售决策。 (3)web挖掘(Web Mining) 随着网络的迅速发展，今天它己经成为人们交流思想，获取信息的便利手段。但这些信息缺乏结构化、组织的规律性、随意的散布在网络的各个角落，这已经成为这座世界性图书馆的一大缺憾。数据挖掘在因特网上的应用主要包括三种:在搜索引擎上(Search Engine)对文档进行自动分类、帮助用户寻找感兴趣的新 第 6 页 ,共 52页 南华大学计算机科学与技术学院毕业设计(论文) 闻以及利用数据挖掘设计一个电子新闻过滤系统。它利用文本学习建立起该用户的趣向模型，当用户进入一份电子报纸的网页时，该系统就会根据学习所得的模型对其中的每一篇文章按与用户的兴趣的接近程度进行打分排序，以便使用户看到他最感兴趣的新闻。 这些实践将数据挖掘和各特定领域知识结合起来，满足了特定任务的需要，也取得了一些很大的成绩。数据挖掘任务和方法的多样性给数据挖掘提出了许多挑战性的课题。在未来的课题研究中，数据挖掘研究人员、系统和应用开发人员 [6]所面临的主要问题有: (1)挖掘算法的效率和可扩展性 目前，GB数量级的数据库已经不鲜见，TB数量级的数据库也开始出现。海量数据库中存有成百个属性和表，成百万个元组，问题的维数很大，这不但增大了知识发现算法的搜索空间，也增加了盲目发现的可能性。因此，必须通过增加知识发现过程中系统和用户的交互，既充分利用领域知识除去无关数据，降低问题维数，对待挖掘数据进行有效的预处理，又要利用领域知识进一步精练所发现的模式，滤除因搜索空间过大可能获得的无用信息，从而设计出更理想的知识发现算法。 (2)待挖掘数据的时序性 在应用领域的数据库中，数据大多是随时间变化的，这可能使得原先发现的知识失去效用，也为开发强有力的知识发现系统提供了潜在的舞台，因为重新训练一个系统毕竟要比重新训练一个人(改变他的思维、观点等)容易得多。我们可以来用随时间逐步修正所发现的模式来指导新的发现过程。互联网络上的知识发现正日益普及，在这信息的海洋中可以发现大量的新知识。己有一些资源发现工具可用来发现含有关键字的文本。目前的问题是，如何从复杂的数据例如多媒体结构化的数据中提取有用的信息，对多层次数据库的维护，以及如何处理数据的异类性和自主性等等。 (3)和其它系统的集成 一个方法、功能单一的发现系统，其适用范围必然受到限制。要在更广阔的领域发现知识，知识发现系统就应该是数据库、知识库、专家系统、决策支持系统、可观化工具、网络等多项技术集成的系统。 第 7 页 ,共 52页 南华大学计算机科学与技术学院毕业设计(论文) (4)遗漏的噪声数掘 这个问题在商业数据库中尤其突出，据报告，美国人口调查数据的错误率上升到20%。如果不经认真考虑就来设计待挖掘数据库，重要的属性可能会被遗漏掉。用更复杂的统计策略识别隐藏的变量和相关性成为必然。 (5)挖掘结果的可理解性 这是评估挖掘系统的一个重要环节。我们应该尽可能采用图形表示、有向非循环图结构的规则、自然语言生成以及数据和知识的可视化等技术，提高挖掘结果的可理解性。 (6)私有数据的保护与数据安全性 当我们可以在不同的角度和不同的层次看到数据库中的数据时，这与我们保护数据的安全性和保护私人数据的目标相抵触。因此对在什么情况下数据挖掘将会导致对私有数据造成侵犯和采用何种措施来防止敏感信息泄露的研究变得非常重要。 1.2 决策树分类算法及其研究现状 分类技术是数据挖掘的重要分支，它能够对各个行业提供良好的决策支持，对整个社会的发展产生重要而深远的影响。数据挖掘的分类模式是一种有指导性的学习，即是以实例为基础的归纳学习算法，通过分析由属性描述的训练数据集来构造模型由此来预测新元组的分类标记。数据分类存在很多方法，如判定树归纳、贝叶斯分类、神经网络以及 K-最临近分类、遗传算法和粗糙集等。其中决策树归纳以其易于提取显式规则、计算量相对较小、可以显示重要的决策属性和较高的分类准确率等优点而得到广泛的应用。据统计，目前决策树算法是利用最广泛的数据挖掘算法之一，利用率高达 19%。应用领域已由医疗到博弈论和商务等领域，是一些商业规则归纳系统的基础。在计算机科学中采用树形结构描述数据集已有不短的时间了，但它一直是一个不受重视的知识发现过程。随着数据挖掘技术的产生，决策树得到了很快的发展。 决策树的算法己有很多。1986 年 J.Ross Quinlan 引入了 ID3 算法后，引 [7]起了很大的反响。在此基础上，他又于 1993 年，在其“Program For Machine Learning”一书中，对 ID3 算法进行了补充和改进，提出了后来非常流行的 C4.5算法。在大数据量情况下的效率和生成规则的数量与正确性方面有了显著的提 第 8 页 ,共 52页 南华大学计算机科学与技术学院毕业设计(论文) 高。此外，CHAID 算法也有相当广泛的应用。1996 年又提出了 SLIQ和SPRINT算法,RAINFOREST 框架结构，它们强调算法的可伸缩性。由于数据挖掘的对象是规模庞大的数据，已有的分类算法在数据量小时能够准确、高效的分类，效果很好。但当用于处理大量数据时，已有的算法都会不同程度的出现各种问题，分类效果不理想。因此，研究数据挖掘中准确、有效的分类算法，虽然是一个传统的问题，但仍具有挑战性。目前，在知识发现和数据挖掘的研究和开发中已经取得了一些令人瞩目的成绩，对关联规则、聚类等基本算法的研究已经基本日趋成熟， 人们的研究重点逐渐转移到数据挖掘技术在新的数据类型、应用环境中使用时所出现的新问题的解决上。例如: 1(决策树技术和神经网络技术相结合。决策树也具有产生n 维空间下任意复杂的决策边界的功能。因此, 可以将决策树重新构造成一个多层的神经网络。这类方法解决了由神经网络得到的知识难于被人们理解的缺点。 2(决策树技术和模糊集合原理的结合。决策树技术虽然有许多优点,但也存在着不稳定的缺点,即决策树带来了较大的变动。模糊集合的融通性使人们利用模糊逻辑来解决决策树的这一缺点并取得了不错的效果。 3(决策树技术和进化算法,遗传算法及遗传编程的结合。基于进化算法的决策树系统具有较好的抗噪声能力, 同时进化算法很容易在并行计算机上运行, 因此可以期待基于进化算法的决策树的运算能力有较大的提高。 4(决策树技术和多智能体的结合。多智能体系统的复杂性，而机器学习有潜力提供一个鲁棒性较强的机制来有效协调各智能体间的行为，因此对多智能体结合机器学习是一个很有前途的方向。 5(寻找新的构造决策树的方法。自从Quinlan提出ID3 和C4.5方法后，有不少专家提出了其他构造决策树的方法，M. Amherst 等提出了基于多维可视化下的交互式的决策树构造，此方法在决策树构造阶段加入了专家知识，这样便于用户更深地理解产生决策树的数据及最终产生的决策树，同时也显著地减小了决策树的大小。 6(寻找更好的简化决策树的方法。寻找更好的简化决策树的方法, 这一直是决策树技术研究的一个热点。D. Fournier 等提出的一种新的修剪决策树的方法2DI 修剪法。此方法针对数据不确定的情况, 利用特性索(Quality Index) 来 第 9 页 ,共 52页 南华大学计算机科学与技术学院毕业设计(论文) 权衡处理决策树深度和节点杂质。2DI修剪法将保持那些虽不能减小错误率但能指出一些特殊性质的群体的子树。 7(研究产生决策树的训练和检验数据的大小及特性与决策树特性之间的关系。实际上, 这就是经常提起的数据预处理技术(Data reprocessing) ,与决策 [7]树修剪技术(Pruning) 相对应, 也称它为数据减少技术(Data Reduction Techniques) 。 8(决策树技术的软件实现。将决策树技术软件化一直是决策树技术的方向之一。目前市场上的大多数据挖掘软件如SAS 等都包含有决策树技术部分。 以上这些决策树的研究并不是孤立的, 它们经常相互联系、相互结合。决策树技术早已被证明是利用计算机模仿人类决策的有效方法。由于20 世纪末人工智能陷于低潮, 此技术曾不被重视。值得庆幸的是, 由于数据挖掘技术的兴起, 作为模仿人类决策主要方法之一, 近年来决策树又重新引起了人们的兴趣, 并得到更广泛的应用。将决策树技术与其他新兴的技术相结合,决策树技术将焕发出新的生命力。 1.3数据挖掘分类算法的研究意义 目前分类挖掘在实际应用中有着很重要的应用价值，在很多行业领域都取得一定的成功。比如:在股票市场上对每只股票的历史数据进行分析，通过相应的技术进行预测，从而做出相对比较准确的判断;彩票的购买也可以利用数据挖掘的分类或预测技术进行分析;在金融领域中将贷款对象分为低贷款风险与高贷款风险两类。通过决策树，我们可以很容易地确定贷款申请者是属于高风险的还是低风险的。对于一个计算机销售的系统，原有的数据库信息已定，假定新的顾客添加到数据库中，你想将新计算机的销售信息通知顾客。将促销材料分发给数据库所有的顾客的费用可能很高，这时你就可以通过建立分类模型，把资料只寄给那些可能购买新计算机的用户，从而节省时间和费用，为你带来更大的经济效益。由于决策树方法在分类挖掘技术中有着独特的优势，而分类技术的应用对整个市场的控制、公司的运营和个人的投资都有着很好的控制作用。数据挖掘是一种决策支持过程，是深层次的数据信息分析方法，将数据挖掘技术应用于成绩评估方面是非常有益的，它可以全面地分析考试成绩与各种因素之间隐藏的内在联系，比如，经过对学生相关数据进行分析，数据挖掘工具可以回答诸如“哪些因素对 第 10 页 ,共 52页 南华大学计算机科学与技术学院毕业设计(论文) 学生成绩可能有影响”等类似的问题，这是传统评价方法无法具备的。因此对基于决策树的分类算法的研究有着多层次的研究价值和很高的应用价值。 1.4本文的主要内容 第一章首先阐述了论文课题的研究背景、国内外在数据挖掘领域的研究现状以及论文的组织结构。 第二章是本文的重点之一，详细的阐述了决策树分类模型的基本原理、工作的过程，并讲述了它的核心算法——ID3算法的基本思想。在本章的最后介绍了ID3算法演变和改进来的其他几种算法，并对它们进行了比较，做出概况性描述。 第三章也是本文的研究重点之一，因为ID3算法是经典的数据处理算法，本文主要研究ID3算法，给出了ID3算法的详细描述和它的评价。分析用ID3实现的决策树，以及分类规则的提取。 第四章，用程序实现ID3算法、对它的结果进行分析，实验结果证明，ID3算法是一种经典的数据处理算法，运用它能够解决生活中很多数据问题。 第五章对全文进行总结，提出了进一步的研究方向。ID3算法还有一定的需要改进的地方，在以后的研究中将进行进一步的改进。 第 11 页 ,共 52页 南华大学计算机科学与技术学院毕业设计(论文) 第二章 决策树分类算法相关知识 决策树方法是目前应用最广泛的归纳推理算法之一，是一种逼近离散值的方法，也可以把它看作是一个布尔函数。它是以实例为基础的归纳学习，通常用来形成分类器和预测模型，着眼于从一组无次序、无规则的事例理出决策树表示形成的分类规则。到目前为止决策树有很多实现算法。 2.1决策树方法介绍 [8]在解决分类问题的各种方法中，决策树 (Decision Tree，DT)是比较常用的一种方法，它是一种用于分类、聚类和预测的预测型建模方法，采用“分而治之”的方法将问题的搜索空间分为若干子集。应用这种方法需要构建一棵树对分类过程进行建模。一旦建好了树，就可以将其应用于数据集中的元组并得到分类结果。在决策树方法中，有两个基本步骤:构建树和将树应用于数据集，一般都集中在如何有效的构建树的研究上。 2.1.1决策树的结构 一棵决策树是这样一棵树，该树的每个非终端点均表示被考察数据项目的一个测试或决策。根据测试结果，选择某个分支。为了分类一个特定数据项目，我们从根结点开始，一直向下判定，直到到达一个终端结点(或叶子)为止。当到达一个终端结点时，一个决策树便形成了。 [9]决策树是运用于分类的一种类似于流程图的树结构。其中的每个内部节点(internal node)代表对某个属性的一次测试，一条边代表一个测试结果，叶子(leaf)代表某个类(class)或者类的分布(class distribution)。最上面的节点是根结点。下图 给出一个商业上运用决策树算法得到的一棵决策树，如图2.1所示: 第 12 页 ,共 52页 南华大学计算机科学与技术学院毕业设计(论文) 图2.1 Decision Tree demo 这棵决策树对“买计算机’，的销售记录进行分类。它表示了一个关心电子产品的用户是否会购买PC机的知识，用它可以预测某条记录(某个人)的购买意向。每个内部节点(方形框)代表对某个属性的一次检测。每片叶子(椭圆框)代表一个类(buys-computers=yes或者buys--computers=no)。这个例子中，样本向量如下:(age，student，credit--rating: buys-computers)，被决策数据的格式为(age，student，credit--rating)。输入新的被决策的记录，可以预测该记录隶属于哪个类。 2.1.2决策树的基本原理 决策树的实现是以信息论原理为基础的。信息论是香农(C.E.Shannon)在1948年建立的解决信息传递的不确定性的一系列理论，以数学的方法度量并研究信息。通过通信后对信源中各种符号出现的不确定程度的消除来度量信息量的大小，在这些理论中他提出了一系列概念: (1)自信息量。设X，X，„，X，为信源发出的信号，在收到Xi之前，12n 收信者对信源发出信号的不确定性定义为信息符号的自信息量I(Xi)，即 (2.1) 其中P(Xi)表示信源发出Xi的概率。 (2)信息熵。自信息量只能反映符号的不确定性，而信息熵可以用来度量整个信源X整体的不确定性，定义如下: (2.2) 其中i为信源X所有可能的符号数，即用信源每发一个符号所提供的平均自信息 第 13 页 ,共 52页 南华大学计算机科学与技术学院毕业设计(论文) 量来定义信息熵(平均信息量)。 (3)条件熵。如果信源X与随机变量Y不是相互独立的，收信者收到信息Y，那么用条件熵H(X/Y)来度量收信者在收到随机变量Y之后，对随机变量x仍然存在的不确定性。设X对应信源符号Xi，Y对应信源符号Yj，P(Xi/Yj)为当Y为Yj时,X为Xi的概率，则有: (2.3) (4)平均互信息量。用它来表示信号Y所能提供的关于X的信息量的大小，可用下式表示: I(X，Y)=H(X)-H(X/Y) (2.4) 在信息论中是用熵 (系统信息量的加权平均)(Entropy)来度量信息的不确定性。不确定性是一组消息的描述如M={m，m，„m}。所有消息的产生是相互12n 独立的，消息集合中每个消息m被接受的概率为P(m)，它包含着一定的信息量，ii 定义为I(m)=-?( m)。例如:某个信息源总是发送同样的信息，那么接收者就不2ii 需要更多的信息，此时信息源的熵就为0，也就是没有任何不确定性。相反，如果某个信息发送了n个不同的信息并且每个信息是相互独立的，此时熵的值就是 n?(熵是以二进制位的个数来编码长度的，故用以2为底的对数，后面描述的2 对数都是以2为底)。熵用在决策树中是作为训练集纯度的 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 。在决策树形成过程中，最重要的部分是对分裂属性的选择。 [10]比较常用的一种方法是计算信息增益 (Information Gain)。信息增益的原理来自信息论，它是使某个属性用来分割训练集而导致的期望熵降低。因此，信息增益越大的属性分裂数据集的可能性越大。决策树的形成就是递归的对数据集中的每个节点进行分裂，直到节点的所有类别都属于同一类或没有多余的属性来划分训练样本集。 按照信息论的定义，设S是s个数据样本的集合，类标号属性有n类样本的训练数据集，每类有Si个实例，则把它们分类所需要的信息量I用如下公式2.5表示为: (2.5) 第 14 页 ,共 52页 南华大学计算机科学与技术学院毕业设计(论文) Pi是任意样本属于类C的概率，用S/S估计。 ii 设属性A具有v个不同的值{ a aa }。可以用属性A将S划分为v个子。。。1,2,v 集{S SS }:其中，Sj包含S中这样的一些样本，它们在A上具有值a。假设。。。1,2,vj选取A作为本次分类的属性，则这些子集对应于由包含集合S的节点生长出来的分枝。设s是子集Sj中类C的样本数。根据由A划分成子集的熵(entropy)由iji 公式得出: (2.6) 其中项为第j个子集的权值，并等于子集(即A为a)中的j样本个数除以S中的样本总数。由信息论定义知:熵值越小，子集划分的纯度越高。因此对应给定的子集S有: j (2.7) 其中:是S中的样本属于C的概率。 ji 在A上的分支将获得的编码信息即节点的信息增益为: (2.8) 也就是说，Gain(A)是由于知道属性A的值而导致的熵的期望压缩。为了使下一步所需的信息量最小，要求每一次都选择其信息增益最大的属性作为决策树的新结点，并对属性的每个值创建分枝，依据此思想划分训练数据样本集。 2.1.3决策树的剪枝 当决策树创建时，由于数据中的噪声和孤立点，许多分支反映的是训练数据 [11]中的异常。剪枝方法处理这种过分适应数据问题。通常使用统计度量，剪去最不可靠的分支，这将导致较快的分类，提高树独立于测试数据正确分类的能力。主要有两类剪枝方法: 1(同步修剪 (pre-pruning): 在建树的过程中，当满足一定条件，例如Information Gain或者某些有效 第 15 页 ,共 52页 南华大学计算机科学与技术学院毕业设计(论文) 统计量达到某个预先设定的阈值时，节点不再继续分裂，内部节点成为一个叶子节点。叶子节点取子集中频率最大的类作为自己的标识，或者可能仅仅存储这些实例的概率分布函数。然而，选取一个适当的阈值是困难的，因为较高的阈值可能导致过分简化的数，而较低的阈值可能使得树的化简太少。 2(迟滞修剪(pos-pruning): 与建树时的训练集独立的训练数据进入决策树并到达叶节点时，训练数据的class label与叶子节点的class label不同，这时称为发生了分类错误。当树建好之后，对每个内部节点，算法通过每个枝条的出错率进行加权平均，计算如果不剪枝该节点的错误率。如果裁减能够降低错误率，那么该节点的所有儿子就被剪掉，而该节点成为一片叶子。出错率用与训练集数据独立的测试数据校验。最终形成一棵错误率尽可能小的决策树。在实际应用中可以交叉使用同步修剪和迟滞修剪，形成组合式方法。迟滞修剪所需的计算比同步修剪多，但通常产生更可靠的树。 2.1.4决策树的特性 决策树有很多的优点，是实际应用和学术研究领域最普遍采用的方法之一。主要特点有: 1(灵活性 决策树不需要对数据的分布进行任何假设，它是非参数方法。事例空间被分成子空间，每一个子空间适用于不同的模型。一棵决策树能完全包含一个事例空间，如果有足够的数据，它能近似任意函数的最优贝叶斯错误率。 [12]2(健壮性 对单变量经过单调转换后的输入，单变量树的输出是不变的。例如，对x， xlog或者作为第j个输入变量，会产生同样结构的树。因此没有必要考虑输入变2, 量的转换式。另外由于对内部属性进行了选择，相对于有不相关输入变量的情况，而产生的树更加具有健壮性。 3(可解释性 全面的和复杂的决策可以通过一系列简单和局部的决策近似取得。所有的决策都是用来描述该问题的属性值上的。决策树具有这两个特性，具有可理解性和可解释性，它们是决策树被广泛使用的原因。 第 16 页 ,共 52页 南华大学计算机科学与技术学院毕业设计(论文) 4(速度 决策树算法采用自上而下，分而治之，不需要回溯战略的一种贪婪算法。时间复杂是与例子的数目成线性关系的。 同样，决策树也面对一些问题: 1(分块 分块使得数据被分成较小的子集。假定每次分枝数据都分成相等大小的数目，那决策树所要测试的属性的复杂度不大于O(logn)。在有许多相关属性的情形下，这是理想的结果。 2(复制 子树的复制指的是在不同的分枝复制相同的属性测试。由于属性间存在相关性项性(一个结果可由多个条件决定)，例如，布尔函数f=XX+XX中属性X12341和X或者属性X属性X间不是相互独立的，而是存在相关性;另外该布尔函数，234 有多个乘积项XX和XX。出现这种情况时，生成的决策树会有子树复制问题。1234 复制现象导致决策树理解，同时还导致分块问题:当树很大时，会造成数据集的划分越来越小，从而性能越差。 3(缺值 决策树是一种层次测试方法，如果某个属性值未知的话，就会难以决定下一步分枝，因此必须使用特殊的机制来处理缺值的问题。 4(连续属性 决策树算法的瓶颈是对连续属性的处理。在这种情况下，要在每一个节点对每一个属性进行一系列的操作。有学者认为处理许多的连续属性的操作占决策树构造过程70%的时间。 5(不稳定性 训练集的小的变化能引起最终的树发生很大的变化。在每一个节点，分枝度量准则对属性进行排列并选择最好的属性进行排序。如果有两个以上的属性具有相同的排序值，则训练集数据的小的变化就能改变排序，该节点下面的子树就会发生变化。这种递归的分枝战略表明对于每个产生的分枝，数据集基于测试属性被分割，在进行了一些分割后，通常就只有非常少的数据进行决策，因此靠近叶节点做出的决策就没有在根节点附近做出的决策可靠。 第 17 页 ,共 52页 南华大学计算机科学与技术学院毕业设计(论文) 2.1.5决策树的适用问题 尽管已经开发的每种决策树算法有这样或那样不太一致的能力和要求，通常 [13]决策树算法最适合具有以下特征的问题: (1)实例是由“属性一值”对表示的:实例是用一系列固定的属性和它们的值来描述的。在最简单的决策树学习中，每一个属性取少数的离散的值。但扩展的算法允许处理值域为实数的属性。 (2)目标函数具有离散的输出值:(例如最常见的布尔类型的分类:yes或no)。决策树方法很容易扩展到学习有两个以上输出的函数。 (3)可能需要析取的描述，决策树很自然的可以代表析取表达式。 (4)训练数据可以包含错误:决策树学习对错误有很好的健壮性，无论是训练样例所属的分类错误还是描述这些样例的属性值错误。 (5)训练数据可以包含缺少属性值的实例:决策树学习甚至可以在有未知属性值的训练样例中使用。 己经发现很多实际的问题符合这些特征，所以决策树学习己经被应用到很多问题中。例如根据疾病分类患者;根据起因分类设备故障;根据拖欠支付的可能性分类贷款申请。对于这些问题，核心任务是要把样例分类到各个可能的离散值对应的类别中。 2.2 ID3分类算法基本原理 在本章的开始就已经提到了决策树的生成到目前为止有很多种算法，但它们多数是围绕决策树的核心算法ID3演变而来的。在本文主要是对ID3算法研究和设计实现，具体的内容将在下一章详细介绍。 [14] 早期著名的决策树算法是1986年由Quinlan提出的ID3算法.给出ID3算法ID3tree(T.T attributelist)的具体描述。其中，假设用T代表当前样本集，当前的候选属性集用T-attributelist 表示，候选属性集中的所有属性皆为离散型，连续值属性必须事先经过预处理转化为离散型。 ID3算法运用信息熵理论，选择当前样本集中具有最大信息增益值的属性作为测试属性;样本集的划分则依据测试属性的取值进行，测试属性有多少不同取值就将样本集划分为多少子样本集，同时，决策树上相应于该样本集的节点长出 第 18 页 ,共 52页 南华大学计算机科学与技术学院毕业设计(论文) 新的叶子节点。由于决策树的结构越简单越能从本质的层次上概括事物的规律，我们于是期望非叶节点到达后代节点的平均路径总是最短，即生成的决策树的平均深度最小。这就要求在每个节点选择好的划分。香农的信息论表明:系统的不确定性越小，信息的传递就越充分。ID3算法根据信息理论，采用划分后样本集的不确定性作为衡量划分好坏的标准，用信息增益值度量:信息增益值越大，不确定性越小。因此，算法在每个非叶节点选择信息增益最大的属性作为测试属性。 [15]给出ID3算法信息增益求值的算法: 设S是s个样本的集合。假定类别属性具有m个不同值，定义m个不同类Ci(i=l，„„，m)。设s 是Ci中的样本数。对一个给定的样本集，它总的信息i 熵I值由公式2.9给出: (2.9) Pi是任意样本属于类别C的概率，用S/S估计。 ii 设属性A具有v个不同的值。可以用属性A(a aa)，将S划分为v个子。。。1,2,v 集{S SS };其中，Sj包含S中这样的一些样本，它们在A上具有值a，。假。。。1,2,vj设选取A作为本次分类的属性，则这些子集对应于由包含集合S的节点生长出来的分枝。设s是子集Sj中类C的样本数。根据由A划分成子集的熵(entropy)iji 由公式2.10得出: (2.10) 其中， (2.11) 是S中类为C的样本的概率，最后，用属性A划分样本集S后所ji 得的信息增益值由公式2.12给出: (2.12) 选择属性A使Entropy (E/A)最小，则信息增益将增大。也就是说，Gain(A)是由于知道属性A的值而导致的熵的期望压缩。为了使下一步所需的信息量最 第 19 页 ,共 52页 南华大学计算机科学与技术学院毕业设计(论文) 小，要求每一次都选择其信息增益最大的属性作为决策树的新结点，并对属性的每个值创建分枝，依据此思想划分训练数。 ID3是一个典型的决策树学习系统，它检验数据集的所有特征，它以信息增益作为分离目标评价函数，采用自顶向下，分而治之不可返回的策略，选取决策树的分裂点，对每个分支的子集采用递归调用同种方法建立决策树结点和分枝，直到某一子集中的数据都属于同一类。 2.3其它常见决策树算法 经典的ID3算法在1986年由Quinlan提出后有许多学者对此算法进行了大量的研究，先后出现了以C4.5、CART、SLIQ、SPRINT等较新的有关决策树分类的算法，下面简要描述这几种算法的基本概念和思想。 (1)C4.5算法 C4.5算法是Quinlan在1993年针对ID3存在的一些缺点提出的，它是ID3算法的后继，同时也成为后面诸多决策树算法的基础。C4. 5是ID3的改进版本[16]。它主要在以下几个方面对ID3作了改进:缺省值的预测属性仍可用,提出了修剪思想,可以进行规则推导。特别是在应用单机的决策树算法中，C4.5算法不仅分类准确率高而且速度快。C4.5算法在ID3的基础上弥补了对连续型属性、 [23]属性值空缺情况的处理，对树剪枝也进行了处理。与ID3不同，C4.5采用基于信息增益率(information gain ratio)的方法选择测试属性。信息增益率等于信息增益对分割信息量(split information)的比值。对样本集T，假设J是有S个不同取值的离散属性，用J分割样本集所得信息增益的算法同ID3算法。分割信息量由公式:给出。其中|T|为数据集T的例子数;假设a是在连续区间取值的连续型属性，首先将样本集T按属性a的取值从小到大排序，一般用快速排序法。假定排好后属性的取值序列为v，v，„，v，则12m对i?(l，m-1)，有值v=(vi+vi+1)/2和按值V划分的两个子样本集:，这样划分所得的信息增益记为Gain。线性地扫描序列v，v，„，v，找出v’，使得12m Gain v’最大，则v’称为局部阈值。则按连续属性a划分样本集T的信息增益为Gain，T被划分为T vl’，T v2’两个子集，在此划分上求出的信息增益率为连续属性a的最终信息增益率。而在序列v，v，„，v，中找到的最接近但又12m 第 20 页 ,共 52页 南华大学计算机科学与技术学院毕业设计(论文) 不超过局部阈值v’的取值v*成为当前节点在属性a上的分割阈值。按照上述方法求出当前候选属性集中所有属性的信息增益率，比较它们找出信息增益率最高的属性，若为离散属性，则按照该属性的不同取值分割当前样本集;若为连续属性，则依据它的分割阈值，将当前样本集分为两个子样本集。对每个子样本集用同样的方法继续分割直到不可分割或到达停止条件为止。 当训练集中含有的一些样本在某些属性上的值空缺，该算法为每个样本设 立的初始权值为1.0。当从样本训练集T中选择了测试属性A将T划分S个子样本集TT„T，对每个子样本集T，它包含的样本为T中A=a和A值空缺的样1，2，nii 本。T中含空缺值的样本的权值成正比于T中A值不空缺的样本数对T中A值不ii 空缺的样本数的比值。 在生成决策树后，就开始计算每个节点的分类错误进行树剪枝。对每个叶子节点，分类错误为该节点中不属于该节点所表示类别的样本的权值之和;对于非叶节点，分类错误为它的各个孩子节点的分类错误之和。如果计算出某节点N的分类错误超过了将节点N所代表的样本集T中的所有样本分配为T中出现最多的类别所得的分类错误，则将节点N的所有子枝剪去，使N成为叶节点，将T中出现最多的类别分配给它。由于C4.5采用训练样本集来估计分类错误，因此使得到的决策树模型融入了训练集中的异常，而这些异常通常在总体样本中并不出现，从而导致决策树倾向于过度拟合。这个缺陷可以使用一种悲观估计来补偿，选择一组独立于训练样本集的测试集来优化决策树。 [24]比较ID3算法，C4.5算法在效率上有了很大的提高。不仅可以直接处理连续型属性，还可以允许训练样本集中出现属性空缺的样本。生成的决策树的分枝也较少。但是，C4.5算法在选择测试属性，分割样本集上所采用的技术仍然没有脱离信息熵原理，因此生成的决策树仍然是多叉树。如果想生成结构更为简洁的二叉树，必须采用新的原理来分割样本集。 (2)CART算法 [17]CART 是(Classfication And Regression Tree)的简称，可以处理高度倾斜或多态的数值型的数据，它与ID3、C4.5算法的最大不同之处是采用的分裂 [29]节点的标准，它采用的是计算GINI系数，GINI系数越小划分越合理，样本的纯度也越高，划分的效果越好。 第 21 页 ,共 52页 南华大学计算机科学与技术学院毕业设计(论文) 2例如，对训练集T，gini(T)=1-?p。其中p是类别j在T中出现的概率。jj 若T被划分为T，T，则此次划分的GIN1系数为12 其中，S是T中样本的个数，s，s分别为T，121T中的样本个数。对候选属性集中的每一个属性，CART算法计算该属性上每种2 可能划分的GINI系数，找到GINI系数最小的划分作为该属性上的最佳划分，然后比较所有候选属性上最佳划分的GINI系数，拥有最小划分GINI系数的属性成为最终测试属性。与ID3、C4.5的算法只为叶子节点分配类别不同，CART算法考虑到每个节点都有成为叶子节点的可能，对每个节点(包括叶节点和非叶节点)都分配类别。分配类别的方法可以用当前节点中出现最多的类别，也可以参考当前节点的分类错误或其它的方法。CART算法在下列条件之一满足时停止构建决策树:(l)所有节点中的样本数为1或样本属于同一类;(2)决策树高度到达用户设置的阀值。 (3)SLIQ算法 ID3、C4.5等算法对规模较小的，可以全部放入主存的训练数据集很有效，但当训练样本集大到不能全部放入主存时，这些算法的效率明显降低。为了提高算法的可伸缩性，使之对大规模训练数据集也能有效地生成分类模型，需要对传统的算法进行改进。一种改进方法是:首先将训练样本集划分成若干子集，使得每一个子集都能完全放入主存;然后对每个子集分别构造一棵决策树;再将这些树综合，得到最终的决策树。这种算法与前面介绍的算法相比，减少了运行时间。但生成的决策树分类准确率有所下降。 [18]SLIQ (Supervised Learning In Quest)算法是IBM研究人员提出的一种快速可伸缩的适合处理较大规模数据的决策树分类算法。SLIQ算法首次提出在算法中运用一些特殊数据结构如属性表和类表。SLIQ算法在执行过程中需要随时修改类表，因此类表常驻内存，而类表的大小会随着训练集增大而增大，因此SLIQ算法受到主存容量的限制。 由于使用了新的数据结构，SLIQ算法可并行化。在有多处理器的并行环境中，假设每个处理器都各自拥有独立的主存和辅存。SLIQ算法可将属性表平均分配给各个处理器，使决策树的生成并行进行。对于类表，可以让每个处理器都 第 22 页 ,共 52页 南华大学计算机科学与技术学院毕业设计(论文) 有一份，或将它分割后分给各个处理器。根据对类表的不同处理，并行SLIQ算法可分为SLIQ/R和SLIQ/D两种版本。SLIQ/R为每个处理器都拷贝一份全局的类表。在各个处理器并行扫描属性表的过程中，对某个处理器中的类表进行的修改都要及时更新到各个处理器的类表中。处理器间要不断通信，保证每一时刻各个处理器上的类表一样。SLIQ/D将类表分割后再平均分给各个处理器。它的问题是，在某个处理器中扫描到的属性项，它对应的类表可能在另一个处理器中，处理器间也要通过通信来更新类表。 (4)SPRINT算法 SPRINT (Scalable Parallelizable Induction of Classification Tree) 算法的提出其目的是解决主存容量的受限问题，并能处理大规模的训练样本集，有效的生成决策树模型。SLIQ算法要求类表驻留内存,当训练集增加，导致类表 [19]放不进内存时，SLIQ算法就无法进行，这限制了SLIQ处理数据的最大规模。SPRINT算法使用了与SLIQ算法不同的数据结构。不使用独立的类表，而是为每个属性建立一个属性表，表项形如(属性值，类别，样本序号)连续属性的属性表要按属性值预排序;离散属性表则没有预排序过程。属性表不须常驻内存。在建树过程中，SPRINT为每个待分裂节点设立一个类直方图。它记录了每个不同取值的样本在各个类别中的个数。当测试条件形成，节点分裂时，属性表也分裂到新的叶节点中。每个待分裂的叶节点对应一张属性表，SPRINT扫描属性表寻找最佳分割，计算最佳分割的信息可从相应的直方图获得，因此计算每次分割至多只需要一张属性表的直方图常驻内存。由于直方图的大小不会随属性表的增大而增大，SPRINT算法完全摆脱了主存容量的限制。 SPRINT建树具体步骤如下: 1)生成根节点，并为所有属性建立属性表，同时预排序连续属性的属性表。 2)如果节点中的样本可归成一类，则算法停止;否则转3); 3)利用属性表寻找拥有最小Gini值的划分作为最佳划分 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 。算法依次扫描该节点上的每张属性表。由于计算Gini值需要该节点上直方图的信息，因此处理每一张属性表前均要清空并初始化直方图。对于连续属性A，要求初始化Cbelow为0。，Cabove为该节点上的样本关于A的总体分布。每扫描A属性表的一条记录(设属性值为v)，都要更新一次Cbelow和Cabove且计算对应于划分A 第 23 页 ,共 52页 南华大学计算机科学与技术学院毕业设计(论文) ?v的Gini值。这样，一遍扫描完A属性表，就可得到该节点上关于A属性的最佳划分，并记录下来。对于离散属性，先清空count matrix，在扫描B属性表的同时更新count matrix，扫描完后，根据构造好的count matrix求解最佳划分中的S，并记录下来。当扫描完该节点的所有属性表时就可得到该节点的最佳划分方案。 4)根据划分方案，生成该节点的两个子节点N1，N2。 5)划分该节点上的各属性表，使之关联到N1或N2上。首先划分测试属性的属性表:依次扫描记录<属性值x，类别属性c，样本号id>，判断x属于哪个孩子，然后将该条记录移至该孩了节点的新属性表中，同时将id值写入Hash表，以保存划分后样本所在孩子节点的信息。然后划分其余属性表:依次扫描记录，依据样本号查找Hash表中该样本划分后所在的孩子节点，然后将该记录移至该孩子节点的新属性表中。 6)分别转2)考察N1、N2节点。 通过实践表明，在SLQI的类表可以存进内存的情况下，SPRINT比SLQI执行得慢;然而在训练数据集规模超过SLIQ能承受得最大规模后，SPRINT的效率比SLIQ的要好得多，且数据量越大，SPRINT的效率越高。 (5)PUBLIC算法 上述含有剪枝的算法都是分成两步进行，即先建树再剪枝。而Rageev.R等人在1998年提出的PUBLIC算法将建树、剪枝结合到一步完成，在建树阶段不生成会被剪枝的子树，因而大大提高了效率。PUBLIC的建树基于SPRINT方法、剪 [20]枝基于MDL(最小描述长度法)原则。PUBLIC采用低估策略正过高的代价估算来防止过度剪枝，即对将要扩展的叶节点计算编码代价的较低阈值，而对于另两类叶节点(剪枝形成的、不能被扩展的)，估算方法不变。计算较低阈值的方法有多种，但最简单有效的方法是将它设置为1。 2.4决策树算法总结比较 以上对各种决策树作了简单的介绍，下面我们对决策树做一下比较和评估，对决策树方法的比较可采用下面的标准: (1)在选择测试属性技术方面:ID3算法采用信息增益作为测试属性，信息最小的熵作为根结点，C4.5算法采用信息增益率作为测试属性，而CART算法， 第 24 页 ,共 52页 南华大学计算机科学与技术学院毕业设计(论文) SLIQ算法，SPRINT算法则都采用GINI系数作为测试属性。 (2)在连续属性的处理技术方面:ID3算法采用离散化技术，C4.5算法，CART算法，SLIQ算法，SPRINT算法则都采用预排序方法来处理连续属性。 (3)在剪枝方法方面:ID3，C4.5算法和CART算法采用分类错误方法对决策树进行修剪，而SLIQ和SPRINT算法则采用MDL方法对决策树进行修剪。 (4)在测试样本方面:ID3算法需要独立的测试样本，而C4.5算法，CART算法，SLIQ算法，SPRINT算法都不需要独立的测试样本。 (5)在可伸缩性的评估方面:ID3算法，C4.5算法，CART算法的可伸缩性较差，而SPRINT算法的可伸缩性好，而SLIQ算法相比较前几种算法，可伸缩性就相对较好一些。 (6)在并行性方面:ID3算法，C4.5算法，CART算法的并行性就差一些，而SPRINT算法的并行性就比前几个算法好一些，而SLIQ算法的并行性相比前几个就更好一些。 (7)在结构方面:ID3算法和C4.5算法生成的决策树是多叉树，而CART算法，SLIQ算法，SPRINT算法生成的决策树则是以二叉树的形式存在。 (8)ID3算法，C4.5算法，CART算法，SLIQ算法，SPRINT算法中剪枝的算法都是分成两步进行，即先建树再剪枝，而PUBLIC算法的建树基于SPRINT方法，剪枝基于MDL(最小描述长度法)原则将建树、剪枝结合到一步完成，在建树阶段不生成会被剪枝的子树，因而大大提高了效率。 2.5实现平台简介 本实验在java_jdk_1_5_0_04平台上实现，java_jdk_1_5_0_04是在Windows [41]操作系统上的最新版本。1995年Java语言刚一推出，便以其纯面向对象、XP 平台无关性、多线程、高安全性、良好的可移植性和可扩展性等特性，受到了计算机界的普遍欢迎，并得到了广泛的应用和发展。近几年来，Java的应用已经扩展到各个应用领域，加上各种功能配件的推陈出新，使得Java能够满足产品开发的需求，成为网络时代最流行的程序设计语言。利用Java来开发软件，具有跨平台、易整合、易扩展的优点。 (1)Java的产生: 1991年初，美国加州的Sun Microsystem公司(以下简称Sun公司)成立了 第 25 页 ,共 52页 南华大学计算机科学与技术学院毕业设计(论文) 一个以James Gosling为首、名为Green的项目研发小组，其目标是开发一个面向家用电器市场的软件产品，用软件实现一个对家用电器进行集成控制的小型控制装置。他们首先注意到这个产品必须具有平台独立性，即让该软件在任何CPU上都能运行。为达到此目的，Gosling首先从改写C++语言的编译器着手。但是，他们很快便意识到这个产品还必须具有高度的简洁性和安全性，而C++在这方面显然无法胜任。因此，Gosling决定自行开发一种新的语言，并将该语言命名为Oak(橡树)。Oak是Green项目小组开发的一个名为“*7”(Star Seven)产品中的一个组成部分。Star Seven是一个集成了Oak、GreenOS(一种操作系统)、用户接口模块和硬件模块四个部分的类似于PDA(Personal Digital Assistant，个人数字助理)的设备。 有趣的是，在这段时间里，WWW的发展却如日中天。1993年7月，伊利诺斯大学的NCSA推出了一个在Internet上广为流行的WWW浏览器Mosaic 1.0版。然而，这时的WWW页面虽然内容丰富，可以实现声、图、文并茂，但它却是静态的，若想增强WWW的动感，需要通过一种机制来使它具有动态性。其解决方案显然是嵌入一种既安全可靠，又非常简练的语言。Oak完全满足这一要求。但是，要将它推向市场，为人们所广泛接受，还必须采用一种合适的策略。1994年，Sun公司的创始人之一Bill Joy的介入，使Oak成为Java而得以走红。 (2)Java的特点: Sun公司在“Java白皮书”中对Java的定义是:“Java: A simple, object-oriented, distributed, interpreted, robust, secure, architecture-neutral, portable, high-performance, multi-threaded, and dynamic language.”。按照这个定义，Java是一种具有“简单、面向对象的、分布式、解释型、健壮、安全、与体系结构无关、可移植、高性能、多线程和动态执行”等特性的语言。下面我们简要叙述Java的这些特性。 1)简单性 Java语言简单而高效，基本Java系统(编译器和解释器)所占空间不到250 KB。Gosling等人在设计Java之初，是从改写C++编译器入手的，这就使Java具有类似于C++的风格，保留了C++语言的优点;摈弃了C++中不安全且容易引发程序错误的指针;消除了C++中可能给软件开发、实现和维护带来麻烦的地方， 第 26 页 ,共 52页 南华大学计算机科学与技术学院毕业设计(论文) 包括其冗余、二义性和存在安全隐患之处，如操作符重载、多重继承和数据类型自动转换等;简化了内存管理和文件管理——Java提供了C++中不具备的自动内存垃圾搜集机制，从而减轻了编程人员进行内存管理的负担，有助于减少软件错误。 2)面向对象 Java语言是纯面向对象的，它不像C++那样既支持面向对象的技术，又支持面向过程的程序设计技术。在面向对象的技术中，把现实世界中的任何实体，都可以看作是对象。对象其实就是现实世界模型的一个自然延伸。现实世界中的对象均具有属性和行为，映射到计算机程序上，属性用数据表示，行为用程序代码实现。可见，对象实际上就是数据和算法(程序代码)的封装体，它用一个自主式框架把代码和数据联编在一起，形成一个对象。面向对象的程序设计技术较传统的面向过程的程序设计技术更能真实地模拟现实世界。 3)可移植性(平台无关性) 程序的可移植性指的是程序不经修改而在不同硬件或软件平台上运行的特性。可移植性在一定程度上决定了程序的可应用性。可移植性分为两个层次:源代码级可移植性和二进制代码级可移植性。Java不仅源代码级是可移植的，甚至源代码经过编译之后形成的二进制代码——字节码，也同样是可移植的。 4)稳定性和安全性 [26]网络分布式计算环境要求软件具有高度的稳定性和安全性。Java首先摒弃了指针数据类型，这样，程序员便不再能够凭借指针在任意内存空间中“遨游”;其次，Java提供了数组下标越界检查机制，从而使网络“黑客”们无法构造出类似C和C++语言所支持的那种指针;第三，Java提供了自动内存管理机制，它可以利用系统的空闲时间来执行诸如必要的垃圾清除等操作。 5)高性能 一般情况下，可移植性、稳定性和安全性几乎总是以牺牲性能为代价的，解释型语言的执行效率一般也要低于直接执行源码的速度。但Java所采用的措施却很好地弥补了这些性能差距。 这些措施包括:?高效的字节码。?多线程。?及时编译和嵌入C代码。 6)动态特性 第 27 页 ,共 52页 南华大学计算机科学与技术学院毕业设计(论文) Java采用“滞后联编”机制避免了这个问题。Java程序的基本组成单元为类，这些类是在运行过程中动态装载的。因此，Java可以在分布式环境中动态地维护应用程序及其支持类库之间的一致性。这样，对于Java而言，其支持类库升级之后，相应的应用程序不必重新编译，也一样可以利用升级后类库的新增功能。“滞后联编”机制使得Java完全利用了面向对象编程模式的优点，使Java程序能够适应不断变化的执行环境。此外，Java的动态性还体现在对动态数据类型和动态协议的支持上。利用一种特殊的Applet，即内容句柄，编程人员可很方便地使HotJava支持新的数据类型。类似地，通过编写协议句柄，可以使HotJava支持新的、自定义的传输协议。 简言之，Java的动态性使用户能够真正拥有“即插即用”(p1ug-and-play)的软件模块功能。 7)分布式 分布的概念包括数据分布和操作分布两个方面。数据分布是指数据可以分散存放于网络上不同的主机中，以解决海量数据的存储问题;操作分布则指把计算分散到不同的主机上进行处理，这就如同由许多人协作共同完成一项大而复杂的工作一样。Java支持WWW客户机/服务器计算模式。对于数据分布，Java提供了一个URL对象，利用此对象我们可以打开并访问网络上的对象，其访问方式与访问本地文件系统几乎完全相同。对于操作分布，Java的客户机/服务器模式可以把计算从服务器分散到客户端，从而提高整个系统的执行效率，避免瓶颈制约，增加动态可扩充性。由上述特征可以看出，Java的确是一门适合Internet和分布式环境的编程语言。 (3)按照Java 2 SDK的安装方法安装完SDK后，就完成了开发环境的建立，在这个平台上就可以运行Java源程序了。本实现就是在这个开发平台上实现。 (4)Java工具集 Java工具集为开发人员提供了创建和运行Java代码的工具，这些工具如下表所示: 第 28 页 ,共 52页 南华大学计算机科学与技术学院毕业设计(论文) 表2.1 Java 2 SDK 开发工具集 工具名称 说明 Javac Java编译器，用于将Java源程序编译成字节码 Java Java解释器，用于解释执行Java字节码 appletviewer 小应用程序浏览器，用于测试和运行Java applet 程 序 Javadoc Java文档生成器 Javap Java类文件反编译器 Jdb Java测试器 Javah C文件生成器，利用此命令可以在Java类中调用C++ 代码 2.6本章小结 本章详细介绍了决策树的方法，决策树的结构，决策树算法的基本原理，生成决策树算法的简单描述以及决策树的特性和决策树适用的问题，后面对决策树分类算法的核心算法——ID3分类算法做了初步的介绍，也分别介绍了基于ID3算法研究出的决策树分类算法的其它常见算法，并对这几种算法做了简单的比较和分析，通过本章，可以对决策树算法有比较清楚的了解。 第 29 页 ,共 52页 南华大学计算机科学与技术学院毕业设计(论文) 第三章 ID3算法的具体分析 前面主要介绍了决策树的相关知识，对它的核心算法——ID3算法作了简单介绍并且对由它演变而来的几种常用算法作了原理的分析和描述，并对它们对数据处理的功能进行了分析与比较。在这一章里我们主要对ID3算法进行具体分析和介绍。 3.1 ID3算法分析 3.1.1 ID3算法流程 (1)根据上一章对ID3算法的简单描述，用S表示训练样本集，A表示分类样本集合，N表示一个分类叶节点，画出算法流程图如下所示: 第 30 页 ,共 52页 南华大学计算机科学与技术学院毕业设计(论文) 用样本集S创建结点N Y 返回N A是否为空? N Y 返回N A是否纯, N For A=1 to m 求gain(A)选取最佳的属性A* S分裂为Si For i=1 to m S分裂为Si Y 返回N S是否为空, i N Builder Tree (S, A-A*) i 图3.1 ID3算法流程图 (2)算法流程描述如下: 算法:Generate_decision_tree由给定的训练数据产生一棵决策树 输入:训练样本samples，由离散属性表示;侯选属性的集合attribute-list 输出:一棵判定树 方法步骤描述如下: 1.创建节点N; 第 31 页 ,共 52页 南华大学计算机科学与技术学院毕业设计(论文) 2.if samples都在同一个类C then 3.返回N作为叶节点，以类C标记; 4.if attribute_list为空then 5.返回N作为叶节点，标记为samples中最普通的类; 6.选择attribute_list中具有最高信息增益的属性test_attribute; 7.标记节点N为test_attribute; 8.for each test-attribute中的已知值ai //划分samples 9.由节点N长出一个条件为test_attribute=ai的分支; 10.设si是samples中test-attribute=ai的样本的集合;//一个划分 11.if si为空then 12.加上一个树叶，标记为samples中最普通的类; 13.else加Generate_decision_tree (si,attribute_list_test_attribute) 返回的节点，继续分裂结点; 上面的13个步骤给出的是算法基本流程，算法的详细解释可理解为: (1)决策树从训练样本中的一个结点属性开始，对应上面步骤的第1步 (2)如果样本都属于同一个类，则该结点成为树叶，并用该类标记，对应步骤2、3 (3)否则，算法使用称为信息增益的基于熵的度量作为启发信息，选择能够最好地将样本分类的属性(步骤6)。该属性成为该结点的“测试”或“判定”属性，对应步骤7 (4)对测试属性的每个已知的值，创建一个分支，并按此划分样本，对应步骤8到10 (5)算法使用同样的过程递归的形成每个划分上的样本决策树。如果一个属性出现在节点上，就不必考虑该结点的后代，对应步骤13 (6)递归划分步骤仅当下列条件之一时停止算法的递归 *给定结点的所有样本属于同一类，对应步骤2、3没有剩余属性可以用来进一步划分样本(步骤4)。此时使用应用中使用最多的类(步骤5)。这牵涉到将给定的结点转换成树叶，并利用samples中的多数所在的类进行标记。 *分枝test-attribute=a，没有样本(步骤11)。这种情况以samples中的i 第 32 页 ,共 52页 南华大学计算机科学与技术学院毕业设计(论文) 多数类创建一个树叶，对应步骤12。 3.1.2 ID3算法评价 由于寻找最优决策树目前是一个NP难题，通过各种算法构建的决策树不一定都是最优的，因此ID3算法同样存在着一定的优缺点，从算法的描述和原理以及与其它几种算法的比较，我们对其总结如下: (1)ID3的优点 1)搜索空间是完全的假设空间，目标函数必在搜索空间中，不存在无解的危险; 2)全盘使用训练数据，而不是像候选剪除算法一个一个地考虑训练例，这样做可以利用全部训练例的统计性质进行决策，从而抵抗噪音; 3)可以生成容易理解的IF-THEN分类规则，如果建立一个包含几百个属性的决策树，虽然看起来很复杂，但每一条从根结点到叶子节点的路径所描述的含义还是可以理解的。 4)决策树算法擅长处理非数值型数据。 (2)ID3的缺点 1)这种基于互信息的计算方法偏向于属性取值数目较多的特征，而属性值较多的属性却并不总是最优的属性，即按照使熵值最小的原则被ID3算法列为应该首先判断的属性在现实情况中却并不是那么重要。例如:在股票市场个股的选择，欺诈分析等等。 2)该算法对噪声比较敏感，不容易除去噪声。对于噪声，Quinlan的定义是训练例子中的错误就是噪声。它包含两方面,一是特征取值错,二是类别给错。 )当训练集增加时，该算法生成的决策树随之变化。在建树过程中，各特3 征的相互信息会随例子的增加而改变，决策树也随之变化，这对变化的数据集的学习是不适合的。 4)在数据挖掘中，由于某种操作对象很多是巨型数据集的数据库，因此计算复杂的问题将是非常重要的一个环节，将直接影响生成与使用模型的计算成本，数据集越大，算法的计算量增加的越快。 5)缺乏伸缩性:由于要进行深度优先搜速，所以算法受到内存大小的限制，难于处理大的训练集。 第 33 页 ,共 52页 南华大学计算机科学与技术学院毕业设计(论文) 6)对连续的属性，必须先对其离散化、取样，而为了这种处理大数据集的算法，不仅增加了分类算法的额外开销，还降低了分类的准确性。 7)ID3将注意力集中在属性的选择上，而这种研究方式己受到一些学者的怀疑，属性选择对决策树的精度是否影响很大，至今仍无定论。 3.2决策树模型的建立 3.2.1 决策树的生成 根据上节的算法流程分析，下面我们用一个具体实例阐述经典ID3算法的整个构建流程。下页表3-1 给出了来自All Electronics顾客数据库数据元组训练集。邮寄清单用于分发介绍新产品和降价信息材料。该数据集用于描述顾客是否买电脑有4个属性(age，income，student，credit_rating)，类标号即类别属性buys_computer有两个不同值(yes和no)即m=2，因此有两个不同的类。 表3.1 样本训练集 RID age income student credit_rating Class:buy_compuer 1 <=30 high no fair no 2 <=30 high no excellent no 3 31„40 high no fair yes 4 >40 medium no fair yes 5 >40 low yes fair yes 6 >40 low yes excellent no 7 31„40 low yes excellent yes 8 <=30 medium no fair no 9 <=30 low yes fair yes 10 >40 medium yes fair yes 11 <=30 medium yes excellent yes 12 31„40 medium no excellent yes 13 31„40 high yes fair yes 14 >40 medium no excellent no 第 34 页 ,共 52页 南华大学计算机科学与技术学院毕业设计(论文) 假设类C对应于yes，而类C对应于no。类C有9个样本，类C有5个样1212本。对下面的数据集用ID3算法的原理和流程来构建决策树模型，对顾客进行分类，整个计算过程如下: 1.计算给定样本集的信息熵，我们使用公式2.9: 所以 2.计算每个属性的信息增益 (1)对于属性age，需要知道age的每个样本值yes和no的分布。 *如果age=“<=30”,则p=2 (此时类别为yes的个数)，n=3(此时类别为 11no的个数)，由公式2.9知: *如果age=“31„40”,则p=4(此时类别为yes的个数)，n=0(此时类别为22no的个数)，由公式2.9知:I(p n)=0; 2,2 *如果age=“>40”,则p=3(此时类别为yes的个数)，n=2(此时类别为no33的个数)，由公式2.9知:I(p n)=0.971; 3,3 根据训练样本集的属性划分成子集的熵的公式2.10可知: 因此如果按照age来划分训练集，则其信息增益由公式2.12得到: Gain(age)=I(p,n)-E(age)=0.246 2)对于属性income, 需要知道income的每个样本值yes和no的分布。 ( *如果income=“high”,则p=2 (此时类别为yes的个数)，n=2(此时类别11为 no的个数)，由公式2.9知: *如果income=“medium”,则p=4(此时类别为yes的个数)，n=2(此时类22别为no的个数)，由公式2.9知:I(p n)=0.148; 2,2 *如果income=“low”,则p=3(此时类别为yes的个数)，n=1(此时类别为33 第 35 页 ,共 52页 南华大学计算机科学与技术学院毕业设计(论文) no的个数)，由公式2.9知:I(p n)=0.279; 3,3 根据训练样本集的属性划分成子集的熵的公式2.10可知: E(income)=0.911 因此如果按照age来划分训练集，则其信息增益是: Gain(income)=I(p,n)-E(income)=0.029 同理求得Gain(student)=0.151和Gain(credit_rating)=0.048。 (3)从这四个结果我们很容易知道age在属性中具有最高信息增益，即它的信息熵E(age)是最小的。按照信息论的原理，age被选为测试属性，作为决策树的根节点。 (4)生成决策树的根和分枝。由于age属性具有3个不同的属性值，故从age根节点引出的分枝有3个，如下图3.2所示，从图中可以看出当age为31„40时，节点所对应的类别均为yes值，所以此时该节点的I(p2,n2)节点的信息熵为O,而<=30的属性和>40的属性都还有两个类别，所以要对它们进一步划分。 age <=30 >40 income student credit_rating class 30 income student credit_rating class high no fair no … medium no fair yes high no excellent no 40 low yes fair yes medium no fair no low yes excellent no low yes fair yes medium yes fair yes medium yes excellent yes medium no excellent no income student credit_rating class high no fair yes low yes excellent yes medium no excellent yes high yes fair yes 图3.2 age分枝属性详细图 (5)在age作为根节点对训练集进行划分后，还有两个节点需要对其进行进一步细分，对每个子集求子样本集的信息熵，再求每个属性的信息熵，最后求 第 36 页 ,共 52页 南华大学计算机科学与技术学院毕业设计(论文) 出每个属性的信息增益，找出其中具有最大信息增益的节点，将该节点作为图3.3节点l和节点2的根。整个过程同上面在整个训练样本集里求具有最大信息增益的节点是类似的，只是类别数和属性的个数有所改变。 图3.3 age分枝属性简化图 (6)按照上述的算法原理，对整个训练数据集进行递归分解，直到节点的所有类别都属于同一类或没有多余的属性来划分训练样本集，满足这个条件就可以生成最终的决策树分类模型，得到决策树的理想化模型如图3.4所示: 图3.4 决策树理想化模型 3.2.2 分类规则的提取 分类规则就是一个决策树生成的规则，通过分析决策树就可以找出这个规则，决策树分类器就是用于提取分类规则的。通过提取分类规则，可以用于新的数据问题的分析。决策树分类器其中的一个优点就是容易转换成IF_THEN分类规则，该规则的生成使得数据间的关系更加易于理解，特别是在数据量很大，生成 第 37 页 ,共 52页 南华大学计算机科学与技术学院毕业设计(论文) 的决策树比较复杂的时候。从决策树的根到叶子节点的每条路径都对应的创建一条规则。沿着给定路径上的每个属性值一一对应形成规则前件(即IF部分)的一个合取项。叶节点包含类结果，形成规则后件(即THEN部分)。针对上面的例子，我们可以从上节生成的这棵决策树中提取出对应的IF_THEN分类规则，通过这一规则，我们可以用来快速判断新的或未来顾客的购买电脑的可能性。 上面的例子的分类规则如下: (1)IF age=“<=30”AND student=“no” THEN buys_computer=“no” (2) IF age=“<=30”AND student=“yes” THEN buys_computer=“yes” (3)IF age=“31„40”， THEN buys_computer=“yes” (4)IF age=“>40”，AND credit_rating=“excellent” THEN buys_computer= “no” (5)IF age=“>40”，AND credit_rating=“fair”THEN buys_cocmputer= “yes” 3.2.3模型准确性评估 该步骤的目的就是利用生成的规则来预测测试集中的未知数据是属于哪一分类，并通过测试结果与实际情况相吻合的准确率来判断该决策树是否有效，如果准确率达到或超过我们预先确定的阈值，则认为所建立的决策树模型是有效的，能够应用于实际工作，否则该模型的分类效果不好，需要重新选定训练集生成新的决策树，并继续利用准确率来判断该决策树模型的优劣，直到准确率达到预定的阈值为止。 模型准确性评估的过程如图3.5所示。 图3.5 模型准确性评估示意图 第 38 页 ,共 52页 南华大学计算机科学与技术学院毕业设计(论文) 3.3 本章小结 本章对ID3算法做了详细的介绍，首先描述了算法流程，并对ID3算法做出评价，虽然ID3算法有很多优点，但也存在一定的缺点，缺点的改进有待于进一步的研究，限于本人的水平局限，不多加说明。通过举例说明运用ID3算法的实现决策树的过程，通过对实例决策树的分析，找出了该例中的分类规则。通过本章内容的介绍，可以对ID3算法有更深刻的了解。 第 39 页 ,共 52页 南华大学计算机科学与技术学院毕业设计(论文) 第四章 实验结果分析 上一章中对ID3算法做了详细的介绍，并用例子说明了ID3算法生成决策树的过程,分析了运用ID3算法原理所得到的决策树，以及分类规则的提取和分类规则的应用。本章就要通过程序来实现上一章分析所得到的结果。对结果做进一步的说明，利于以后在实际应用中用ID3算法解决实际问题。 本实验的程序运用java语言，在java编译器上实现ID3算法。 4.1 实验结果分析 4.1.1生成的决策树 程序实现的决策树结果如图4.1所示: 图4.1 ID3算法实现的决策树 4.1.2 分类规则的提取 将上述生成的决策树转换成IF-THEN分类规则将使得决策树的分类结果更 直观、清晰。结果如图4.2所示: 第 40 页 ,共 52页 南华大学计算机科学与技术学院毕业设计(论文) 图4.2 ID3算法生成的分类规则 经过输入新的测试数据，可以发现该分类规则的准确度达到要求，说明该分类模型是有效的。 4.2 本章小结 本章通过运用决策树的经典算法——ID3算法用java语言编程实现上一章所描述的顾客购买计算机的可能性的决策树，通过分析我们可以知道，运用ID3算法能够对数据进行有效的处理，为我们的生活带来方便。同时ID3还存在很多不足，有待于进一步的研究。 第 41 页 ,共 52页 南华大学计算机科学与技术学院毕业设计(论文) 第五章 总结与展望 在这个信息化的时代，处理大量混乱而又复杂的数据的一个很好的方法是分类，在分类技术的发展过程中，流行的几个技术是贝叶斯分类、神经网络、遗传算法和决策树等。与神经网络和贝叶斯分类比较，决策树更容易被人们理解。而且，训练一个神经网络将花费大量的时间和进行上千次的迭代，生成决策树则要有效得多，因此，适用于大的训练集。另外决策树生成算法除了包含在训练数据中的信息外不要求其他的信息(例如，领域知识或数据/类的概率分布的预知信息)，且决策树还表现出很好的分类精确度。并且，与其它分类方法比起来，决策树算法的基础理论清晰、更加容易被人们理解、能够直接显示出数据所具有的特点以及数据之间的相互关系，并具有较好的分类预测能力，因此对决策树算法的研究有着重要的研究价值和实际意义。 本文主要做了以下工作: (1)首先阐述了论文课题的研究背景、国内外在数据挖掘领域的究现状以及论文的组织结构。 (2)详细的阐述了决策树分类模型的基本原理、工作的过程，并讲述了它的核心算法——ID3算法的基本原理。最后介绍了ID3算法演变和改进来的其他几种算法，并对它们进行了比较，做出概况性描述。 (3)给出了ID3算法的详细描述和它的评价。用实例运用ID3算法来实现决策树的生成，以及分类规则的提取。实验结果证明，ID3算法是一种经典的数据处理算法，运用它能够解决生活中很多数据问题。 虽然ID3算法非常实用，但它自身存在的问题也是较多的，目前很多研究者都在研究对ID3算法的改进，比如:在提高决策树的分类效率基础上控制好决策树的规模，尽量去减小决策树的深度;对噪声的处理，即该算法没有将正确的数据与错误的数据区分开;算法的可伸缩性的研究;特别是现在网络的发展，给我们提出了并行处理的情况，即需要我们去研究分布式的简化熵值算法等等。这些问题由于本人的限度，有待于进一步的研究。另外，基于ID3算法而来的其它几种算法能够解决不同的数据问题，但也存在不同程度的问题，还需要进一步的研究和改进。 目前，针对决策树的研究有很多，如:基于决策树的分类算法的并行化研究 第 42 页 ,共 52页 南华大学计算机科学与技术学院毕业设计(论文) 及应用，基于决策树的协同进化分类算法研究，决策树分类算法在姜寨一期聚落遗迹分类中的应用研究，基于决策树的分布式分类算法研究，PUBLIC算法的简化，基于决策树和K最近邻算法的文本分类研究，基于决策树分类算法的CRM系统研究，粗糙集与决策树算法用于冠心病分类研究，还有各种决策树应用于实际问题中的研究等等。数据挖掘技术可以为我们的生活提供很多方便，所以针对数据挖掘的决策树分类算法的研究也将是无止境的，我们需要不断的努力。 第 43 页 ,共 52页 南华大学计算机科学与技术学院毕业设计(论文) 参考文献 [1] 毛国君,段立娟,王实,石云.数据挖掘原理与算法[M]. 北京:清华大学出版社, 2005 [2] Jiawei Han，Micheline Kamber著.范明，孟小峰 等译.数据挖掘概念与技术[M].北 京:机械工业出版社，2001 [3] 美Mehmed Kantardzic 著. 数据挖掘—— 概念、模型、方法和算法[M]. 闪四清,陈 茵，程雁 等译. 北京: 清华大学出版社, 2003 [4] 张维东 等.利用决策树进行数据挖掘中的信息熵计算[J]. 计算机工程, 2001(3):66-68 [5] 王大玲等.基于概念层次树的数据挖掘算法的研究与实现[J]. 计算机科 学,2001.2(2):63-66 [6] 唐华松 等.数据挖掘中决策树算法的探讨[J].计算机应用研究, 2001(8):36-40 [7] 许兆新 等.决策支持系统相关技术综述[J].计算机应用研究, 2001(2):22-26 [8] Ruggieri S. Efficient C4.5. IEEE Transactions on Knowledge and Data Engineering, 2002(6):55-58 [9] Breiman L, Friedman JH, Olshen RA, et al. Classification and Regr- s. Chapman & Hall(Wadsworth, Inc.): New York, 1984 ession Tree [10] 王熙照 等，决策树简化(剪切)方法综述[J].计算机工程与应用，2004(40):32-35 [11] 胡江洪 基于决策树的分类算法研究[J].计算机工程与应用，2005(27):66-69 [12] 张白一, 崔尚森编著. 面向对象程序设计——Java[M]. 西安:电子科技大学出版社, 2006,6 [13] 谈恒贵 等.数据挖掘分类算法综述[J].微型计算机与应用，2005(2):4-24 [14] Jing Luan, Data Mining and Its Applications in Higher Education,New Directions for Institutional Research,2002(13):17-36 [15] 杨明 等，决策树学习算法ID3的研究[J].微机发展，2002(5):6-9 [16] 李强. 创建决策树算法的比较研究_ID3_C4_5_C5_0算法的比较[J].计算机应用， 2005(5): 64-69 第 44 页 ,共 52页 南华大学计算机科学与技术学院毕业设计(论文) 致谢 时间如梭，转眼间，大学四年就要结束了，在这几年的学习中，如果没有老师和同学的帮助，我的课程和论文工作是不能顺利完成的。借此列述如下:表达我深深的谢意。 首先向我的导师表示由衷的感谢。本论文的写作过程中，从论文选题到最后定稿，其中的每一步，肖老师都给予了精心的指导和帮助。而且，肖老师平易近人，他严谨的治学态度和渊博的知识使我受益匪浅。更重要的是，肖老师身上流露出一种可贵的敬业精神，让我感动。这是我受益终身的财富。感谢教授大学课程的所有任课老师。正是他们的谆谆教导，使我一步步的走到今天。在论文的写作过程中，他们所传授的基础知识给了我很大的帮助，在此，谨向他们表示诚挚的谢意。 对辅导老师肖老师和曾老师在大学期间给予的管理工作上的关心和帮助表示谢意。感谢我同班和同寝室的同学们，在和他们的互相交流讨论中，我学到了很多知识，得到了很多建议。 感谢我的家人所给予的关心、帮助和支持，正是他们的深切关怀，帮我走过了几年的艰苦学涯。 第 45 页 ,共 52页 南华大学计算机科学与技术学院毕业设计(论文) 附录 源程序: package graph; import java.util.ArrayList.*; import java.util.List.*; import java.util.TreeSet.*; public class DTree { TreeNode root; //根结点 private static boolean[] visable; private Object[] array; //可见性数组 private int index; public static void main(String[] args) { //初始数据 Object[] array = new Object[] { new String[]{ "<=30" ,"high" ,"no" ,"fair" ,"No" }, new String[]{ "<=30" ,"high" ,"no" ,"excellent" ,"No" }, new String[]{ "31...40" ,"high" ,"no" ,"fair","Yes"}, new String[]{ ">40" ,"medium" ,"no" ,"fair" ,"Yes"}, new String[]{ ">40" ,"low" ,"yes" ,"fair" ,"Yes"}, new String[]{ ">40" ,"low" ,"yes" ,"excellent" ,"No" }, new String[]{ "31...40" ,"low" ,"yes" ,"excellent" ,"Yes"}, new String[]{ "<=30" ,"medium" ,"no" ,"fair" ,"No" }, new String[]{ "<=30" ,"low" ,"yes" ,"fair" ,"Yes"}, new String[]{ ">40" ,"medium" ,"yes" ,"fair" ,"Yes"}, new String[]{ "<=30" ,"medium" ,"yes" ,"excellent" ,"Yes"}, new String[]{ "31...40" ,"medium" ,"no" ,"excellent" ,"Yes"}, new String[]{"31...40", "high", "yes", "fair", "Yes"}, new String[]{ ">40","medium" ,"no" ,"excellent" ,"No" }, 第 46 页 ,共 52页 南华大学计算机科学与技术学院毕业设计(论文) }; DTree tree = new DTree(); tree.create(array,4); } public void create(Object[] array,int index){ this.array = array; init(array,index); createDTree(array); printDTree(root); } public Object[] getMaxGain(Object[] array){ //计算最大信息增益值作为判定属性 Object[] result = new Object[2]; double gain = 0; int index = 0; for(int i=0;i0){ String[] strs = (String[])array[0]; return strs[index]; } return null; } public int getNodeIndex(String name) { String[] strs = new String[] {"age","income","student","credit_rating","class:buy_compuer"}; for(int i=0;i