毕业设计论文-数据挖掘技术

毕业设计论文--数据挖掘技术

目录摘要(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数据挖掘的应用与面临的挑战(6)1.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.2ID3分类算法基本原理(18)2.3其它常见决策树算法(20)2.4决策树算法总结比较(24)2.5实现平台简介(25)2.6本章小结(29)第三章ID3算法的具体分析(30)3.1ID3算法分析(30)3.1.1ID3算法流程(30)3.1.2ID3算法评价(33)3.2决策树模型的建立(34)3.2.1决策树的生成(34)3.2.2分类规则的提取(377)3.2.3模型准确性评估(388)3.3本章小结(39)第四章实验结果分析(40)4.1实验结果分析(40)4.1.1生成的决策树(40)4.1.2分类规则的提取(40)4.2本章小结(41)第五章总结与展望(42)参考文献(44)致谢(45)附录(46)摘要:信息高速发展的今天，面对海量数据的出现，如何有效利用海量的原始数据分析现状和预测未来，已经成为人类面临的一大挑战。由此，数据挖掘技术应运而生并得到迅猛发展。数据挖掘是信息技术自然演化的结果，是指从大量数据中抽取挖掘出来隐含未知的、有价值的模式或规律等知识的复杂过程。本文主要介绍如何利用决策树方法对数据进行分类挖掘。文中详细的阐述了决策树的基本知识和相关算法，并对几种典型的决策树算法进行了分析比较，如:核心经典算法——ID3算法;能够处理不完整的数据、对连续属性的数据离散化处理以及克服了ID3算法偏向于选择取值较多的属性作为测试属性的缺点的C4.5算法;利用GINI系数判别数据集中的分裂属性并形成二叉树的CART算法;使数据的分类不受机器主存的限制，有着良好的伸缩和并行性的SLIQ和SPRNIT算法。ID3算法是最核心的技术，所以本文主要对它进行了研究和设计实现。第四章在JAVA编译器上实现ID3算法，并对结果进行分析，决策树生成，分类规则的提取，以便于以后直接使用这一规则进行数据分析。在论文的最后一章介绍了目前数据挖掘技术的研究前景。关键词:数据挖掘；决策树；ID3算法；信息增益；熵值Abstract:Today,themassageispassedveryquickly.HowtoinvestigatecurrentstatusandforecastthefuturewithgooduseoftremendousoriginalDatahasbeenbecomingthebigchallengetohumanbeingswhenfacingtheemergenceofmassDataininformationera.Consequently,Dataminingtechnologyemergeandboomquickly.Datamining,istheproductoftheevolutionofinformationtechnology,whichisacomplexprocessexcactingtheimplicatedandvaluablepattens,knowledgeandrulesfromalargescaleofdataset.Thispapermainlyintroducesthedecisiontreealgorithmforclassification.Firstly,thebasicknowledgeaboutdecisiontreeandsomerepresentativealgorithmsforinducingdecisiontreearediscussed,includingID3,whichisclassical;C4.5,whichcandealwithcontinuousattributesandsomeemptyattribute,atthesametime,itcanovercometheID3’weaknesswhichisapttoselectsomeattributewithmorevalue;CART,whichusesGINIcoefficientaboutattributeselectionandinducesabinarytree;SLIQandSPRINT,whicharescalableandcanbeeasilyparallelized,moreovertheydon’thaveanylimitationofmainmemory.BecauseID3algorithmswhichisclassical,sointhepaperImainintroduceit.Thefirthchapter,ID3algorithmisdevelopedonthejavaplatformbyjava，andcarriesontheanalysistotheresult,thedecisiontreeproduction,theclassifiedruleextraction,itwillbeadvantageousforustousethisruletocarryonthedataanalysisdirectlyinthefuture.Iintroducedataminingtechnologyresearchprospectinthepaperlastchapter.Keywords:Datamining;Decisiontree;ID3algorithm;Informationgain;Entropyvalue第一章绪论1.1数据挖掘技术1.1.1数据挖掘技术的应用背景最近几十年以来，随着互联网的发展和企业信息化程度的日益提高，科研政府部门普遍使用电子事物处理技术，商品条形码被广泛使用，以及电子商务和科学数据库的急剧增长为我们带来了海量的数据。激增的数据背后隐藏着许多重要的信息，人们希望能够对其进行更高层次的分析，以便更好地利用这些数据。而目前的数据库系统可以高效地实现数据的录入、查询、统计等功能，但无法发现数据中存在的关系和规则，无法根据现有的数据预测未来的发展趋势，缺乏挖掘数据背后隐藏的知识的手段，从而导致了“数据爆炸但知识贫乏”的现象。大量信息在给人们带来方便的同时也带来了一大堆问题：第一是信息过量，难以消化；第二是信息真假难以辨识；第三是信息安全难以保证；第四是信息形式不一致，难以统一处理。人们开始考虑：“如何才能不被信息淹没，而是从中及时发现有用的知识、提高信息利用率？”这就引发了一门新兴的自动信息提取技术：数据中的知识发现，简称KDD[1](KnowledgeDiscoveryinDataBase)。其内容主要涉及人工智能领域中的机器学习，模式识别、统计学、智能数据库、知识获取、专家系统、数据库可视化、数据库领域的数据仓库联机分析处理(OLAP)，多维数据库等方面。KDD已经是解决目前信息系统中普遍面临的“数据爆炸”而“信息缺乏”状况的最有效的手段之一，并且它的研究领域具有较大的研究意义和较多的研究方向一度成为数据库研究界最热的研究方向，拥有人数众多的研究群体，受到学术界和企业界的极大关注。多学科的相互交融和相互促进，使得这一学科得以蓬勃发展，而且已初具规模。并行计算、计算机网络和信息工程等其他领域的国际学会、学刊也把数据挖掘和知识发现列为专题和专刊讨论，甚至到了脍炙人口的程度。数据挖掘是目前研究的热点，它可以说是数据库研究中的一个非常有应用价值的新领域，它融合了数据库、人工智能、机器学习、数理统计学、模糊数学等多个领域的理论和技术。数据挖掘DM[2](DataMining)是KDD的一个最关键步骤，因此实际应用中把DM和KDD不作区分。数据挖掘是目前研究的热点，它可以说是数据库研究中的一个非常有应用价值的新领域，它融合了数据库、人工智能、机器学习、数理统计学、模糊数学等多个领域的理论和技术。从数据分析的观点来看，数据挖掘分为两类:描述性数据挖掘和预测性数据挖掘。描述性数据挖掘以概要方式描述数据，提供数据所具有的一般性质;预测性数据挖掘分析数据，建立一个或一组模型，产生关于数据的预测。包括分类和回归。分类可用于提取描述重要数据的模型或预测未来的数据趋势。1995年，在美国计算机年会(ACM)上，提出了数据挖掘的概念。即通过从数据库中抽取隐含的，未知的，具有潜在使用价值信息的过程。数据挖掘应用的普遍性及带来的巨大的经济和社会效益，吸引了许多专家和研究机构从事该领域的研究，许多公司推出了自己的数据库挖掘系统。从1989年举行的第十一届国际联合人工智能学术会议上KDD被提出，到现在不过十多年的时间，但在GartnerGroup的一次高级技术调查中将数据挖掘和人工智能列为“未来5年内将对工业产生深远影响的五大关键技术”之首，并且还将数据挖掘列为未来五年内十大新兴技术投资焦点的第二位。根据最近Gartner的HPC研究表明，“随着数据捕获、传输和存储技术的快速发展，大型系统用户将更多地需要采用新技术来挖掘市场以外的价值，采用更为广阔的并行处理系统来创建新的商业增长点。”1.1.2数据挖掘的定义及系统结构数据挖掘也称为数据库中的知识发现KDD(KnowledgeDiscoveryinDataBase)。指的是从存放在数据库、数据仓库或其他信息库中的大量数据中挖掘出人们感兴趣的知识，这些知识是隐含的、事先未知的潜在有用信息。目的是帮助决策者寻找数据间潜在的关联，发现被忽略的要素，而这些信息对预测趋势和决策行为也许是十分有用的。数据挖掘技术能从DW中自动分析数据，进行归纳性推理，从中发掘出潜在的模式，或产生联想，建立新的业务模型，这是一个高级的处理过程。高级的处理过程是指一个多步骤的处理过程，多步骤之间相互影响、反复调整，形成一种螺旋式上升过程。这个过程与人类问题求解的过程是存在巨大相似性的。决策树分类算法的研究与改进挖掘过程可能需要多次的循环反复，每一个步骤一旦与预期目标不符，都要回到前面的步骤，重新调整，重新执行。从广义角度讲数据、信息是知识的表现形式，但在数据挖掘中更多把概念、规则、模式、规律和约束等看作知识。原始数据可以是结构化的，如关系型数据库中的数据，也可以是半结构化的，如文本、图形、图像数据、甚至是分布在网络上的异构型数据。发现知识的方法可以是数学的或非数学的、演绎的或归纳的。发现的知识可以被用于信息管理、查询优化、决策支持、过程控制等。总之，数据挖掘是一门广义的交叉学科，它的发展和应用涉及到不同的领域尤其是数据库、人工智能、数理统计、可视化、并行计算等。因此，概括起来从广义上来说，数据挖掘是从大型数据集（可能是不完全的，有噪声的，不确定的，各种存储形式的）中，挖掘隐含在其中的，人们事先不知道的，对决策有用的知识的过程[3]。从狭义上来说，数据挖掘是从特定形式的数据集中提炼知识的过程。数据挖掘的系统结构可以用以下的图来说明：图1.1数据挖掘系统结构图·数据库、数据仓库或其他信息库:这是一个或一组数据库、数据仓库、电子表格或其他类型的信息库。可以在数据上进行数据清理和集成。·数据库或数据仓库服务器:根据用户的数据挖掘请求负责提取相关数据。·知识库:这是领域知识，用于指导、搜索或评估结果模式的兴趣度。·数据挖掘引擎:这是数据挖掘系统的基本部分。由一组功能模块组成，用于特征化、关联、分类、聚类分析以及演变和偏差分析。·模式评估模块:通常，此模块使用兴趣度度量，并与数据挖掘模块交互，以便将搜索聚焦在有趣的模式上。·图形用户界面:本模块在用户和数据挖掘系统之间通信，允许用户与系统交互，指定数据挖掘查询或任务，提供信息，帮助搜索聚焦，根据数据挖掘的中间结果进行探索式数据挖掘。此外，此模块还允许用户浏览数据库和数据仓库模式或数据结构，评估挖掘的模式，以不同的形式对模式可视化。1.1.3数据挖掘的方法数据挖掘的功能用于指定数据挖掘任务中要找的模式类型，其任务一般可分为两类:描述和预测。描述性挖掘任务刻画数据库中数据的一般特性，预测性挖掘任务在当前数据上进行推断，以进行预测。在实际应用中，往往根据模式的实际应用细分为以下6种[4]:1.分类模式2.回归模式3.时间序列模式4.聚类模式5.关联模式6.序列模式本文主要介绍分类算法，所以下面主要介绍分类分析方法，分类分析要分析数据库中的一组对象，找出其共同属性，构造分类模型，然后利用分类模型对其它的数据对象进行分类。要构造分类模型，需要一个训练样本数据集作为输入，训练集由一组数据库记录或元组组成，每个元组包含一些字段值，又称“属性”或“特征”，这些字段和测试集中记录的字段相同，另外，每个训练样本记录有一个类别标识。分类目标是分析训练集中的数据，利用数据中能得到的特征，为每一类建立一个恰当的描述或模型，然后根据这些分类描述对测试数据进行分类或产生更恰当的描述。我们可以举一个简单的例子，信用卡公司的数据库中保存着各持卡人的记录，公司根据信誉程度将持卡人记录分成三类:良好、一般、较差，并且类别标记己赋给了各个记录。分类分析就是分析该数据库的记录数据，对每个信誉等级做出准确描述，如“信誉良好的客户是指那些年收入在5万元以上，年龄在40-50岁之间的人士”，然后根据这些描述对其它具有相同属性的数据库记录进行分类。在分类分析中，分类模型的构造方法有统计方法、神经网络方法及机器学习方法等。统计方法包括贝叶斯法和非参数法(近邻学习或基于事例的学习)，对应的知识表示为判别函数和原型事例。神经网络方法主要是多层前向神经网络的误差反向传播(errorbackpropagation，BP)算法，用模型表示是前向反馈神经网络模型，该算法实质是一种非线性的判别函数。机器学习方法包括决策树法和规则归纳法，前者对应的表示是决策树或判别树，后者则一般为产生式规则。另外，近年来又出现了一种称为粗糙集(Roughset)新的理论方法，它将知识表示为产生式规则。在解决实际问题时，经常要同时使用多种模式。分类模式和回归模式是使用最普遍的模式。分类模式、回归模式、时间序列模式也被认为是受监督知识，因为在建立模式前数据的结果是已知的，可以直接用来检测模式的准确性，模式的产生是在受监督的情况下进行的。一般在建立这些模式时，使用一部分数据作为样本，用另一部分数据来检验、校正模式。1.1.4数据挖掘系统的发展根据R.Grossman的观点，数据挖掘的发展过程可分为如下所介绍的一到四代[5]:第一代:第一代的数据挖掘系统仅支持一个或少数几个数据挖掘算法，这些算法只能够挖掘向量数据。如果数据足够大，并且频繁的变化，这就需要利用数据库或者数据仓库技术进行管理，第一代系统显然不能满足需求。第二代:第二代系统的主要特点是支持与数据库和数据仓库的高性能接口，并有高的可测量性和功能性。第二代系统提供了数据挖掘模式和数据挖掘查询语言，从而具有更高的灵活性。然而第二代系统只注重模型的生成，如何和预言模型系统集成的问题导致了第三代数据挖掘系统的开发。第三代:第三代数据挖掘系统可挖掘intranets和extranets上的分布的和高度异质的数据，并能有效的和操作系统结合。这一代数据挖掘系统的关键技术之一是提高对建立在异质系统上的多个预言模型以及管理这些预言模型的元数据提供第一级别的支持。第四代:第四代数据挖掘系统可以挖掘嵌入式、移动式以及一般性的计算设备所产生的各种数据。1.1.5数据挖掘的应用与面临的挑战尽管数据挖掘是一个新兴的研究领域，但是却得到了稳定的发展，每年市场上都会出现新的数据挖掘系统，各大数据库软件公司也分别推出了自己的数据挖掘产品。数据挖掘广泛应用于科学研究、商业应用、以及Web挖掘等很多领域。（1）科学研究数据挖掘在天文学上有一个著名的应用系统:SKICAT[27](SkyImageCatalogingandAnalysisTool)。它是加州理工学院喷气推进实验室与天文学家合作开发的用于帮助天文学家发现遥远的类星体的一个工具。SKICAT的任务是构造星体分类器对星体进行分类，使用了决策树方法构造分类器，结果使得能分辨的星体较以前的方法在亮度上要低一个数量级之多，而且新的方法比以往的方法要在效率上要高40倍以上。数据挖掘在生物学上的应用主要集中于分子生物学特别是基因工程的研究上。进几年，通过用计算生物分子系统分析法，尤其是基因数据库搜索技术以在基因研究上做出了很多重大发现，数据挖掘在分子生物学上的工作可分为两种:一是从各种生物体的DNA序列中定位出具有某种功能的基因串;二是在基因数据库中搜索与某种具有高阶结构(不是简单的线形结构)或功能的蛋白质相似的高阶结构序列。（2）商业应用数据挖掘技术以及应用此技术所获得知识和信息可以被广泛的应用于信息管理、商务管理、过程控制、市场分析、工程设计和科学研究等众多领域，这些领域的管理决策层可以通过对历史数据的分析，发现诸如市场供需规律、商品价格走势、家庭收入与消费特点、购买商品的习惯等规律，以支持企业的生产、经营和销售决策。（3）web挖掘(WebMining)随着网络的迅速发展，今天它己经成为人们交流思想，获取信息的便利手段。但这些信息缺乏结构化、组织的规律性、随意的散布在网络的各个角落，这已经成为这座世界性图书馆的一大缺憾。数据挖掘在因特网上的应用主要包括三种:在搜索引擎上(Searc