数据挖掘决策树算法概述

决策树是分类应用中采用最广泛的模型之一。与神经网络和贝叶斯方法相比，决策树无须花费大量的时间和进行上千次的迭代来训练模型，适用于大规模数据集，除了训练数据中的信息外不再需要其他额外信息，表现了很好的分类精确度。其核心问题是测试属性选择的策略，以及对决策树进行剪枝。连续属性离散化和对高维大规模数据降维，也是扩展决策树算法应用范围的关键技术。本文以决策树为研究对象，主要研究内容有：首先介绍了数据挖掘的历史、现状、理论和过程，然后详细介绍了三种决策树算法，包括其概念、形式模型和优略性，并通过实例对其进行了分析研究目录TOC\o"1-5"\h\z一、引言 1二、数据挖掘 2（一）概念 2（二）数据挖掘的起源 2（三）数据挖掘的对象 3（四）数据挖掘的任务 3（五）数据挖掘的过程 3（六）数据挖掘的常用方法 3（七）数据挖掘的应用 5三、决策树算法介绍 5（一）归纳学习 5（二）分类算法概述 5（三）决策树学习算法 6\o"CurrentDocument"1、决策树描述 7\o"CurrentDocument"2、决策树的类型 8\o"CurrentDocument"3、递归方式 8\o"CurrentDocument"4、决策树的构造算法 8\o"CurrentDocument"5、决策树的简化方法 9\o"CurrentDocument"6、决策树算法的讨论 10四、 ID3、C4.5和CART算法介绍 10（一）ID3学习算法 11\o"CurrentDocument"1、基本原理 11\o"CurrentDocument"2、ID3算法的形式化模型 13（二） C4.5算法 14（三） CART算法 17\o"CurrentDocument"1、 CART算法理论 17\o"CurrentDocument"2、 CART树的分支过程 17（四） 算法比较 19五、 结论 24参考文献 错误！未定义书签。致谢 错误！未定义书签。II数据挖掘中决策树算法的研究一、引言在激烈的市场竞争中，信息对于企业的生存和发展越来越起到至关重要的作用，随着数据库技术的迅速发展以及数据库管理系统的广泛应用，数据库中表达信息的数据亦随着时间和业务的发展而急剧膨胀，人们需要对数据进行更高层次的处理，从中找出规律和模式，以帮助人们更好的利用数据进行决策和研究。目前的数据库系统虽然可以实现高效的数据录入、查询、统计等功能，却无法发现数据中存在的关系和规则，无法根据现有的数据预测未来的发展趋势。由于缺乏挖掘数据背后隐藏的知识的手段，导致了“数据爆炸但知识贫乏”的现象，面对“人们被数据淹没，人们却饥饿于知识”的挑战，数据挖掘和知识发现技术应运而生，并得以蓬勃发展，越来越显示出其强大的生命力。数据挖掘的核心部分是为数据集建立模型的过程，不同的数据挖掘方法构造数据模型的方式也不相同，在进行数据挖掘时可采用许多不同的方法，例如神经网络、决策树、遗传算法和可视化技术等，同时同一方法下又有数以百计的派生方法。决策树算法是数据挖掘常用的方法之一，但它一直未受到人们重视，直到1984年Breiman等人合著出版了《分类和回归树》一书，决策树方法才开始被统计学界接受并获得了信赖，并很快得到推广应用。现在很多公司的数据挖掘产品中都采用了决策树数据挖掘算法，J.R.Quinlan对决策树算法作出了详细的理论描述决策树算法中一种广为人知的算法就是ID3算法，是1986年由Quinlan提出的一种基于信息墒的决策树算法，近年来在很多知识发现领域得到应用，很多学者针对ID3算法进行研究。本课题主要研究了ID3算法、C4.5算法等的优势和略势，比较了各算法在实际应用中的好处和不足。二、数据挖掘（一）概念图1-1数据挖掘，在人工智能领域，习惯上又称为数据库中知识发现（KnowledgeDiscoveryinDatabase,KDD），也有人把数据挖掘视为数据库中知识发现过程的一个基本步骤。知识发现过程以下三个阶段组成：（1）数据准备，（2）数据挖掘，（3）结果表达和解释。数据挖掘可以与用户或知识库交互。并非所有的信息发现任务都被视为数据挖掘。例如，使用数据库管理系统查找个别的记录，或通过因特网的搜索引擎査找特定的Web页面，则是信息检索（informationretrieval）领域的任务。虽然这些任务是重要的，可能涉及使用复杂的算法和数据结构，但是它们主要依赖传统的计算机科学技术和数据的明显特征来创建索引结构，从而有效地组织和检索信息。尽管如此，数据挖掘技术也已用来增强信息检索系统的能力。（二）数据挖掘的起源要是发明之母。近年来，数据挖掘引起了信息产业界的极大关注，其主要原因是存在大量数据，可以广泛使用，并且迫切需要将这些数据转换成有用的信息和知识。获取的信息和知识可以广泛用于各种应用，包括商务管理，生产控制，市场分析，工程设计和科学探索等。（三）数据挖掘的对象数据挖掘可以在任何类型的数据上进行,即可以来自社会科学,又可以来自自然科学产生的数据,还可以是卫星观测得到的数据。数据形式和结构也各不相同,可以是传统的关系数据库,可以是面向对象的高级数据库系统,也可以是面向特殊应用的数据库,如空间数据库、时序数据库、文本数据库和多媒体数据库等，还可以是Web数据信息。（四） 数据挖掘的任务数据挖掘的目标是从海量数据中发现隐含的、有意义的知识。它的任务主要是分类、预测、时间序列模式、聚类分析、关联分析预测和偏差分析等。分类：分类就是按照一定的标准把数据对象划归成不同类别的过程。预测：预测就是通过对历史数据的分析找出规律，并建立模型，通过模型对未来数据的种类和特征进行分析。时间序列模式：时间序列模式就是根据数据对象随时间变化的规律或趋势来预测将来的值。聚类分析：聚类分析是在没有给定划分类的情况下，根据数据信息的相似度进行数据聚集的一种方法。关联分析预测：关联分析就是对大量的数据进行分析，从中发现满足一定支持度和可信度的数据项之间的联系规则。偏差分析：偏差分析就是通过对数据库中的孤立点数据进行分析，寻找有价值和意义的信息。（五） 数据挖掘的过程数据挖掘使用一定的算法从实际应用数据中挖掘出未知、有价值的模式或规律等知识，整个过程由数据准备、数据挖掘、模式评估、结果分析和运用知识等步骤组成。数据准备：数据挖掘的处理对象是数据，这些数据一般存储在数据库系统中，是长期积累的结果。但往往不适合直接在这些数据上进行知识挖掘，首先要清除数据噪声和与挖掘主题明显无关的数据;其次将来自多数据源中的相关数据组合并;然后将数据转换为易于进行数据挖掘的数据存储形式，这就是数据准备。数据挖掘：数据挖掘就是根据数据挖掘的目标，选取相应算法及参数，分析准备好的数据，产生一个特定的模式或数据集，从而得到可能形成知识的模式模型。模式评估：由挖掘算法产生的模式规律，存在无实际意义或无实用价值的情况，也存在不能准确反映数据的真实意义的情况，甚至在某些情况下与事实相反，因此需要对其进行评估，从挖掘结果中筛选出有意义的模式规律。在此过程中，为了取得更为有效的知识，可能会返回前面的某一处理步骤中以反复提取，从而提取出更有效的知识。巩固知识：解释并评估结果.其使用的分析方法一般应作数据挖掘操作而定，通常会用到可视化技术.运用知识：将分析所得到的知识集成到业务信息系统的组织结构中去.（六）数据挖掘的常用方法决策树方法：决策树是一种常用于预测模型的算法,它通过一系列规则将大量数据有目的分类,从中找到一些有价值的、潜在的信息。它的主要优点是描述简单,分类速度快,易于理解、精度较高,特别适合大规模的数据处理,在知识发现系统中应用较广。它的主要缺点是很难基于多个变量组合发现规则。在数据挖掘中,决策树方法主要用于分类。神经网络方法：神经网络是模拟人类的形象直觉思维,在生物神经网络研究的基础上,根据生物神经元和神经网络的特点,通过简化、归纳、提炼总结出来的一类并行处理网络,利用其非线性映射的思想和并行处理的方法,用神经网络本身结构来表达输入和输出的关联知识。粗糙集方法：粗糙集理论是一种研究不精确、不确定知识的数学工具。粗糙集处理的对象是类似二维关系表的信息表。目前成熟的关系数据库管理系统和新发展起来的数据仓库管理系统,为粗糙集的数据挖掘奠定了坚实的基础。粗糙集理论能够在缺少先验知识的情况下,对数据进行分类处理。在该方法中知识是以信息系统的形式表示的,先对信息系统进行归约,再从经过归约后的知识库抽取得到更有价值、更准确的一系列规则。因此,基于粗糙集的数据挖掘算法实际上就是对大量数据构成的信息系统进行约简,得到一种属性归约集的过程,最后抽取规则。遗传算法：遗传算法是一种基于生物自然选择与遗传机理的随机搜索算法。数据挖掘是从大量数据中提取人们感兴趣的知识,这些知识是隐含的、事先未知的、潜在有用的信息。因此,许多数据挖掘问题可以看成是搜索问题,数据库或者数据仓库为搜索空间,挖掘算法是搜索策略。应用遗传算法在数据库中进行搜索,对随机产生的一组规则进行进化,直到数据库能被该组规则覆盖,就可以挖掘出隐含在数据库中的规则。（七）数据挖掘的应用数据挖掘技术在各个需要进行信息分析的领域得到十分广泛的应用。它可以带来显著的经济效益,不仅可以控制成本,也可以给企业带来更多效益。在金融业,可以通过信用卡历史数据的分析,判断哪些人有风险,哪些人没有;在超市,可以通过对超市交易信息的分析,安排货价货物摆设,以提高销售收入;在保险业,可以通过对保险公司客户记录的分析,来判定哪些客户是花费昂贵的对象;在学校,可以通过分析学校学生课程及成绩等信息,来判断课程之间的关系。此外,在医学中,可以利用数据挖掘技术对疾病发作前后症状的分析,来对病症进行诊断;在体育运动中,利用数据挖掘技术对对抗性强的积极运动进行分析,发现对方弱点,制定有效的战术。三、决策树算法介绍（一）归纳学习归纳学习是符号学习中研究的最为广泛的一种方法。它着眼于从一组无次序、无规则的实力中，找出蕴涵规律，事例一般是基于属性理论的，有特定的属性值得到问题某个结论，给定关于某个概念的一系列已知的正例和反例，其任务是从中归纳出一个通用概念描述。它能够获得新的概念，创立新的规则，发现新的理论。它的一般的操作是泛化和特化。泛化用来扩展假设的语义信息，以使其包含更多的正例，应用于更多的情况。特化是泛化的相反操作，用于限制概念描述的应用范围。分类算法是归类学习的一种类型。（二）分类算法概述分类算法是数据挖掘中的一个重要课题，可用于预测和决策。分类算法也是数据挖掘算法中很很重要的一种，决策树（decisiontree）算法是主要分类算法之一。分类问题可描述为：输入数据，或称训练集（Trainingset）,是一条条的数据库记录组成的。每一条记录包含若干属性，组成一个特征向量，训练集的每条记录还有一个特定的标签类与之对应，该类标签是系统的输入，通常是以往的一些经验数据。一个具体样本的形式可为样本向量：(v,v,,v；c)。这里的v表示字段值，c表示类别。12nn分类的目的是分析输入数据，通过在训练集中的数据表现出来的特性，为每个类找到一种准确的描述或者模型。由此生成的类用来对未来的测试数据进行分类。尽管这些未来的测试数据的类标签是未知的，我们仍可以由此预测这些新数据所属的类。注意，是预测而不是肯定。我们也可以由此对数据中的每一个类有更好的理解，或者说我们获得了这个类的知识。分类器评价或比较尺度主要有三种：预测准确度预测准确度是用的最多的一种比较尺度，特别是对于预测型分类任务，目前公认的方法的分层交叉验证法。计算复杂度计算复杂度依赖于具体的实现细节和硬件环境，在数据挖掘中，由于操作对象是巨量的数据库因此空间和时间的复杂度问题将是非常重要的一个环节。模型描述的简洁度对于描述型的分类任务，模型描述越简洁越受欢迎;例如采用规则表示的分类器构造法就比较简单，而神经网络方法产生的结果就难以理解。决策树学习算法决策树学习算法是以实例为基础的归纳学习算法，通常用来形成分类器和预测模型，可以对未知数据进行分类或预测、数据预处理、数据挖掘等。它通常包括两部分：树的生成和树的剪枝。1、决策树描述一颗决策树的内部结点是属性或属性的集合，叶节点是所要学习划分的类，内部结点的属性称为测试属性。当经过一批训练实例集的训练产生一颗决策树，决策树可以根据属性的取值对一个未知实例集进行分类。使用决策树对实例进行分类的时候，有树根开始对该对象的属性逐渐测试其值，并且顺着分支向下走，直至到达某个叶结点，此叶结点代表的类即为该对象所处的类。决策树是一个可以自动对数据进行分类的树型结构，是树形结构的知识表示，可以直接转换为决策规则，它能被看作一棵树的预测模型，树的根节点是整个数据集合空间，每个分节点是一个分裂问题，它是对一个单一变量的测试，给测试将数据集合空间分割成两个或更多块，每个叶结点是带有分类的数据分割。决策树也可以解释成一种特殊形式的规则集，其特征是规则的层次组织关系。决策树算法主要是用来学习以离散型变量作为属性类型的学习方法。连续型变量必须被离散化才能被学习。表1给出了决策树与自然树的对应关系以及在分类问题中的代表含义。表1自然树对应决策树中的意义分类问题中的表示意义树根根节点训练实例整个数据集空间杈内部（非叶）结点、决策结点待分类对象的属性（集合）树枝分支属性的一个可能取值叶子叶结点、状态结点数据分割（分类结果）2、决策树的类型决策树的内节点的测试属性可能是单变量的，即每个内节点只包含一个属性。也可能是多变量的，即存在包含多个属性的内节点。根据测试属性的不同属性值的个数，可能使得每个内节点有两个或多个分支。如果每个内节点只有两个分支则称之为二叉决策树。每个属性可能是值类型，也可能是枚举类型。分类结果既可能是两类又可能是多类，如果二叉决策树的结果只能有两类则称之为布尔决策树。布尔决策树可以很容易以析取范式的方法表示，并且在决策树学习的最自然的情况就是学习析取概念。3、递归方式决策树学习采用自顶向下的递归方式，在决策树的内部结点进行属性值的比较并根据不同的属性值判断从该结点向下的分支，在决策树的叶结点得到结论。所以从根到叶结点的一条路径就对应着一条合取规则，整个决策树就对应着一组析取表达式规则。决策树生成算法分成两个步骤：一是树的生成，开始时所有数据都在根节点，然后递归的进行数据分片。二是树的修剪，就是去掉一些可能是噪音或异常的数据决策树停止分割的条件有：一个结点上的数据都是属于同一个类别；没有属性可以在用于对数据进行分割。4、决策树的构造算法决策树的构造算法可通过训练集T完成，其中T={<x,c>},而jx=(a,a,…,a)为一个训练实例，它有n个属性，分别列于属性表12n(A,A，…，A)，其中a表示属性A的取值。c.^C={C,C，…，C}为X12niij12m的分类结果。算法分以下几步：从属性表中选择属性A作为分类属性；若属性A的取值有K个，则将T划分为K个子集T，•…，T，其中i i i 1 KiT={<x,C>l<x,c>}WT,且X的属性取值A为第K个值；iji从属性表中删除属性A;i对于每一个T（lWjWK），令T=T；ij1ij如果属性表非空，返回（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的概念学习系统(ConceptLearningSystemCLS)

