数据管理决策树建模

数据管理决策树建模§4.1决策树介绍 分类是数据挖掘的一个重要课题,它的目的是：

构造一个分类函数或分类模型(也常称为分类器),该模型能把数据库中的数据项映射到给定类别中的某一个。 数据分类的过程一般来说主要包含两个步骤 第一步,建立一个描述已知数据集类别或概念的模型 第二步,利用所获得的模型进行分类操作第2页,共154页，星期六，2024年，5月§4.1决策树介绍链接 分类是数据挖掘的一个重要课题,它的目的是：

构造一个分类函数或分类模型(也常称为分类器),该模型能把数据库中的数据项映射到给定类别中的某一个。 数据分类的过程一般来说主要包含两个步骤 第一步,建立一个描述已知数据集类别或概念的模型 第二步,利用所获得的模型进行分类操作第3页,共154页，星期六，2024年，5月§4.1 决策树介绍-2第一步,建立一个描述已知数据集类别或概念的模型 该模型是通过对数据库中各数据进行内容的分析而获得的。 分类学习方法所使用的数据集称为训练样本集合，每一数据行都属于一个确定的数据类别，其类别值是由一个属性来描述的(被称为类别标记属性)。 因此分类学习又可称为监督学习，它是在已知训练样本类别情况下，通过学习建立相应模型。而无监督学习则是在训练样本的类别与类别个数均未知的情况下进行的，如聚类分析。第4页,共154页，星期六，2024年，5月§4.1 决策树介绍-2第二步,利用所获得的模型进行分类操作 首先对模型分类准确率进行估计。

Holdout方法是一种简单的估计方法，它利用一组带有类别的样本(称为测试样本)对由训练样本所构造出模型的

准确性进行测试，通常测试样本是随机获得的，且与

训练样本独立同分布。 模型的准确性可以通过由该模型所正确分类的测试样本个数所占总测试样本的比例得到。即对于每一个测试样本，比较其已知的类别与学习所获模型的预测类别。第5页,共154页，星期六，2024年，5月§4.1 决策树介绍-2 若模型的准确率是通过对训练数据集本身的测试所获得，由于学习模型倾向于过分逼近训练效据，从而造成对模型测试准确率的估计过于乐观。因此需要使用一个测试数据集来对学习所获模型的准确率进行测试工作。 如果一个学习所获模型的准确率经测试被认为是可以

接受的，那么就可以使用这一模型对未来数据行或对象

(其类别未知)进行分类，即利用学习所获得的模型

进行预测，对未知类别的数据行或对象判断其

类别(属性)取值。第6页,共154页，星期六，2024年，5月由训练数据产生分类规则第7页,共154页，星期六，2024年，5月由分类规则对新的样本数据进行分类第8页,共154页，星期六，2024年，5月§4.1 决策树介绍-2常用的分类预测算法：决策树归纳分类贝叶斯分类基于规则的分类用后向传播分类遗传算法、粗糙集方法、模糊集方法第9页,共154页，星期六，2024年，5月§4.1 决策树介绍-24.1.1决策树的基本知识决策树方法最早产生于20世纪60年代，是由Hunt等人研究人类概念建模时建立的学习系统CLS(conceptlearningsystem)。到了70年代末，

J.RossQuinlan提出ID3算法，引进信息论中的有关思想，提出用信息

增益(informationgain)作为特征判别能力的度量，来选择属性作为决策树的节点，并将建树的方法嵌在一个迭代的程序之中。当时他的主要目的在于减少树的深度，却忽略了叶子数目的研究。1975年和1984年，分别有人提出了CHAID和CART算法。1986年，J.C.Schlinner提出ID4算法。1988年，P.E.Utgoff提出ID5R算法。1993年，Quinlan本人以ID3算法为基础研究出C4.5算法。新算法在对预测变量的缺失值处理、剪枝技术、派生规则等方面作了较大的改进，C5.0是C4.5的商业改进版。第10页,共154页，星期六，2024年，5月4.1.1决策树的基本知识 决策树技术发现数据模式和规则的核心是归纳算法。 归纳是从特殊到一般的过程。 归纳推理从若干个事实表征出的特征、特性或属性中,通过比较、总结、概括而得出一个规律性的结论。 归纳学习的过程就是寻找一般化描述(归纳断言)的过程。这种一般化描述能够解释给定的输入数据，并可以用来预测新的数据。 归纳学习由于依赖于经验数据，因此又称作经验学习。第11页,共154页，星期六，2024年，5月4.1.1决策树的基本知识-2 归纳学习存在一个基本假定:

任一模型如果能在足够大的训练样本集中很好地逼近

目标函数，则它也能在未见样本中很好地逼近目标函数。

这个假定是归纳学习有效性的前提条件。 归纳过程就是在描述空间中进行搜索的过程。第12页,共154页，星期六，2024年，5月4.1.1决策树的基本知识-2 归纳可以分为自下而上、自上而下和双向搜索三种方式 自下而上法一次处理一个输入对象，将描述逐步

一般化，直到最终的一般化描述。 自上而下法则对可能的一般化描述集进行搜索，试图

找到一些满足一定要求的最优的描述。 双向搜索方式则是这两者的结合。第13页,共154页，星期六，2024年，5月4.1.1决策树的基本知识-2 决策树学习是应用最广的归纳推理算法之一。它是一种逼近离散函数值的方法，分类精度高，操作简单，并且对噪声数据有很好的稳健性，因而成为比较实用且比较流行的数据挖掘算法。 它的最大优点是，在学习过程中不需要使用者了解很多背景知识，只要训练样本集能够用“属性-值”的方式表达

出来就能使用决策树学习算法来分类。第14页,共154页，星期六，2024年，5月4.1.1决策树的基本知识-2 该方法先根据训练子集(又称为窗口)形成决策树，如果该树不能对所有对象给出正确的分类，那么选择一些例外

加入到窗口中，重复该过程一直到形成正确的决策集。 最终结果是“一棵树”，其叶节点是类名，中间节点是

带有分枝的属性，该分枝对应该属性的某一可能值。第15页,共154页，星期六，2024年，5月4.1.1决策树的基本知识-2 决策树通常有两大类型，分别为分类决策树和

回归决策树。 分类决策树用来实现对定类或定序目标变量的分类，

回归决策树则完成对定距目标变量取值的预测。 根据决策树各种不同的属性，可分为以下几类:

决策树内节点的测试属性可能是单变量的，即每个内节点只包含一个

属性;也可能是多变量的，既存在包含多个属性的内节点。测试属性的不同属性值的个数，可能使得每个内节点有两个或多个

分枝。如果一棵决策树每个内节点只有两个分枝则称之为二叉

