第9章 决策树算法

第9章决策树算法1编辑ppt本章大纲：

决策树算法原理常用决策树算法决策树剪枝由决策树提取分类规则应用实例分析2编辑ppt9.1决策树算法原理优点：使用者不需要了解很多背景知识，只要训练事例能用属性→结论的方式表达出来，就能用该算法学习；决策树模型效率高，对训练集数据量较大的情况较为适合；分类模型是树状结构，简单直观，可将到达每个叶结点的路径转换为IF→THEN形式的规则，易于理解；决策树方法具有较高的分类精确度。3编辑ppt9.1决策树算法原理传统的数据分类操作通常有以下两个步骤:模型训练阶段：根据给定的训练集，找到合适的映射函数H:→C的表示模型。使用上一步训练完成的函数模型预测数据的类别，或利用该函数模型，对数据集中的每一类数据进行描述，形成分类规则。4编辑ppt9.1决策树算法原理工作过程：决策树分类模型的工作过程图5编辑ppt9.1决策树算法原理定义9.1给定一个训练数据集D＝，其中每个实例，称为例子，训练数据集中包含以下属性A=。同时给定类别集合C。对于训练数据集D，决策树是指具有以下性质的树：每个内部节点都被标记一个属性Ai。每个弧都被标记一个值，这个值对应于相应父结点的属性。每个叶节点都被标记一个类Cj。6编辑ppt9.1决策树算法原理定义9.2分裂准则定义为在决策树算法中将训练数据集D中的元组划分为个体类的最好的方法与策略，它告诉我们在节点N上测试哪个属性合适，如何选择测试与测试的方法，从节点N上应该生长出哪些分支。定义9.3分裂属性Xi定义为决策树中每个内部节点都对应的一个用于分裂数据集的属性。XiA=7编辑ppt9.1决策树算法原理定义9.4

如果Xi是连续属性，那么分裂准则的形式为Xi，其中，就称为节点n的分裂点。定义9.5如果Xi是离散属性，那么的形式为，其中，就称为节点n的分裂子集。注意：分裂准则与分裂属性、分裂点、分裂子集并不等同，它们是四个不同的概念，并且分裂子集分裂点分裂属性分裂准则8编辑ppt9.1决策树算法原理将上面的定义结合实际的决策树例子可得决策树图如下图9-1，图9-2，图9-3所示，图中设X为分裂属性，是属性X的已知值。

图9-2按照分裂点划分而成的决策树图与相关的具体例子图9编辑ppt9.1决策树算法原理

图9-3按照分裂子集划分而成的决策树图与相关的两个具体例子图10编辑ppt9.1决策树算法原理图9-4按照分裂子集划分而成的决策树（只能是二叉树）图与相关的具体例子图

11编辑ppt9.1决策树算法原理目前主要使用如下几个量化评估标准(1)预测准确性(2)模型强健性(3)描述的简洁性(4)计算复杂性(5)处理规模性12编辑ppt9.2常用决策树算法ID3算法

ID3是Quinlan于1986年提出的，是机器学习中一种广为人知的一个算法，它的提出开创了决策树算法的先河，而且是国际上最早最有影响的决策树方法，在该算法中，引入了信息论中熵的概念，利用分割前后的熵来计算信息增益，作为判别能力的度量。

13编辑ppt9.2.1ID3算法

定义9.6信息熵自信息量只能反映符号的不确定性，而信息熵可以用来度量整个信源X整体的不确定性。设某事物具有n种相互独立的可能结果(或称状态)：，每一种结果出现的概率分别为且有：（9.1）那么，该事物所具有的不确定量为：（9.2）

14编辑ppt9.2.1ID3算法上式即为著名的香农信息量公式。注意到式中的对数以2为底，当n=2时且时，熵=1比特。由此可见，一个等概率的二选一事件具有1比特的不确定性。所以，可以把一个等概率的二选一事件所具有信息量定为信息量的单位。任何一个事件能够分解成n个可能的二选一事件，它的信息量就是n比特。15编辑ppt9.2.1ID3算法Quinlan的首创性工作主要是在决策树的学习算法中第一次引入了信息论中的互信息（称之为信息增益），以之作为属性选择的标准，并且将建树的方法嵌入在其中，其核心是在决策树的各级节点上选择属性，用信息增益作为属性选择标准16编辑ppt9.2.1ID3算法下面给出的是ID3算法中将香农的信息熵定义应用到决策树构造中，进而给出的信息增益的定义。

