决策树是分类应用中采用最广泛的模型之一。与神经网络和贝叶斯方法相比，决策树无须花费大量的时间和进行上千次的迭代来训练模型，适用于大规模数据集，除了训练数据中的信息外不再需要其他额外信息，表现了很好的分类精确度。其核心问题是测试属性选择的策略，以及对决策树进行剪枝。连续属性离散化和对高维大规模数据降维，也是扩展决策树算法应用范围的关键技术。本文以决策树为研究对象，主要研究内容有：首先介绍了数据挖掘的历史、现状、理论和过程，然后详细介绍了三种决策树算法，包括其概念、形式模型和优略性，并通过实例对其进行了分析研究
目录
一、引言........................................................................................................................ I I
二、数据挖掘.............................................................................................................. III
(一)概念...............................................................................................................III
(二)数据挖掘的起源...........................................................................................III
(三)数据挖掘的对象.......................................................................................... IV
(四)数据挖掘的任务.......................................................................................... IV
(五)数据挖掘的过程.......................................................................................... IV
(六)数据挖掘的常用方法.................................................................................. IV
(七)数据挖掘的应用.......................................................................................... VI
三、决策树算法介绍.................................................................................................. VI
(一)归纳学习...................................................................................................... VI
(二)分类算法概述.............................................................................................. VI
(三)决策树学习算法......................................................................................... VII
1、决策树描述....................................................................................... V III
2、决策树的类型..................................................................................... IX
3、递归方式............................................................................................. IX
4、决策树的构造算法............................................................................. IX
5、决策树的简化方法............................................................................... X
6、决策树算法的讨论............................................................................. XI
四、ID3、C4.5和CART算法介绍.......................................................................... XI
(一)ID3学习算法 ............................................................................................. XII
1、基本原理............................................................................................ XII
2、ID3算法的形式化模型................................................................... XIV
（二）C4.5算法............................................................................................... X V
（三）CART算法........................................................................................ X VIII
1、CART算法理论 ............................................................................ X VIII
2、CART树的分支过程 .................................................................... X VIII
（四）算法比较 ............................................................................................... X X
五、结论.................................................................................................................. X XV
参考文献...................................................................................... 错误！未定义书签。
致谢.............................................................................................. 错误！未定义书签。
数据挖掘中决策树算法的研究
一、引言
在激烈的市场竞争中，信息对于企业的生存和发展越来越起到至关重要的作用，随着数据库技术的迅速发展以及数据库管理系统的广泛应用，数据库中表达信息的数据亦随着时间和业务的发展而急剧膨胀，人们需要对数据进行更高层次的处理，从中找出规律和模式，以帮助人们更好的利用数据进行决策和研究。目前的数据库系统虽然可以实现高效的数据录入、查询、统计等功能，却无法发现数据中存在的关系和规则，无法根据现有的数据预测未来的发展趋势。由于缺乏挖掘数据背后隐藏的知识的手段，导致了“数据爆炸但知识贫乏”的现象，面对“人们被数据淹没，人们却饥饿于知识”的挑战，数据挖掘和知识发现技术应运而生，并得以蓬勃发展，越来越显示出其强大的生命力。
数据挖掘的核心部分是为数据集建立模型的过程，不同的数据挖掘方法构造数据模型的方式也不相同，在进行数据挖掘时可采用许多不同的方法，例如神经网络、决策树、遗传算法和可视化技术等，同时同一方法下又有数以百计的派生方法。决策树算法是数据挖掘常用的方法之一，但它一直未受到人们重视，直到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）算法是主要分类算法之一。
分类问题可描述为：输入数据，或称训练集（Training set），是一条
条的数据库记录组成的。每一条记录包含若干属性，组成一个特征向量，训练集的每条记录还有一个特定的标签类与之对应，该类标签是系统的输入，通常是以往的一些经验数据。一个具体样本的形式可为样本向量：(
v,2v,……, n v;c)。这里的n v表示字段值，c表示类别。
1
分类的目的是分析输入数据，通过在训练集中的数据表现出来的特性，为每个类找到一种准确的描述或者模型。由此生成的类用来对未来的测试数据进行分类。尽管这些未来的测试数据的类标签是未知的，我们仍可以由此预测这些新数据所属的类。注意，是预测而不是肯定。我们也可以由此对数据中的每一个类有更好的理解，或者说我们获得了这个类的知识。
分类器评价或比较尺度主要有三种：
预测准确度预测准确度是用的最多的一种比较尺度，特别是对于预测型分类任务，目前公认的方法的分层交叉验证法。
计算复杂度计算复杂度依赖于具体的实现细节和硬件环境，在数据挖掘中，由于操作对象是巨量的数据库因此空间和时间的复杂度问题将是非常重要的一个环节。
模型描述的简洁度对于描述型的分类任务，模型描述越简洁越受欢迎;例如采用规则表示的分类器构造法就比较简单，而神经网络方法产生的结果就难以理解。
(三)决策树学习算法
决策树学习算法是以实例为基础的归纳学习算法，通常用来形成分类
器和预测模型，可以对未知数据进行分类或预测、数据预处理、数据挖掘等。它通常包括两部分：树的生成和树的剪枝。
1、决策树描述
一颗决策树的内部结点是属性或属性的集合，叶节点是所要学习划分的类，内部结点的属性称为测试属性。当经过一批训练实例集的训练产生一颗决策树，决策树可以根据属性的取值对一个未知实例集进行分类。使用决策树对实例进行分类的时候，有树根开始对该对象的属性逐渐测试其值，并且顺着分支向下走，直至到达某个叶结点，此叶结点代表的类即为该对象所处的类。
决策树是一个可以自动对数据进行分类的树型结构，是树形结构的知识表示，可以直接转换为决策规则，它能被看作一棵树的预测模型，树的根节点是整个数据集合空间，每个分节点是一个分裂问题，它是对一个单一变量的测试，给测试将数据集合空间分割成两个或更多块，每个叶结点是带有分类的数据分割。决策树也可以解释成一种特殊形式的规则集，其特征是规则的层次组织关系。决策树算法主要是用来学习以离散型变量作为属性类型的学习方法。连续型变量必须被离散化才能被学习。表1给出了决策树与自然树的对应关系以及在分类问题中的代表含义。
表1
自然树对应决策树中的意义分类问题中的表示意义
树根根节点训练实例整个数据集空间
杈内部（非叶）结点、决策结点待分类对象的属性（集合）
树枝分支属性的一个可能取值
叶子叶结点、状态结点数据分割（分类结果）
2、决策树的类型
决策树的内节点的测试属性可能是单变量的，即每个内节点只包含一个属性。也可能是多变量的，即存在包含多个属性的内节点。
根据测试属性的不同属性值的个数，可能使得每个内节点有两个或多个分支。如果每个内节点只有两个分支则称之为二叉决策树。
每个属性可能是值类型，也可能是枚举类型。
分类结果既可能是两类又可能是多类，如果二叉决策树的结果只能有两类则称之为布尔决策树。布尔决策树可以很容易以析取范式的方法表示，并且在决策树学习的最自然的情况就是学习析取概念。
3、递归方式
决策树学习采用自顶向下的递归方式，在决策树的内部结点进行属性值的比较并根据不同的属性值判断从该结点向下的分支，在决策树的叶结点得到结论。所以从根到叶结点的一条路径就对应着一条合取规则，整个决策树就对应着一组析取表达式规则。决策树生成算法分成两个步骤：一是树的生成，开始时所有数据都在根节点，然后递归的进行数据分片。二是树的修剪，就是去掉一些可能是噪音或异常的数据决策树停止分割的条件有：一个结点上的数据都是属于同一个类别；没有属性可以在用于对数据进行分割。
4、决策树的构造算法
c>},而
决策树的构造算法可通过训练集T完成，其中T={ j x=( a,2a,…, n a)为一个训练实例，它有n个属性，分别列于属性表1 （ A,2A,…，n A），其中i a表示属性i A的取值。j C∈C={1C, 2C,..., m C}为X 1 的分类结果。算法分以下几步： 从属性表中选择属性 A作为分类属性； i 若属性i A 的取值有i K 个，则将T 划分为i K 个子集1T ，…, i K T ,其中 ij T ={ 从属性表中删除属性i A ； 对于每一个ij T （1≤j ≤1K ），令T =ij T ； 如果属性表非空，返回（1），否则输出。 目前比较成熟的决策树方法有ID3、C4.5、CART 、SLIQ 等。 5、决策树的简化方法 在决策树学习过程中，如果决策树过于复杂，则存储所要花费的代价也就越大；而如果结点个数过多，则每个节点所包含的实例个数就越小，支持每个叶结点假设的实例个数也越小，学习后的错误率就随之增加；同时对用户来说难于理解，使得很大程度上分类器的构造没有意义，实践表明简单的假设更能反映事物之间的关系，所以在决策树学习中应该对决策树进行简化。 简化决策树的方法有控制树的规模、修改测试空间、修改测试属性、数据库约束、改变数据结构等。 控制树的规模可以采用预剪枝、后剪枝算法及增量树方法来实现，预剪枝算法不要求决策树的每一个叶结点都属于同一个类，而是在这之前就停止决策树的扩张，具体何时停止是其研究的主要内容，例如可以规定决策树的高度，达到一定高度即停止扩张；或计算扩张对系统性能的增益，如小于某个规定的值则停止扩张。后剪枝算法则首先利用增长集生成一颗未经剪枝的决策树T 并进行可能的修剪，把T 作为输入，再利用修剪集进 行选择，输出选择最好的规则。 6、决策树算法的讨论 基于决策树的学习算法具有建立速度快、精度高、可以生成可理解的规则、计算量相对来说不是很大、可以处理连续值和离散值属性、可以清晰的显示哪些属性比较重要等优点，另外在学习过程中不需要使用者了解很多背景知识，只要训练例子能够用属性——结论式的方式表达出来，就能使用该算法来学习。 决策树算法的缺点：对连续性的字段比较难预测；对有时间顺序的数据，需要很多预处理工作；当类别太多时，错误可能就会增加的比较快；算法分类时只是根据一个字段来分类。 决策树技术是一种“贪心”搜索，使用了贪心算法，它把每个属性值依次试探加入左子树，如果能够找到更大的信息增益那么就把这个属性值加入左子树，否则把它退回右子树。这样试探下去，直到左子树不能再变大为止，就能求到最大的属性值。贪心算法总是做出在当前看来最好的选择，并不从整体最优考虑，它所做出的选择只是在某种意义上的局部最优选择。 四、ID3、C4.5和CART算法介绍 决策树的生成算法主要有ID3、C4.5、CART、CHAID等方法。ID3算法在1979年由J.R.Quinlan提出，是机器学习中广为人知的一个算法，在归纳学习中，它代表着基于决策树方法的一大类，ID3及后来的C4.5均是Quinlan在Hunt的概念学习系统(Concept Learning System CLS) 上发展起来的一种自顶向下的学习算法，而C4.5算法又是Quinlan 本人针对ID3算法提出的一种改进算法，他在1993年出版了专著《机器学习规划》对C4.5算法进行了详细的描述。CHAID(即Chi-Square Automatic Interacion Detector 的缩写，卡方自动互动侦测器)算法是Gordon B.Kass 博士在1976年提出的，可用来对于分类性数据进行挖掘。CART (即Classification And Regression Tree 的缩写，分类回归树)算法从1984年开始得到普及推广，可对连续型因变量进行处理。针对这些算法的缺点，很多研究人员尝试在控制树的大小和简化决策树等方面作出努力，通过研究各种预剪枝算法和后剪枝算法来控制树的规模，同时在修改测试属性空间、改进测试属性选择方法、限制数据集、改变数据结构等方面提出了许多新的算法和标准。 本章只介绍ID3算法、C4.5算法和CART 算法。 (一)ID3学习算法 1、基本原理 信息熵在信息论中称为平均信息量，是对被传送的信息进行度量所采用的一种平均值。信源中被传送的信息包括有限数目的互斥并联合完备的事件，它们都以一定的概率出现，用数学式子来表示就是:一组事件1X ,… ,r X ，以既定概率p(1X ),…,p(r X )出现，其平均值H(X)就是信 息熵，它的值等于每个事件的(自)信息量I(X)的数学期望，即: 11 ()()()()log ()r r i i r r H X p Xi I Xi p X p X ===-=-∑∑ 传统ID3学习算是以信息熵(也称信息不确定性)的下降速度作为选取测试属性的标准。该算法根据属性集的取值选择实例的类别。它的核心是在决策树中各级结点上选择属性，用信息增益作为属性选择标准，使得在每一非叶结点进行测试时，能获得关于被测试例子最大的类别信息。使用该属性将例子集分成子集后，系统的熵值最小，期望该非叶结点到达各后代叶节点的平均路径最短，使生成的决策树平均深度较小。可以看出训练例集在目标分类方面越模糊越杂乱无序，它的熵就越高；训练例集在目标分类方面越清晰则越有序，它的熵越低，ID3算法就是根据“信息赢取(增益)越大的属性对训练例的分类越有利”的原则在算法的每一步选取“属性表中可对训练例集进行最佳分类的属性”。一个属性的信息增益就是由于使用这个属性分割样例而导致系统熵的降低，计算各个属性的信息赢取并加以比较是ID3算法的关键操作。 ID3算法的步骤如下： (1)选出整个训练实例集X的规模为W的随机子集Xl (W称为窗口规模，子集称为窗口)； (2)以使得信息熵的值最小为标准，选取每次的测试属性，形成当前窗口的决策树； (3)顺序扫描所有训练实例，找出当前的决策树的例外，如果没有例外则训练结束； (4)组合当前窗口的一些训练实例与某些在(3)中找到的例外形成新的窗口，转(2)。 2、ID3算法的形式化模型 ID3基本原理是基于两类分类问题，其数学模型可描述如下:设E = 1F *2F *…*n F 是n 维有穷向量空间，其中j F 是有穷离散符号集，E 中的元 素e=<1V ,2V ，…，n V >叫做实例，其中j V ∈j F , J=1,2, …, n 。设P 和N 是 E 和 F 的两个实例集，分别叫正例集和反例集。假设向量空间E 中的正例集PE 和反例集NE 的大小分别为P 和N, ID3基于下列两个假设： (1)在向量空间E 上的一棵正确决策树，对任意例子的分类概率同E 中的正、反例的概率一致。 (2)一棵决策树能对一实例作出正确类别判断所需的信息量(原集合E 的熵)为: ()log log P P N N E E P N P N P N P N =--++++ 如果以属性A 作为决策树的根，A 具有v 个值（1V 、2V …v V ），它将E 分为v 个子集（1E ,2E …v E ），假设i E 中含有i P 个正例和i N 个反例，子集i E 的信息熵为()i E E ： ()log log Pi Pi Ni Ni E Ei Pi Ni Pi Ni Pi Ni Pi Ni =--++++ 以属性A 为根分类后的信息熵（用A 分类后上的期望值）为E(A): 1()()v r Pi Ni E A E Ei P N =+=+∑ 因此，以属性为根的信息增益I （A ）是： ()()()I A E E E A =- ID3选择使I(A)最大(即E(A)最小)的属性A 作为根结点。对A 的不 同的取值对应的E 的v 个子集i E 递归调用上述过程，生成A 的子结点1B ，2B ，…，v B 。 ID3的基本原理是基于两类分类问题，但很容易扩展到多类。设样本集S 共有C 类样本，每类样本数为Pi,(i=1, 2, 3,…,c)。若以属性A 作为决策树的根，A 具有v 个值1V ， 2V ，…，v V ，它将E 分成v 个子集[1E ，2E ，…，v E ]，假设i E 中含有j 类样本的个数为ij P =1，2，…，c ，那么子集i E 的信息量是E(i E )为： 1 ()log ||||c j Pij Pij E Ei Ei Ei ==-∑ 以A 为根分类的信息熵为： 1||()()|| v i Ei E A E Ei E ==∑ 选择属性A 使公式6中E(A)最小，信息增益也将增大。 （二）C4.5算法 C4.5算法是由Quinlan 自己扩充ID3算法而提出的，是ID3算法的改进。C4.5算法每接受一个新的训练例就更新一次决策树。在C4.5的决策树中，每个结点都保存了可用于计算E 值的属性的信息，这些信息由属性的每个取值所对应的正例、反例计数组成。根据放在结点的信息，就可以判断出哪个属性的训练例集Es 值最小，从而确定当前用哪一个属性来进行划分。C4.5算法使用了一个适合小数据量的方法:基于训练例自身的性能估计。当然训练例进行估计很可能产生偏向于规则的结果，为了克服 这一点，C4.5算法采用了保守估计。它采用的具体方法是:计算规则对其使用的各个训练例分类的精度a ，然后计算这个精度的二项分布的标准差s ，最后对给定信任度(95%)，取下界(a-1.96)为该规则的性能度量pa;在有大量数据的情况下，s 接近于0,pa 接近于a;随着数据量的减少，pa 与a 的差别将会增大。C4.5算法使用更复杂的方法是为属性A 的各种取值赋以概率，具有未知属性A 值的实例按概率值分为大小不等的碎片，沿相应属性A 值的分支向树的下方分布，实例的碎片将用于计算信息赢取。这个实例碎片在学习后，还可以用来对属性值不全的新实例进行分类。 与ID3相比，C4.5主要改进如下： a.用信息增益率来选择属性，克服了用信息增益来选择属性时偏向选择值多的属性的不足。信息增益率定义为： (,)(,)(,)Gain S A GainRatio S A SplitInfo S A = 其中Gain(S,A)与ID3算法中的信息增益相同，而分裂信息SplitInfo(S,A)代表了按照属性A 分裂样本集S 的广度和均匀性。 |||| 21||(,)||Si c S i Si SplitInfo S A Log S ==-∑ 其中，1S 到c S 是c 个不同值的属性A 分割S 而形成的c 个样本子集。 b.可以处理连续数值型属性。例如，假设A 为一个连续的数值型属性，首先检查样本集中该属性的所有取值，然后将其按升序排列为1A ，2A ，…，m A 。对于每一个j A ，j=1，2，…，m-1，将样本集划分为两个样本子集， 一子集是各记录属性A 的值均小于等于j A ，另一子集是其各记录属性A 的值均大于j A 。对于每个划分，计算相应的信息增益率，然后选择增益 率最大的划分，作为属性A 的信息增益率。 c.为了避免树的高度无节制的增长，避免过度拟合数据，采用了一种后剪枝方法，该方法是从一种称为“规则后修剪”（rulepost-pruning ）的方法演变而来。该方法使用训练样本集本身来估计剪枝前后的误差，从而决定是否真正剪枝。方法中使用的公式如下： Pr[](1)/f q z c q q N ->=- 其中N 是实例的数量，f=E/N 为观 察到的误差率（其中E 为N 个实例中分类错误的个数），q 为真实的误差率，c 为置信度（C4.5算法的一个输入参数，一般情况下为0.25），z 为对应于置信度c 的标准差，其值可根据c 的设定值通过查正态分布表得到。通过该公式即可计算出真实误差率q 的一个置信度上限，用此上限为该节点误差率e 做一个悲观的估计： 222 22 241z f f z f Z N N N N e z N ++-+=+ 通过判断剪枝前后e 的大小，从而决定是否需要剪枝。 d.对于缺失值的处理。在某些情况下，可供使用的数据可能缺少某些属性的值。假如〈x ，c(x)〉是样本集S 中的一个训练实例，但是其属性A 的值A(x)未知。处理缺少属性值的一种策略是赋给它结点n 所对应的训练实例中该属性的最常见值；另外一种更复杂的策略是为A 的每个可能值赋予一个概率。例如，给定一个布尔属性A ，如果结点n 包含6个已知A=1 和4个A=0的实例，那么A(x)=1的概率是0.6，而A(x)=0的概率是0.4。于是，实例x的60%被分配到A=1的分支，40%被分配到另一个分支。这些片断样例（fractional examples）的目的是计算信息增益，另外，如果有第二个缺少值的属性必须被测试，这些样例可以在后继的树分支中被进一步细分。C4.5就是使用这种方法处理缺少的属性值。 （三）CART算法 1、CART算法理论 分类回归树CART是一种典型的二叉决策树，主要用来进行分类研究，可以同时处理连续变量和分类变量。如果目标变量是分类变量，则CART 生成分类决策树，如果目标变量是连续变量，则CART变量生成回归决策树。无论是分类决策树还是回归决策树，CART的首要目标都是构造一个准确的分类模型用来进行预测，即研究引起分类现象发生的变量及变量之间的作用，通过建立决策树和决策规则对类型未知的对象进行类别预测，即通过类型未知的对象的某些相关变量值就可以对其做出类型判定。 2、CART树的分支过程 CART算法在对一个节点进行分支时首先要确定一个最佳的分支预测变量以及该预测变量的最佳分支阀值点。然后将性质相同的对象分在同一个节点中，并且同一个父节点的两个子节点间具有显著的差异性。 CART算法选择指标的方法是使用“杂质函数”，当节点中数据都属于同一个类时，杂质函数值为0，当节点中的对象均匀分布与所有可能的类 时，杂质函数值最大。节点的杂质函数定义如下: 121t p p p ++∧+= 111(,,,)max J J J φ∧= (1,0,,0)(0,1,,0)(0,0,,1)0φφφ∧=∧=∧=∧= 其中t p 是节点t(包括根结点)中对象属于j 类的概率。类似的，树T 的杂质函数是树中包含的各个叶节点杂质函数的加权平均值。可以表示如下: 1()()n i i k N E T E t N ==∑ 这里n 是树T 中的叶节点个数，t N 是叶节点i 中的对象个数，N 是所 有叶节点中对象的总数或根节点中对象的数量，E(i t )是叶节点i 中的杂 质函数值。 CART 算法中最常使用的杂质函数是GINI 系数，其公式如下: 2121(,,,)21J j i j j i j j p p p p p P φ≠=∧==-∑∑ 因为对所有的j ，∑j p =1,并且0≤j p ≤1，所以GINI 系数总为正数， 除非其中的一个j p 为1,而其他均为0。此为，对于所有j,当j p =1/J 时， 这个函数达到最大值。对于一个节点，其分支前后的杂质应该减少的最多，也就是说分支后数据的纯度应该比分之前提高的最多。其中杂质的改变量为： (,)(){()()}l l r r E s t E t p E t p E t ?=-+ 这里t 是父节点；E （t ）是父节点t 的杂质函数值；E(1t )和E(r t )分别是分支后左右两个子节点的杂质函数值;而l p 和r p 分别是分支后左右 两个子节点中包含的对象百分比。大括号中的式子是左右两个子节点的杂质函数值的加权值，也是以节点t 为根节点的子树的杂质函数值。只有当子树的杂质含量少于树根的杂质含量时，进一步的分支才是有意义的。 树停止分支的时候有以下几种情况:分枝后的叶节点中的样本数小十给定的阀值；分枝后的叶节点中的样本属于同一类；节点中只包含一个对象。 （四）算法比较 用weka 软件分别以ID3、C4.5和CART 算法对以下数据集进行分类： 图 4-1 软件weka 视图： 决策树算法研究及应用? 王桂芹黄道 华东理工大学实验十五楼206室 摘要:信息论是数据挖掘技术的重要指导理论之一,是决策树算法实现的理论依据。决 策树算法是一种逼近离散值目标函数的方法,其实质是在学习的基础上,得到分类规则。本文简要介绍了信息论的基本原理,重点阐述基于信息论的决策树算法,分析了它们目前 主要的代表理论以及存在的问题,并用具体的事例来验证。 关键词:决策树算法分类应用 Study and Application in Decision Tree Algorithm WANG Guiqin HUANG Dao College of Information Science and Engineering, East China University of Science and Technology Abstract:The information theory is one of the basic theories of Data Mining,and also is the theoretical foundation of the Decision Tree Algorithm.Decision Tree Algorithm is a method to approach the discrete-valued objective function.The essential of the method is to obtain a clas-sification rule on the basis of example-based learning.An example is used to sustain the theory. Keywords:Decision Tree; Algorithm; Classification; Application 1 引言 决策树分类算法起源于概念学习系统CLS(Concept Learning System,然后发展 到ID3 3.1 分类与决策树概述 3.1.1 分类与预测 分类是一种应用非常广泛的数据挖掘技术，应用的例子也很多。例如，根据信用卡支付历史记录，来判断具备哪些特征的用户往往具有良好的信用；根据某种病症的诊断记录，来分析哪些药物组合可以带来良好的治疗效果。这些过程的一个共同特点是：根据数据的某些属性，来估计一个特定属性的值。例如在信用分析案例中，根据用户的“年龄”、“性别”、“收入水平”、“职业”等属性的值，来估计该用户“信用度”属性的值应该取“好”还是“差”，在这个例子中，所研究的属性“信用度”是一个离散属性，它的取值是一个类别值，这种问题在数据挖掘中被称为分类。 还有一种问题，例如根据股市交易的历史数据估计下一个交易日的大盘指数，这里所研究的属性“大盘指数”是一个连续属性，它的取值是一个实数。那么这种问题在数据挖掘中被称为预测。 总之，当估计的属性值是离散值时，这就是分类；当估计的属性值是连续值时，这就是预测。 3.1.2 决策树的基本原理 1.构建决策树 通过一个实际的例子，来了解一些与决策树有关的基本概念。 表3-1是一个数据库表，记载着某银行的客户信用记录，属性包括“姓名”、“年龄”、“职业”、“月薪”、......、“信用等级”，每一行是一个客户样本，每一列是一个属性（字段）。这里把这个表记做数据集D。 银行需要解决的问题是，根据数据集D，建立一个信用等级分析模型，并根据这个模型，产生一系列规则。当银行在未来的某个时刻收到某个客户的贷款申请时，依据这些规则，可以根据该客户的年龄、职业、月薪等属性，来预测其信用等级，以确定是否提供贷款给该用户。这里的信用等级分析模型，就可以是一棵决策树。在这个案例中，研究的重点是“信用等级”这个属性。给定一个信用等级未知的客户，要根据他/她的其他属性来估计“信用等级”的值是“优”、“良”还是“差”，也就是说，要把这客户划分到信用等级为“优”、“良”、“差”这3个类别的某一类别中去。这里把“信用等级”这个属性称为“类标号属性”。数据集D中“信用等级”属性的全部取值就构成了类别集合：Class={“优”， 数据挖掘方法综述 [摘要]数据挖掘（DM，DataMining）又被称为数据库知识发现（KDD,Knowledge Discovery in Databases）,它的主要挖掘方法有分类、聚类、关联规则挖掘和序列模式挖掘等。 [关键词]数据挖掘分类聚类关联规则序列模式 1、数据挖掘的基本概念 数据挖掘从技术上说是从大量的、不完全的、有噪声的、模糊的、随机的数据中提取隐含在其中的、人们事先不知道的、但又是潜在的有用的信息和知识的过程。这个定义包括好几层含义: 数据源必须是真实的、大量的、含噪声的、发现的是用户感兴趣的知识, 发现的知识要可接受、可理解、可运用, 并不要求发现放之四海皆准的知识, 仅支持特定的发现问题, 数据挖掘技术能从中自动分析数据进行归纳性推理从中发掘出潜在的数据模式或进行预测, 建立新的业务模型帮助决策者调整策略做出正确的决策。数据挖掘是是运用统计学、人工智能、机器学习、数据库技术等方法发现数据的模型和结构、发现有价值的关系或知识的一门交叉学科。数据挖掘的主要方法有分类、聚类和关联规则挖掘等 2、分类 分类（Classification）又称监督学习（Supervised Learning）。监 督学习的定义是：给出一个数据集D，监督学习的目标是产生一个联系属性值集合A和类标（一个类属性值称为一个类标）集合C的分类/预测函数，这个函数可以用于预测新的属性集合（数据实例）的类标。这个函数就被称为分类模型（Classification Model），或者是分类器（Classifier）。分类的主要算法有：决策树算法、规则推理、朴素贝叶斯分类、支持向量机等算法。 决策树算法的核心是Divide-and-Conquer的策略，即采用自顶向下的递归方式构造决策树。在每一步中，决策树评估所有的属性然后选择一个属性把数据分为m个不相交的子集，其中m是被选中的属性的不同值的数目。一棵决策树可以被转化成一个规则集，规则集用来分类。 规则推理算法则直接产生规则集合，规则推理算法的核心是Separate-and-Conquer的策略，它评估所有的属性-值对（条件），然后选择一个。因此，在一步中，Divide-and-Conquer策略产生m条规则，而Separate-and-Conquer策略只产生1条规则，效率比决策树要高得多，但就基本的思想而言，两者是相同的。 朴素贝叶斯分类的基本思想是：分类的任务可以被看作是给定一个测试样例d后估计它的后验概率，即Pr（C=c j︱d），然后我们考察哪个类c j对应概率最大，便将那个类别赋予样例d。构造朴素贝叶斯分类器所需要的概率值可以经过一次扫描数据得到，所以算法相对训练样本的数量是线性的，效率很高，就分类的准确性而言，尽管算法做出了很强的条件独立假设，但经过实际检验证明，分类的效果还是 import java.util.HashMap; import java.util.HashSet; import java.util.LinkedHashSet; import java.util.Iterator; //调试过程中发现4个错误，感谢宇宙无敌的调试工具——print //1、selectAtrribute中的一个数组下标出错 2、两个字符串相等的判断 //3、输入的数据有一个错误 4、selectAtrribute中最后一个循环忘记了i++ //决策树的树结点类 class TreeNode { String element; //该值为数据的属性名称 String value; //上一个分裂属性在此结点的值 LinkedHashSet 数据挖掘分类算法介绍 ----------------------------------------------------------------------------------------------------------------------------- 分类是用于识别什么样的事务属于哪一类的方法，可用于分类的算法有决策树、bayes分类、神经网络、支持向量机等等。 决策树 例1 一个自行车厂商想要通过广告宣传来吸引顾客。他们从各地的超市获得超市会员的信息，计划将广告册和礼品投递给这些会员。 但是投递广告册是需要成本的，不可能投递给所有的超市会员。而这些会员中有的人会响应广告宣传，有的人就算得到广告册不会购买。 所以最好是将广告投递给那些对广告册感兴趣从而购买自行车的会员。分类模型的作用就是识别出什么样的会员可能购买自行车。 自行车厂商首先从所有会员中抽取了1000个会员，向这些会员投递广告册，然后记录这些收到广告册的会员是否购买了自行车。 数据如下： 在分类模型中，每个会员作为一个事例，居民的婚姻状况、性别、年龄等特征作为输入列，所需预测的分类是客户是否购买了自行车。 使用1000个会员事例训练模型后得到的决策树分类如下： ※图中矩形表示一个拆分节点，矩形中文字是拆分条件。 ※矩形颜色深浅代表此节点包含事例的数量，颜色越深包含的事例越多，如全部节点包含所有的1000个事例，颜色最深。经过第一次基于年龄的拆分后，年龄大于67岁的包含36个事例，年龄小于32岁的133个事例，年龄在39和67岁之间的602个事例，年龄32和39岁之间的229个事例。所以第一次拆分后，年龄在39和67岁的节点颜色最深，年龄大于67岁的节点颜色最浅。 ※节点中的条包含两种颜色，红色和蓝色，分别表示此节点中的事例购买和不购买自行车的比例。如节点“年龄>=67”节点中，包含36个事例，其中28个没有购买自行车，8个购买了自行车，所以蓝色的条比红色的要长。表示年龄大于67的会员有74.62%的概率不购买自行车，有23.01%的概率购买自行车。 在图中，可以找出几个有用的节点： 1. 年龄小于32岁，居住在太平洋地区的会员有7 2.75%的概率购买自行车； 2. 年龄在32和39岁之间的会员有68.42%的概率购买自行车； 3. 年龄在39和67岁之间，上班距离不大于10公里，只有1辆汽车的会员有66.08%的概率购买自行车； 1 分类的概念及分类器的评判 分类是数据挖掘中的一个重要课题。分类的目的是学会一个分类函数或分类模型（也常常称作分类器），该模型能把数据库中的数据项映射到给定类别中的某一个。分类可用于提取描述重要数据类的模型或预测未来的数据趋势。 分类可描述如下：输入数据，或称训练集（training set）是一条条记录组成的。每一条记录包含若干条属性（attribute），组成一个特征向量。训练集的每条记录还有一个特定的类标签（类标签）与之对应。该类标签是系统的输入，通常是以往的一些经验数据。一个具体样本的形式可为样本向量：(v1,v2,…,…vn:c)。在这里vi表示字段值，c表示类别。 分类的目的是：分析输入数据，通过在训练集中的数据表现出来的特性，为每一个类找到一种准确的描述或者模型。这种描述常常用谓词表示。由此生成的类描述用来对未来的测试数据进行分类。尽管这些未来的测试数据的类标签是未知的，我们仍可以由此预测这些新数据所属的类。注意是预测，而不能肯定。我们也可以由此对数据中的每一个类有更好的理解。也就是说：我们获得了对这个类的知识。 对分类器的好坏有三种评价或比较尺度： 预测准确度：预测准确度是用得最多的一种比较尺度，特别是对于预测型分类任务，目前公认的方法是10番分层交叉验证法。 计算复杂度：计算复杂度依赖于具体的实现细节和硬件环境，在数据挖掘中，由于操作对象是巨量的数据库，因此空间和时间的复杂度问题将是非常重要的一个环节。 模型描述的简洁度：对于描述型的分类任务，模型描述越简洁越受欢迎；例如，采用规则表示的分类器构造法就更有用。 分类技术有很多，如决策树、贝叶斯网络、神经网络、遗传算法、关联规则等。本文重点是详细讨论决策树中相关算法。 决策树分类算法 学号：20120311139 学生所在学院：软件工程学院学生姓名：葛强强 任课教师：汤亮 教师所在学院：软件工程学院2015年11月 12软件1班 决策树分类算法 葛强强 12软件1班 摘要：决策树方法是数据挖掘中一种重要的分类方法，决策树是一个类似流程图的树型结构，其中树的每个内部结点代表对一个属性的测试，其分支代表测试的结果，而树的每个 叶结点代表一个类别。通过决策树模型对一条记录进行分类，就是通过按照模型中属 性测试结果从根到叶找到一条路径，最后叶节点的属性值就是该记录的分类结果。 关键词：数据挖掘，分类，决策树 近年来，随着数据库和数据仓库技术的广泛应用以及计算机技术的快速发展，人们利用信息技术搜集数据的能力大幅度提高，大量数据库被用于商业管理、政府办公、科学研究和工程开发等。面对海量的存储数据，如何从中有效地发现有价值的信息或知识，是一项非常艰巨的任务。数据挖掘就是为了应对这种要求而产生并迅速发展起来的。数据挖掘就是从大型数据库的数据中提取人们感兴趣的知识，这些知识是隐含的、事先未知的潜在有用的信息，提取的知识表示为概念、规则、规律、模式等形式。 分类在数据挖掘中是一项非常重要的任务。 分类的目的是学会一个分类函数或分类模型，把数据库中的数据项映射到给定类别中的某个类别。分类可用于预测，预测的目的是从历史数据记录中自动推导出对给定数据的趋势描述，从而能对未来数据进行预测。分类算法最知名的是决策树方法，决策树是用于分类的一种树结构。 1决策树介绍 决策树（decisiontree）技术是用于分类和预测 的主要技术，决策树学习是一种典型的以实例为基础的归纳学习算法，它着眼于从一组无次序、无规则的事例中推理出决策树表示形式的分类规则。它采用自顶向下的递归方式，在决策树的内部节点进行属性的比较，并根据不同属性判断从该节点向下的分支，在决策树的叶节点得到结论。所以从根到叶节点就对应着一条合取规则，整棵树就对应着一组析取表达式规则。 把决策树当成一个布尔函数。函数的输入为物体或情况的一切属性（property），输出为”是”或“否”的决策值。在决策树中，每个树枝节点对应着一个有关某项属性的测试，每个树叶节点对应着一个布尔函数值，树中的每个分支，代表测试属性其中一个可能的值。 最为典型的决策树学习系统是ID3，它起源于概念学习系统CLS，最后又演化为能处理连续属性的C4．5（C5．0）等。它是一种指导的学习方法，该方法先根据训练子集形成决策树。如果该树不能对所有给出的训练子集正确分类，那么选择一些其它的训练子集加入到原来的子集中，重复该过程一直到时形成正确的决策集。当经过一批训练实例集的训练产生一棵决策树，决策树可以根据属性的取值对一个未知实例集进行分类。使用决策树对实例进行分类的时候，由树根开始对该对象的属性逐渐测试其值，并且顺着分支向下走，直至到达某个叶结点，此叶结点代表的类即为该对象所处的类。 决策树是应用非常广泛的分类方法，目前有多种决策树方法，如ID3，C4．5，PUBLIC， 决策树是分类应用中采用最广泛的模型之一。与神经网络和贝叶斯方法相比，决策树无须花费大量的时间和进行上千次的迭代来训练模型，适用于大规模数据集，除了训练数据中的信息外不再需要其他额外信息，表现了很好的分类精确度。其核心问题是测试属性选择的策略，以及对决策树进行剪枝。连续属性离散化和对高维大规模数据降维，也是扩展决策树算法应用范围的关键技术。本文以决策树为研究对象，主要研究内容有：首先介绍了数据挖掘的历史、现状、理论和过程，然后详细介绍了三种决策树算法，包括其概念、形式模型和优略性，并通过实例对其进行了分析研究 目录 一、引言 (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) 参考文献...................................................................................... 错误！未定义书签。 致谢.............................................................................................. 错误！未定义书签。 实验四决策树 一、实验目的 1.了解典型决策树算法 2.熟悉决策树算法的思路与步骤 3.掌握运用Matlab对数据集做决策树分析的方法 二、实验内容 1.运用Matlab对数据集做决策树分析 三、实验步骤 1.写出对决策树算法的理解 决策树方法是数据挖掘的重要方法之一，它是利用树形结构的特性来对数据进行分类的一种方法。决策树学习从一组无规则、无次序的事例中推理出有用的分类规则，是一种实例为基础的归纳学习算法。决策树首先利用训练数据集合生成一个测试函数，根据不同的权值建立树的分支，即叶子结点，在每个叶子节点下又建立层次结点和分支，如此重利生成决策树，然后对决策树进行剪树处理，最后把决策树转换成规则。决策树的最大优点是直观，以树状图的形式表现预测结果，而且这个结果可以进行解释。决策树主要用于聚类和分类方面的应用。 决策树是一树状结构，它的每一个叶子节点对应着一个分类，非叶子节点对应着在某个属性上的划分，根据样本在该属性上的不同取值将其划分成若干个子集。构造决策树的核心问题是在每一步如何选择适当的属性对样本进行拆分。对一个分类问题，从已知类标记的训练样本中学习并构造出决策树是一个自上而下分而治之的过程。 2.启动Matlab，运用Matlab对数据集进行决策树分析，写出算法名称、数据集名称、关键代码，记录实验过程，实验结果，并分析实验结果 (1)算法名称: ID3算法 ID3算法是最经典的决策树分类算法。ID3算法基于信息熵来选择最佳的测试属性，它选择当前样本集中具有最大信息增益值的属性作为测试属性；样本集的划分则依据测试属性的取值进行，测试属性有多少个不同的取值就将样本集划分为多少个子样本集，同时决策树上相应于该样本集的节点长出新的叶子节点。ID3算法根据信息论的理论，采用划分后样本集的不确定性作为衡量划分好坏的标准，用信息增益值度量不确定性：信息增益值越大，不确定性越小。因此，ID3算法在每个非叶节点选择信息增益最大的属性作为测试属性，这样可以得到当前情况下最纯的划分，从而得到较小的决策树。 ID3算法的具体流程如下： 1）对当前样本集合，计算所有属性的信息增益； 2）选择信息增益最大的属性作为测试属性，把测试属性取值相同的样本划为同一个子样本集； 3）若子样本集的类别属性只含有单个属性，则分支为叶子节点，判断其属性值并标上相应的符号，然后返回调用处；否则对子样本集递归调用本算法。 (2)数据集名称：鸢尾花卉Iris数据集 选择了部分数据集来区分Iris Setosa（山鸢尾）及Iris Versicolour（杂色鸢尾）两个种类。 决策树分类算法的时间和性能测试 姓名：ls 学号： 目录 一、项目要求 (3) 二、基本思想 (3) 三、样本处理 (4) 四、实验及其分析 (9) 1.总时间 (9) 2.分类准确性. (12) 五、结论及不足 (13) 附录 (14) 一、项目要求 (1)设计并实现决策树分类算法（可参考网上很多版本的决策树算法及代码， 但算法的基本思想应为以上所给内容）。 (2)使用UCI 的基准测试数据集，测试所实现的决策树分类算法。评价指标 包括：总时间、分类准确性等。 (3) 使用UCI Iris Data Set 进行测试。 二、基本思想 决策树是一个类似于流程图的树结构，其中每个内部节点表示在一个属性变量上的测试，每个分支代表一个测试输出，而每个叶子节点代表类或分布，树的最顶层节点是根节点。 当需要预测一个未知样本的分类值时，基于决策树，沿着该树模型向下追溯，在树的每个节点将该样本的变量值和该节点变量的阈值进行比较，然后选取合适的分支，从而完成分类。决策树能够很容易地转换成分类规则，成为业务规则归纳系统的基础。 决策树算法是非常常用的分类算法，是逼近离散目标函数的方法，学习得到的函数以决策树的形式表示。其基本思路是不断选取产生信息增益最大的属性来划分样例集和，构造决策树。信息增益定义为结点与其子结点的信息熵之差。信息熵是香农提出的，用于描述信息不纯度(不稳定性)，其计算公式是 Pi为子集合中不同性(而二元分类即正样例和负样例)的样例的比例。这样信息收益可以定义为样本按照某属性划分时造成熵减少的期望，可以区分训练样本中正负样本的能力，其计算公式是 贝叶斯分类算法 学号：20120311108 学生所在学院：软件工程学院学生姓名：朱建梁 任课教师：汤亮 教师所在学院：软件工程学院 2015年11月 12软件1班 贝叶斯分类算法 朱建梁 12软件1班 摘要：贝叶斯分类是一类分类算法的总称，这类算法均以贝叶斯定理为基础，故统称为贝叶斯分类。本文作为分类算法的第一篇，将首先介绍分类问题，对分类问题进行一个正 式的定义。然后，介绍贝叶斯分类算法的基础——贝叶斯定理。最后，通过实例讨论 贝叶斯分类中最简单的一种：朴素贝叶斯分类。 关键词：朴素贝叶斯；文本分类 1 贝叶斯分类的基础——贝叶斯定理 每次提到贝叶斯定理，我心中的崇敬之情都油然而生，倒不是因为这个定理多高深，而是因为它特别有用。这个定理解决了现实生活里经常遇到的问题：已知某条件概率，如何得到两个事件交换后的概率，也就是在已知P(A|B)的情况下如何求得P(B|A)。这里先解释什么是条件概率： P(A|B)表示事件B已经发生的前提下，事件A发生的概率，叫做事件B发生下事件A的条件概率。其基本求解公式为：P(A|B)=P(AB)/P(B)。 贝叶斯定理之所以有用，是因为我们在生活中经常遇到这种情况：我们可以很容易直接得出P(A|B)，P(B|A)则很难直接得出，但我们更关心P(B|A)，贝叶斯定理就为我们打通从P(A|B)获得P(B|A)的道路。 下面不加证明地直接给出贝叶斯定理：P(B|A)=P(A|B)P(B)/P(A) 2 朴素贝叶斯分类的原理与流程 朴素贝叶斯分类是一种十分简单的分类算法，叫它朴素贝叶斯分类是因为这种方法的思想真的很朴素，朴素贝叶斯的思想基础是这样的：对于给出的待分类项，求解在此项出现的条件下各个类别出现的概率，哪个最大，就认为此待分类项属于哪个类别。通俗来说，就好比这么个道理，你在街上看到一个黑人，我问你你猜这哥们哪里来的，你十有八九猜非洲。为什么呢？因为黑人中非洲人的比率最高，当然人家也可能是美洲人或亚洲人，但在没有其它可用信息下，我们会选择条件概率最大的类别，这就是朴素贝叶斯的思想基础。 朴素贝叶斯分类的正式定义如下： 1、X={a1,a2,....am}设为一个待分类项，而每个a为x的一个特征属性。 2、有类别集合c={y1,y2,...,yn} 3、计算p(y1|x),p(y2|x),...,p(yn|x)。 4、如果p(yk|x)=max{p(y1|x),p(y2|x),...,p(yn|x)}， 那么现在的关键就是如何计算第3步中的各个条件概率。我们可以这么做： 1、找到一个已知分类的待分类项集合，这个集合叫做训练样本集。 2、统计得到在各类别下各个特征属性的条件概率估计。即p(a1|y1),p(a2|y1),...,p(am|y1);p(a1|y2),p(a2|y2),...,p(am|y2);p(a1|yn),p(a2 |yn),...,p(am|yn);。 数据挖掘中的文本挖掘的分类算法综述 摘要 随着Internet上文档信息的迅猛发展，文本分类成为处理和组织大量文档数据的关键技术。本文首先对数据挖掘进行了概述包括数据挖掘的常用方法、功能以及存在的主要问题；其次对数据挖掘领域较为活跃的文本挖掘的历史演化、研究现状、主要内容、相关技术以及热点难点问题进行了探讨；在第三章先分析了文本分类的现状和相关问题，随后详细介绍了常用的文本分类算法，包括KNN 文本分类算法、特征选择方法、支持向量机文本分类算法和朴素贝叶斯文本分类算法；；第四章对KNN文本分类算法进行深入的研究，包括基于统计和LSA降维的KNN文本分类算法；第五章对数据挖掘、文本挖掘和文本分类的在信息领域以及商业领域的应用做了详细的预测分析；最后对全文工作进行了总结和展望。 关键词：数据挖掘，文本挖掘，文本分类算法 ABSTRACT With the development of Web 2.0, the number of documents on the Internet increases exponentially. One important research focus on how to deal with these great capacity of online documents. Text classification is one crucial part of information management. In this paper we first introduce the basic information of data mining, including the methods, contents and the main existing problems in data mining fields; then we discussed the text mining, one active field of data mining, to provide a basic foundation for text classification. And several common algorithms are analyzed in Chapter 3. In chapter 4 thorough research of KNN text classification algorithms are illustrated including the statistical and dimension reduction based on LSA and in chapter 5 we make some predictions for data mining, text mining and text classification and finally we conclude our work. KEYWORDS： data mining, text mining, text classification algorithms，KNN 目录 摘要 (1) ABSTRACT (1) 目录 (1) 基于专家知识的决策树分类 概述 基于知识的决策树分类是基于遥感影像数据及其他空间数据，通过专家经验总结、简单的数学统计和归纳方法等，获得分类规则并进行遥感分类。分类规则易于理解，分类过程也符合人的认知过程，最大的特点是利用的多源数据。 如图1所示，影像+DEM就能区分缓坡和陡坡的植被信息，如果添加其他数据，如区域图、道路图土地利用图等，就能进一步划分出那些是自然生长的植被，那些是公园植被。 图1.JPG 图1 专家知识决策树分类器说明图 专家知识决策树分类的步骤大体上可分为四步：知识（规则）定义、规则输入、决策树运行和分类后处理。 1.知识（规则）定义 规则的定义是讲知识用数学语言表达的过程，可以通过一些算法获取，也可以通过经验总结获得。 2.规则输入 将分类规则录入分类器中，不同的平台有着不同规则录入界面。 3.决策树运行 运行分类器或者是算法程序。 4.分类后处理 这步骤与监督/非监督分类的分类后处理类似。 知识（规则）定义 分类规则获取的途径比较灵活，如从经验中获得，坡度小于20度，就认为是缓坡，等等。也可以从样本中利用算法来获取，这里要讲述的就是C4.5算法。 利用C4.5算法获取规则可分为以下几个步骤： （1）多元文件的的构建：遥感数据经过几何校正、辐射校正处理后，进行波段运算，得到一些植被指数，连同影像一起输入空间数据库；其他空间数据经过矢量化、格式转换、地理配准，组成一个或多个多波段文件。 （2）提取样本，构建样本库：在遥感图像处理软件或者GIS软件支持下，选取合适的图层，采用计算机自动选点、人工解译影像选点等方法采集样本。 （3）分类规则挖掘与评价：在样本库的基础上采用适当的数据挖掘方法挖掘分类规则，后基于评价样本集对分类规则进行评价，并对分类规则做出适当的调整和筛选。这里就是C4.5算法。 4.5算法的基本思路基于信息熵来“修枝剪叶”，基本思路如下： 从树的根节点处的所有训练样本D0开始，离散化连续条件属性。计算增益比率，取GainRatio（C0）的最大值作为划分点V0，将样本分为两个部分D11和D12。对属性C0的每一个值产生一个分支，分支属性值的相应样本子集被移到新生成的子节点上，如果得到的样本都属于同一个类，那么直接得到叶子结点。相应地将此方法应用于每个子节点上，直到节点的所有样本都分区到某个类中。到达决策树的叶节点的每条路径表示一条分类规则，利用叶列表及指向父结点的指针就可以生成规则表。 朴素贝叶斯： 有以下几个地方需要注意： 1. 如果给出的特征向量长度可能不同，这是需要归一化为通长度的向量（这里以文本分类为例），比如说是句子单词的话，则长度为整个词汇量的长度，对应位置是该单词出现的次数。 2. 计算公式如下： 其中一项条件概率可以通过朴素贝叶斯条件独立展开。要注意一点就是的计算方法，而由朴素贝叶斯的前提假设可知， = ，因此一般有两种，一种是在类别为ci的那些样本集中，找到wj出现次数的总和，然后除以该样本的总和；第二种方法是类别为ci的那些样本集中，找到wj出现次数的总和，然后除以该样本中所有特征出现次数的总和。 3. 如果中的某一项为0，则其联合概率的乘积也可能为0，即2中公式的分子为0，为了避免这种现象出现，一般情况下会将这一项初始化为1，当然为了保证概率相等，分母应对应初始化为2（这里因为是2类，所以加2，如果是k类就需要加k，术语上叫做laplace 光滑, 分母加k的原因是使之满足全概率公式）。 朴素贝叶斯的优点： 对小规模的数据表现很好，适合多分类任务，适合增量式训练。 缺点： 对输入数据的表达形式很敏感。 决策树： 决策树中很重要的一点就是选择一个属性进行分枝，因此要注意一下信息增益的计算公式，并深入理解它。 信息熵的计算公式如下: 其中的n代表有n个分类类别（比如假设是2类问题，那么n=2）。分别计算这2类样本在总样本中出现的概率p1和p2，这样就可以计算出未选中属性分枝前的信息熵。 现在选中一个属性xi用来进行分枝，此时分枝规则是：如果xi=vx的话，将样本分到树的一个分支；如果不相等则进入另一个分支。很显然，分支中的样本很有可能包括2个类别，分别计算这2个分支的熵H1和H2,计算出分枝后的总信息熵H’=p1*H1+p2*H2.，则此时的信息增益ΔH=H-H’。以信息增益为原则，把所有的属性都测试一边，选择一个使增益最大的属性作为本次分枝属性。 决策树的优点： 计算量简单，可解释性强，比较适合处理有缺失属性值的样本，能够处理不相关的特征； 缺点： 容易过拟合（后续出现了随机森林，减小了过拟合现象）； Logistic回归： Logistic是用来分类的，是一种线性分类器，需要注意的地方有： 1. logistic函数表达式为： 其导数形式为： 2. logsitc回归方法主要是用最大似然估计来学习的，所以单个样本的后验概率为： 到整个样本的后验概率： 决策树分类算法 决策树是一种用来表示人们为了做出某个决策而进行的一系列判断过程的树形图。决策树方法的基本思想是：利用训练集数据自动地构造决策树，然后根据这个决策树对任意实例进行判定。 1．决策树的组成 决策树的基本组成部分有：决策节点、分支和叶，树中每个内部节点表示一个属性上的测试，每个叶节点代表一个类。图1就是一棵典型的决策树。 图1 决策树 决策树的每个节点的子节点的个数与决策树所使用的算法有关。例如，CART算法得到的决策树每个节点有两个分支，这种树称为二叉树。允许节点含有多于两个子节点的树称为多叉树。 下面介绍一个具体的构造决策树的过程，该方法 是以信息论原理为基础，利用信息论中信息增益寻找数据库中具有最大信息量的字段，建立决策树的一个节点，然后再根据字段的不同取值建立树的分支，在每个分支中重复建立树的下层节点和分支。 ID3算法的特点就是在对当前例子集中对象进行分类时，利用求最大熵的方法，找出例子集中信息量（熵）最大的对象属性，用该属性实现对节点的划分，从而构成一棵判定树。 首先，假设训练集C 中含有P 类对象的数量为p ，N 类对象的数量为n ，则利用判定树分类训练集中的对象后，任何对象属于类P 的概率为p/(p+n)，属于类N 的概率为n/(p+n)。 当用判定树进行分类时，作为消息源“P ”或“N ”有关的判定树，产生这些消息所需的期望信息为： n p n log n p n n p p log n p p )n ,p (I 22++-++- = 如果判定树根的属性A 具有m 个值｛A 1, A 2, …, A m ｝，它将训练集C 划分成｛C 1, C 2, …, C m ｝，其中A i 包括C 中属性A 的值为A i 的那些对象。设C i 包括p i 个类P 对象和n i 个类N 对象，子树C i 所需的期望信息是I(p i , n i )。以属性A 作为树根所要求的期望信息可以通过加权平均得到 决策树决策树研发二部 目录 1. 算法介绍 (1) 1.1. 分支节点选取 (1) 1.2. 构建树 (3) 1.3. 剪枝 (10) 2. sk-learn 中的使用 (12) 3. sk-learn中源码分析 (13) 1. 算法介绍 决策树算法是机器学习中的经典算法之一，既可以作为分类算法，也可以作 为回归算法。决策树算法又被发展出很多不同的版本，按照时间上分，目前主要包括，ID3、C4.5和CART版本算法。其中ID3版本的决策树算法是最早出现的，可以用来做分类算法。C4.5是针对ID3的不足出现的优化版本，也用来做分类。CART也是针对 ID3优化出现的，既可以做分类，可以做回归。 决策树算法的本质其实很类似我们的if-elseif-else语句，通过条件作为分支依据，最终的数学模型就是一颗树。不过在决策树算法中我们需要重点考虑选取分支条件的理由，以及谁先判断谁后判断，包括最后对过拟合的处理，也就是剪枝。这是我们之前写if语句时不会考虑的问题。 决策树算法主要分为以下3个步骤： 1. 分支节点选取 2. 构建树 3. 剪枝 1.1. 分支节点选取 分支节点选取，也就是寻找分支节点的最优解。既然要寻找最优，那么必须要有一个衡量标准，也就是需要量化这个优劣性。常用的衡量指标有熵和基尼系数。 熵：熵用来表示信息的混乱程度，值越大表示越混乱，包含的信息量也就越多。比如，A班有10个男生1个女生，B班有5个男生5个女生，那么B班的熵值就比A班大，也就是B班信息越混乱。 Entropy = -V p ” 基尼系数：同上，也可以作为信息混乱程度的衡量指标。 Gini = 1 - p： l-L 电子商务数据挖掘的常用公式和算法 汇总几何平均数 )]lg ...lg (lg 1[lg )(2111321321n n n n n x x x n x x x x x x x x +++=?????=?????-总体方差2 σN x /)(22∑-=μσ标准方差 把2σ开平方根就得到标准方差N x /)(2 ∑-= μσ随机变量的概率分布 随机变量的概率分布可以用下面的公式表示： ) ()(x X P x f <= 极差标准化 极差标准化是数据标准化的另外一种常用方式。对纪录值进行极差标准化变换是将各个纪录 极差正规化 相似度公式 ||||*||||),cos(),(B A B A B A B A similarity ?= =关于βF 的通用公式 recall precision recall precision F +???+=22 )1(βββ当β=1时，所表示的就是F1的公式 recall precision recall precision F +??=21PR 值 PR 值的简化公式是： ∑∈=u B v v L v PR u PR )()()(在公式中)(u PR 、)(v PR 是页面u 和v 的PR 值，)(v L 是页面v 的外链数，u B 是链向页面u 的所有页面集合。 消除重复记录的算法 消除重复记录的算法有优先队列算法，SNM算法（Sorted-Neighborhood Method, 近邻排序算法），MPN算法（Multi-PassSorted-Neighborhood, 多趟近邻排序算法）等： ●优先队列算法通过减少记录比较的次数，提高匹配的效率，而且该算法几乎不受数据规 模的影响，能很好地适应数据规模的变化。但是算法复杂度比较高，实现相对困难。 ●SNM近邻排序算法采用滑动窗口的方法，每次只比较窗口中的w条记录，提高匹配效 率；采用滑动窗口也提高了比较速度，只需要进行ｗ×Ｎ次比较识别重复记录的精度很大程度上依赖于排序所选择的关键字，而且滑动窗口的大小ｗ的选取很难控制。 ●MPN多趟近邻排序算法精确度高，但是不能正确地检测出数据库中没有包含主键域的 记录。 二元混淆矩阵（Confusion Matrix） 我们通常用二元混淆矩阵来判定一个二元分类方法是否有效。请看下图： 图II-1 混淆矩阵示意图 在图II-1中各个数据的含义解释如下： ●TP（True Positive）：预测值和真实值相一致都为1的个数。 ●FP（False Positive）：预测值为1而真实值为0的个数。 ●FN（False Negative）：预测值为0而真实值为1的个数。 ●TN（True Negative）：预测值和真实值相一致都为0的个数。 ROC分类器效果评估 下图是一张ROC曲线图，ROC曲线（receiver operating characteristic curve）是受试者工作特征曲线的缩写, 该曲线常用于医疗临床诊断，数据挖掘兴起后也被用于分类器的效果评价。 论贝叶斯分类、决策树分类、感知器分类挖掘算法的优势与劣势 摘要本文介绍了在数据挖掘中数据分类的几个主要分类方法，包括：贝叶斯分类、决策树分类、感知器分类，及其各自的优势与劣势。并对于分类问题中出现的高维效应，介绍了两种通用的解决办法。 关键词数据分类贝叶斯分类决策树分类感知器分类 引言 数据分类是指按照分析对象的属性、特征，建立不同的组类来描述事物。数据分类是数据挖掘的主要内容之一，主要是通过分析训练数据样本，产生关于类别的精确描述。这种类别通常由分类规则组成，可以用来对未来的数据进行分类和预测。分类技术解决问题的关键是构造分类器。 一．数据分类 数据分类一般是两个步骤的过程： 第1步：建立一个模型，描述给定的数据类集或概念集（简称训练集）。通过分析由属性描述的数据库元组来构造模型。每个元组属于一个预定义的类，由类标号属性确定。用于建立模型的元组集称为训练数据集，其中每个元组称为训练样本。由于给出了类标号属性，因此该步骤又称为有指导的学习。如果训练样本的类标号是未知的，则称为无指导的学习（聚类）。学习模型可用分类规则、决策树和数学公式的形式给出。 第2步：使用模型对数据进行分类。包括评估模型的分类准确性以及对类标号未知的元组按模型进行分类。 常用的分类规则挖掘方法 分类规则挖掘有着广泛的应用前景。对于分类规则的挖掘通常有以下几种方法，不同的方法适用于不同特点的数据：1．贝叶斯方法 2．决策树方法 3．人工神经网络方法 4．约略集方法 5．遗传算法 分类方法的评估标准： 准确率：模型正确预测新数据类标号的能力。 速度：产生和使用模型花费的时间。 健壮性：有噪声数据或空缺值数据时模型正确分类或预测的能力。 伸缩性：对于给定的大量数据，有效地构造模型的能力。 可解释性：学习模型提供的理解和观察的层次。 影响一个分类器错误率的因素 (1) 训练集的记录数量。生成器要利用训练集进行学习，因而训练集越大，分类器也就越可靠。然而，训练集越大，生成器构造分类器的时间也就越长。错误率改善情况随训练集规模的增大而降低。 (2) 属性的数目。更多的属性数目对于生成器而言意味着要计算更多的组合，使得生成器难度增大，需要的时间也更长。有时随机的关系会将生成器引入歧途，结果可能构造出不够准确的分类器（这在技术上被称为过分拟合）。因此，如果我们通过常识可以确认某个属性与目标无关，则将它从训练集中移走。 (3) 属性中的信息。有时生成器不能从属性中获取足够的信息来正确、低错误率地预测标签（如试图根据某人眼睛的颜色来决定他的收入）。加入其他的属性（如职业、每周工作小时数和年龄），可以降低错误率。 (4) 待预测记录的分布。如果待预测记录来自不同于训练集中记录的分布，那么错误率有可能很高。比如如果你从包含家用轿车数据的训练集中构造出分类器，那么试图用它来对包含许多运动用车辆的记录进行分类可能没多大用途，因为数据属性值的分布可能是有很大差别的。 评估方法 有两种方法可以用于对分类器的错误率进行评估，它们都假定待预测记录和训练集取自同样的样本分布。 (1) 保留方法(Holdout)：记录集中的一部分（通常是2/3）作为训练集，保留剩余的部分用作测试集。生成器使用2/3 的数据来构造分类器，然后使用这个分类器来对测试集进行分类，得出的错误率就是评估错误率。 虽然这种方法速度快，但由于仅使用2/3 的数据来构造分类器，因此它没有充分利用所有的数据来进行学习。如果使用所有的数据，那么可能构造出更精确的分类器。 (2) 交叉纠错方法(Cross validation)：数据集被分成k 个没有交叉数据的子集，所有子集的大小大致相同。生成器训练和测试共k 次；每一次，生成器使用去除一个子集的剩余数据作为训练集，然后在被去除的子集上进行测试。把所有决策树算法研究及应用概要
决策树算法介绍(DOC)
数据挖掘算法综述
数据挖掘决策树算法Java实现
数据挖掘分类算法介绍
基于决策树的分类算法
数据挖掘——决策树分类算法 (1)
数据挖掘决策树算法概述
生物数据挖掘-决策树实验报告
决策树分类算法的时间和性能测试(DOC)
数据挖掘——决策树分类算法 (2)
数据挖掘中的文本挖掘的分类算法综述
决策树分类-8页文档资料
数据挖掘主要算法
决策树分类算法
决策树算法总结
电子商务数据挖掘常用公式和算法汇总
论贝叶斯分类、决策树分类、感知器分类挖掘算法的优势与劣势
相关主题
文本预览