决策树，如由CART算法生成的决策树。每个属性可能是值类型(连续值)，也可能是枚举类型(离散值)。分类结果既可能是两类也有可能是多类，如果二叉决策树的结果只有

两类，则称之为布尔决策树。第16页,共154页，星期六，2024年，5月4.1.1决策树的基本知识-2决策树方法的(相对)优点:可以生成可理解的规则

数据挖掘产生的模式的可理解度是判别数据挖掘算法的主要指标之一，相比于一些数据挖掘算法，决策树算法产生的规则比较容易理解，并且决策树模型的建立过程也很直观。计算量较小。可以处理连续和集合属性。决策树的输出包含属性的排序

生成决策树时，按照最大信息增益选择测试属性，

因此，在决策树中可以大致判断属性的相对重要性。第17页,共154页，星期六，2024年，5月4.1.1决策树的基本知识-2决策树方法的缺点:对于具有连续值的属性预测比较困难。-对于顺序相关的数据，需要很多预处理的工作。当类别太多时，通常会增加误差分枝间的拆分不够平滑，进行拆分时，不考虑其对将来拆分的影响。缺值数据处理问题:因为决策树进行分类预测时，完全基于数据的测试属性，所以对于测试属性缺失的数据，决策树将无法处理。通常仅根据单个属性来分类:决策树方法根据单个属性对数据进行

分类，而在实际的分类系统中，类的划分不仅仅与单个属性有关，往往与一个属性集有关。因此，将决策树算法推广到考虑多属性

是一个有待研究的课题。第18页,共154页，星期六，2024年，5月4.1.1决策树的基本知识-2决策树学习算法适用的问题:样本可以用“属性-值”的方式来描述目标函数的输出值为离散值训练数据中允许包含有错误:

样本的分类错误或属性值错误都允许训练数据中有样本属性值缺失第19页,共154页，星期六，2024年，5月§4.1 决策树介绍-24.1.2决策树的应用和发展趋势 决策树由于结构简单、效率高等优点而获得了广泛的应用。在国外，决策树在商业、工业、天文、医学、风险分析、社会科学和分类学等领域的应用已经取得了很好的经济和社会效益。

国内目前有关决策树的研究多是围绕算法的改进以及决策树在商业、工业等领域的运用。在商业领域，决策树方法所能解决的典型商业问题有:客户关系

管理、数据库营销、客户群体划分、交叉销售等市场分析

行为，以及客户流失分析、客户信用计分及欺诈发现，等等。在工业领域，决策树可以用于故障诊断、工业生产过程控制等。在医学领域，决策树方法可用于疾病诊断治疔、

基因与高分子序列分析、医院信息系统挖掘及医疗政策分析等。第20页,共154页，星期六，2024年，5月决策树方法的需求和发展：1.决策树的精度2.决策树的规模3.处理大规模数据集4.增量式算法5.与其他方法的结合6.知识的表示第21页,共154页，星期六，2024年，5月§4.2树的建模过程首页决策树总体思路第22页,共154页，星期六，2024年，5月§4.2 树的建模过程—总体步骤决策树的构造基本可以分为如下两步:决策树的生成 决策树的生成是指由训练样本数据集生成决策树的过程。一般情况下，训练样本数据集是根据实际需要由实际的历史数据生成的、有一定综合程度的、用于数据分析处理的

数据集。决策树的剪枝 决策树剪枝是对上一阶段所生成的决策树进行检验、

校正和修正的过程，主要是采用新的样本数据集(称为

测试数据集)中的数据检验决策树生成过程中产生的初步

规则，将那些影响预测准确性的分枝剪除。一般情况下，根据测试数据集中的每一元组对生成的规则进行预测准确性的检验，如果预测准确性过低，则将该分枝剪除。第23页,共154页，星期六，2024年，5月§4.2 树的建模过程—总体步骤决策树的构造基本可以分为如下两步:决策树的生成 决策树的生成是指由训练样本数据集生成决策树的过程。一般情况下，训练样本数据集是根据实际需要由实际的历史数据生成的、有一定综合程度的、用于数据分析处理的

数据集。决策树的剪枝 决策树剪枝是对上一阶段所生成的决策树进行检验、

校正和修正的过程，主要是采用新的样本数据集(称为

测试数据集)中的数据检验决策树生成过程中产生的初步

规则，将那些影响预测准确性的分枝剪除。一般情况下，根据测试数据集中的每一元组对生成的规则进行预测准确性的检验，如果预测准确性过低，则将该分枝剪除。第24页,共154页，星期六，2024年，5月§4.2 树的建模过程 决策树算法通过构造决策树来发现数据中蕴涵的分类规则，包含许多种不同的算法，主要可以分为三类:(1)基于统计学理论的方法，以CART为代表，在这类算法中，对于非终端节点来说，有两个分枝

;(2)基于信息理论的方法，以ID3算法为代表，此类算法中，非终端的节点的分枝由样本类别个数决定

;(3)以AID，CHAD为代表的算法，在此类算法中，非终端节点的分枝数在2至样本类别个数范围内分布。这些算法在分类中应用的过程与思想基本上是一致的。如何构造精度高、规模小的决策树是决策树算法的核心内容第25页,共154页，星期六，2024年，5月§4.2 树的建模过程4.2.1数据要求(数据准备)

在进行分类和预测挖掘之前，首先必须准备好有关挖掘数据。一般需要对数据进行以下预处理，以帮助提高分类和预测过程的准确性、有效性和可伸缩性。主要的工作包括：数据清洗相关分析数据转换第26页,共154页，星期六，2024年，5月4.2.1数据准备数据清洗 这一数据预处理步骤，主要是帮助除去数据中的噪声，并妥善解决缺失数据问题，尽管大多数分类算法都包含一些处理噪声和缺失数据的方法，但这一预处理步骤可以有效

减少学习过程可能出现相互矛盾情况的问题。第27页,共154页，星期六，2024年，5月4.2.1数据准备相关分析 由于数据集中的许多属性与挖掘任务本身可能是无关的，例如记录银行贷款申请(单)填写时的星期数(属性)，就可能与申请成功与否的描述无关。此外，有些属性也可能是冗余的。因此需要对数据进行相关分析，以使在学习阶段之前就消除无关或冗余属性。在机器学习中，这一相关分析步骤被称为属性选择(featureselection)，包含与挖掘任务无关的属性可能会减缓甚至误导整个学习过程。在理想情况下，相关分析所花费的时间加上对削减后属性(子)集进行归纳