上发展起来的一种自顶向下的学习算法，而C4.5算法又是Quinlan本人针对ID3算法提出的一种改进算法，他在1993年出版了专著《机器学习规划》对C4.5算法进行了详细的描述。CHAID(即Chi-SquareAutomaticInteracionDetector的缩写，卡方自动互动侦测器)算法是GordonB.Kass博士在1976年提出的，可用来对于分类性数据进行挖掘°CART(即ClassificationAndRegressionTree的缩写，分类回归树)算法从1984年开始得到普及推广，可对连续型因变量进行处理。针对这些算法的缺点，很多研究人员尝试在控制树的大小和简化决策树等方面作出努力，通过研究各种预剪枝算法和后剪枝算法来控制树的规模，同时在修改测试属性空间、改进测试属性选择方法、限制数据集、改变数据结构等方面提出了许多新的算法和标准。本章只介绍ID3算法、C4.5算法和CART算法。ID3学习算法1、基本原理信息熵在信息论中称为平均信息量，是对被传送的信息进行度量所采用的一种平均值。信源中被传送的信息包括有限数目的互斥并联合完备的事件，它们都以一定的概率出现，用数学式子来表示就是:一组事件x，…,x，以既定概率p(x)，…,p(x)出现，其平均值H(X)就是信1r1r息熵，它的值等于每个事件的(自)信息量I(X)的数学期望，即:H(X)=—工p(Xi)I(Xi)=—工p(X)logp(X)iir=1rr=1传统ID3学习算是以信息熵(也称信息不确定性)的下降速度作为选取测试属性的标准。该算法根据属性集的取值选择实例的类别。它的核心是在决策树中各级结点上选择属性，用信息增益作为属性选择标准，使得在每一非叶结点进行测试时，能获得关于被测试例子最大的类别信息。使用该属性将例子集分成子集后，系统的熵值最小，期望该非叶结点到达各后代叶节点的平均路径最短，使生成的决策树平均深度较小。可以看出训练例集在目标分类方面越模糊越杂乱无序，它的熵就越高；训练例集在目标分类方面越清晰则越有序，它的熵越低，ID3算法就是根据“信息赢取(增益)越大的属性对训练例的分类越有利”的原则在算法的每一步选取“属性表中可对训练例集进行最佳分类的属性”。一个属性的信息增益就是由于使用这个属性分割样例而导致系统熵的降低，计算各个属性的信息赢取并加以比较是ID3算法的关键操作。ID3算法的步骤如下：选出整个训练实例集X的规模为W的随机子集Xl(W称为窗口规模，子集称为窗口)；以使得信息熵的值最小为标准，选取每次的测试属性，形成当前窗口的决策树；顺序扫描所有训练实例，找出当前的决策树的例外，如果没有例外则训练结束；组合当前窗口的一些训练实例与某些在(3)中找到的例外形成新的窗口，转(2)。

