咨询工具决策树算法及应用拓展ppt课件.ppt

决策树算法及应用拓展 内容简介 概述预备知识决策树生成 BuildingDecisionTree 决策树剪枝 PruningDecisionTree 捕捉变化数据的挖掘方法小结 1 概述 一 传统挖掘方法的局限性只重视从数据库中提取规则 忽视了库中数据的变化挖掘所用的数据来自稳定的环境 人为干预较少 2 概述 二 捕捉新旧数据变化的目的 挖掘出变化的趋势例 啤酒 尿布阻止 延缓不利变化的发生例 金融危机 银行的信贷策略差异挖掘算法的主要思想 合理比较新 旧数据的挖掘结果 并清晰的描述其变化部分 3 预备知识一 BuildingTree 基本思想 用途 提取分类规则 进行分类预测 4 使用决策树进行分类 决策树一个树性的结构内部节点上选用一个属性进行分割每个分叉都是分割的一个部分叶子节点表示一个分布决策树生成算法分成两个步骤树的生成开始 数据都在根节点递归的进行数据分片树的修剪去掉一些可能是噪音或者异常的数据决策树使用 对未知数据进行分割按照决策树上采用的分割属性逐层往下 直到一个叶子节点 5 决策树算法 基本算法 贪心算法 自上而下分而治之的方法开始时 所有的数据都在根节点属性都是种类字段 如果是连续的 将其离散化 所有记录用所选属性递归的进行分割属性的选择是基于一个启发式规则或者一个统计的度量 如 informationgain 停止分割的条件一个节点上的数据都是属于同一个类别没有属性可以再用于对数据进行分割 6 伪代码 BuildingTree ProcedureBuildTree S 用数据集S初始化根节点R用根结点R初始化队列QWhileQisnotEmptydo 取出队列Q中的第一个节点NifN不纯 Pure for每一个属性A估计该节点在A上的信息增益选出最佳的属性 将N分裂为N1 N2 7 属性选择的统计度量 信息增益 Informationgain ID3 C4 5 所有属性假设都是种类字段经过修改之后可以适用于数值字段基尼指数 Giniindex IBMIntelligentMiner 能够适用于种类和数值字段 8 信息增益度度量 ID3 C4 5 任意样本分类的期望信息 I s1 s2 sm Pilog2 pi i 1 m 其中 数据集为S m为S的分类数目 PiCi为某分类标号 Pi为任意样本属于Ci的概率 si为分类Ci上的样本数由A划分为子集的熵 E A s1j smj s I s1j smj A为属性 具有V个不同的取值信息增益 Gain A I s1 s2 sm E A 9 训练集 举例 ID3算法 10 使用信息增益进行属性选择 ClassP buys computer yes ClassN buys computer no I p n I 9 5 0 940Computetheentropyforage HenceSimilarly 11 DecisionTree 结果输出 age overcast student creditrating no yes fair excellent 30 40 no no yes yes yes 30 40 12 基尼指数GiniIndex IBMIntelligentMiner 集合T包含N个类别的记录 那么其Gini指标就是pj类别j出现的频率如果集合T分成两部分N1andN2 那么这个分割的Gini就是提供最小Ginisplit就被选择作为分割的标准 对于每个属性都要遍历所有可以的分割方法 13 预备知识二 PruningTree 目的 消除决策树的过适应 OverFitting 问题实质 消除训练集中的异常和噪声两种方法 先剪枝法 Public算法 后剪枝法 Sprint算法 14 两种剪枝标准 最小描述长度原则 MDL 思想 最简单的解释最期望的做法 对Decision Tree进行二进位编码 编码所需二进位最少的树即为 最佳剪枝树 期望错误率最小原则思想 选择期望错误率最小的子树进行剪枝对树中的内部节点计算其剪枝 不剪枝可能出现的期望错误率 比较后加以取舍 15 CostofEncodingDataRecords 对n条记录进行分类编码的代价 2种方法 n 记录数 k 类数目 ni 属于类i的记录数 16 CostofEncodingTree 编码树结构本身的代价编码每个分裂节点的代价确定分类属性的代价确定分类属性值的代价 其中 v是该节点上不同属性值的个数编码每个树叶上的记录分类的代价 17 剪枝算法 设N为欲计算其最小代价的节点两种情形 N是叶结点 C S 1 Cost1N是内部节点 有两个子节点N1 N2已剪去N1 N2 N成为叶子节点 Cost1计算N节点及其子树的代价 使用递归过程Csplit N 1 minCost1 minCost2 Cost2比较Cost1和Cost2 选取代价较小者作为返回值 18 计算最小子树代价的伪代码 ProcedureComputeCost Prune NodeN ifN是叶子节点 return C S 1 minCost1 Compute Prune NodeN1 minCost2 Compute Prune NodeN2 minCostN min C S 1 Csplit N 1 minCost1 minCost2 ifminCostN C S 1PrunechildnodesN1andN2returnminCostN 19 引入Public算法 一般做法 先建树 后剪枝Public算法 建树的同时进行剪枝思想 在一定量 用户定义参数 的节点分裂后 周期性的进行部分树的剪枝存在的问题 可能高估 Over Estimate 被剪节点的值改进 采纳低估 Under Estimate 节点代价的策略 20 具体思路 三种叶节点 有待扩展 需计算子树代价下界不能扩展 纯节点 剪枝后的结点 C S 1 21 改进算法的伪代码 ProcedureComputCoste Prune NodeN IfN是仍待扩展的结点 returnN节点的代价下界IfN是纯节点或不可扩展的叶节点 return C S 1 两个子节点N1 N2minCost1 Compute Prune NodeN1 minCost2 Compute Prune NodeN2 minCostN min C S 1 Csplit N 1 minCost1 minCost2 ifminCostN C S 1PrunechildnodesN1andN2returnminCostN 22 计算子树代价下界 Public 1 假设节点N的代价至少是1Public S S split计算以N为根且包含S个分裂点的子树代价的下界 包括确定分裂节点属性的代价 Public V V splitvalue同上 还包括确定分裂节点值的代价 23 Public S 算法 一 相关概念 24 Public S 算法 二 定理 任何以N为根结点且有S个分裂点的子树的代价至少是2 S 1 S loga nii s 2 k证明 编码树结构代价2 S 1确定节点分裂属性的代价S loga编码S 1个叶子结点的代价 nii s 2 k 25 Public S 算法 证明一 证明 编码S 1个叶子节点的代价至少为 nii s 2 k相关概念 1 主要类 MajorityClass if 有 则Ci为主要类2 少数类 MinorityClass ifthenCj为少数类 26 Public S 算法 证明二 题设 子树N有S个分裂点 Split K个类S 1个叶子节点至多有S 1个主要类至少有K S 1个少数类取Ci为某少数类 C Sj 为编码叶子节点j上记录的代价又有C S nij编码具有类i且位于叶子节点j的记录的代价是nij所有少数类的代价Cost nii 少数类 27 计算minCost S的代码 ProcedurecomputeMinCostS NodeN Ifk 1return C S 1 S 1tmpCost 2 S 1 S loga inii s 2 kWhiles 12 logado tmpCost tmpCost 2 loga ns 2S Returnmin C S 1 tmpCost 28 Public S 示例 16 truck high 24 sports high 1 log2 1 1 1 N 65 family low 34 truck low 32 sports medi N 1 log2 1 log2 1 1 16 truck high 24 sports high 32 sports medi 65 family low 34 truck low 1 29 Public V 算法 计算分类节点值的代价 编码叶子节点记录的代价i 1 k 1 在所有内部节点编码分裂节点值的代价 2 总代价 1 2 其中 Cj是叶子节点j上的主要类 M是S 1个叶子节点上的主要类的集合 30 算法比较 Sprint 传统的二阶段 构造 剪枝 算法Public 1 用保守的估计值1取代欲扩展节点的代价下界Public S 考虑具有分裂点的子树 同时计算为确定分裂节点及其属性的代价下界Public V 比前者准确 需计算确定结点上属性值的代价下界 31 实验数据 Real life 32 实验结果 一 产生的节点数目 33 实验结果 二 执行时间 S 34 算法结果分析 总体上 比Sprint算法有较大改进相对于最后的剪枝树仍有多余的结点 有待改进挖掘效率与数据分布及噪声有关 35 言归正传 捕捉数据变化的挖掘方法 新生成一棵决策树与旧树完全没有关系生成一棵相关的树未达到旧树中叶节点的深度超出了旧树中相应节点的深度相同的属性 最好的划分 bestcut 相同的属性 相同的划分 36 方法三的对应算法 使新树与旧树有相同的属性和划分 且能及早停止测试在旧树中每个叶子节点的错误变化的情况进一步生成新的树剪枝移除那些无预测特性的分枝比较新 旧树 识别变化部分 37 标识几种不同的变化类型 区域的连接 旧树中的划分不必要边界的移动 旧树中的划分移到了新的位置进一步细化 Refinement 旧树中的叶结点不足以描述新生成数据类标号变化 旧树中的节点类标号发生了变化错误率的变化覆盖率的变化 某个节点具有的数据量的比率 38 小结 BuildingDecisionTree算法PruningDecisionTree算法Pu