学习所花费的时间之和，应小于从初始属性集进行学习所花费的时间，从而达到帮助改善分类效率和可扩展性的目的。第28页,共154页，星期六，2024年，5月4.2.1数据准备数据转换 利用概念层次树，数据能够被泛化到更高的层次。概念层次树对连续数值的转换非常有效。例如，属性“收入”的数值就可以被泛化为若干离散区间，诸如低、中和高。类似地，像“街道”这样的属性也可以被泛化到更高的抽象层次，如泛化到城市。由于泛化操作压缩了原来的数据集，从而可以帮助有效减少学习过程所涉及的输入输出操作。此外，初始数据可能还需要规格化，特别是在利用距离计算方法实施各种学习方法时，如在基于示例学习方法中，规格化处理是不可或缺的重要处理操作。。第29页,共154页，星期六，2024年，5月§4.2 树的建模过程4.2.2树的生长 决策树算法是一种常用的数据挖掘算法，它是从

机器学习领域中逐渐发展起来的一种分类函数逼近方法。

决策树学习的基本算法是贪心算法，采用自上而下的递归

方式构造决策树。Hunt等人于1966年提出的概念学习系统

(conceptlearningsystem，CLS)是最早的决策树算法，以后的许多决策树算法都是对CLS算法的改进或由CLS衍生而来。目前，利用决策树进行数据分类的方法已经被深入研究，并且形成了许多决策树算法。第30页,共154页，星期六，2024年，5月§4.2 树的建模过程 决策树算法的分类模型是一棵有向无环树， 下面将以二叉树为例说明基本的决策树算法。 决策树的每个节点有0或2个子节点，除了根节点以外，每个节点有且仅有一个父节点。如果节点没有子节点，则称它为叶节点，否则称为内部节点。第31页,共154页，星期六，2024年，5月§4.2 树的建模过程 每个叶节点对应一个类标号，使用决策树对未知样本

分类的类标号的值即为叶节点的值。每个内部节点都对应

一个分枝方案，它包括用于节点分裂的属性A和分枝的

判断规则q。 训练样本的属性分为数值属性和分类属性，数值属性的取值范围是一个连续的区间，比如实数集R;而分类属性的取值范围则是离散值的集合S(A)，比如性别属性的取值范围就是集合{男，女}。 如果属性A是数值属性，那么q的形式是A≤v，其中v是属于A的取值范围的一个常量;

如果A是分类属性，那么q的形式是A∈S’,其中S’是S(A)的子集。第32页,共154页，星期六，2024年，5月4.2.2树的生长 决策树是“一棵树”，它的根节点是整个数据集合空间，每个分节点是对一个单一变量(属性)的测试，该测试将数据集合空间分割成两个或更多块。每个叶节点是属于单一类别的记录。 首先，通过训练集生成决策树，再通过测试集对决策树进行修剪。

决策树的功能是预测一个新的记录属于哪一类。第33页,共154页，星期六，2024年，5月4.2.2树的生长 通常,通过自上而下递归分割的过程来构建决策树,分为三个步骤:(1)寻找初始分裂。整个训练集作为产生决策树的集合，

训练集每个记录必须是已经分好类的。决定哪个属性(field)域作为目前最好的分类指标。一般的做法是穷尽所有的属性域，对每个属性域分裂的好坏做出量化，计算出最好的一个分裂。(2)树增长到一棵完整的树。重复第一步，直至每个叶节点

内的记录都属于同一类，或达到其他停止准则。(3)数据的修剪。去掉一些可能是噪音或者异常的数据或节点第34页,共154页，星期六，2024年，5月4.2.2树的生长其通用的基本算法(贪心算法)为:

以自上而下分而治之的方法，开始时，所有的数据都在根节点;属性都是种类字段(如果是连续的，将其离散化);所有记录用所选属性递归地进行分割;属性的选择是基于一个启发式规则或者一个统计的度量(如informationgain)。 停止分割的条件:一个节点上的数据都是属于同一个

类别或没有属性可以再用于对数据进行分割。第35页,共154页，星期六，2024年，5月4.2.2树的生长—算法的形式描述ProcedureBuildTree(S){

用数据集S初始化根节点R

用根节点R初始化队列Q Whi1eQisnotEmpty,do{

取出队列Q中的第一个节点N ifN不纯(impure){ for每一个属性A

估计该节点在A上的信息增益 选出最佳的属性,将N分裂为N1,N2 } } }第36页,共154页，星期六，2024年，5月树的生长—CLS算法示例第37页,共154页，星期六，2024年，5月树的生长—CLS算法示例-2分类目标：设对上述数据按人种进行分类， 人员属性包括眼睛颜色、头发颜色和所属人种，记为:

A={眼睛颜色，头发颜色，所属人种}，其中A3={所属人种}为分类结果属性，分类属性值集，即分类结果R={黄种人，白种人，混血人种}，测试属性为{眼睛颜色，头发颜色}。第38页,共154页，星期六，2024年，5月树的生长—CLS算法示例-2 假设首先选择{眼睛颜色}作为测试属性，因为眼睛颜色属性值VA1={黑色，蓝色，灰色}，所以从该节点引出三个分枝，如下图所示。 这三个分枝将样本集分成三个子集{1，6}，{2，4，8}和{3，5，7}。因为这三个子集中的元素都不属于同一个结果类，因此它们都不是叶节点，需要继续划分，即需要添加新的测试节点。第39页,共154页，星期六，2024年，5月树的生长—CLS算法示例-2 因此，对这三个子集继续添加新的测试节点

{头发颜色}，因为头发颜色的属性值VA2={黑色，金色，红色}，因此从子集中可以引出新的三个分枝，如下图示。第40页,共154页，星期六，2024年，5月§4.2 树的建模过程-34.2.3有效性和风险性 基本的决策树算法没有考虑噪声,生成的决策树完全与训练例子拟合。 这样虽然能降低算法的时间复杂度，但也使算法在

较深层次的样本划分中，专注于训练样本集某个子集的统计信息，而忽视各类样本的整体分布情况，造成了对噪声敏感。 所以，虽然一棵完整的决策树能够非常准确地反映

训练样本集中数据的特征，但因失去了一般代表性而无法

对新数据进行准确的分类或预测，出现了过匹配现象。第41页,共154页，星期六，2024年，5月4.2.3有效性和风险性

过匹配指的是模型由于过度训练，导致其记住的不是训练数据的一般特性，而是训练集的局部特性。 当将这个模型应用到新的测试集上时就导致预测结果的不准确。 因此，一个完整的决策树构造过程将包含决策树的创建和决策树的剪枝这两方面。 剪枝是一种克服噪声的技术，用于解决过匹配问题，

同时它也能使树得到简化而变得更容易理解。第42页,共154页，星期六，2024年，5月4.2.3有效性和风险性剪枝的原则包括:奥卡姆剃刀原则——“如无必要，勿增实体”。即在与