2、ID3算法的形式化模型ID3基本原理是基于两类分类问题，其数学模型可描述如下：设e=F*F*„*F是n维有穷向量空间，其中F是有穷离散符号集，E中的元12nj素e=<V,V，…，V>叫做实例，其中VeF,J=1,2,…,n。设P和N是12njjE和F的两个实例集，分别叫正例集和反例集。假设向量空间E中的正例集PE和反例集NE的大小分别为P和N,ID3基于下列两个假设：(1)在向量空间E上的一棵正确决策树，对任意例子的分类概率同E中的正、反例的概率一致。(2)一棵决策树能对一实例作出正确类别判断所需的信息量(原集合ENP+W的熵)为NP+WE(E)=—卩log卩— “logP+NTTN如果以属性A作为决策树的根，A具有v个值(V、V…V)，它将E12v分为v个子集(E,E…E)，假设E中含有P个正例和N个反例，子集E12viiii的信息熵为E(E)：iPi PiNi NiE(Ei)=- log -Nlog__Pi+NiPi+NiPi+NiPi+Ni以属性A为根分类后的信息熵(用A分类后上的期望值)为E(A):vPi+NiE(A)=工 E(Ei)P+Nr=1因此，以属性为根的信息增益I(A)是：I(A)=E(E)—E(A)ID3选择使1(A)最大(即E(A)最小)的属性A作为根结点。对A的不

