决策树是分类应用中采用最广泛的模型之一。

与神经网络和贝叶斯方法相比，决策树无须花费大量的时间和进行上千次的迭代来训练模型，适用于大规模数据集，除了训练数据中的信息外不再需要其他额外信息，表现了很好的分类精确度。

其核心问题是测试属性选择的策略，以及对决策树进行剪枝。

连续属性离散化和对高维大规模数据降维，也是扩展决策树算法应用范围的关键技术。

本文以决策树为研究对象，主要研究内容有：首先介绍了数据挖掘的历史、现状、理论和过程，然后详细介绍了三种决策树算法，包括其概念、形式模型和优略性，并通过实例对其进行了分析研究目录一、引言 (1)二、数据挖掘 (2)(一)概念 (2)(二)数据挖掘的起源 (2)(三)数据挖掘的对象 (3)(四)数据挖掘的任务 (3)(五)数据挖掘的过程 (3)(六)数据挖掘的常用方法 (3)(七)数据挖掘的应用 (5)三、决策树算法介绍 (5)(一)归纳学习 (5)(二)分类算法概述 (5)(三)决策树学习算法 (6)1、决策树描述 (7)2、决策树的类型 (8)3、递归方式 (8)4、决策树的构造算法 (8)5、决策树的简化方法 (9)6、决策树算法的讨论 (10)四、ID3、C4.5和CART算法介绍 (10)(一)ID3学习算法 (11)1、基本原理 (11)2、ID3算法的形式化模型 (13)（二）C4.5算法 (14)（三）CART算法 (17)1、CART算法理论 (17)2、CART树的分支过程 (17)（四）算法比较 (19)五、结论 (24)参考文献...................................................................................... 错误！未定义书签。

致谢.............................................................................................. 错误！未定义书签。

数据挖掘中决策树算法的研究一、引言在激烈的市场竞争中，信息对于企业的生存和发展越来越起到至关重要的作用，随着数据库技术的迅速发展以及数据库管理系统的广泛应用，数据库中表达信息的数据亦随着时间和业务的发展而急剧膨胀，人们需要对数据进行更高层次的处理，从中找出规律和模式，以帮助人们更好的利用数据进行决策和研究。

目前的数据库系统虽然可以实现高效的数据录入、查询、统计等功能，却无法发现数据中存在的关系和规则，无法根据现有的数据预测未来的发展趋势。

由于缺乏挖掘数据背后隐藏的知识的手段，导致了“数据爆炸但知识贫乏”的现象，面对“人们被数据淹没，人们却饥饿于知识”的挑战，数据挖掘和知识发现技术应运而生，并得以蓬勃发展，越来越显示出其强大的生命力。

数据挖掘的核心部分是为数据集建立模型的过程，不同的数据挖掘方法构造数据模型的方式也不相同，在进行数据挖掘时可采用许多不同的方法，例如神经网络、决策树、遗传算法和可视化技术等，同时同一方法下又有数以百计的派生方法。

决策树算法是数据挖掘常用的方法之一，但它一直未受到人们重视，直到1984年Breiman等人合著出版了《分类和回归树》一书，决策树方法才开始被统计学界接受并获得了信赖，并很快得到推广应用。

现在很多公司的数据挖掘产品中都采用了决策树数据挖掘算法，J.R.Quinlan对决策树算法作出了详细的理论描述决策树算法中一种广为人知的算法就是ID3算法，是1986年由Quinlan提出的一种基于信息墒的决策树算法，近年来在很多知识发现领域得到应用，很多学者针对ID3算法进行研究。

本课题主要研究了ID3算法、C4.5算法等的优势和略势，比较了各算法在实际应用中的好处和不足。

二、数据挖掘(一)概念图 1-1数据挖掘，在人工智能领域，习惯上又称为数据库中知识发现(Knowledge Discovery in Database, KDD)，也有人把数据挖掘视为数据库中知识发现过程的一个基本步骤。

知识发现过程以下三个阶段组成：（1）数据准备，（2）数据挖掘，（3）结果表达和解释。

数据挖掘可以与用户或知识库交互。

并非所有的信息发现任务都被视为数据挖掘。

例如，使用数据库管理系统查找个别的记录，或通过因特网的搜索引擎查找特定的Web页面，则是信息检索（information retrieval）领域的任务。

虽然这些任务是重要的，可能涉及使用复杂的算法和数据结构，但是它们主要依赖传统的计算机科学技术和数据的明显特征来创建索引结构，从而有效地组织和检索信息。

尽管如此，数据挖掘技术也已用来增强信息检索系统的能力。

(二)数据挖掘的起源要是发明之母。

近年来，数据挖掘引起了信息产业界的极大关注，其主要原因是存在大量数据，可以广泛使用，并且迫切需要将这些数据转换成有用的信息和知识。

获取的信息和知识可以广泛用于各种应用，包括商务管理，生产控制，市场分析，工程设计和科学探索等。

(三)数据挖掘的对象数据挖掘可以在任何类型的数据上进行,即可以来自社会科学,又可以来自自然科学产生的数据,还可以是卫星观测得到的数据。

数据形式和结构也各不相同,可以是传统的关系数据库,可以是面向对象的高级数据库系统,也可以是面向特殊应用的数据库,如空间数据库、时序数据库、文本数据库和多媒体数据库等,还可以是Web数据信息。

(四)数据挖掘的任务数据挖掘的目标是从海量数据中发现隐含的、有意义的知识。

它的任务主要是分类、预测、时间序列模式、聚类分析、关联分析预测和偏差分析等。

分类：分类就是按照一定的标准把数据对象划归成不同类别的过程。