观察相容的情况下，应当选择最简单的一棵决策树。决策树越小就越容易理解，其存储与传输的代价也就

越小。决策树越复杂，节点越多，每个节点包含的训练样本个数越少，则支持每个节点的假设的样本个数就越少，可能导致决策树在测试集上的分类错误率就会增大。

但决策树过小也会导致错误率较大。因此，

需要在树的大小与正确率之间寻找均衡点第43页,共154页，星期六，2024年，5月4.2.3有效性和风险性 常用的剪枝技术有预剪枝(pre-pruning)和后剪枝(post-pruning)两种。

预剪枝：在构造决策树时，决定不再对不纯的训练子集

进行进一步划分的剪枝方法

预剪枝技术限制了决策树的过度生长

如CHAID,ID3系列的ID3、C4.5算法等

后剪枝：在树完全生成之后的剪枝策略

如CART算法等 剪枝的目的就是删除由于噪声数据而引起的分枝，从而避免决策树的过匹配。第44页,共154页，星期六，2024年，5月4.2.3有效性和风险性 预剪枝中最直接而简单的方法是事先指定决策树生长的最大深度，使决策树不能得到充分生长。这种停止标准一般能够取得比较好的效果。不过指定树的高度的方法要求用户对数据的取值分布有较为清晰的把握，而且须对参数值进行反复尝试，否则无法给出一个较为合理的树高度阈值。

更普遍的做法是采用统计意义上的检验、信息增益等度量，评估每次节点分裂对系统性能的增益。如果节点分裂的增益值小于预先给定的阈值，则不对该节点进行扩展。如果在最好情况下的扩展增益都小于阈值，即使有些节点的样本不属于同一类，算法也可以终止。选取阈值是困难的，阈值较高可能导致决策树过于简化，而阈值较低可能对树的化简不够充分。第45页,共154页，星期六，2024年，5月4.2.3有效性和风险性 后剪枝技术允许决策树过度生长，然后根据一定的

规则，剪去决策树中那些不具有一般代表性的叶节点或分枝。 后剪枝算法有自上而下和自下而上两种剪枝策略。 自下而上的算法首先从最底层的内节点开始，剪去满足一定条件的内节点，在生成的新决策树上递归调用这个算法，直到没有可以剪枝的节点为止。 自上而下的算法是从根节点开始向下逐个考虑节点的剪枝问题，只要节点满足剪枝的条件就进行剪枝。第46页,共154页，星期六，2024年，5月4.2.3有效性和风险性 目前，决策树修剪策略主要有三种:悲观修剪(pessimisticpruning)，代价复杂度修剪(cost-complexitypruning)和基于最小描述长度(minimumdescriptionlength，MDL)原理的修剪。 悲观修剪是Quinlan在1987年提出的，该方法将所有的样本用于树的构建和修剪，但是这种方法产生的树太大，并且有时候精度不高。代价复杂度修剪使用了独立的样本用于修剪，这种策略适用于训练样本比较多的情况。在训练样本数目较少的情况下，需要将所有的样本既用于树的构建，又用于树的修剪。基于MDL原理的修剪是使用较多并且效果较好的方法。第47页,共154页，星期六，2024年，5月§4.2 树的建模过程4.2.4属性选择

属性选择的统计度量(又称为分枝指标splittingindex，SI)的计算是决策树构建算法的关键。 不同的决策树算法采用不同的统计度量，主要有:

信息增益——InformationGain(ID3和C4.5算法使用)，

所有属性假设都是种类字段，经过修改之后可以适用于

数值字段;

基尼指数——Giniindex(即Gini指标)

CART算法、CHAID算法和SLIQ算法使用

适用于种类和数值字段等等。第48页,共154页，星期六，2024年，5月4.2.4属性选择1.ID3算法

ID3算法是Quinlan为了从数据中归纳分类模型而构造的算法，它是一种经典决策树分类算法。ID3算法的基本概念包括:(1)决策树的每个内部节点对应样本的一个非类别属性，该节点的每棵子树代表这个属性的取值范围的一个子区间(子集)。一个叶节点代表从根节点到该叶节点的路径对应的样本所属的类别。这也是决策树的定义。(2)决策树的每个内部节点都与具有最大信息量的非类别属性相关联，这决定什么是一棵好的决策树。(3)通常用“熵”来衡量一个内部节点的信息量，熵的定义使用信息论中的定义。第49页,共154页，星期六，2024年，5月4.2.4属性选择-2

ID3的基本思想是自上而下地使用贪心算法搜索

训练样本集，在每个节点处测试每一个属性,从而构建决策树。 为了选择训练样本的最优分枝属性，ID3使用信息增益作为分枝指标。 下面将首先介绍信息增益的概念，然后给出ID3算法的

步骤，最后对ID3算法做一个简单的评价。第50页,共154页，星期六，2024年，5月4.2.4属性选择-2熵和信息增益 为了寻找对样本进行分类的最优方法，我们要做的工作就是使对一个样本进行分类时需要问的问题最少(即树的深度最小)。因此，需要某种函数来衡量哪些问题将提供最为平衡的划分，信息增益就是这样的函数之一。第51页,共154页，星期六，2024年，5月4.2.4属性选择-2 设S是训练样本集，它包含n

个类别的样本，这些类别分别用Cl，C2，…，Cn

表示，那么S的熵(entropy)或者

期望信息为:式中，pi

表示类Ci的概率。 如果将S中的n

类训练样本看成n

种不同的消息，那么S的熵表示对每一种消息编码平均需要的比特数。第52页,共154页，星期六，2024年，5月4.2.4属性选择-2

|S|*entropy(S)就表示对S进行编码需要的比特数，

其中，|S|表示S中的样本数目。e.g.

如果n=2，p1=p2=0.5，那么

entropy(S)=－0.51og20.5－0.51og20.5=1

如果n=2，p1=0.67，p2=0.33，那么

entropy(S)=－0.67log20.67－0.33log20.33=0.92第53页,共154页，星期六，2024年，5月4.2.4属性选择-2 可见，样本的概率分布越均匀，它的信息量(熵)就

越大，样本集的混杂程度也越高。因此，熵可以作为训练集的不纯度(Impurity)的一个度量，熵越大，不纯度就越高。 这样，决策树的分枝原则就是使划分后的样本的子集

越纯越好，即它们的熵越小越好。第54页,共154页，星期六，2024年，5月4.2.4属性选择-2 当样本属于每个类的概率相等时，即对任意i

有