同的取值对应的E的V个子集E递归调用上述过程，生成A的子结点B,i1B，…，B。2vID3的基本原理是基于两类分类问题，但很容易扩展到多类。设样本集S共有C类样本，每类样本数为Pi,(i=l,2,3,...,c)。若以属性A作为决策树的根,A具有v个值V，V，…，V，它将E分成v个子集［E，E，…,12v12E］，假设E中含有j类样本的个数为P=1，2，…，C，那么子集E的信viiji息量是E(E)为：i賈logIEiIPijVE!\IEi賈logIEiIPijVE!\IEiITETE(Ei)E(Ei)=」j=1以A为根分类的信息熵为：vE(A)=工i=1选择属性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的差别将会增大。4.5算法使用更复杂的方法是为属性A的各种取值赋以概率，具有未知属性A值的实例按概率值分为大小不等的碎片，沿相应属性A值的分支向树的下方分布，实例的碎片将用于计算信息赢取。这个实例碎片在学习后，还可以用来对属性值不全的新实例进行分类。与ID3相比，C4.5主要改进如下：用信息增益率来选择属性，克服了用信息增益来选择属性时偏向选择值多的属性的不足。信息增益率定义为：GainRatio(S,A)=Gain"S，ASplitlnfo(S,A)其中Gain(S,A)与ID3算法中的信息增益相同，而分裂信息ISiI也 LogisiTST ISiI也 LogisiTST 2cSplitInfo(S,A)二i=1其中，S到S是c个不同值的属性A分割S而形成的c个样本子集。1c可以处理连续数值型属性。例如，假设A为一个连续的数值型属性首先检查样本集中该属性的所有取值，然后将其按升序排列为A，A，„，12A。对于每一个A，j=l,2，…，m-1，将样本集划分为两个样本子集，mj一子集是各记录属性A的值均小于等于A，另一子集是其各记录属性A