设训练数据集D=,是n维有穷向量空间，其中是有穷离散符号集，D中的每个元素，叫做例子，其中设PD和ND是D的两个子集，分别叫做正例集和反例集。17编辑ppt9.2.1ID3算法

假设训练数据集D中的正例集PD和反例集ND的大小分别为p和n，则ID3基于下面两个假设给出该决策树算法中信息增益的定义，因为信息是用二进制编码的，所以在下面的公式定义中都用以2为底的对数。（1）在训练数据集D上的一棵正确决策树对任意例子的分类概率同D中正反例的概率一致；（2）一棵决策树能对一个例子做出正确类别判断所需的信息量如下公式所示：18编辑ppt9.2.1ID3算法

如果以属性A作为决策树的根，A具有v个值，它将A分为v个子集，假设中含有p个正例和n个反例，那么子集所需的信息期望是，那么，以属性A为根所需的信息期望如下公式所示：因此，以A为根的信息增益如下公式所示：

19编辑ppt9.2.1ID3算法上面给出的ID3中的信息论的相关定义主要是在两类分类问题的前提下，下面给出将其扩展到多类后的相关定义描述。设训练数据集D一共有m类样例，每类样例数为：。同样以属性A作为决策树的根，具有v个值，它将D分为v个子集，假设子集中任意元组属于类C的概率用表示，并用估计。那么，该子集的信息量定义如下所示：

那么以A为根分类后所需的信息期望如下面公式所示：20编辑ppt9.2.2C4.5算法

（1）分裂（2）连续数据（3）缺失数据（4）规则21编辑ppt9.2.2.1C4.5的分裂属性选择度量ID系列的算法为什么会产生归纳偏置呢？归纳偏置是一系列前提，这些前提与训练数据一起演绎论证未来实例分类。如果给定一个训练数据集，那么通常有很多决策树与这些样例一致。所以，要描述ID系列算法的归纳偏置，应找到它从所有一致假设中选择一个的根据。22编辑ppt9.2.2.1C4.5的分裂属性选择度量ID系列的搜索策略为：（1）优先选择较短的树而不是较长的；（2）选择那些信息增益高的属性离根节点较近的树。结论：ID系列算法的归纳偏置是因为它在选的时候较短的树比较长的树优先所产生的，也就是那些信息增益高的属性更靠近的根节点将会有优先生成树的特权。23编辑ppt9.2.2.1C4.5的分裂属性选择度量为了避免这个偏置，弥补ID系列算法的不足就要舍弃信息增益这个度量而选择别的决策属性作为度量标准。Quinlan在他1986年中的论文中提出了一种可以使用的度量标准：增益比率。增益比率通过加入一个被称为分裂信息（splitinformation）的项来惩罚类似Date这样的属性，分裂信息用来衡量属性分裂数据的广度和均匀性，它由如下公式所示：

24编辑ppt9.2.2.1C4.5的分裂属性选择度量增益比率的公式如下所示：

25编辑ppt9.2.2.2C4.5对连续数据的处理ID3算法最初的定义是假设属性值是离散值，但在实际环境中，有很多属性是连续的，不能够用一个确定的标准来对其进行划分。C4.5使用下面的一系列处理过程来对连续的属性划分成离散的属性，进而达到能够建立决策树的目的。26编辑ppt9.2.2.2C4.5对连续数据的处理Step1根据训练数据集D中各个属性的值对该训练数据集进行排序；Step2利用其中各属性的值对该训练数据集动态地进行划分；Step3在划分后的得到的不同的结果集中确定一个阈值，该阈值将训练数据集数据划分为两个部分；Step4针对这两边各部分的值分别计算它们的增益或增益比率，以保证选择的划分使得增益最大。27编辑ppt9.2.2.3C4.5对缺失数据的处理为了评估属性A是否是决策节点n的最佳测试属性，要计算决策树在该节点的信息增益Gain(D,A)。假定<,c()>是S中的一个训练样例，并且其属性A的通过值分得的信息值表示为

.28编辑ppt9.2.2.4C4.5对生成规则的利用只要生成了决策树后，就可以把树转换成一个IF-THEN规则的集合。当然，每种算法生成的决策树都可以转换成相应的if-then规则，C4.5算法处理规则与其他算法不同在于它把规则存储在一个二维数组中，每一行都代表着树中的一个规则，即从树根到叶子之间的一个路径.29编辑ppt9.2.3CART算法