pi=1/n时，上述的熵取到最大值log2n。而当所有样本属于同一类时，S的熵为0。其他情况的熵介于0~log2n之间。第55页,共154页，星期六，2024年，5月4.2.4属性选择-2 设属性A将

S划分成m份，根据A划分的子集的熵或

期望信息由下式给出： 式中，Si表示根据属性A划分的S的第i

个子集，|S|和|Si|分别表示S和Si

中的样本数目。 信息增益用来衡量熵的期望减少值，因此，使用属性A对S进行划分获得的信息增益为: gain(S，A)=entropy(S)－entropy(S，A)第56页,共154页，星期六，2024年，5月4.2.4属性选择-2

gain(S，A)是指因为知道属性A的值后导致的熵的期望压缩。

gain(S，A)越大，说明选择测试属性A对分类提供的信息越多。

因为熵越小代表节点越纯，按照信息增益的定义，信息增益越大，熵的减少量也越大，节点就趋向于更纯。 因此，可以对每个属性按照它们的信息增益大小排序，获得

最大信息增益的属性被选择为分枝属性。 即熵值反映了对样本集合S分类的不确定性，也是对样本分类的期望信息。熵值越小，划分的纯度越高，对样本分类的不确定性越低。一个属性的信息增益，就是用这个属性对样本分类而导致的熵的期望值下降。因此，ID3算法在每一个节点选择取得最大信息增益的属性。第57页,共154页，星期六，2024年，5月4.2.4属性选择-2

ID3算法在每一个节点选择取得

最大信息增益gain(S，A)的属性作为

分枝属性第58页,共154页，星期六，2024年，5月4.2.4属性选择-2

ID3算法

ID3算法在每个节点处评估每个属性的信息增益，选择获得最大信息增益的属性作为分枝属性。值得注意的是，

ID3算法在计算最优分枝属性时不考虑已经使用过的属性，即在从

决策树的根节点到叶节点的一条路径中，所有内部节点选择的分枝属性都是不同的。最初的ID3算法不能处理数值属性，在根据分枝属性划分样本时，

对该属性的每一个不同取值都产生一个新的节点，并将训练样本按照它们在该属性上的取值分配到这些新的子节点中。显然，ID3算法的决策树模型是一棵多叉树。

ID3算法是一种典型的决策树分类算法，后来发展的

许多决策树算法都是以ID3算法为基础的，第59页,共154页，星期六，2024年，5月4.2.4属性选择-2例子：使用信息增益进行决策树的分枝生长。 如下页训练数据集，反映了不同的顾客购买计算机的情况，其分类属性为buys_computer，即是否购买，分为二类。 求出该训练集在根节点的最佳分类。第60页,共154页，星期六，2024年，5月信息增益计算示例表第61页,共154页，星期六，2024年，5月4.2.4属性选择-2解：首先计算该训练集的熵， 根据熵公式，需知道各分类的概率，

buys_computer=yes的记录有9条，其概率为9/14,

记该集合为C1

buys_computer=no的记录有5条，其概率为5/14,

记该集合为C2

则，

entropy(S)=信息增益表第62页,共154页，星期六，2024年，5月4.2.4属性选择-2接下来计算根据每个非类别属性划分子集时的熵， 首先考察age

这一分类属性，需要知道按age分类后的各子集的目标属性集的概率，

age的youth类有5个样本，其中有2个属于C1

类，即buys_computer=yes，3个属于C2类，即buys_computer=no age的middle_aged类有4个样本，4个属于C1

类，0个属于C2类

age的senior类有5个样本，3个属于C1

类，2个属于

C2类于是，有entropy(S,age)=信息增益表第63页,共154页，星期六，2024年，5月4.2.4属性选择-2因此，属性age的增益为：gain(S,age)=entropy(S)－entropy(S,age)

=0.940－0.694=0.246位同理，可计算得：

gain(S,income)=0.029位gain(S,student)=0.151位

gain(S,credit_rating)=0.048位 可见，按属性age分类具有最高的增益，因此选择其为分枝属性。其分枝结果如下图示。 继续在每个节点迭代进行下去，可得到进一步生长的树，如下下页图示。第64页,共154页，星期六，2024年，5月4.2.4属性选择-2第65页,共154页，星期六，2024年，5月4.2.4属性选择-2age?student?credit_rating?yesnoyesnoyesyouthmiddle_agedseniornoyesfairexcellent第66页,共154页，星期六，2024年，5月4.2.4属性选择-2ID3算法本身还存在着许多需要改进的地方：(1)ID3算法只能处理分类属性，而不能处理数值属性。一个改进的办法是事先将数值属性划分为多个区间，形成新的分类属性。划分区间的主要问题是阈值的计算，即区间

端点的选取，这将包含大量的计算。(2)每个节点的合法分类数比较少，并且只能用单一属性

作为分枝测试属性。(3)ID3对训练样本质量的依赖性很强。训练样本的质量主要是指是否存在噪声和是否存在足够的样本。(4)ID3的决策树模型是多叉树，节点的子树个数取决于分枝属性的不同取值个数，这不利于处理分枝属性的取值数目较多的情况。目前流行的决策树算法大都采用二叉树模型。第67页,共154页，星期六，2024年，5月4.2.4属性选择-2(5)ID3算法不包括树的修剪，这样模型受噪声数据和

统计波动的影响比较大。(6)在不重建整棵树的条件下，不能方便地对决策树做更改。也就是说，当一个新样本不能被正确分类时，我们就

需要对树进行修改以适用于这一新样本。可以通过局部修补来实现这一点，但是在这种情况下，决策树却会

逐渐地失掉它作为某些重要概念的最有效表达的作用。或者也可以从头开始建立一棵新树，但是这样做必须

记住所有遇见过的样本。显然，这样做不是一个好办法。第68页,共154页，星期六，2024年，5月4.2.4属性选择-22.C4.5算法

ID3算法还存在着许多需要改进的地方，为此，Quinlan在1993年提出了ID3算法的改进版本C4.5算法。它与ID3算法的不同点包括:(1)分枝指标采用增益比例，而不是ID3算法所使用的信息增益。(2)按照数值属性值的大小对样本排序，从中选择一个分割点，划分数值

属性的取值区间，从而将ID3算法的处理能力扩充到数值属性上来。(3)将训练样本集中的未知属性值用最常用的值代替，或者用该属性的

所有取值的平均值代替,从而处理缺少属性值的训练样本。(4)使用Κ次迭代交叉验证,评估模型的优劣程度。(5)根据生成的决策树，可以产生一个if-then规则的集合，每一个规则

代表从根节点到叶节点的一条路径。第69页,共154页，星期六，2024年，5月4.2.4属性选择-2增益比例 信息增益是一种衡量最优分枝属性的有效函数，但是它倾向于选择具有大量不同取值的属性，从而产生许多

