决策树算法

第9章决策树算法1第9章决策树算法第9章决策树算法2本章大纲：决策树算法原理常用决策树算法决策树剪枝由决策树提取分类规则应用实例分析第9章决策树算法39.1决策树算法原理优点：使用者不需要了解很多背景知识，只要训练事例能用属性→结论的方式表达出来，就能用该算法学习；决策树模型效率高，对训练集数据量较大的情况较为适合；分类模型是树状结构，简单直观，可将到达每个叶结点的路径转换为if→then形式的规则，易于理解；决策树方法具有较高的分类精确度。第9章决策树算法49.1决策树算法原理传统的数据分类操作通常有以下两个步骤:模型训练阶段：根据给定的训练集，找到合适的映射函数H:→C的表示模型。使用上一步训练完成的函数模型预测数据的类别，或利用该函数模型，对数据集中的每一类数据进行描述，形成分类规则。第9章决策树算法59.1决策树算法原理工作过程：训练数据集决策树分类算法评估模式预测预测结果类别未知的数据集测试集1、创建决策树过程2、使用决策树模型预测过程决策树分类模型的工作过程图第9章决策树算法69.1决策树算法原理定义9.1给定一个训练数据集D，其中每个实例，称为例子，训练数据集中包含以下属性A。同时给定类别集合C。对于训练数据集D，决策树是指具有以下性质的树：每个内部节点都被标记一个属性Ai。每个弧都被标记一个值，这个值对应于相应父结点的属性。每个叶节点都被标记一个类Cj。第9章决策树算法79.1决策树算法原理定义9.2分裂准则定义为在决策树算法中将训练数据集D中的元组划分为个体类的最好的方法与策略，它告诉我们在节点N上测试哪个属性合适，如何选择测试与测试的方法，从节点N上应该生长出哪些分支。定义9.3分裂属性Xi定义为决策树中每个内部节点都对应的一个用于分裂数据集的属性。XiA=},,,{21hAAA第9章决策树算法89.1决策树算法原理定义9.4如果Xi是连续属性，那么分裂准则的形式为Xi，其中，就称为节点n的分裂点。定义9.5如果Xi是离散属性，那么的形式为，其中，就称为节点n的分裂子集。注意：分裂准则与分裂属性、分裂点、分裂子集并不等同，它们是四个不同的概念，并且分裂子集分裂点分裂属性分裂准则第9章决策树算法99.1决策树算法原理将上面的定义结合实际的决策树例子可得决策树图如下图9-1，图9-2，图9-3所示，图中设X为分裂属性，是属性X的已知值。Xx2X=x1X52,000=52,000收入图9-2按照分裂点划分而成的决策树图与相关的具体例子图第9章决策树算法109.1决策树算法原理Xx1xix2……绿蓝橙红颜色中等高低收入图9-3按照分裂子集划分而成的决策树图与相关的两个具体例子图第9章决策树算法119.1决策树算法原理图9-4按照分裂子集划分而成的决策树（只能是二叉树）图与相关的具体例子图noyesiYX否是},{绿红颜色第9章决策树算法129.1决策树算法原理目前主要使用如下几个量化评估标准(1)预测准确性(2)模型强健性(3)描述的简洁性(4)计算复杂性(5)处理规模性第9章决策树算法139.2常用决策树算法ID3算法ID3是Quinlan于1986年提出的，是机器学习中一种广为人知的一个算法，它的提出开创了决策树算法的先河，而且是国际上最早最有影响的决策树方法，在该算法中，引入了信息论中熵的概念，利用分割前后的熵来计算信息增益，作为判别能力的度量。第9章决策树算法149.2.1ID3算法定义9.6信息熵自信息量只能反映符号的不确定性，而信息熵可以用来度量整个信源X整体的不确定性。设某事物具有n种相互独立的可能结果(或称状态)：，每一种结果出现的概率分别为且有：（9.1）那么，该事物所具有的不确定量为：（9.2）nxxx,,,21),(),(),(21nxPxPxP1)(1niixp)(log)()()()()()()()(212211iniinnxPxpxIxpxIxpxIxpXH第9章决策树算法159.2.1ID3算法上式即为著名的香农信息量公式。注意到式中的对数以2为底，当n=2时且时，熵=1比特。由此可见，一个等概率的二选一事件具有1比特的不确定性。所以，可以把一个等概率的二选一事件所具有信息量定为信息量的单位。任何一个事件能够分解成n个可能的二选一事件，它的信息量就是n比特。第9章决策树算法169.2.1ID3算法Quinlan的首创性工作主要是在决策树的学习算法中第一次引入了信息论中的互信息（称之为信息增益），以之作为属性选择的标准，并且将建树的方法嵌入在其中，其核心是在决策树的各级节点上选择属性，用信息增益作为属性选择标准第9章决策树算法179.2.1ID3算法下面给出的是ID3算法中将香农的信息熵定义应用到决策树构造中，进而给出的信息增益的定义。nDDD21jDntttd,,,21njDtjj,,2,1,设训练数据集D=,是n维有穷向量空间，其中是有穷离散符号集，D中的每个元素，叫做例子，其中设PD和ND是D的两个子集，分别叫做正例集和反例集。第9章决策树算法189.2.1ID3算法假设训练数据集D中的正例集PD和反例集ND的大小分别为p和n，则ID3基于下面两个假设给出该决策树算法中信息增益的定义，因为信息是用二进制编码的，所以在下面的公式定义中都用以2为底的对数。（1）在训练数据集D上的一棵正确决策树对任意例子的分类概率同D中正反例的概率一致；（2）一棵决策树能对一个例子做出正确类别判断所需的信息量如下公式所示：第9章决策树算法199.2.1ID3算法如果以属性A作为决策树的根，A具有v个值，它将A分为v个子集，假设中含有p个正例和n个反例，那么子集所需的信息期望是，那么，以属性A为根所需的信息期望如下公式所示：npnnpnnppnppnpI22loglog),(},,,{21vvvv},,,{21veee),()(1iiviiinpInpnpAE因此，以A为根的信息增益如下公式所示：)(),()(AEnpIAgain第9章决策树算法209.2.1ID3算法上面给出的ID3中的信息论的相关定义主要是在两类分类问题的前提下，下面给出将其扩展到多类后的相关定义描述。设训练数据集D一共有m类样例，每类样例数为：。同样以属性A作为决策树的根，具有v个值，它将D分为v个子集，假设子集中任意元组属于类C的概率用表示，并用估计。那么，该子集的信息量定义如下所示：mipi,,2,1,vvvv,,21},,,{21veeeipDCDi/,)(log)(21imiirppeI那么以A为根分类后所需的信息期望如下面公式所示：)()(1rvjreIDeAE第9章决策树算法219.2.2C4.5算法（1）分裂（2）连续数据（3）缺失数据（4）规则第9章决策树算法229.2.2.1C4.5的分裂属性选择度量ID系列的算法为什么会产生归纳偏置呢？归纳偏置是一系列前提，这些前提与训练数据一起演绎论证未来实例分类。如果给定一个训练数据集，那么通常有很多决策树与这些样例一致。所以，要描述ID系列算法的归纳偏置，应找到它从所有一致假设中选择一个的根据。第9章决策树算法239.2.2.1C4.5的分裂属性选择度量ID系列的搜索策略为：（1）优先选择较短的树而不是较长的；（2）选择那些信息增益高的属性离根节点较近的树。结论：ID系列算法的归纳偏置是因为它在选的时候较短的树比较长的树优先所产生的，也就是那些信息增益高的属性更靠近的根节点将会有优先生成树的特权。第9章决策树算法249.2.2.1C4.5的分裂属性选择度量为了避免这个偏置，弥补ID系列算法的不足就要舍弃信息增益这个度量而选择别的决策属性作为度量标准。Quinlan在他1986年中的论文中提出了一种可以使用的度量标准：增益比率。增益比率通过加入一个被称为分裂信息（splitinformation）的项来惩罚类似Date这样的属性，分裂信息用来衡量属性分裂数据的广度和均匀性，它由如下公式所示：)(log)(21DeDeDSplitIrvjrA第9章决策树算法259.2.2.1C4.5的分裂属性选择度量增益比率的公式如下所示：)()()(ASplitIAGainAGainRatio第9章决策树算法269.2.2.2C4.5对连续数据的处理ID3算法最初的定义是假设属性值是离散值，但在实际环境中，有很多属性是连续的，不能够用一个确定的标准来对其进行划分。C4.5使用下面的一系列处理过程来对连续的属性划分成离散的属性，进而达到能够建立决策树的目的。第9章决策树算法279.2.2.2C4.5对连续数据的处理Step1根据训练数据集D中各个属性的值对该训练数据集进行排序；Step2利用其中各属性的值对该训练数据集动态地进行划分；Step3在划分后的得到的不同的结果集中确定一个阈值，该阈值将训练数据集数据划分为两个部分；Step4针对这两边各部分的值分别计算它们的增益或增益比率，以保证选择的划分使得增益最大。第9章决策树算法289.2.2.3C4.5对缺失数据的处理为了评估属性A是否是决策节点n的最佳测试属性，要计算决策树在该节点的信息增益Gain(D,A)。假定,c()是S中的一个训练样例，并且其属性A的通过值分得的信息值表示为.ididie第9章决策树算法299.2.2.4C4.5对生成规则的利用只要生成了决策树后，就可以把树转换成一个if-then规则的集合。当然，每种算法生成的决策树都可以转换成相应的if-then规则，C4.5算法处理规则与其他算法不同在于它把规则存储在一个二维数组中，每一行都代表着树中的一个规则，即从树根到叶子之间的一个路径.第9章决策树算法309.2.3CART算法CART（ClassificationandRegressionTrees）算法是由几位统计学家L.Breiman，J.Friedman，R.Olshen和C.Stone在发表的刊物《分类与回归树》中提出的一种产生二叉决策树分类模型的技术。它与前面Quinlan提出的ID系列算法和C4.5不同的是，使用的属性度量标准是Gini指标，它和后面将要介绍的算法的共同点也是在于都是利用了相同的属性度量标准Gini指标。第9章决策树算法319.2.3CART算法Gini指标主要是度量数据划分或训练数据集D的不纯度为主，系数值的属性作为测试属性，Gini值越小，表明样本的“纯净度”越高。Gini指标定义为如下公式：miipDGini121)(第9章决策树算法329.2.3CART算法由于二叉树不易产生数据碎片，精确度往往也会高于多叉树，所以在CART算法中，统计学家们采用了二元划分，在分支节点上进行Gini值的测试，如果满足一定纯度则划分到左子树，否则划分到右子树，最终生成一棵二叉决策树。在只有二元分裂的时候，对于训练数据集D中的属性A将D分成的D1和D2，则给定划分D的Gini指标如下公式所示：)()()(2211DGiniDDDGiniDDDGiniA第9章决策树算法339.2.3CART算法对于离散值属性，在算法中递归的选择该属性产生最小Gini指标的子集作为它的分裂子集。对于连续值属性，必须考虑所有可能的分裂点。其策略类似于上面ID3中介绍的信息增益处理方法，可以用如下公式所示：)()(1iviiADGiniDDDGini第9章决策树算法349.2.3CART算法CART算法在满足下列条件之一，即视为叶节点不再进行分支操作。（1）所有叶节点的样本数为1、样本数小于某个给定的最小值或者样本都属于同一类的时候；（2）决策树的高度达到用户设置的阈值，或者分支后的叶节点中的样本属性都属于同一个类的时候；（3）当训练数据集中不再有属性向量作为分支选择的时候。第9章决策树算法359.3决策树剪枝在现实世界中，获得的数据