的值均大于A。对于每个划分，计算相应的信息增益率，然后选择增益j率最大的划分，作为属性A的信息增益率。为了避免树的高度无节制的增长，避免过度拟合数据，采用了一种后剪枝方法，该方法是从一种称为“规则后修剪”(rulepost-pruning)的方法演变而来。该方法使用训练样本集本身来估计剪枝前后的误差，从而决定是否真正剪枝。方法中使用的公式如下：f—qPr[」q >z]=c其中N是实例的数量，f二E/N为观察到的误差率(其中E为N个实例中分类错误的个数)，q为真实的误差率，c为置信度(C4.5算法的一个输入参数，一般情况下为0.25)，z为对应于置信度c的标准差，其值可根据c的设定值通过查正态分布表得到。通过该公式即可计算出真实误差率q的一个置信度上限，用此上限为该节点误差率e做一个悲观的估计:z21+:N通过判断剪枝前后e的大小，从而决定是否需要剪枝。对于缺失值的处理。在某些情况下，可供使用的数据可能缺少某些属性的值。假如〈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%被分配到另一个分支。这些片断样例(fractionalexamples)的目的是计算信息增益，另外，如果有第二个缺少值的属性必须被测试，这些样例可以在后继的树分支中被进一步细分。C4.5就是使用这种方法处理缺少的属性值。CART算法1、 CART算法理论分类回归树CART是一种典型的二叉决策树，主要用来进行分类研究,可以同时处理连续变量和分类变量。如果目标变量是分类变量，则CART生成分类决策树，如果目标变量是连续变量，则CART变量生成回归决策树。无论是分类决策树还是回归决策树，CART的首要目标都是构造一个准确的分类模型用来进行预测，即研究引起分类现象发生的变量及变量之间的作用，通过建立决策树和决策规则对类型未知的对象进行类别预测即通过类型未知的对象的某些相关变量值就可以对其做出类型判定。2、 CART树的分支过程CART算法在对一个节点进行分支时首先要确定一个最佳的分支预测变量以及该预测变量的最佳分支阀值点。然后将性质相同的对象分在同一个节点中，并且同一个父节点的两个子节点间具有显著的差异性。CART算法选择指标的方法是使用“杂质函数”，当节点中数据都属于同一个类时，杂质函数值为0，当节点中的对象均匀分布与所有可能的类