小而纯的子集。例如病人的ID、姓名和就诊日期等，特别是作为关系数据库中记录的主码属性，根据这样的属性划分的子集都是单元集，对应的决策树节点当然是纯节点。因此，需要新的指标来降低这种情况下的增益。Quinlan提出使用增益比例来代替信息增益。第70页,共154页，星期六，2024年，5月4.2.4属性选择-2 首先定义训练样本关于属性值的信息量(熵)split_info(S，A)，其中，S代表训练样本集，A代表属性，这个信息量是与样本的类别无关的，它的计算公式如下:式中，Si

表示根据属性A划分的第i个样本子集。 样本在A上的取值分布越均匀，split_info的值也就越大。split_info用来衡量属性分裂数据的广度和均匀性。 属性A的增益比例计算如下:第71页,共154页，星期六，2024年，5月4.2.4属性选择-2 当存在i

使得|Si|≈|S|时，split_info将非常小，从而导致增益比例异常的大，C4.5为解决此问题，进行了改进，它计算每个属性的信息增益，对于超过平均信息增益的属性，再进一步根据增益比例来选取属性。 一个属性分割样本的广度越大，均匀性越强，该属性的split_info越大，增益比例就越小。因此，split_info降低了

选择那些值较多且均匀分布的属性的可能性。

大于平均信息增益的增益率最大的属性即为所选分枝属性。

第72页,共154页，星期六，2024年，5月4.2.4属性选择-2

数值属性的处理C4.5处理数值属性的过程如下:l按照属性值对训练样本进行排序。2用不同的阈值对训练数据进行动态划分。3当输入改变时确定一个阈值.4取当前样本的属性值和前一个样本的属性值的中点作为

新的阈值。5生成两个划分，所有样本分布到这两个划分中;6得到所有可能的阈值、增益和增益比例。 每一个数值属性划分为两个区间，即大于阈值或小于等于阈值。第73页,共154页，星期六，2024年，5月4.2.4属性选择-2

未知属性值的处理

C4.5处理样本中未知属性值的方法是将未知值用最常用的值代替，或者用该属性的所有取值的平均值代替。另一种解决办法是采用概率的办法，对属性的每一个取值赋予一个概率，在划分样本集时，将未知属性值的样本按照属性值的概率分配到子节点中去，这些概率的获取依赖于已知的

属性值的分布。第74页,共154页，星期六，2024年，5月4.2.4属性选择-2

k

次交叉验证 交叉验证是一种模型评估方法，它将使用学习样本产生的决策树模型应用于独立的测试样本，从而对学习的结果进行验证。如果对学习样本进行分析产生的大多数或者全部分枝都是基于随机噪声的，那么使用测试样本进行分类的结果将非常糟糕。 如果将上述的学习-验证过程重复k次，就称为

k

次迭代交叉验证。 首先将所有的训练样本平均分成k份，每次使用其中的一份作为测试样本，使用其余的k－1份作为学习样本，

然后选择平均分类精度最高的树作为最后的结果。第75页,共154页，星期六，2024年，5月4.2.4属性选择-2 通常，分类精度最高的树并不是节点最多的树。除了用于选择规模较小的树，交叉验证还用于决策树的修剪。

k

次迭代交叉验证非常适用于训练样本数目比较少的情形。

但是，由于要构建k棵决策树,它的计算量非常大。第76页,共154页，星期六，2024年，5月4.2.4属性选择-2

规则的产生

C4.5还提供了将决策树模型转换为if-then规则的算法。 规则存储于一个二维数组中，每一行代表一个规则。

表的每一列代表样本的一个属性，列的值代表了属性的不同取值，例如，对于分类属性来说，0,1分别代表取属性的第一、二个值，对于数值属性来说，0,1分别代表小于等于和大于阈值。如果列值为-1，则代表规则中不包含该属性。第77页,共154页，星期六，2024年，5月4.2.4属性选择-23.CART算法

生成的是二叉树，用gini指标作为分枝度量，用

代价复杂度指标进行修剪，是一种后剪枝算法

CART算法更准确的应记为“C&RT算法”

(ClassificationandRegressionTrees，分类与回归树) CART算法是由Brieman等人在1984年提出的。在他们1984年出版的ClassificationandRegressionTrees

一书中有对算法的详尽介绍。这些来自斯坦福和加州大学伯克利分校的研究者们演示了如何将这一新算法用到各种不同的问题中，如从包含大量光谱的数据中发现氯元素。第78页,共154页，星期六，2024年，5月4.2.4属性选择-2

CART的一大优点是它将模型的验证和最优通用树的发现嵌在了

算法中。

CART是这样实现这一目标的:它先生成一棵非常复杂的树，再根据交叉验证和测试集验证的结果对树进行剪枝，从而得到最优通用树。这棵树是根据剪枝后不同版本的树在测试集数据上的性能得到的。复杂的树很少能在备用数据上表现出好的性能，因为对训练数据来说它是

过适应的。使用交叉验证，可能选择到最适应未来数据的树。 相对来说，CART算法对缺少数据的情况是比较稳健的。如果某条记录中缺少某个非类别属性的值，生成树时将不用这条记录来决定

最优分裂。实际上，CART是用它手头上所有可用的信息来决定可能的最优分裂。第79页,共154页，星期六，2024年，5月4.2.4属性选择-2 当在新数据上用CART进行分类时，可以用替代属性来处理缺少的值。替代属性是模拟树中实际分类的分裂值和非类别属性，当首选非类别属性的数据缺失时可以用它来代替。 例如,尽管把鞋的大小作为分类属性不如用身高作为

分类属性好，但当用CART模型进行分裂，而某条记录的

身高信息缺失时，可以试着用鞋的大小作为替代属性来模拟基于身高的分裂。第80页,共154页，星期六，2024年，5月4.2.4属性选择-CART算法-2根据给定样本集S构建分类树由以下三步组成:(1)使用S构建最大树Tmax，使得Tmax中每一个叶节点要么

很小(节点内部所包含的样本数小于给定值)，要么是

纯节点(节点内部样本属于同一个类)，要么不存在

非类别属性作为分枝属性。(2)使用修剪算法构建一个有限的、节点数目递减的

有序子树序列。(3)使用评估算法从子树序列中选出一棵最优树，作为

最终的决策树。第81页,共154页，星期六，2024年，5月4.2.4属性选择-CART算法-2上面的过程简单说来，即是：构建最大决策树

数据准备、gini指标、构建最大树修剪决策树

代价复杂度修剪子树评估