预测：预测就是通过对历史数据的分析找出规律,并建立模型,通过模型对未来数据的种类和特征进行分析。

时间序列模式：时间序列模式就是根据数据对象随时间变化的规律或趋势来预测将来的值。

聚类分析：聚类分析是在没有给定划分类的情况下,根据数据信息的相似度进行数据聚集的一种方法。

关联分析预测：关联分析就是对大量的数据进行分析,从中发现满足一定支持度和可信度的数据项之间的联系规则。

偏差分析：偏差分析就是通过对数据库中的孤立点数据进行分析,寻找有价值和意义的信息。

(五)数据挖掘的过程数据挖掘使用一定的算法从实际应用数据中挖掘出未知、有价值的模式或规律等知识,整个过程由数据准备、数据挖掘、模式评估、结果分析和运用知识等步骤组成。

数据准备：数据挖掘的处理对象是数据,这些数据一般存储在数据库系统中,是长期积累的结果。

但往往不适合直接在这些数据上进行知识挖掘,首先要清除数据噪声和与挖掘主题明显无关的数据;其次将来自多数据源中的相关数据组合并;然后将数据转换为易于进行数据挖掘的数据存储形式,这就是数据准备。

数据挖掘：数据挖掘就是根据数据挖掘的目标,选取相应算法及参数,分析准备好的数据,产生一个特定的模式或数据集,从而得到可能形成知识的模式模型。

模式评估：由挖掘算法产生的模式规律,存在无实际意义或无实用价值的情况,也存在不能准确反映数据的真实意义的情况,甚至在某些情况下与事实相反,因此需要对其进行评估,从挖掘结果中筛选出有意义的模式规律。

在此过程中,为了取得更为有效的知识,可能会返回前面的某一处理步骤中以反复提取,从而提取出更有效的知识。

巩固知识：解释并评估结果.其使用的分析方法一般应作数据挖掘操作而定,通常会用到可视化技术.运用知识：将分析所得到的知识集成到业务信息系统的组织结构中去.(六)数据挖掘的常用方法决策树方法：决策树是一种常用于预测模型的算法,它通过一系列规则将大量数据有目的分类,从中找到一些有价值的、潜在的信息。

它的主要优点是描述简单,分类速度快,易于理解、精度较高,特别适合大规模的数据处理,在知识发现系统中应用较广。

它的主要缺点是很难基于多个变量组合发现规则。

在数据挖掘中,决策树方法主要用于分类。

神经网络方法：神经网络是模拟人类的形象直觉思维,在生物神经网络研究的基础上,根据生物神经元和神经网络的特点,通过简化、归纳、提炼总结出来的一类并行处理网络,利用其非线性映射的思想和并行处理的方法,用神经网络本身结构来表达输入和输出的关联知识。

粗糙集方法：粗糙集理论是一种研究不精确、不确定知识的数学工具。

粗糙集处理的对象是类似二维关系表的信息表。

目前成熟的关系数据库管理系统和新发展起来的数据仓库管理系统,为粗糙集的数据挖掘奠定了坚实的基础。

粗糙集理论能够在缺少先验知识的情况下,对数据进行分类处理。

在该方法中知识是以信息系统的形式表示的,先对信息系统进行归约,再从经过归约后的知识库抽取得到更有价值、更准确的一系列规则。

因此,基于粗糙集的数据挖掘算法实际上就是对大量数据构成的信息系统进行约简,得到一种属性归约集的过程,最后抽取规则。

遗传算法：遗传算法是一种基于生物自然选择与遗传机理的随机搜索算法。

数据挖掘是从大量数据中提取人们感兴趣的知识,这些知识是隐含的、事先未知的、潜在有用的信息。

因此,许多数据挖掘问题可以看成是搜索问题,数据库或者数据仓库为搜索空间,挖掘算法是搜索策略。

应用遗传算法在数据库中进行搜索,对随机产生的一组规则进行进化,直到数据库能被该组规则覆盖,就可以挖掘出隐含在数据库中的规则。

(七)数据挖掘的应用数据挖掘技术在各个需要进行信息分析的领域得到十分广泛的应用。

它可以带来显著的经济效益,不仅可以控制成本,也可以给企业带来更多效益。

在金融业,可以通过信用卡历史数据的分析,判断哪些人有风险,哪些人没有;在超市,可以通过对超市交易信息的分析,安排货价货物摆设,以提高销售收入;在保险业,可以通过对保险公司客户记录的分析,来判定哪些客户是花费昂贵的对象;在学校,可以通过分析学校学生课程及成绩等信息,来判断课程之间的关系。

此外,在医学中,可以利用数据挖掘技术对疾病发作前后症状的分析,来对病症进行诊断;在体育运动中,利用数据挖掘技术对对抗性强的积极运动进行分析,发现对方弱点,制定有效的战术。

三、决策树算法介绍(一)归纳学习归纳学习是符号学习中研究的最为广泛的一种方法。

它着眼于从一组无次序、无规则的实力中，找出蕴涵规律，事例一般是基于属性理论的，有特定的属性值得到问题某个结论，给定关于某个概念的一系列已知的正例和反例，其任务是从中归纳出一个通用概念描述。

它能够获得新的概念，创立新的规则，发现新的理论。

它的一般的操作是泛化和特化。

泛化用来扩展假设的语义信息，以使其包含更多的正例，应用于更多的情况。

特化是泛化的相反操作，用于限制概念描述的应用范围。

分类算法是归类学习的一种类型。

(二)分类算法概述分类算法是数据挖掘中的一个重要课题，可用于预测和决策。

分类算法也是数据挖掘算法中很很重要的一种，决策树（decision tree）算法是主要分类算法之一。