CART（ClassificationandRegressionTrees）算法是由几位统计学家L.Breiman，J.Friedman，R.Olshen和C.Stone在发表的刊物《分类与回归树》中提出的一种产生二叉决策树分类模型的技术。它与前面Quinlan提出的ID系列算法和C4.5不同的是，使用的属性度量标准是Gini指标，它和后面将要介绍的算法的共同点也是在于都是利用了相同的属性度量标准Gini指标。30编辑ppt9.2.3CART算法Gini指标主要是度量数据划分或训练数据集D的不纯度为主，系数值的属性作为测试属性，Gini值越小，表明样本的“纯净度”越高。Gini指标定义为如下公式：31编辑ppt9.2.3CART算法由于二叉树不易产生数据碎片，精确度往往也会高于多叉树，所以在CART算法中，统计学家们采用了二元划分，在分支节点上进行Gini值的测试，如果满足一定纯度则划分到左子树，否则划分到右子树，最终生成一棵二叉决策树。在只有二元分裂的时候，对于训练数据集D中的属性A将D分成的D1和D2，则给定划分D的Gini指标如下公式所示：32编辑ppt9.2.3CART算法对于离散值属性，在算法中递归的选择该属性产生最小Gini指标的子集作为它的分裂子集。对于连续值属性，必须考虑所有可能的分裂点。其策略类似于上面ID3中介绍的信息增益处理方法，可以用如下公式所示：33编辑ppt9.2.3CART算法CART算法在满足下列条件之一，即视为叶节点不再进行分支操作。（1）所有叶节点的样本数为1、样本数小于某个给定的最小值或者样本都属于同一类的时候；（2）决策树的高度达到用户设置的阈值，或者分支后的叶节点中的样本属性都属于同一个类的时候；（3）当训练数据集中不再有属性向量作为分支选择的时候。34编辑ppt9.2.4PUBLIC算法

前面几个小节的决策树算法都是先建树再剪枝。PUBLIC(PruningandBuildingIntegratedinClassification)算法[8,17]将建树、剪枝结合到一步完成，即是预剪枝，在建树阶段不生成会被剪枝的子树，从而大大提高了效率。

PUBLIC算法的建树是基于SPRINT方法、对其决策树的剪枝使用的是基于最小编码代价的MDL算法，但MDL原则不能直接应用。35编辑ppt9.2.5SLIQ算法SLIQ(SupervisedLearningInQuest)算法利用3种数据结构来构造树，分别是属性表、类表和类直方图。SLIQ算法在建树阶段，对连续属性采取预排序技术与广度优先相结合的策略生成树，对离散属性采取快速的求子集算法确定划分条件。具体步骤如下：Step1建立类表和各个属性表，并且进行预排序，即对每个连续属性的属性表进行独立排序，以避免在每个节点上都要给连续属性值重利用新排序；Step2如果每个叶节点中的样本都能归为一类，则算法停止；否则转(3)；Step3利用属性表寻找拥有最小Gini值的划分作为最佳划分方案。36编辑ppt9.2.5SLIQ算法Step4根据第3步得到的最佳方案划分节点，判断为真的样本划归为左孩子节点，否则划归为右孩子节点。这样，(3)(4)步就构成了广度优先的生成树策略。Step5更新类表中的第二项，使之指向样本划分后所在的叶节点。Step6转到步骤(2)。37编辑ppt9.2.6SPRINT算法SPRINT算法是对SLIQ算法的改进，其目的有两个：一是为了能够更好的并行建立决策树，二是为了使得决策树T适合更大的数据集。SPRINT(ScalableParallelizableInductionofClassificationTree)算法是一种可扩展的、可并行的归纳决策树，它完全不受内存限制，运行速度快，且允许多个处理器协同创建一个决策树模型。

38编辑ppt9.2.6SPRINT算法SPRINT算法定义了两种数据结构，分别是属性表和直方图。属性表由一组三元组<属性值、类别属性、样本号>组成，它随节点的扩张而划分，并附属于相应的子节点。与SLIQ算法不同，SPRINT算法采取传统的深度优先生成树策略，具体步骤如下：

