数据挖掘——决策树
序言
决策树(Decision Tree）是在已知各种情况发生概率的基础上，通过构成决策树来求取净现值的期望值大于等于零的概率，评价项目风险，判断其可行性的决策分析方法，是直观运用概率分析的一种图解法。由于这种决策分支画成图形很像一棵树的枝干，故称决策树。在机器学习中，决策树是一个预测模型，他代表的是对象属性与对象值之间的一种映射关系。Entropy = 系统的凌乱程度，使用算法ID3, C4.5和C5.0生成树算法使用熵。这一度量是基于信息学理论中熵的概念。
决策树易于理解和实现，人们在在学习过程中不需要使用者了解很多的背景知识，这同时是它的能够直接体现数据的特点，只要通过解释后都有能力去理解决策树所表达的意义。对于决策树，数据的准备往往是简单或者是不必要的，而且能够同时处理数据型和常规型属性，在相对短的时间内能够对大型数据源做出可行且效果良好的结果。易于通过静态测试来对模型进行评测，可以测定模型可信度；如果给定一个观察的模型，那么根据所产生的决策树很容易推出相应的逻辑表达式。
I
数据挖掘——决策树
目录
一、引言 ...............................................................................................................1 二、数据挖掘 .......................................................................................................1 三、决策树算法介绍 ...........................................................................................3 四、决策树算法分类 ...........................................................................................6 五、ID3学习算法 ................................................................................................6 六、结论 ...............................................................................................................9 七、决策树代码 ...................................................................................................9
II
数据挖掘——决策树
数据挖掘中决策树算法的研究
一、引言
在激烈的市场竞争中，信息对于企业的生存和发展越来越起到至关重要的作用，随着数据库技术的迅速发展以及数据库管理系统的广泛应用，数据库中表达信息的数据亦随着时间和业务的发展而急剧膨胀，人们需要对数据进行更高层次的处理，从中找出规律和模式，以帮助人们更好的利用数据进行决策和研究。目前的数据库系统虽然可以实现高效的数据录入、查询、统计等功能，却无法发现数据中存在的关系和规则，无法根据现有的数据预测未来的发展趋势。由于缺乏挖掘数据背后隐藏的知识的手段，导致了“数据爆炸但知识贫乏”的现象，面对“人们被数据淹没，人们却饥饿于知识”的挑战，数据挖掘和知识发现技术应运而生，并得以蓬勃发展，越来越显示出其强大的生命力。
数据挖掘的核心部分是为数据集建立模型的过程，不同的数据挖掘方法构造数据模型的方式也不相同，在进行数据挖掘时可采用许多不同的方法，例如神经网络、决策树、遗传算法和可视化技术等，同时同一方法下又有数以百计的派生方法。决策树算法是数据挖掘常用的方法之一，但它一直未受到人们重视，直到1984年Breiman等人合著出版了《分类和回归树》一书，决策树方法才开始被统计学界接受并获得了信赖，并很快得到推广应用。现在很多公司的数据挖掘产品中都采用了决策树数据挖掘算法，J.R.Quinlan对决策树算法作出了详细的理论描述决策树算法中一种广为人知的算法就是ID3算法，是1986年由Quinlan提出的一种基于信息墒的决策树算法，近年来在很多知识发现领域得到应用，很多学者针对ID3算法进行研究。
二、数据挖掘
(一)数据挖掘概念
图 1-1
1
数据挖掘——决策树
数据挖掘，在人工智能领域，习惯上又称为数据库中知识发现(Knowledge Discovery in Database, KDD)， 也有人把数据挖掘视为数据库中知识发现过程的一个基本步骤。知识发现过程以下三个阶段组成：（1）数据准备，（2）数据挖掘，（3）结果表达和解释。数据挖掘可以与用户或知识库交互。
并非所有的信息发现任务都被视为数据挖掘。例如，使用数据库管理系统查找个别的记录，或通过因特网的搜索引擎查找特定的Web页面，则是信息检索（information retrieval）领域的任务。虽然这些任务是重要的，可能涉及使用复杂的算法和数据结构，但是它们主要依赖传统的计算机科学技术和数据的明显特征来创建索引结构，从而有效地组织和检索信息。尽管如此，数据挖掘技术也已用来增强信息检索系统的能力。
数据挖掘可以在任何类型的数据上进行,即可以来自社会科学,又可以来自自然科学产生的数据,还可以是卫星观测得到的数据。数据形式和结构也各不相同,可以是传统的关系数据库,可以是面向对象的高级数据库系统,也可以是面向特殊应用的数据库,如空间数据库、时序数据库、文本数据库和多媒体数据库等,还可以是Web数据信息。
数据挖掘的目标是从海量数据中发现隐含的、有意义的知识。它的任务主要是分类、预测、时间序列模式、聚类分析、关联分析预测和偏差分析等。
分类：分类就是按照一定的标准把数据对象划归成不同类别的过程。
预测：预测就是通过对历史数据的分析找出规律,并建立模型,通过模型对未来数据的种类和特征进行分析。
时间序列模式：时间序列模式就是根据数据对象随时间变化的规律或趋势来预测将来的值。 聚类分析：聚类分析是在没有给定划分类的情况下,根据数据信息的相似度进行数据聚集的一种方法。
关联分析预测：关联分析就是对大量的数据进行分析,从中发现满足一定支持度和可信度的数据项之间的联系规则。
偏差分析：偏差分析就是通过对数据库中的孤立点数据进行分析,寻找有价值和意义的信息。
(二)数据挖掘的过程
数据挖掘使用一定的算法从实际应用数据中挖掘出未知、有价值的模式或规律等知识,整个过程由数据准备、数据挖掘、模式评估、结果分析和运用知识等步骤组成。
数据准备：数据挖掘的处理对象是数据,这些数据一般存储在数据库系统中,是长期积累的结果。但往往不适合直接在这些数据上进行知识挖掘,首先要清除数据噪声和与挖掘主题明显无关的数据;其次将来自多数据源中的相关数据组合并;然后将数据转换为易于进行数据挖掘的数据存储形式,这就是数据准备。
数据挖掘：数据挖掘就是根据数据挖掘的目标,选取相应算法及参数,分析准备好的数据,产生一个特定的模式或数据集,从而得到可能形成知识的模式模型。
模式评估：由挖掘算法产生的模式规律,存在无实际意义或无实用价值的情况,也存在不能准确反映数据的真实意义的情况,甚至在某些情况下与事实相反,因此需要对其进行评估,从挖掘结果中筛选出有意义的模式规律。在此过程中,为了取得更为有效的知识,可能会返回前面的某一处理步骤中以反复提取,从而提取出更有效的知识。
（三）数据挖掘的常用方法
决策树方法：决策树是一种常用于预测模型的算法,它通过一系列规则将大量数据有目的分类,从中找到一些有价值的、潜在的信息。它的主要优点是描述简单,分类速度快,易于理解、精度较高,特别适合大规模的数据处理,在知识发现系统中应用较广。它的主要缺点是很难基于多个变量组合发现规则。在数据挖掘中,决策树方法主要用于分类。
2
数据挖掘——决策树
神经网络方法：神经网络是模拟人类的形象直觉思维,在生物神经网络研究的基础上,根据生物神经元和神经网络的特点,通过简化、归纳、提炼总结出来的一类并行处理网络,利用其非线性映射的思想和并行处理的方法,用神经网络本身结构来表达输入和输出的关联知识。
粗糙集方法：粗糙集理论是一种研究不精确、不确定知识的数学工具。粗糙集处理的对象是类似二维关系表的信息表。目前成熟的关系数据库管理系统和新发展起来的数据仓库管理系统,为粗糙集的数据挖掘奠定了坚实的基础。粗糙集理论能够在缺少先验知识的情况下,对数据进行分类处理。在该方法中知识是以信息系统的形式表示的,先对信息系统进行归约,再从经过归约后的知识库抽取得到更有价值、更准确的一系列规则。因此,基于粗糙集的数据挖掘算法实际上就是对大量数据构成的信息系统进行约简,得到一种属性归约集的过程,最后抽取规则。
遗传算法：遗传算法是一种基于生物自然选择与遗传机理的随机搜索算法。数据挖掘是从大量数据中提取人们感兴趣的知识,这些知识是隐含的、事先未知的、潜在有用的信息。因此,许多数据挖掘问题可以看成是搜索问题,数据库或者数据仓库为搜索空间,挖掘算法是搜索策略。应用遗传算法在数据库中进行搜索,对随机产生的一组规则进行进化,直到数据库能被该组规则覆盖,就可以挖掘出隐含在数据库中的规则。
三、决策树算法介绍
（一）决策树简介
决策树是分类应用中采用最广泛的模型之一。与神经网络和贝叶斯方法相比，决策树无须花费大量的时间和进行上千次的迭代来训练模型，适用于大规模数据集，除了训练数据中的信息外不再需要其他额外信息，表现了很好的分类精确度。其核心问题是测试属性选择的策略，以及对决策树进行剪枝。连续属性离散化和对高维大规模数据降维，也是扩展决策树算法应用范围的关键技术。
决策树的结构,顾名思义,就像一棵树。它利用树的结构将数据记录进行分类,树的一个叶结点就代表某个条件下的一个记录集,根据记录字段的不同取值建立树的分支;在每个分支子集中重复建立下层结点和分支,便可生成一棵决策树。
(二)归纳学习
归纳学习是符号学习中研究的最为广泛的一种方法。它着眼于从一组无次序、无规则的实力中，找出蕴涵规律，事例一般是基于属性理论的，有特定的属性值得到问题某个结论，给定关于某个概念的一系列已知的正例和反例，其任务是从中归纳出一个通用概念描述。它能够获得新的概念，创立新的规则，发现新的理论。它的一般的操作是泛化和特化。泛化用来扩展假设的语义信息，以使其包含更多的正例，应用于更多的情况。特化是泛化的相反操作，用于限制概念描述的应用范围。分类算法是归类学习的一种类型。
(三)分类算法概述
分类算法是数据挖掘中的一个重要课题，可用于预测和决策。分类算法也是数据挖掘算法中很很重要的一种，决策树（decision tree）算法是主要分类算法之一。
分类问题可描述为：输入数据，或称训练集（Training set），是一条条的数据库记录组成的。每一条记录包含若干属性，组成一个特征向量，训练集的每条记录还有一个特定的标签类与之对应，该类标签是系统的输入，通常是以往的一些经验数据。一个具体样本的形式可为样本向量：
3