重替代评估、测试样本评估、交叉验证评估第82页,共154页，星期六，2024年，5月4.2.4属性选择-CART算法-2构建最大树 给定训练样本集，构建最大树就是使决策树充分生长，最终产生描述训练样本的最大二叉树。

CART能够处理数值属性和分类属性，在构建决策树之前，CART首先要对这些属性数据进行数据准备工作，包括降低属性的势和构造属性的标准问题集。与上面介绍的算法不同，CART使用的分枝指标是gini指标，而不是信息增益。 其主要工作包括：

数据准备计算gini指标构建最大树第83页,共154页，星期六，2024年，5月4.2.4属性选择-CART算法-2(l)数据准备

CART的数据准备工作包括降低属性的势和构造属性的标准问题集。

属性的势(cardinality)又称为属性的基数，样本的每个

属性的所有取值构成了一个有限集合，对于有限集来说，

集合的势就是集合中元素的个数。 因此，降低属性的势就是为每一个属性分配一组

离散值，按照业务需求，将属性的实际值映射到这组离散值上，通常选定的这组离散值的个数要少于属性的实际取值的个数。

属性的标准问题集是所有候选的分枝方案的集合，数值属性和分类属性的标准问题的形式是不一样的。第84页,共154页，星期六，2024年，5月4.2.4属性选择-CART算法-2 若属性A是数值属性，那么A的标准问题集是由形如

“IsA≤d?”的分枝测试构成的集合。

首先取出训练样本中属性A的所有不同取值，将这些值按照

从小到大的顺序排序，然后计算排序后的数值序列中每相邻两个数值的中间值，得到一个新的序列A’

，最后根据A’生成属性A的标准问题集。 例如，假设属性A所有不同取值在排序后得到的序列为:

(1，1.5，1.7,1.9，2，2.6，2.9，3.3，3.8,4.2，5)那么中间值序列为:

A’=(1.25，1.6,1.8，1.95，2.3，2.75，3.1，3.55,4,4.6)于是，属性A的标准问题集为:

{IsA≤1.25，IsA≤1.6,IsA≤1.8，IsA≤1.95，IsA≤2.3，IsA≤2.75，IsA≤3.1，IsA≤3.55,IsA≤4,IsA≤4.6}第85页,共154页，星期六，2024年，5月4.2.4属性选择-CART算法-2 若属性A是分类属性，那么A的标准问题集是由形如

“IsA∈s?”

的分枝测试构成的集合，其中s是属性A的所有不同取值构成的集合S(A)的非空子集。 首先取出训练样本中属性A中所有不同取值构成集合S(A)，然后计算一个由S(A)的子集构成的集合subsets(A),最后根据subsets(A)生成属性A的标准问题集。

subsets(A)的元素满足以下两个条件:1)如果s∈subsets(A)，那么s≠S(A)，并且s不为空;2)如果s1,s2∈subsets(A)，那么s1∪s2≠S(A)。第86页,共154页，星期六，2024年，5月4.2.4属性选择-CART算法-2 例如：S(A)={a1,a2,a3,a4}，根据既定算法得出subsets(A)={{a1},{a1,a2},{a2},{a1,a3},{a1,a2,a3},{a2,a3},{a3}},

于是，得到问题A的标准问题集为：{IsA∈{a1},IsA∈{a1,a2},IsA∈{a2},IsA∈{a1,a3},IsA∈{a1,a2,a3},{a2,a3},{a3}},第87页,共154页，星期六，2024年，5月4.2.4属性选择-CART算法-2(2)gini指标 假设S是用来划分的样本集合，我们选择的划分方法

必须使S的子集比它本身更“纯”，可以用一个不纯函数χ

来评估各种划分方法的优劣。 如果我们用χ(t)

来表示任意节点t的不纯度，那么χ(t)可以表示为:式中，p(ci|t)表示类ci

在数据集t

中的概率。第88页,共154页，星期六，2024年，5月4.2.4属性选择-CART算法-2 根据这个定义，分枝方案s的优劣度可以用不纯度的

减少量△χs(t)

来定义.

如果测试s将样本集合t分为n个子集t1,t2,…,tn,那么分枝优劣度可以定义为:第89页,共154页，星期六，2024年，5月4.2.4属性选择-CART算法-2如果用gini指标，那么函数χ的定义为:这时，在测试s下gini(s)可以用不纯度的减少量△χs(t)

表示为:如果某个测试s使gini(s)最大，那么表示在测试s下不纯度的减少量最大，则s就是最优的分枝方案。第90页,共154页，星期六，2024年，5月4.2.4属性选择-CART算法-2(3)构建最大树Tmax

当数据准备完成后，就可以根据训练样本构建

最大树Tmax。 首先初始化决策树的根节点，并将所有的训练样本分配给根节点;然后通过递归来划分训练样本，将之分配给

新生成的子节点;最终产生一棵完全生长的决策树，递归

结束的条件是所有的叶节点要么很小，要么是纯节点，要么不存在非类别属性作为分枝属性。

CART的决策树模型是二叉树，在对某个节点执行分裂时，将节点中的样本划分成tL和tR两部分，样本的概率分别为pL

和pR，然后将tL和tR的样本分别分配到该节点的左右子节点中。第91页,共154页，星期六，2024年，5月4.2.4属性选择-CART算法-2 在划分训练样本、执行节点分裂之前，首先要计算节点的分枝方案，分枝方案是从数据准备阶段生成的属性的标准问题集中挑选出来的。

在每个节点处评估所有属性的每个标准问题的

gini指标，然后选择gini指标最大的标准问题作为分枝方案。第92页,共154页，星期六，2024年，5月4.2.4属性选择-CART算法-2 设样本有n个属性，分别为A1，A2，…,An，对应的

标准问题集为Ql，Q2，…，Qn，标准问题集Qi

的第j个标准问题用Qi，tj

表示。 在节点N中，属性Ai

的第j

个标准问题的gini指标用gini(i,j,N)表示，使用属性Ai

执行分裂的最大gini指标用gini(i，N)表示，最优分枝方案(gini指标最大的分枝方案)的gini指标用gini(N)表示，显然有

gini指标为gini(N)的标准问题Qi,tj

被选为节点N的分枝方案。第93页,共154页，星期六，2024年，5月4.2.4属性选择-CART算法-2上面的过程简单说来，即是：构建最大决策树

数据准备、gini指标、构建最大树

修剪决策树

代价复杂度修剪子树评估

重替代评估、测试样本评估、交叉验证评估第94页,共154页，星期六，2024年，5月4.2.4属性选择-CART算法-2

修剪决策树

CART的决策树修剪采用一种称为代价复杂度修剪的

策略，产生一个节点数目递减的子树序列。在生成子树序列之后，还要确定叶节点对应的类别。其主要工作包括：

