《决策树分类算法数据挖掘.docx》由会员分享，可在线阅读，更多相关《决策树分类算法数据挖掘.docx（40页珍藏版）》请在三一办公上搜索。
1、本科毕业论文（设计）（题目：决策树分类算法在教学分析中的应用）姓 名： 学 号： 1142151204 专 业： 计算机科学与技术院 系： 信息工程学院指导老师： 袁张露 职称学历： 助教/研究生 完成时间：教务处制安徽新华学院本科毕业论文（设计）独创承诺书本人按照毕业论文（设计）进度计划积极开展实验（调查）研究活动，实事求是地做好实验（调查）记录，所呈交的毕业论文（设计）是我个人在导师指导下进行的研究工作及取得的研究成果。据我所知，除文中特别加以标注引用参考文献资料外，论文（设计）中所有数据均为自己研究成果，不包含其他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究所做的工作已在论文
2、中作了明确说明并表示谢意。毕业论文（设计）作者签名：日期：决策树分类算法在教学分析中的应用摘 要随着信息科技的高速发展，人们对于积累的海量数据量的处理工作也日益增重，需求是发明之母，数据挖掘技术就是为了顺应这种需求而发展起来的一种数据处理技术。数据挖掘技术又称数据库中的知识发现，是从一个大规模的数据库的数据中有效地、隐含的、以前未知的、有潜在使用价值的信息的过程。在学生管理以及教学科学化的今天，传统的教学分析已经不能适应社会发展的需求。学生信息数据不断的增多，教学分析工作也日益加重。学生信息数据量不断的增多，对之前所累计的大量学生考试成绩数据运用数据挖掘技术进行分析挖掘是具有重大的意义的，这样
3、可以把所挖掘分析出来的信息反馈用于指导学校的教学分析，从而提高学生的学习成绩。本文通过学生成绩信息运用数据挖掘技术，对所采集的数据进行预处理，运用决策树分类算法中的C4.5算法对成绩进行分析得到了成绩分析决策树，分析研究出有用的信息找到影响学生的因素，发现某些规律的存在，用以指导学校教学分析工作的开展。关键词:数据挖掘；学生成绩；决策树 Application of decision tree in computer grade examination analysisAbstractWith the rapid development of Information Technology, p
4、eople are facing much more work load in dealing with the accumulated mass data. However, Data Mining Technique is a kind of data processing technique that follows this change. In recent years, colleges and other institutions of higher education had increased their enrollments, more and more students
5、 got enrolled and consequently, the students information data pool gets much bigger. However, the traditional data processing technology cant accommodate itself to study and analyze the accumulated mass data at a deeper level any more, while Data Mining Technique can solve these problems much better
6、.The increasing data base of the students concludes much, like students test score. With the rapid development of computer technology, Computer Rank Examination becomes more and more popular; hence, the data base of students test score becomes much bigger. So, to use Data Mining Technique to mine th
7、e accumulated mass CRE score is of great meaning with regarding to the improvement of the students score on CRE, since people can apply the results of data mining in school computer teaching research. This paper intends to show the use of Data Mining Technique in the analysis of students score infor
8、mation in Computer Rank Examination, from the pretreatment on the collected data to the use of decision tree technique in data analysis. This employs ID3 algorithm in decision tree technique to get the decision tree of the students score. Then by analyzing the useful information to find out the elem
9、ents that can influence CRE score and the rules in these influences to instruct school teaching work. Keywords:Data mining；computer examination；decision tree；SqlServer2008目 录1 绪 论11.1研究背景与意义11.2数据挖掘的产生11.3数据挖掘的国内外研究现状21.4论文研究内容及结构安排32 数据挖掘技术42.1数据挖掘的概念42.1.1 数据挖掘的定义42.2 数据挖掘的过程42.2.1 数据对象确立阶段52.2.2数
10、据预处理阶段52.2.2数据挖掘阶段62.2.3结果的解释和评估阶段62.3数据挖掘的主要方法62.4数据挖掘的功能102.5数据挖掘的系统结构122.6数据挖掘应用的成功案例132.7本章小结143 决策树技术153.1决策树简介153.2决策树的主要算法163.2.1 ID3算法163.2.2 C4.5算法173.3决策树剪枝183.3.1决策树剪枝的方法183.4本章小结204 决策树在计算机等级考试成绩分析中的应用214.1成绩分析方法的依据214.2 决策树算法在计算机等级考试成绩分析中的应用214.2.1 确定对象集目标214.2.2 数据的采集224.2.3 数据预处理234.2
11、.4 数据挖掘工作的展开244.2.5结果分析275总结与展望295.1研究结果295.2后续研究与展望29参考文献321 绪 论1.1研究背景与意义无论在企业应用领域，还是在科学领域，数据挖掘技术有着广泛的应用价值。在企业应用领域，用于制定好的市场策略以及企业的关键性决策。在商业方面，数据挖掘技术可以增强企业的竞争优势，缩短销售周期，降低生产成本，有助于制定市场计划和销售策略，并已经成为电子商务中的关键技术。近年来，随着我国高等教育的飞速发展，高校的教学管理信息不断增多。教学工作信息化有了很大的进步，好多高校在管理学生和教师信息方面有了很好的方式。比如我校的教务系统，这些系统为老师和学生提供
12、了很好的帮助。这些系统中积累了大量的数据。目前的这些数据库系统虽然基本上都可以实现数据的录入、修改、统计、查询等功能，但是这些数据所隐藏的价值并没有被充分的挖掘和利用，信息资源的浪费还是比较严重的。随着数据挖掘技术的不断扩展，许多高校为了避免信息浪费，已经将数据挖掘技术应用于高校的教学分析中。数据挖掘技术的应用将对提高学生成绩和提高教学水平起到很好的指导作用。为了提高教学质量，将数据挖掘技术引入到高校学生成绩分析中，对这些数据进行深入的挖掘和合理的分析，从而挖掘出传统的分析方法所无法得出的结论。进而利用分析结果引导教学的开展，从而有利于提高教学质量。本文主要是基于如下背景开展的：以安徽新华学院
13、历届学生成绩为背景，首先学习数据挖掘的理论知识以及决策树技术，然后建立新华学院学生成绩数据库，并利用数据挖掘技术中的决策树对自己建立的数据库进行深入的挖掘。最后对自己的挖掘结果进行分析，得到影响学生成绩的因素。从而更好的辅助今后学校的教学分析工作。1.2数据挖掘的国内外研究现状1989年8月在美国召开的第十一届国际人工智能联合会议的专题讨论会上，与数据挖掘（Date Mining）极为相似的术语从数据库中发现知识一词被提出。1993年以后，美国计算机协会美年都举行了专门研究探讨数据挖掘技术的会议，会议的规模也发展成为国际学术大会，并且在各个领域里取得了很多研究成果。最近，Gartner Gro
14、up的一次高级技术调查将数据挖掘和人工智能列为“未来三到五年内将对工业产生深远影响的五大关键技术”之首，并且还将并行处理体系和数据挖掘列为未来五年内投资焦点的十大新兴技术前两位。1根据最近Gartner的HPC研究表明，“随着数据捕获、传输和存储技术的快速发展，大型系统用户将更多地需要采用新技术来挖掘市场以外的价值，采用更为广阔的并行处理系统来创建新的商业增长点。”国外研究数据挖掘的组织、机构或大学很多。比较著名的如卡内基梅隆大学、斯坦福大学、麻省理工学院。著名的研究机构如：ACM、KDNet、NCDM等。国外比较著名的挖掘工具：IBM公司的Intelligent Miner 、SAS公司的E
15、nterprise Miner、SGI公司的SetMiner、SPSS公司的Clementine、Oracle Darwin等。不少的软件在国外得到了广泛的应用，并收到了明显的效益。与国外相比，国内对DMKD的研究稍晚，没有形成整体力量。1993年国家自然科学基金首次支持我们对该领域的研究项目。目前，国内的许多科研单位和高等院校竞相开展知识发现的基础理论及其应用研究，这些单位包括清华大学、中科院计算技术研究所、空军第三研究所、海军装备论证中心等。其中，北京系统工程研究所对模糊方法在知识发现中的应用进行了较深入的研究，北京大学也在开展对数据立方体代数的研究，华中理工大学、复旦大学、浙江大学、中国
16、科技大学、中科院数学研究所、吉林大学等单位开展了对关联规则开采算法的优化和改造；南京大学、四川联合大学和上海交通大学等单位探讨、研究了非结构化数据的知识发现以及Web数据挖掘。1.3论文研究内容及结构安排本课题的主要工作是将数据挖掘技术和学校的信息管理系统相结合，新华学院多年来的信息化教学管理工作积累了大量的教学数据，从新华学院的数据库中收集学生的考试成绩信息。利用数据挖掘技术对这些数据进行分析，获得影响学生成绩的因素，更好的辅助学校如何提高学生成绩以及提高教学质量。本课题根据指导老师提供的11级学生成绩的信息，建立安徽新华学院11级学生成绩库，采用数据挖掘技术对成绩库进行挖掘。通过对实验结果
17、进行深入分析，获得影响学生考试成绩的因素，辅助教师在以后的教学工作中采用更恰当的教学方式，指导学生应该具有什么样的学习态度，从而提高学生考试成绩。 论文结构如下：第一章 绪论。 主要介绍了论文的研究背景与意义，叙述了国内外数据挖掘技术的研究现状。第二章 数据挖掘的基础知识。 主要叙述了数据挖掘的定义、数据挖掘的过程以及数据挖掘的方法。第三章 决策树。 主要简要介绍了决策树以及决策树的经典算法。第四章 决策树在计算机等级考试成绩分析中的应用第五章 总结与展望。总结本篇论文并展望今后论文的继续研究方向内容方向。2 数据挖掘技术2.1数据挖掘的概念2.1.1数据挖掘的背景随着信息技术的高速发展，人们
18、积累的数据量急剧增长，如何从海量的数据中提取有用的知识成为当务之急。数据库技术的成熟以及数据应用的普及，虽然目前的数据库系统可以高效的实现数据的录入、查询、统计的功能，但无法发现数据中潜在的信息和价值，无法利用这些数据来预测未来的发展趋势。于是，新的问题就被提出来了：人类如何在这浩瀚的数据中及时发现有用的知识，提高数据的利用率呢？在不懈的努力下，从数据库中发现知识（Knowledge Discovery in Datebases）及其核心技术数据挖掘（Date Mining）便应运而生，并得以蓬勃的发展，越来越显出其强大的生命力。2.1.1 数据挖掘的定义数据挖掘(Data Mining)，又
19、译为资料探勘、数据采矿。它是数据库中的知识发现(Knowledge Discovery in Datebases,简称：KDD)，是目前人工智能和数据库领域研究的热点问题，数据挖掘一般是指从大量的数据中通过算法搜索隐藏于其中信息的过程。所谓数据挖掘是指从大量的、不完全的、有噪声的、模糊的、随机的数据中自动搜索隐藏于其中的有着特殊关系的信息，提取隐含在其中的，人们事先不知道的、但又是潜在有用的信息和知识的过程5。2.2 数据挖掘的过程数据挖掘(Data Mining)的过程可以分为以下几个部分：理解数据和数据的来源（understanding）、 获取相关知识与技术（acquisition）、
20、整合与检查数据（integration and checking）、 去除错误或不一致的数据（data cleaning）、 建立模型和假设（model and hypothesis development）、 实际数据挖掘工作（data mining）、测试和验证挖掘结果、解释和应用（interpretation and use）。大概可以四个部分数据对象的确立(Date Object Determined)数据预处理(Date Preprocessing)、数据挖掘(Date Mining)及结果的解释和评估(Interpretation and Evaluation)。图2.1 数据挖掘
21、的过程2.2.1 数据对象的确立明确我们研究问题所需要的数据，理解数据并提出问题，需要进行数据挖掘的数据信息，明确数据挖掘的目标的定义。确定数据挖掘目标是数据挖掘重要的一步。我们进行数据挖掘时，挖掘的结果往往是不可预测的，但对要进行挖掘的目标是可预见的，即明确数据挖掘的最终目标7。 数据对象的确立，包括对大量数据的选取、数据属性的确定等。本文是安徽新华学院学生成绩的数据挖掘技术应用，这些数据包含新华学院历届的学生考试成绩数据，数据属性包括学生姓名、性别。年龄、专业、成绩等。2.2.2数据预处理阶段现实世界中数据大体上都是不完整的、含有噪声的、甚至不一致的脏数据，我们无法直接对其进行数据挖掘，或
22、者挖掘结果会差强人意。为了提高数据挖掘的质量，人们提出了数据预处理技术7。数据预处理是数据挖掘过程中的一个很重要的步骤，数据预处理有很多种方法，一般将数据预处理又分为四个步骤：数据清洗、数据集成、数据变换、数据归约。数据清洗处理过程通常包括：填补遗漏的数据值、光滑有噪声数据、识别或删除异常值、以及解决不一致问题。数据集成就是将多个数据源的数据合并到一起并统一存储，建立数据仓库的过程实际上就是数据集成。在数据集成时要特别注意消除数据的冗余。数据变换主要是对数据进行规格化操作，将数据转换成适用于数据挖掘的形式。数据挖掘时对应的数据量往往是非常大的，数据归约是缩小所挖掘数据的规模，但保持数据的完整性
23、。2.2.3数据挖掘阶段数据挖掘阶段是数据挖掘的核心步骤，也是技术难点所在。而数据挖掘阶段的核心就是模式的发现13。此阶段主要是确定对数据进行分类还是聚类，确定数据的关联规则等等。然后确定用什么数据挖掘算法对数据进行挖掘，再利用数据挖掘的工具和一系列方法对之前所确定以及转换后的数据进行分析、产生一个特定的有意义的模式以更好的对已处理好的数据进行分析，获取有用信息。2.2.4结果的解释和评估阶段数据挖掘阶段会产生的模式或数据集经过评估存在冗余或多余的模式，这时需要将其剔除，过滤出有用的知识。过滤后用于呈现给用户；一般情况下，为了方便用户理解产生的模式，处理员应该利用可视化技术将数据挖掘产生的有意
24、义模式以图形或者其他可视化的形式表示，让用户更容易理解。例如把分类决策树转换为“ifthen”的形式。如果数据挖掘过程中的发现的知识不能满足用户的需求，我们则需要重新对数据进行处理，选择一些其他的数据挖掘方法、算法对数据进行再次挖掘，并分析结果，直到满足用户的需求。2.3数据挖掘的主要方法（1）关联规则在数据挖掘的知识模式中，关联规则模式是比较重要的一种。关联规则的概念由Agrawal、Imielinski、Swami 提出，是数据中一种简单但很实用的规则。关联规则模式属于描述型模式，发现关联规则的算法属于无监督学习的方法。关联规则是描述了数据库中数据项之间所存在的关系的规则，即根据一个事务中
25、某些项的出现可导出另一些项在同一事务中也出现，即隐藏在数据间的关联或相互关系。（2）决策树所谓决策树，顾名思义，是一种树，一种依托于策略抉择而建立起来的树。一种用树枝状展现数据受各变量的影响情况的分析预测模型，根据对目标变量产生效应的不同而制定分类规则，它是建立在信息论基础之上，对数据进行分类的一种方法。它首先通过一批已知的训练数据建立一棵决策树，然后采用建好的决策树对数据进行预测。决策树的建立过程是数据规则的生成过程，因此这种方法实现了数据规则的可视化，其输出结果容易理解，精确度较好，效率较高，因而较常用。常用的方法有分类及回归树法、卡方自动交互探测法等。决策树是一个预测模型；他代表的是对象
26、属性与对象值之间的一种映射关系。树中每个节点表示某个对象，而每个分叉路径则代表的某个可能的属性值，而每个叶结点则对应从根节点到该叶节点所经历的路径所表示的对象的值。决策树仅有单一输出，若欲有复数输出，可以建立独立的决策树以处理不同输出。决策树算法是一种逼近离散函数值的方法。它是一种典型的分类方法，首先对数据进行处理，利用归纳算法生成可读的规则和决策树，然后使用决策对新数据进行分析。本质上决策树是通过一系列规则对数据进行分类的过程。（3）神经网络一种模仿人脑思考结构的数据分析模式，由输入变量或数值中自我学习并根据学习经验所得的知识不断调整参数，以期得到资料的模式。是建立在自学习的数学模型基础之上
27、，它可以对大量复杂的数据进行分析，并能完成对人脑或计算机来说极为复杂的模式抽取及趋势分析。神经网络的处理过程主要是通过网络的学习功能找到一个恰当的连接加权值来得到最佳结果。比较典型的学习方法是回溯法。通过将输出结果同一些已知值进行一系列比较，加权值不断调整，得到一个新的输出值，再经过不断的学习过程，最后该神经网络得到一个稳定的结果。 （4）相关规则是一种简单而实用的关联分析规则，它描述一个事物中某些属性同时出现的规律和模式，由一连串的“如果则”的逻辑规则对资料进行细分的技术。关联规则一般应用在事物数据库中，其中每个事物都由一个记录集合组成。这种事物数据库通常都包括极为庞大的数据，因此当前的关联
28、规则发现技巧正努力根据基于一定考虑的记录支持度来削减搜索空间。其中的支持度是一种基于用户事物在事物日志中出现的数目的度量。（5）遗传算法一种新的最佳化空间搜索方法，它应用算法的适应函数来决定搜索的方向，运用一些拟生物化的人工运算过程进行一代一代的周而复始的演化，求得一个最佳结果。特点是具有强固形与求值空间的独立性。强固形使问题的限制条件降到最低，并大幅度提高系统的容错能力；而求值空间的独立性则使遗传算法的设计单一化，且适用于多种不同性质、领域的问题。将遗传算法运用于数据挖掘，可以开采出与众不同的信息，是别的算法所不能替代的。（6）连机分析处理简称OLAP，是基于大型数据库或数据仓库的信息分析过
29、程，是大型数据库或数据仓库的用户接口部分，其目的是满足决策支持或多维环境特定的查询和报表要求。OLAP具有快速性、可分析性、多维性、信息性和共享性等特点，它是跨部门、面向主题的。OLAP不同于传统的连机事物处理的应用。OLAP主要是用来完成客户的事务处理，如民航、车船的订票系统等，通常要进行大量的更新操作，对响应时间要求也比较高。而OLAP主要是对用户当前及历史数据进行分析，辅助决策。其典型的应用有对银行信用卡风险的分析与预测等，主要是进行大量的查询操作，对时间的要求不太严格。（7）粗糙集粗糙集算法将知识理解为对数据的划分，每一被划分的集合称为概念，主要思想是利用已知的知识库，将不精确或不确定
30、的知识用已知的知识库中的知识来近似刻划处理粗糙集理论，是继概率论、模糊集、证据理论之后的又一个处理不确定性的数学工具。作为一种较新的软计算方法，粗糙集近年来越来越受到重视，其有效性已在许多科学与工程领域的成功应用中得到证实，是当前国际上人工智能理论及其应用领域中的研究热点之一。在很多实际系统中均不同程度地存在着不确定性因素，采集到的数据常常包含着噪声，不精确甚至不完整。它将知识理解为对数据的划分，每一被划分的集合称为概念，主要思想是利用已知的知识库，将不精确或不确定的知识用已知的知识库中的知识来近视刻划处理。2.4数据挖掘的功能数据挖掘的功能是从大型数据集中提取人们感兴趣的知识，这些知识是隐含
31、的、具有一定可信度的、对用户而言是新颖的且有潜在价值的知识，提取的知识表示为概念、规则、模式等多种形式。一般情况下，数据挖掘的任务可以大体分为两类：描述和预测。描述性挖掘任务描述数据库中数据的一般性质，而预测性挖掘任务是指对当前数据进行处理、分析和推断，以做出相应的预测。数据挖掘在实际的工作中，有时候用户并不清楚自己需要什么样的数据，因此数据挖掘工作有必要挖掘出多种类型的模式，以达到满足不同的用户需求和应用。一般情况下，数据挖掘的功能以及可能发现的模式类型如下：（1）分类目的是构造一个分类函数或分类模型（也常常称作分类器），该模型能把数据库中的数据项映射到给定类别中的某一个。要构造分类器，需要
32、有一个训练样本数据集作为输入。训练集由一组数据库记录或元组构成，每个元组是一个由有关字段（又称属性或特征）值组成的特征向量，此外，训练样本还有一个类别标记。一个具体样本的形式可表示为：（v1，v2，vn；c），其中vi表示字段值，c表示类别。 例如：银行部门根据以前的数据将客户分成了不同的类别，现在就可以根据这些来区分新申请贷款的客户，以采取相应的贷款方案。（2）关联分析关联分析就是从大量的数据中发现项集之间有趣的关联或因果结构。关联分析展示了属性与值频繁的在给定的数据集中的一起出现的条件。一般如下形式： 如XY，即“|A1.AnB1.Bn”的规则。其中，Ai (i1,.m),Bj (j1,.
33、n)是属性值对。关联规则XY即表示：“满足X中条件的数据库元组多半也满足Y中的条件”。 简而言之，就是分析两个事物之间的一些特性，通过一个事物去预测另外一个事物，这就是关联分析。（3）概念/类描述概念描述（concept description）就是通过对与某类对象关联数据的汇总、分析和比较，对此类对象的内涵进行描述，并概括这类对象的有关特征。这种描述是汇总的、简洁的和精确的知识。 （4）聚类分析聚类分析就是将物理或抽象对象的集合分组成由类似的对象组成的多个类的过程。聚类是把整个数据库分成不同的群组。它的目的是使群与群之间差别很明显，而同一个群之间的数据尽量相似。这种方法通常用于客户细分。在开
34、始细分之前不知道要把用户分成几类，因此通过聚类分析可以找出客户特性相似的群体，如客户消费特性相似或年龄特性相似等。在此基础上可以制定一些针对不同客户群体的营销方案。对象根据最大化类内部的相似性、最小化类之间的相似性的原则进行聚类或分组。也就是说，对象的簇（cluster）这样形成，使得相比之下在一个簇中的对象具有很高的相似性，而与其他簇中的对象很不相似。所形成的每个簇可以看作一个对象类，由它可以导出规则。聚类也便于分类法组织形式（taxonomy formation），将观测组织成类分层结构，把类似的事件组织在一起。通过聚类，人们能够认识到密集和稀疏的区域，因而发现全局的分类模式，以及数据属性
35、之前的相互关系。（5）离群点分析数据库中可能包含一些数据对象，它们与数据的一般行为或模型不一致。这些数据对象是离群点（outlier）。大部分数据挖掘方法将离群点视为噪声或异常而丢弃。然而，在一些应用中（如欺骗检测），罕见的事件可能比正常出现的事件更令人感兴趣。离群点数据分析称作离群点挖掘（outlier mining）。可以假定一个数据分布或概率模型，使用统计检验检测离群点；或者使用距离度量，将远离任何簇的对象视为离群点。基于偏差的方法通过考察一群对象主要特征上的差别来识别离群点，而不是使用统计或距离度量。（6） 演变分析数据演变分析（evolution analysis）描述行为随时间变化
36、的对象的规律或趋势，并对其建模。尽管这可能包括时间相关数据的特征化、区分、关联和相关分析、分类、预测或聚类，这类分析的不同特点包括时间序列数据分析、序列或周期模式匹配和基于相似性的数据分析。2.5数据挖掘应用的成功案例（1）、中国宝钢集团（直接数据挖掘，分类分析方法） 宝钢自1985年投产至今，积累了大量的生产数据，从每一炉钢到每一块板坯到每一个钢圈，各级计算机系统可以把这些数据完整地收集起来。采用数据挖掘技术对钢材生产的全流程进行质量监控和分析（通过全流程实时监控获得了丰富的生产数据），构建故障地图，实时分析产品出现瑕疵的原因，有效提高了产品的优良率。 宝钢采用了两个数据挖掘工具，一个是自行
37、研发的基于SAS的practical Miner，另一个是美国SAS公司的Enterprise Miner。在冷轧和热轧的产品质量控制中，仅2001年就取得超过3000万元的经济效益。在配矿优化项目中，通过确定不同铁矿石的合理比例，每年可为宝钢降低成本6000万元。另外，通过分析轧制计划，分析和优化库存结构，降低库存成本和平衡物流成本Credilogros Ca Financiera S.A. 是阿根廷第五大信贷公司，资产估计价值为9570万美元，对于Credilogros而言，重要的是识别与潜在预先付款客户相关的潜在风险，以便将承担的风险最小化。（2）、沃尔玛超市里的尿布与啤酒（间接数据挖掘
38、，关联规则）大家都应该了解这个事件，数据挖掘中的经典成功案例。在一家超市里，有一个有趣的现象：尿布和啤酒赫然摆在一起出售。但是这个奇怪的举措却使尿布和啤酒的销量双双增加了。沃尔玛拥有世界上最大的数据仓库系统，为了能够准确了解顾客在其门店的购买习惯，沃尔玛对其顾客的购物行为进行购物篮分析，想知道顾客经常一起购买的商品有哪些。沃尔玛数据仓库里集中了其各门店的详细原始交易数据。在这些原始交易数据的基础上，沃尔玛利用数据挖掘方法对这些数据进行分析和挖掘。一个意外的发现是：跟尿布一起购买最多的商品竟是啤酒！经过大量实际调查和分析，揭示了一个隐藏在尿布与啤酒背后的美国人的一种行为模式：在美国，一些年轻的父
39、亲下班后经常要到超市去买婴儿尿布，而他们中有30%40%的人同时也为自己买一些啤酒。产生这一现象的原因是：美国的太太们常叮嘱她们的丈夫下班后为小孩买尿布，而丈夫们在买尿布后又随手带回了他们喜欢的啤酒。（3）、股票预测股票市场是一个具有大量相互作用因素的复杂系统，它受政治形势、金融政策、公司状况和重大消息等多方面因素的影响。股票价格一般要受一国货币、财政政策、物价、利率、汇率、上市公司重大事项、国际经济环境、投资者心理等信息的作用，其内部规律非常复杂，变化周期无序，更使行情的走势变化莫测。 利用决策树分类算法中的ID3算法并适当调整以对股票交易数据样本集进行测试分析，由此生成决策树作为分类器并对
40、其结果进行了检验，最后根据决策树分类规则开发出一淘股票分析预测系统。更早之前，通过相关分析，可以找出一支股票与另一支股票走势的潜在规律，比如数据挖掘曾经得到过这个结论“如果微软的股票下跌4%，那么IBM的股票将在两周内下跌5%”2.7本章小结本章在介绍数据挖掘基本概念的基础上，简要的概括了数据挖掘的过程、数据挖掘的方法、数据挖掘的功能，并简要介绍了几个数据挖掘应用的成功案例。这些基本理论知识为数据挖掘的实践应用研究奠定了理论基础。3 决策树技术3.1决策树简介随着社会的发展，数据挖掘显的尤为的重要。在数据挖掘中决策树算法是目前数据挖掘领域中应用的最广泛、最流行的推理算法之一。决策树分类算法是将
41、数据分类、预测和规格的提取。随着ID3算法和C4.5算法的提出，决策树技术在数据挖掘领域得到了进一步的拓展，并且在人们生产生活中得到了广泛应用。决策树是一种根据自变量的值进行递归划分以及预测因变量的方法。决策树的主要作用是揭示数据中的结构化信息。它提供一种在什么条件下会得到什么值的类似规则的方法。若因变量为分类变量，我们称相应的决策树为分类树；若因变量为连续变量，我们称相应的决策树为回归树。分类树对离散变量做决策树，回归树对连续变量做决策树。一般的数据挖掘工具，允许选择分裂条件和修剪规则，以及控制参数（最小结点的大小，最大树的深度等等），来限制决策树的。决策树作为一棵树，树的根节点是整个数据集
42、合空间，每个分节点是对一个单一变量的测试，该测试将数据集合空间分割成两个或更多块。每个叶节点是属于一类别的记录。图3.1为以典型的决策树。图3.1 决策树3.2决策树的主要算法近年来，决策树方法在很多机器学习、知识的探究等过程中得到了广泛的应用。迄今为止，国内外研究人员先后提出了十几种决策树的分类方法，因此决策树的算法还是挺多的，本文介绍了两种比较经典的决策树算法，分别是ID3算法和C4.5算法。3.2.1 ID3算法ID3(induction decision-tree)算法，它是一种用来由数据构造决策树的递归过程，是在1986年由Quinlan首先提出的，该算法以信息论为基础，信息论是数学
43、中的概率论和数理统计的一个分支，用于处理信息和信息熵、通信系统、数据传输和率失真理论、密码学、信噪比、数据压缩和相关课题。以信息熵和信息增益度为衡量标准，从而实现数据的归纳分类，它是一个从上到下、分而治之 的归纳过程。ID3算法的大概过程是：我们试探性的选择一个属性放置在根节点，并对该属性的每个值产生一个分支。这样，分裂根节点上的数据集，并一道子女节点，产生一个局部的树。在决策树各级结点上选择属性时，通过计算信息增益来选择属性，以使得在每一个非叶结点进行测试时，能获得关于被测试记录的最大的类别信息。其具体方法是：我们需要检测所有的属性，在它们中间选择信息增益最大的属性作为决策树结点，由该属性的
44、不同取值建立分支，再对各分支的子集递归调用该方法建立决策树结点的分支，直到所有的子集仅包含同一类别的数据为止。最后得到的一棵决策树，它可以用来对新的样本进行分类。要想了解ID3算法，我们要了解ID3算法中的一些基本概念：（1）熵熵是一个物理名词，源于热力学的概念，数值为温度除热量所得的值。1948年Shannon提出并发展了信息论并引入了信息熵。一个训练集合S根据类别属性的值被分成m个互相独立的类C1、C2、.、Cn，则识别D的一个元组所属哪个类所需的信息量为Info（S）。设Ci，d 是S中Ci类的元组的集合， Cn的概率分布，P=P1,Pn，任意元组属于分类Ci的概率为Pi，则由该分布传递
45、的信息量称为S的熵，记为：Info（S）= Pilog2（Pi）Plog2 P-Plog2 P上述公式中，p+代表正样例，而p-则代表反样例。（2）信息增益度信息增益度是两个信息量之间的差值，已经有了熵作为衡量训练样例集合纯度的标准，现在可以定义属性分类训练数据的效力的度量标准。这个标准被称为“信息增益（informationgain）”。简单的说，一个属性的信息增益就是由于使用这个属性分割样例而导致的期望熵降低(或者说，样本按照某属性划分时造成熵减少的期望)。更精确地讲，一个属性A相对样例集合S的信息增益Gain(S,A)被定义为：G（S,A）=Info（D）-Info（A）最后根据信息增益
46、最大的原则选择根节点来构成决策树。3.2.2 C4.5算法C4.5是机器学习算法中的另一个分类决策树算法，它是基于ID3算法进行改进后的一种重要算法，相比于ID3算法，改进有如下几个要点：1、用信息增益率来选择属性。ID3选择属性用的是子树的信息增益，这里以用很多方法来定义信息，ID3使用的是熵（entropy， 熵是一种不纯度度量准则），也就是熵的变化值，而C4.5用的是信息增益率。2、在决策树构造过程中进行剪枝，因为某些具有很少元素的结点可能会使构造的决策树过适应（Overfitting），如果不考虑这些结点可能会更好。3、对非离散数据也能处理。4、能够对不完整数据进行处理由于ID3算法在实际应用中的一些局限，Quinlan再次改进了ID3算法。C4.5算法是ID3算法的改进版本，C4.5算法可以处理多种数据类型。此外，C4.5的效率相比于ID3算法也有了很多的提高。通过对ID3算法的介绍我们已经了解熵，和信息增益。在C4.5算法中我们引入了新的概念信息增益率。 C4.5算法的具体步骤如下：（1）创建节点N；（2）如果训练集为空，在返回节点N标记为Failure；（3）如果训练集中的所有记录都属于同一个类别，则以该类别标记节点N；（4）如果候选属性为空，则返回N作为叶节点，标记为训练集中最普通的类；（5）for each
