决策树培训讲义(PPT 50页).ppt

决策树 上 武承羲 内容 决策树基础经典决策树剪枝 决策树 决策树 用来表示决策和相应的决策结果对应关系的树 树中每一个非叶节点表示一个决策 该决策的值导致不同的决策结果 叶节点 或者影响后面的决策选择 示例 决策树 决策树类型分类树 叶节点对应于一类别回归树 叶节点对应于一连续值ID3 C4 5andC5 0 RossQuinlan CART L Breiman J Friedman R Olshen和C Stone 思想 空间划分 比如 用变量y表示因变量 分类变量 用x1 x2 x3 xm表示自变量 通过递归的方式把关于自变量的m维空间划分为不重叠的矩形 图示 决策树 ID3 C4 5 C5 0 RossQuinlanID31986年C4 51993年C5 01998年2011年获得KDD创新奖 ID3 C4 5 C5 0的分类基础 信息熵1948年 香农提出了 信息熵 的概念 解决了对系统信息的量化度量问题 香农认为信息的准确信息量可以用下面的信息熵公式计算 一个系统越是有序 信息熵就越低 反之 一个系统越乱 信息熵就越高 所以 信息熵也可以说是系统有序化程度的一个衡量 信息增益 informationgain 是指期望信息或者信息熵的有效减少量 信息增益率 informationgainratio 由划分个数引起的偏置问题 划分越多 引起每个划分内部数据纯度的变化 分块越小 数据纯度可能越高 进而引起偏置问题 设样本集S按离散属性F的V个不同的取值划分为 共V个子集定义Split S F 则用F对S进行划分的信息增益率为 ID3 1986年由Quilan提出的ID3算法选择具有最高信息增益的属性作为测试属性 ID3 DataSet featureList 创建根节点R如果当前DataSet中的数据都属于同一类 则标记R的类别为该类如果当前featureList集合为空 则标记R的类别为当前DataSet中样本最多的类别递归情况 从featureList中选择属性F 选择Gain DataSet F 最大的属性 根据F的每一个值v 将DataSet划分为不同的子集DS 对于每一个DS 创建节点C如果DS为空 节点C标记为DataSet中样本最多的类别如果DS不为空 节点C ID3 DS featureList F 将节点C添加为R的子节点C源码 http id3alg altervista org 示例 1属性及值域 outlook sunny overcast rain temperature hot mild cool humidity high normal wind weak strong Gain S Temperature 0 029Gain S Humidity 0 151Gain S Wind 0 048由此选择根节点划分属性为outlook 参考 http www cise ufl edu ddd cap6635 Fall 97 Short papers 2 htmhttp en wikipedia org wiki ID3 algorithm C4 5 1993年由Quilan提出的C4 5算法 对ID3的改进 信息增益率连续值属性缺失值后剪枝基于错误剪枝EBP Error BasedPruning C4 5 连续型属性 离散化处理 将连续型的属性变量进行离散化处理 形成决策树的训练集把需要处理的样本 对应根节点 或样本子集 对应子树 按照连续变量的大小从小到大进行排序假设该属性对应的不同的属性值一共有N个 那么总共有N 1个可能的候选分割阈值点 每个候选的分割阈值点的值为上述排序后的属性值中两两前后连续元素的中点用信息增益率选择最佳划分 C4 5 缺失值 缺失值 在某些情况下 可供使用的数据可能缺少某些属性的值 例如 X y 是样本集S中的一个训练实例 X F1 v F2 v Fn v 但是其属性Fi的值Fi v未知 处理策略 处理缺少属性值的一种策略是赋给它结点t所对应的训练实例中该属性的最常见值另外一种更复杂的策略是为Fi的每个可能值赋予一个概率 例如 给定一个布尔属性Fi 如果结点t包含6个已知Fi v 1和4个Fi v 0的实例 那么Fi v 1的概率是0 6 而Fi v 0的概率是0 4 于是 实例x的60 被分配到Fi v 1的分支 40 被分配到另一个分支 这些片断样例 fractionalexamples 的目的是计算信息增益 另外 如果有第二个缺少值的属性必须被测试 这些样例可以在后继的树分支中被进一步细分 C4 5中使用 简单处理策略就是丢弃这些样本 C4 5 算法步骤示意 C4 5 DataSet featureList 创建根节点R如果当前DataSet中的数据都属于同一类 则标记R的类别为该类如果当前featureList集合为空 则标记R的类别为当前DataSet中样本最多的类别递归情况 从featureList中选择属性F 选择GainRatio DataSet F 最大的属性 连续属性参见上面的离散化过程 根据F的每一个值v 将DataSet划分为不同的子集DS 对于每一个DS 创建节点C如果DS为空 节点C标记为DataSet中样本最多的类别如果DS不为空 节点C C4 5 DS featureList F 将节点C添加为R的子节点源码 C4 5 C4 5算法优点 产生的分类规则易于理解准确率较高 C4 5算法缺点 在构造树的过程中 需要对数据集进行多次的顺序扫描和排序 因而导致算法的低效 C5 0 思想 加入Boosting算法框架特点 更快内存使用更有效更小的决策树商业机密C5 0教程 CART 分类回归树CART ClassificationandRegressionTrees 1984 L Breiman J Friedman R Olshen和C Stonehttp www stat berkeley edu breiman http www stat stanford edu jhf http www stat stanford edu olshen 目标变量是类别的 分类树目标变量是连续的 回归树 CART 二元划分二叉树不易产生数据碎片 精确度往往也会高于多叉树 所以在CART算法中 采用了二元划分不纯性度量分类目标 Gini指标 Towing orderTowing连续目标 最小平方残差 最小绝对残差剪枝 用独立的验证数据集对训练集生长的树进行剪枝 Gini指标 Giniindex Gini指标用来度量数据集的不纯度 Gini越小 数据越纯CART中计算Gini指标考虑每个属性上的二元划分 根据训练数据集S中的属性F将S分成的S1和S2 则给定划分的Gini指标如下公式所示 最小化Gini指标 离散属性outlook sunny overcast rain Outlook值的子集有 8个 sunny overcast rain sunny overcast overcast rain sunny rain sunny overcast rain 去除不代表任何分裂的集合 空集 和全集 sunny overcast rain 则基于Outlook的划分方式有3种 分别计算每种划分的Gini指标 选择划分 CART 分类树 对于离散值属性 在算法中递归的选择该属性产生最小Gini指标的子集作为它的分裂子集 或使用其他不纯度 对于连续值属性 必须考虑所有可能的划分点 其策略类似于C4 5中介绍的方法 利用Gini指数最小原则 选择划分点 CART 分类树 节点t的类classify t CART classification DataSet featureList alpha 创建根节点R如果当前DataSet中的数据的类别相同 则标记R的类别标记为该类如果决策树高度大于alpha 则不再分解 标记R的类别classify DataSet 递归情况 标记R的类别classify DataSet 从featureList中选择属性F 选择Gini DataSet F 最小的属性划分 连续属性参考C4 5的离散化过程 以Gini最小作为划分标准 根据F 将DataSet做二元划分DS L和DS R 如果DS L或DS R为空 则不再分解如果DS L和DS R都不为空 节点C L CART classification DS L featureList alpha C R CART classification DS RfeatureList alpha 将节点C L和C R添加为R的左右子节点 CART 分类树算法步骤示意 CART 回归树 样本 X y y为分类 分类树y为实数 回归树设t代表树的某个节点 t中的样本集合为 X1 y1 X2 y2 应变量为实数 N t 是节点t中的样本个数 节点t的应变量的均值 节点t内的平方残差最小化 squaredresidualsminimizationalgorithm CART 回归树 划分 属性 F将t划分成左右节点tL和tR phi值 能最大化上式的就是最佳的 属性 划分 CART regression DataSet featureList alpha delta 创建根节点R如果当前DataSet中的数据的值都相同 则标记R的值为该值如果最大的phi值小于设定阈值delta 则标记R的值为DataSet应变量均值如果其中一个要产生的节点的样本数量小于alpha 则不再分解 标记R的值为DataSet应变量均值递归情况 从featureList中选择属性F 选择phi DataSet F 最大的属性 连续属性 或使用多个属性的线性组合 参考C4 5的离散化过程 以phi最大作为划分标准 根据F 将DataSet做二元划分DS L和DS R 如果DS L或DS R为空 则标记节点R的值为DataSet应变量均值如果DS L和DS R都不为空 节点C L CART regression DS L featureList alpha delta C R CART regression DS RfeatureList alpha delta 将节点C L和C R添加为R的左右子节点 CART 回归树算法步骤示意 CART 后剪枝 代价 复杂度剪枝CCP Cost ComplexityPruning CART 回归树与多元线性回归的区别 空间划分 非线性 线性 其他决策树 Quest quickunbiasedefficientstatisticaltree 算法Gini系数SLIQ SupervisedLearningInQuest 算法Gini系数SPRINT ScalableParallelizableInductionofClassificationTree 算法Gini系数并行PUBLIC PruningandBuildingIntegratedinClassification 算法Gini系数预剪枝 MDL剪枝算法CHAID Chi squaredAutomaticInteractionDetector 算法Chi square 决策树剪枝 数据噪音训练数据量少过拟合 决策树剪枝 预剪枝 前剪枝 通过提前停止树的构造来对决策树进行剪枝一旦停止该节点下树的继续构造 该节点就成了叶节点 该叶节点持有其数据集中样本最多的类或者其概率分布后剪枝首先构造完整的决策树 允许决策树过度拟合训练数据 然后对那些置信度不够的结点的子树用叶结点来替代该叶节点持有其子树的数据集中样本最多的类或者其概率分布 预剪枝 预剪枝判断停止树生长的方法可以归纳为以下几种 最为简单的方法就是在决策树到达一定高度的情况下就停止树的生长 到达此结点的实例个数小于某一个阈值也可停止树的生长 到达此结点的实例具有相同的特征向量 而不必一定属于同一类 也可停止生长 这种情况可以处理数据中的数据冲突问题 计算每次生长对系统性能的增益 如果这个增益值小于某个阈值则不进行生长 如果在最好情况下的生长增益都小于阈值 即使有些叶子结点的实例不属于同一类 也停止树的增长 后剪枝 降低错误剪枝REP ReducedErrorPruning 悲观错误剪枝PEP PessimisticErrorPruning 基于错误剪枝EBP Error BasedPruning 代价 复杂度剪枝CCP Cost ComplexityPruning 最小错误剪枝MEP MinimumErrorPruning 降低错误剪枝REP ReducedErrorPruning Quinlan独立的剪枝集D基本思路 对于决策树T的每棵非叶子树s 用叶子替代这棵子树 如果s被叶子替代后形成的新树关于D的误差等于或小于s关于D所产生的误差 则用叶子替代子树s优点 计算复杂性低对未知示例预测偏差较小 悲观错误剪枝PEP PessimisticErrorPruning Quinlan克服REP需要独立剪枝集的缺点误差估计的连续性校正自上而下悲观 基于训练集建立的树 对训练集合的错误率 对于未知集合来说是不可信的 设原始决策树T 叶节点z z节点训练实例个数为n z 其中错分个数为e z定义误差率为 偏向性 训练数据 增加连续性校正 相应的误差数 E z e z 0 5对于子树t 误差数 标准错误 剪枝条件 符合此条件 剪掉t 基于错误剪枝EBP Error BasedPruning QuinlanPEP的改进 C4 5中应用 更加悲观自下而上无需独立剪枝集概率角度 置信区间 描述一个随机变量的可能的值域范畴可能的取值范围可能性 置信水平取值范围 置信区间例如 x有95 的可能取值在 25 75 中 25 75 中 25是置信区间下限 25 75 中 75是置信区间上限从概率角度描述错分样本率统计检验 概率角度错分样本率r t 可看成是n t 次试验中某事件发生e t 次的概率 二项分布得到关于错分样本率在置信水平为CF的置信区间计算置信区间上限 二项式置信区间的最简单和最常用的公式依赖于逼近二项式分布的正态分布C4 5中使用Wilsonscoreinterval http en wikipedia org wiki Binomial proportion confidence interval Normal approximation interval EBP步骤 第一步 计算叶节点的错分样本率估计的置信区间上限U第二步 计算叶节点的预测错分样本数叶节点的预测错分样本数 到达该叶节点的样本数 该叶节点的预测错分样本率U第三步 判断是否剪枝及如何剪枝分别计算三种预测错分样本数 计算子树t的所有叶节点预测错分样本数之和 记为E1计算子树t被剪枝以叶节点代替时的预测错分样本数 记为E2计算子树t的最大分枝的预测错分样本数 记为E3比较E1 E2 E3 如下 E1最小时 不剪枝E2最小时 进行剪枝 以一个叶节点代替tE3最小时 采用 嫁接 grafting 策略 即用这个最大分枝代替t 代价 复杂度剪枝CCP Cost ComplexityPruning CCP又叫CART剪枝法代价 cost 样本错分率复杂度 complexity 树t的叶节点数 Breiman 定义t的代价复杂度 cost complexity 参数 用于衡量代价与复杂度之间关系表示剪枝后树的复杂度降低程度与代价间的关系如何定义 对t来说 剪掉它的子树s 以t中最优叶节点代替 得到新树new t new t可能会比t对于训练数据分错M个 但是new t包含的叶节点数 却比t少 Leaf s 1 个 复杂度降低了代价可能升高了如何平衡 令替换之后代价复杂度相等 增加了M个错分样本 但是减少了 leafs 1 个叶节点 negative M N Leaf sub 1 1 2514 3 0 000133 CCP剪枝步骤 第一步 计算完全