Step1生成根节点，并为所有属性建立属性表，同时预排序连续属性的属性表。Step2如果节点中的样本可归为一类，则算法停止；否则转(3)。Step3利用属性表寻找拥有最小Gini值的划分作为最佳划分方案。算法依次扫描该节点上的每张属性表。Step4根据划分方案，生成该节点的两个子节点,。Step5划分该节点上的各属性表，使之关联到或上。39编辑ppt9.2.6SPRINT算法Step6分别转到步骤(2)考察,节点。SPRINT算法在剪枝阶段进行基于MDL的剪枝，至此构成了SPRINT算法的串行化算法。将串行化算法稍加改进，就成为并行化算法：将训练数据集平均分布到n个处理器上，而后每个处理器生成自己的数据分片。由于连续属性值要求全局排序，因此要将n个处理器上的连续属性的属性表综合重新排序，再平均分布到n个处理器上。在建立Hash表之前，需要从n个处理器上收集所有的样本号信息。40编辑ppt9.3决策树剪枝在现实世界中，获得的数据并不可能保证其完美性与完整性，所以，在当被用来创建决策树的训练数据集中存在有噪声，或者数量太少以至于不能产生目标函数的有代表性的采样的时候，我们使用决策树算法生成的决策树很多分支反映的是训练数据集中的异常。在上面任意一种情况发生的时候，利用简单算法产生的树会出现过拟合训练样例的现象。41编辑ppt9.3决策树剪枝在利用决策树算法进行分类的过程中，有两个过程，在9.1节中有介绍，第一个过程我们必须要利用训练数据来进行决策树分类模型的建立，另一个过程则是将建立好的决策树分类模型对给定的测试数据进行分类。42编辑ppt9.3.1预剪枝预剪枝也称为先剪枝，在该方法中主要是通过提前停止树的构造（例如，通过确定在给定的节点不再分裂或划分训练元组的子集）来对决策树进行剪枝。一旦停止以后，剩下的那个节点就成为了树叶。该树叶可能持有子集元组中最频繁的类或这些元组的概率分布。43编辑ppt9.3.1预剪枝预剪枝判断停止决策树的生长的方法大体上可以归纳为以下几种：（1）一种最为简单的方法就是在决策树到达一定高度的情况下就停止树的生长；（2）到达此结点的实例具有相同的特征向量，而不必一定属于同一类，也可停止生长。这种情况可以处理数据中的数据冲突问题；（3）到达此结点的实例个数小于某一个阈值也可停止树的生长；（4）更为普遍的做法是计算每次扩张对系统性能的增益，如果这个增益值小于某个阈值则不进行扩展。如果在最好情况下的扩展增益都小于阈值，即使有些叶子结点的实例不属于同一类，也停止树的增长。44编辑ppt9.3.2后剪枝

后剪枝算法已经得到了广泛的应用，这个算法最初是由Breiman等提出，它首先构造完整的决策树，允许决策树过度拟合训练数据，然后对那些置信度不够的结点的子树用叶子结点来替代，这个叶子结点所应标记的类别为子树中大多数实例所属的类别。45编辑ppt悲观错误剪枝PEP(PessimisticErrorPruning)REP方法进行剪枝具有以下优点：（1）运用REP方法得到的决策树是关于测试数据集的具有最高精度的子树，并且是规模最小的树。（2）它的计算复杂性是线性的，这是因为决策树中的每个非叶子结点只需要访问一次就可以评估其子树被修剪的概率。（3）由于使用独立的测试数据集，和原始决策树相比，修剪后的决策树对未来新事例的预测偏差较小。46编辑ppt悲观错误剪枝PEP(PessimisticErrorPruning)正是由于REP方法出现的一系列问题，随后Quinlan提出了可以在一定程度弥补上面缺陷的PEP方法，也就是悲观剪枝方法。该方法引入了统计学上连续修正的概念来弥补这一个缺陷，在评价子树的训练错误的公式中添加了一个常数，假定每个叶节点都自动对实例的某部分进行错误的分类。47编辑ppt悲观错误剪枝PEP(PessimisticErrorPruning)所用来剪枝的度量的基本思想可以概述为以下几点：（1）假设训练数据集生成原始树为T，某一叶子结点的实例个数为，其中错误分类的个数为；（2）我们定义训练数据集的误差率如下公式9.13所示：（9.13）由于训练数据集既用来生成决策树又用来修剪树，所以是有偏倚的，利用它来修剪的决策树树并不是最精确，最好的；（3）为此，Quinlan在误差估计度量中增加了连续性校正，将误差率的公式修改为如下公式9.14所示:

（9.14）48编辑ppt悲观错误剪枝PEP(PessimisticErrorPruning)

那么，同样的，我们假设s为树T的子树的其中一个子节点，则该子树的叶子结点的个数为，的分类误差率如下公式所示:在定量的分析中，为简单起见，我们用误差总数取代上面误差率的表示，即有公式:

