第9章决策树算法.ppt

第9章决策树算法 1 数据挖掘原理与SPSSClementine应用宝典元昌安主编邓松李文敬刘海涛编著电子工业出版社 第9章决策树算法 2 第9章决策树算法 第9章决策树算法 3 本章大纲 决策树算法原理常用决策树算法决策树剪枝由决策树提取分类规则应用实例分析 第9章决策树算法 4 9 1决策树算法原理 优点 使用者不需要了解很多背景知识 只要训练事例能用属性 结论的方式表达出来 就能用该算法学习 决策树模型效率高 对训练集数据量较大的情况较为适合 分类模型是树状结构 简单直观 可将到达每个叶结点的路径转换为IF THEN形式的规则 易于理解 决策树方法具有较高的分类精确度 第9章决策树算法 5 9 1决策树算法原理 传统的数据分类操作通常有以下两个步骤 模型训练阶段 根据给定的训练集 找到合适的映射函数H C的表示模型 使用上一步训练完成的函数模型预测数据的类别 或利用该函数模型 对数据集中的每一类数据进行描述 形成分类规则 第9章决策树算法 6 9 1决策树算法原理 工作过程 决策树分类模型的工作过程图 第9章决策树算法 7 9 1决策树算法原理 定义9 1给定一个训练数据集D 其中每个实例 称为例子 训练数据集中包含以下属性A 同时给定类别集合C 对于训练数据集D 决策树是指具有以下性质的树 每个内部节点都被标记一个属性Ai 每个弧都被标记一个值 这个值对应于相应父结点的属性 每个叶节点都被标记一个类Cj 第9章决策树算法 8 9 1决策树算法原理 定义9 2分裂准则定义为在决策树算法中将训练数据集D中的元组划分为个体类的最好的方法与策略 它告诉我们在节点N上测试哪个属性合适 如何选择测试与测试的方法 从节点N上应该生长出哪些分支 定义9 3分裂属性Xi定义为决策树中每个内部节点都对应的一个用于分裂数据集的属性 XiA 第9章决策树算法 9 9 1决策树算法原理 定义9 4如果Xi是连续属性 那么分裂准则的形式为Xi 其中 就称为节点n的分裂点 定义9 5如果Xi是离散属性 那么的形式为 其中 就称为节点n的分裂子集 注意 分裂准则与分裂属性 分裂点 分裂子集并不等同 它们是四个不同的概念 并且分裂子集分裂点分裂属性分裂准则 第9章决策树算法 10 9 1决策树算法原理 将上面的定义结合实际的决策树例子可得决策树图如下图9 1 图9 2 图9 3所示 图中设X为分裂属性 是属性X的已知值 图9 2按照分裂点划分而成的决策树图与相关的具体例子图 第9章决策树算法 11 9 1决策树算法原理 图9 3按照分裂子集划分而成的决策树图与相关的两个具体例子图 第9章决策树算法 12 9 1决策树算法原理 图9 4按照分裂子集划分而成的决策树 只能是二叉树 图与相关的具体例子图 第9章决策树算法 13 9 1决策树算法原理 目前主要使用如下几个量化评估标准 1 预测准确性 2 模型强健性 3 描述的简洁性 4 计算复杂性 5 处理规模性 第9章决策树算法 14 9 2常用决策树算法 ID3算法ID3是Quinlan于1986年提出的 是机器学习中一种广为人知的一个算法 它的提出开创了决策树算法的先河 而且是国际上最早最有影响的决策树方法 在该算法中 引入了信息论中熵的概念 利用分割前后的熵来计算信息增益 作为判别能力的度量 第9章决策树算法 15 9 2 1ID3算法 定义9 6信息熵自信息量只能反映符号的不确定性 而信息熵可以用来度量整个信源X整体的不确定性 设某事物具有n种相互独立的可能结果 或称状态 每一种结果出现的概率分别为且有 9 1 那么 该事物所具有的不确定量为 9 2 第9章决策树算法 16 9 2 1ID3算法 上式即为著名的香农信息量公式 注意到式中的对数以2为底 当n 2时且时 熵 1比特 由此可见 一个等概率的二选一事件具有1比特的不确定性 所以 可以把一个等概率的二选一事件所具有信息量定为信息量的单位 任何一个事件能够分解成n个可能的二选一事件 它的信息量就是n比特 第9章决策树算法 17 9 2 1ID3算法 Quinlan的首创性工作主要是在决策树的学习算法中第一次引入了信息论中的互信息 称之为信息增益 以之作为属性选择的标准 并且将建树的方法嵌入在其中 其核心是在决策树的各级节点上选择属性 用信息增益作为属性选择标准 第9章决策树算法 18 9 2 1ID3算法 下面给出的是ID3算法中将香农的信息熵定义应用到决策树构造中 进而给出的信息增益的定义 设训练数据集D 是n维有穷向量空间 其中 是有穷离散符号集 D中的每个元素 叫做例子 其中 设PD和ND是D的两个子集 分别叫做正例集和反例集 第9章决策树算法 19 9 2 1ID3算法 假设训练数据集D中的正例集PD和反例集ND的大小分别为p和n 则ID3基于下面两个假设给出该决策树算法中信息增益的定义 因为信息是用二进制编码的 所以在下面的公式定义中都用以2为底的对数 1 在训练数据集D上的一棵正确决策树对任意例子的分类概率同D中正反例的概率一致 2 一棵决策树能对一个例子做出正确类别判断所需的信息量如下公式所示 第9章决策树算法 20 9 2 1ID3算法 如果以属性A作为决策树的根 A具有v个值 它将A分为v个子集 假设中含有p个正例和n个反例 那么子集所需的信息期望是 那么 以属性A为根所需的信息期望如下公式所示 因此 以A为根的信息增益如下公式所示 第9章决策树算法 21 9 2 1ID3算法 上面给出的ID3中的信息论的相关定义主要是在两类分类问题的前提下 下面给出将其扩展到多类后的相关定义描述 设训练数据集D一共有m类样例 每类样例数为 同样以属性A作为决策树的根 具有v个值 它将D分为v个子集 假设子集中任意元组属于类C的概率用表示 并用估计 那么 该子集的信息量定义如下所示 那么以A为根分类后所需的信息期望如下面公式所示 第9章决策树算法 22 9 2 2C4 5算法 1 分裂 2 连续数据 3 缺失数据 4 规则 第9章决策树算法 23 9 2 2 1C4 5的分裂属性选择度量 ID系列的算法为什么会产生归纳偏置呢 归纳偏置是一系列前提 这些前提与训练数据一起演绎论证未来实例分类 如果给定一个训练数据集 那么通常有很多决策树与这些样例一致 所以 要描述ID系列算法的归纳偏置 应找到它从所有一致假设中选择一个的根据 第9章决策树算法 24 9 2 2 1C4 5的分裂属性选择度量 ID系列的搜索策略为 1 优先选择较短的树而不是较长的 2 选择那些信息增益高的属性离根节点较近的树 结论 ID系列算法的归纳偏置是因为它在选的时候较短的树比较长的树优先所产生的 也就是那些信息增益高的属性更靠近的根节点将会有优先生成树的特权 第9章决策树算法 25 9 2 2 1C4 5的分裂属性选择度量 为了避免这个偏置 弥补ID系列算法的不足就要舍弃信息增益这个度量而选择别的决策属性作为度量标准 Quinlan在他1986年中的论文中提出了一种可以使用的度量标准 增益比率 增益比率通过加入一个被称为分裂信息 splitinformation 的项来惩罚类似Date这样的属性 分裂信息用来衡量属性分裂数据的广度和均匀性 它由如下公式所示 第9章决策树算法 26 9 2 2 1C4 5的分裂属性选择度量 增益比率的公式如下所示 第9章决策树算法 27 9 2 2 2C4 5对连续数据的处理 ID3算法最初的定义是假设属性值是离散值 但在实际环境中 有很多属性是连续的 不能够用一个确定的标准来对其进行划分 C4 5使用下面的一系列处理过程来对连续的属性划分成离散的属性 进而达到能够建立决策树的目的 第9章决策树算法 28 9 2 2 2C4 5对连续数据的处理 Step1根据训练数据集D中各个属性的值对该训练数据集进行排序 Step2利用其中各属性的值对该训练数据集动态地进行划分 Step3在划分后的得到的不同的结果集中确定一个阈值 该阈值将训练数据集数据划分为两个部分 Step4针对这两边各部分的值分别计算它们的增益或增益比率 以保证选择的划分使得增益最大 第9章决策树算法 29 9 2 2 3C4 5对缺失数据的处理 为了评估属性A是否是决策节点n的最佳测试属性 要计算决策树在该节点的信息增益Gain D A 假定是S中的一个训练样例 并且其属性A的通过值分得的信息值表示为 第9章决策树算法 30 9 2 2 4C4 5对生成规则的利用 只要生成了决策树后 就可以把树转换成一个IF THEN规则的集合 当然 每种算法生成的决策树都可以转换成相应的if then规则 C4 5算法处理规则与其他算法不同在于它把规则存储在一个二维数组中 每一行都代表着树中的一个规则 即从树根到叶子之间的一个路径 第9章决策树算法 31 9 2 3CART算法 CART ClassificationandRegressionTrees 算法是由几位统计学家L Breiman J Friedman R Olshen和C Stone在发表的刊物 分类与回归树 中提出的一种产生二叉决策树分类模型的技术 它与前面Quinlan提出的ID系列算法和C4 5不同的是 使用的属性度量标准是Gini指标 它和后面将要介绍的算法的共同点也是在于都是利用了相同的属性度量标准Gini指标 第9章决策树算法 32 9 2 3CART算法 Gini指标主要是度量数据划分或训练数据集D的不纯度为主 系数值的属性作为测试属性 Gini值越小 表明样本的 纯净度 越高 Gini指标定义为如下公式 第9章决策树算法 33 9 2 3CART算法 由于二叉树不易产生数据碎片 精确度往往也会高于多叉树 所以在CART算法中 统计学家们采用了二元划分 在分支节点上进行Gini值的测试 如果满足一定纯度则划分到左子树 否则划分到右子树 最终生成一棵二叉决策树 在只有二元分裂的时候 对于训练数据集D中的属性A将D分成的D1和D2 则给定划分D的Gini指标如下公式所示 第9章决策树算法 34 9 2 3CART算法 对于离散值属性 在算法中递归的选择该属性产生最小Gini指标的子集作为它的分裂子集 对于连续值属性 必须考虑所有可能的分裂点 其策略类似于上面ID3中介绍的信息增益处理方法 可以用如下公式所示 第9章决策树算法 35 9 2 3CART算法 CART算法在满足下列条件之一 即视为叶节点不再进行分支操作 1 所有叶节点的样本数为1 样本数小于某个给定的最小值或者样本都属于同一类的时候 2 决策树的高度达到用户设置的阈值 或者分支后的叶节点中的样本属性都属于同一个类的时候 3 当训练数据集中不再有属性向量作为分支选择的时候 第9章决策树算法 36 9 2 4PUBLIC算法 前面几个小节的决策树算法都是先建树再剪枝 PUBLIC PruningandBuildingIntegratedinClassification 算法 8 17 将建树 剪枝结合到一步完成 即是预剪枝 在建树阶段不生成会被剪枝的子树 从而大大提高了效率 PUBLIC算法的建树是基于SPRINT方法 对其决策树的剪枝使用的是基于最小编码代价的MDL算法 但MDL原则不能直接应用 第9章决策树算法 37 9 2 5SLIQ算法 SLIQ SupervisedLearningInQuest 算法利用3种数据结构来构造树 分别是属性表 类表和类直方图 SLIQ算法在建树阶段 对连续属性采取预排序技术与广度优先相结合的策略生成树 对离散属性采取快速的求子集算法确定划分条件 具体步骤如下 Step1建立类表和各个属性表 并且进行预排序 即对每个连续属性的属性表进行独立排序 以避免在每个节点上都要给连续属性值重利用新排序 Step2如果每个叶节点中的样本都能归为一类 则算法停止 否则转 3 Step3利用属性表寻找拥有最小Gini值的划分作为最佳划分方案 第9章决策树算法 38 9 2 5SLIQ算法 Step4根据第3步得到的最佳方案划分节点 判断为真的样本划归为左孩子节点 否则划归为右孩子节点 这样 3 4 步就构成了广度优先的生成树策略 Step5更新类表中的第二项 使之指向样本划分后所在的叶节点 Step6转到步骤 2 第9章决策树算法 39 9 2 6SPRINT算法 SPRINT算法是对SLIQ算法的改进 其目的有两个 一是为了能够更好的并行建立决策树 二是为了使得决策树T适合更大的数据集 SPRINT ScalableParallelizableInductionofClassificationTree 算法是一种可扩展的 可并行的归纳决策树 它完全不受内存限制 运行速度快 且允许多个处理器协同创建一个决策树模型 第9章决策树算法 40 9 2 6SPRINT算法 SPRINT算法定义了两种数据结构 分别是属性表和直方图 属性表由一组三元组组成 它随节点的扩张而划分 并附属于相应的子节点 与SLIQ算法不同 SPRINT算法采取传统的深度优先生成树策略 具体步骤如下 Step1生成根节点 并为所有属性建立属性表 同时预排序连续属性的属性表 Step2如果节点中的样本可归为一类 则算法停止 否则转 3 Step3利用属性表寻找拥有最小Gini值的划分作为最佳划分方案 算法依次扫描该节点上的每张属性表 Step4根据划分方案 生成该节点的两个子节点 Step5划分该节点上的各属性表 使之关联到或上 第9章决策树算法 41 9 2 6SPRINT算法 Step6分别转到步骤 2 考察 节点 SPRINT算法在剪枝阶段进行基于MDL的剪枝 至此构成了SPRINT算法的串行化算法 将串行化算法稍加改进 就成为并行化算法 将训练数据集平均分布到n个处理器上 而后每个处理器生成自己的数据分片 由于连续属性值要求全局排序 因此要将n个处理器上的连续属性的属性表综合重新排序 再平均分布到n个处理器上 在建立Hash表之前 需要从n个处理器上收集所有的样本号信息 第9章决策树算法 42 9 3决策树剪枝 在现实世界中 获得的数据并不可能保证其完美性与完整性 所以 在当被用来创建决策树的训练数据集中存在有噪声 或者数量太少以至于不能产生目标函数的有代表性的采样的时候 我们使用决策树算法生成的决策树很多分支反映的是训练数据集中的异常 在上面任意一种情况发生的时候 利用简单算法产生的树会出现过拟合训练样例的现象 第9章决策树算法 43 9 3决策树剪枝 在利用决策树算法进行分类的过程中 有两个过程 在9 1节中有介绍 第一个过程我们必须要利用训练数据来进行决策树分类模型的建立 另一个过程则是将建立好的决策树分类模型对给定的测试数据进行分类 第9章决策树算法 44 9 3 1预剪枝 预剪枝也称为先剪枝 在该方法中主要是通过提前停止树的构造 例如 通过确定在给定的节点不再分裂或划分训练元组的子集 来对决策树进行剪枝 一旦停止以后 剩下的那个节点就成为了树叶 该树叶可能持有子集元组中最频繁的类或这些元组的概率分布 第9章决策树算法 45 9 3 1预剪枝 预剪枝判断停止决策树的生长的方法大体上可以归纳为以下几种 1 一种最为简单的方法就是在决策树到达一定高度的情况下就停止树的生长 2 到达此结点的实例具有相同的特征向量 而不必一定属于同一类 也可停止生长 这种情况可以处理数据中的数据冲突问题 3 到达此结点的实例个数小于某一个阈值也可停止树的生长 4 更为普遍的做法是计算每次扩张对系统性能的增益 如果这个增益值小于某个阈值则不进行扩展 如果在最好情况下的扩展增益都小于阈值 即使有些叶子结点的实例不属于同一类 也停止树的增长 第9章决策树算法 46 9 3 2后剪枝 后剪枝算法已经得到了广泛的应用 这个算法最初是由Breiman等提出 它首先构造完整的决策树 允许决策树过度拟合训练数据 然后对那些置信度不够的结点的子树用叶子结点来替代 这个叶子结点所应标记的类别为子树中大多数实例所属的类别 第9章决策树算法 47 悲观错误剪枝PEP PessimisticErrorPruning REP方法进行剪枝具有以下优点 1 运用REP方法得到的决策树是关于测试数据集的具有最高精度的子树 并且是规模最小的树 2 它的计算复杂性是线性的 这是因为决策树中的每个非叶子结点只需要访问一次就可以评估其子树被修剪的概率 3 由于使用独立的测试数据集 和原始决策树相比 修剪后的决策树对未来新事例的预测偏差较小 第9章决策树算法 48 悲观错误剪枝PEP PessimisticErrorPruning 正是由于REP方法出现的一系列问题 随后Quinlan提出了可以在一定程度弥补上面缺陷的PEP方法 也就是悲观剪枝方法 该方法引入了统计学上连续修正的概念来弥补这一个缺陷 在评价子树的训练错误的公式中添加了一个常数 假定每个叶节点都自动对实例的某部分进行错误的分类 第9章决策树算法 49 悲观错误剪枝PEP PessimisticErrorPruning 所用来剪枝的度量的基本思想可以概述为以下几点 1 假设训练数据集生成原始树为T 某一叶子结点的实例个数为 其中错误分类的个数为 2 我们定义训练数据集的误差率如下公式9 13所示 9 13 由于训练数据集既用来生成决策树又用来修剪树 所以是有偏倚的 利用它来修剪的决策树树并不是最精确 最好的 3 为此 Quinlan在误差估计度量中增加了连续性校正 将误差率的公式修改为如下公式9 14所示 9 14 第9章决策树算法 50 悲观错误剪枝PEP PessimisticErrorPruning 那么 同样的 我们假设s为树T的子树的其中一个子节点 则该子树的叶子结点的个数为 的分类误差率如下公式所示 在定量的分析中 为简单起见 我们用误差总数取代上面误差率的表示 即有公式 那么 对于子树 它的分类误差总数如下公式所示 第9章决策树算法 51 最小错误剪枝MEP MinimumErrorPruning MEP方法是由Niblett和Bratko首先提出来的 它在一个相对独立的数据集上从树的叶子结点开始 向上搜索一个单一的树来使分类误差的期望概率达到最小 但它并不需要一个额外的修剪数据集 使用的信息来自于训练数据集 其目的是在未知的数据集上产生最小预测分类错误率 第9章决策树算法 52 代价 复杂度剪枝CCP Cost ComplexityPruning CCP方法就是著名的CART ClassificationandRegressionTrees 剪枝算法 它包含两个步骤 1 自底向上 通过对原始决策树中的修剪得到一系列的树 其中是由中的一个或多个子树被替换所得到的 为未经任何修剪的原始树 为只有一个结点的树 2 评价这些树 根据真实误差率来选择一个最优秀的树作为最后被剪枝的树 第9章决策树算法 53 基于错误剪枝EBP Error BasedPruning EBP剪枝法是一种应用于C4 5算法的自下向上的剪枝法 被认为是PEP剪枝法的改进 因为EBP剪枝基于对训练数据集的更加悲观的估计 同PEP剪枝 EBP仅利用训练数据集来构建和剪枝决策树 假设可将叶结点覆盖的实例看作统计样本 叶结点对实例的分类错误率遵循二项式分布 并利用置信因子CF控制剪枝的程度 我们将CF定义为如下公式所示 第9章决策树算法 54 9 4由决策树提取分类规则 决策树分类方法有它的优点 但是也有一定的局限性 比如 利用算法生成的决策树的规模会因为训练数据集的巨大而变得过大使得难以理解 可读性差 如果直接从决策树中提取出IF THEN规则 建立基于规则的分类器 与决策树分类器相比 IF THEN规则可能更容易理解 特别是当决策树分支非常大时也一样 第9章决策树算法 55 9 5应用实例分析 下面我们利用上面表9 1根据天气是否打网球的训练数据集 利用ID3算法来判断某天是否适合打网球 1 类别属性信息熵的计算由于未分区前 训练数据集中共有14个实例 其中有9个实例属于p类 适合打网球的 5个实例属于n类 不适合打网球 因此分区前类别属性的熵为 第9章决策树算法 56 9 5应用实例分析 2 非类别属性信息熵的计算若选择Outlook为测试属性 0 694bit 第9章决策树算法 57 9 5应用实例分析 因此 这种划分的信息增益是 同理 可以求出其它三个属性的信息增益为 由上可知 属性值Outlook在各个属性中具有最高的增益 被选作分裂属性 则第一个根节点T被用标记 并对于每个属性值生长一个分支 3 递归地创建决策树的树枝和叶子选择作为测试属性后 将训练实例集分为三个子集 生成三个子节点 对每个子节点递归采用上述过程进行分类直至每个节点都成为叶节点而已 第9章决策树算法 58 9 5应用实例分析 属性值Outlook在各个属性中具有最高的增益 被选作分裂属性 则第一个根节点T被用标记 并对于每个属性值生长一个分支 根据信息增益结果生成的以Outlook为根节点的初级决策树图 第9章决策树算法 59 9 5应用实例分析 A 分析图中的sunny分支 计算其子属性的信息增益值来决定子分裂属性形成子分支之一 针对sunny中的子训练数据集分支 有两个类别 该分支中有3个实例属于n类 有2个实例属于p类 因此针对分支的信息熵为 若以 sunny分支中的属性Temperature为测试属性 则测试属性Temperature的信息量为 第9章决策树算法 60 9 5应用实例分析 其信息增益为 若以 sunny分支中的属性Humidity为测试属性 则测试属性Humidity的信息量为 0 00bit其信息增益为 若以 sunny分支中的属性Wind为测试属性