1）生成有序子树序列

2）确定叶节点的类别第95页,共154页，星期六，2024年，5月4.2.4属性选择-CART算法-2(l)生成有序子树序列 采用代价复杂度修剪策略是基于以下两个事实: 1)复杂决策树(节点多)对训练样本有很高的分类精度，但是当将它应用于新的测试样本时，分类精度并不高;

2)理解和解释具有大量叶节点的决策树是一个复杂的

过程。 因此，决策树的复杂度可以用叶节点的数目来衡量，而决策树的代价则以分类精度来衡量，一个好的决策树

分类模型应该在复杂度与代价之间进行权衡。第96页,共154页，星期六，2024年，5月4.2.4属性选择-CART算法-2树T的代价复杂度可以用下面的公式计算:Rα(T)=R(T)+α|~T|其中，Rα(T)

表示树T的代价复杂度;

R(T)

表示T的重替代评估，它是将T用于学习样本时的分类错误率;

|~T|表示T的叶节点数;

α

称为复杂度参数，它定义为每增加一个叶节点所

提高的代价复杂度。第97页,共154页，星期六，2024年，5月4.2.4属性选择-CART算法-2

α越大，复杂度因素对考察决策树的代价复杂度的影响也越大。 当α=0时，表示不考虑复杂度因素对代价复杂度的影响，这时算法倾向于选择叶节点最多的决策树，因为它对

训练样本的分类错误率最低;

当α足够大时，重替代评估的影响可以忽略，算法倾向于选择只有一个叶节点的决策树。

正确衡量决策树的α值应该介于上述两个极端情况之间第98页,共154页，星期六，2024年，5月4.2.4属性选择-CART算法-2 为了得到有序子树序列，还需要提出节点的代价复杂度概念，节点t的代价复杂度实际上就是将t看作叶子节点

(修剪掉t的子树Tt)时的代价复杂度，因此，t的代价复杂度可以用如下公式计算:

Rα({t})=R(t)+α其中，{t}表示由节点t构成的子树;

R(t)表示节点t的重替代评估，即将决策树用于学习样本时节点t上的分类错误率;α为复杂度参数。 可见节点t的代价复杂度可以看作只有一个节点的决策树{t}的代价复杂度。第99页,共154页，星期六，2024年，5月4.2.4属性选择-CART算法-2 如果用Rα(Tt)表示t的子树Tt

的代价复杂度，那么

Rα(Tt)=R(Tt)+α|~Tt|

根据代价复杂度修剪策略，如果节点t的代价复杂度

大于它的子树的代价复杂度，即Rα({t})>Rα(Tt)

，则

应该保留子树Tt，否则就有理由修剪此子树将上面的Rα({t})

和Rα(Tt)代入，得到第100页,共154页，星期六，2024年，5月4.2.4属性选择-CART算法-2 当时，节点t和子树Tt

具有相同的

代价复杂度，但{t}比Tt的节点少，因此，{t}比Tt更可取 当时，节点t的代价复杂度比子树Tt

更小，因此，{t}也比Tt更可取；这就是CART算法逐步修剪生成有序子树序列的主要思想。 当复杂度参数α给定时，的值越小，

表示t的代价复杂度比Tt的代价复杂度小的程度越大，

于是，Tt被修剪的理由越充分。为描述方便，我们称此

计算值为β。第101页,共154页，星期六，2024年，5月4.2.4属性选择-CART算法-2CART产生有序子树序列的步骤 假设生成的子树序列以节点数目递减的顺序排列为T1>T2>T3>…>{tl}，其中{tl}表示只有一个根节点的子树。 生成T1

的方法是减去Tmax所有满足R(T)=R(tL)+R(tR)的子树，其中tL和tR分别表示节点t

的左右子节点，修剪得到的子树即为T1。第102页,共154页，星期六，2024年，5月4.2.4属性选择-CART算法-2 为了构建T2

，首先给出T1的最弱联系节点的定义，对任意

t∈T1，令其中，~T1表示T1叶节点集合。 定义T1的最弱联系节点满足第103页,共154页，星期六，2024年，5月4.2.4属性选择-CART算法-2 将t1从T1中剪去就得到树T2

，如果存在多个最弱

联系点，则将它们全部剪去。 从T2

得到T3的过程与从T1得到T2的过程相同，即剪去T2的最弱联系节点。重复上述过程，直到修剪后的子树

只剩下一个节点，将它作为有序子树序列的最后一个

子树{tl}。第104页,共154页，星期六，2024年，5月4.2.4属性选择-CART算法-2(2)确定叶节点的类别 根据决策树的定义，每个叶节点对应一个类标号，最简单的类别分配方法就是指定节点中样本数目最多的类为

该叶节点的类， 如果存在多个类的样本个数都为最大值，那么就任意指定一个类作为该叶节点的类。

第105页,共154页，星期六，2024年，5月4.2.4属性选择-CART算法-2 如果对任意类i

和j

，将类j

的样本误分为类i

的代价是相同的，那么这样的分配方法是合理的，但是在很多领域中，各个类之间误分的代价往往是不同的，例如在信用评分系统中，将一个低信用度客户误分为高信用度客户的代价可能大于将高信用度客户误分为低信用度客户的代价，因此，我们可以对节点t中每一个类i

计算它的误分代价期望 其中c(i|j)表示将类j

分为类i的代价，当i=j

时,c(i|j)=0;p(j|t)表示节点t

中属于类j

的样本的概率。将取得最小误分代价期望的类i

指定为节点t

的类。第106页,共154页，星期六，2024年，5月4.2.4属性选择-CART算法-2上面的过程简单说来，即是：构建最大决策树

数据准备、gini指标、构建最大树修剪决策树

代价复杂度修剪

子树评估

重替代评估、测试样本评估、交叉验证评估第107页,共154页，星期六，2024年，5月4.2.4属性选择-CART算法-2

子树评估 子树评估的目的是从有序子树序列中选取一棵“最优”子树作为最终的分类模型。

CART的子树评估方法有重替代评估、测试样本评估和交叉验证评估，这三种评估方法都是根据子树的代价来评估的，

Brieman等提出了子树评估的1SE(onestandarderror)

规则，考虑了决策树复杂度的因素。 以下简介几种评估：重替代评估、测试样本评估、

交叉验证评估、及1SE(onestandarderror)规则第108页,共154页，星期六，2024年，5月4.2.4属性选择-CART算法-2(1)重替代评估 重替代评估使用构建决策树的样本来评估决策树的

误分代价。 将学习样本应用于每个子树，子树的重替代评估定义为:

其中，N为训练样本的个数，

c(i|j)表示将类