那么，对于子树，它的分类误差总数如下公式所示：49编辑ppt最小错误剪枝MEP(MinimumErrorPruning)MEP方法是由Niblett和Bratko首先提出来的，它在一个相对独立的数据集上从树的叶子结点开始，向上搜索一个单一的树来使分类误差的期望概率达到最小，但它并不需要一个额外的修剪数据集。使用的信息来自于训练数据集，其目的是在未知的数据集上产生最小预测分类错误率。50编辑ppt代价－复杂度剪枝CCP(Cost-ComplexityPruning)CCP方法就是著名的CART（ClassificationandRegressionTrees)剪枝算法，它包含两个步骤：(1)自底向上，通过对原始决策树中的修剪得到一系列的树，其中是由中的一个或多个子树被替换所得到的，为未经任何修剪的原始树，为只有一个结点的树。(2)评价这些树，根据真实误差率来选择一个最优秀的树作为最后被剪枝的树。51编辑ppt基于错误剪枝EBP(Error-BasedPruning)EBP剪枝法是一种应用于C4.5算法的自下向上的剪枝法，被认为是PEP剪枝法的改进，因为EBP剪枝基于对训练数据集的更加悲观的估计。同PEP剪枝，EBP仅利用训练数据集来构建和剪枝决策树。假设可将叶结点覆盖的实例看作统计样本，叶结点对实例的分类错误率遵循二项式分布，并利用置信因子CF控制剪枝的程度。我们将CF定义为如下公式所示:

52编辑ppt9.4由决策树提取分类规则决策树分类方法有它的优点，但是也有一定的局限性，比如，利用算法生成的决策树的规模会因为训练数据集的巨大而变得过大使得难以理解，可读性差。如果直接从决策树中提取出IF－THEN规则，建立基于规则的分类器，与决策树分类器相比，IF－THEN规则可能更容易理解，特别是当决策树分支非常大时也一样。53编辑ppt9.5应用实例分析下面我们利用上面表9-1根据天气是否打网球的训练数据集，利用ID3算法来判断某天是否适合打网球。（1）类别属性信息熵的计算由于未分区前，训练数据集中共有14个实例，其中有9个实例属于p类（适合打网球的），5个实例属于n类（不适合打网球），因此分区前类别属性的熵为：54编辑ppt9.5应用实例分析（2）非类别属性信息熵的计算若选择Outlook为测试属性。＝0.694bit55编辑ppt9.5应用实例分析因此，这种划分的信息增益是：同理，可以求出其它三个属性的信息增益为，，。由上可知，属性值Outlook在各个属性中具有最高的增益，被选作分裂属性。则第一个根节点T被用标记，并对于每个属性值生长一个分支：（3）递归地创建决策树的树枝和叶子选择作为测试属性后，将训练实例集分为三个子集，生成三个子节点，对每个子节点递归采用上述过程进行分类直至每个节点都成为叶节点而已。

56编辑ppt9.5应用实例分析属性值Outlook在各个属性中具有最高的增益，被选作分裂属性。则第一个根节点T被用标记，并对于每个属性值生长一个分支：根据信息增益结果生成的以Outlook为根节点的初级决策树图

57编辑ppt9.5应用实例分析A．分析图中的sunny分支，计算其子属性的信息增益值来决定子分裂属性形成子分支之一。针对sunny中的子训练数据集分支，有两个类别，该分支中有3个实例属于n类，有2个实例属于p类，因此针对分支的信息熵为：若以：sunny分支中的属性Temperature为测试属性，则测试属性Temperature的信息量为：58编辑ppt9.5应用实例分析其信息增益为：若以：sunny分支中的属性Humidity为测试属性，则测试属性Humidity的信息量为：

0.00bit其信息增益为：若以：sunny分支中的属性Wind为测试属性

，则测试属性windy的信息量为：

0.468bit其信息增益为：＝0.971－0.468=0.493bit0.971-0.00=0.971bit59编辑ppt9.5应用实例分析这时生成的决策树如图所示：决策树构造图260编辑ppt9.5应用实例分析B．分析图9-8中的：rain分支，计算其子属性的信息增益值来确定子分裂属性形成子分支之三。针对：rain中的子训练数据集分支，有两个类别，该分支中有3个实例属于n类，有2个实例属于p类，因此针对分支的信息熵为：若以：rain分支中的属性Temperature为测试属性，则测试属性Temper