时，杂质函数值最大。节点的杂质函数定义如下:p+p+A+p=112t11,A11,A,)=max0(1,0,0(1,0,A,0)=0(0,1,A,0)=A=0(0,0,A,1)=0其中p是节点t(包括根结点)中对象属于j类的概率。类似的，树Tt的杂质函数是树中包含的各个叶节点杂质函数的加权平均值。可以表示如下:nNE(T)=工 iE(t)ik=1这里n是树T中的叶节点个数，N是叶节点i中的对象个数，N是所t有叶节点中对象的总数或根节点中对象的数量，E(t)是叶节点i中的杂i质函数值。CART算法中最常使用的杂质函数是GINI系数，其公式如下:0(p0(p1,p2,A,pj)=2工pp=1—ij1Lp2j详j j=l因为对所有的j,工p=1,并且0WpW1,所以GINI系数总为正数,jj除非其中的一个p为1,而其他均为0。此为，对于所有j,当p=1/J时，jj这个函数达到最大值。对于一个节点，其分支前后的杂质应该减少的最多也就是说分支后数据的纯度应该比分之前提高的最多。其中杂质的改变量为：AE(s,t)=E(t)-{pE(t)+pE(t)}llrr这里t是父节点；E(t)是父节点t的杂质函数值；E(t)和E(t)分1r别是分支后左右两个子节点的杂质函数值;而p和p分别是分支后左右lr两个子节点中包含的对象百分比。大括号中的式子是左右两个子节点的杂

质函数值的加权值，也是以节点t为根节点的子树的杂质函数值。只有当子树的杂质含量少于树根的杂质含量时，进一步的分支才是有意义的。树停止分支的时候有以下几种情况:分枝后的叶节点中的样本数小十给定的阀值；分枝后的叶节点中的样本属于同一类；节点中只包含一个对象。算法比较用weka软件分别以ID3、C4.5和CART算法对以下数据集进行分类:DAO6788O2数匕日力有大等有等有等有大有等有等等大大等有大等巩没很中没中没中没很没中没中中很很中没很中衣多多多常常多多多多多多多多多多常常常多常穿较较较正正很很很很较较很很较较正正正很止度高高高高高中中高高中中中中中中中中高中高温很很很很很适适很很适适适适适适适适很适很度天天天天天天天常常大天常常常常大大常挖常湿很很很很很很很正正很很正正正正很很正瀚正DAO6788O2数匕日力有大等有等有等有大有等有等等大大等有大等巩没很中没中没中没很没中没中中很很中没很中衣多多多常常多多多多多多多多多多常常常多常穿较较较正正很很很很较较很很较较正正正很止度高高高高高中中高高中中中中中中中中高中高温很很很很很适适很很适适适适适适适适很适很度天天天天天天天常常大