决策树-上-ID3C4.5CART及剪枝.pptx

决策树-上,武承羲,内容,决策树基础 经典决策树 剪枝,决策树,决策树： 用来表示决策和相应的决策结果对应关系的树。树中每一个非叶节点表示一个决策，该决策的值导致不同的决策结果(叶节点)或者影响后面的决策选择。 示例：,决策树,决策树类型 分类树：叶节点对应于一类别 回归树：叶节点对应于一连续值 ID3, C4.5 and C5.0 ( Ross Quinlan ) CART ( L.Breiman，J.Friedman，R.Olshen和C.Stone ) 思想：空间划分！ 比如，用变量y表示因变量（分类变量），用x1, x2, x3,.,xm表示自变量。通过递归的方式把关于自变量的m维空间划分为不重叠的矩形。 图示：,决策树,ID3=C4.5=C5.0,Ross Quinlan ID3 1986年 C4.5 1993年 C5.0 1998年 2011年获得KDD创新奖 /Personal/ /download.html /,ID3/C4.5/C5.0的分类基础,信息熵 1948年，香农提出了“信息熵”的概念，解决了对系统信息的量化度量问题。 香农认为信息的准确信息量可以用下面的信息熵公式计算： 一个系统越是有序，信息熵就越低；反之，一个系统越乱，信息熵就越高。所以，信息熵也可以说是系统有序化程度的一个衡量。,信息增益（information gain） 是指期望信息或者信息熵的有效减少量。,信息增益率（information gain ratio） 由划分个数引起的偏置问题（划分越多=引起每个划分内部数据纯度的变化，分块越小，数据纯度可能越高=进而引起偏置问题）： 设样本集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源码：/,示例-1 属性及值域： outlook = sunny, overcast, rain ，temperature = hot, mild, cool humidity = high, normal ，wind = weak, strong ,Gain(S, Temperature) = 0.029 Gain(S, Humidity) = 0.151 Gain(S, Wind) = 0.048 由此选择根节点划分属性为outlook,参考： /ddd/cap6635/Fall-97/Short-papers/2.htm /wiki/ID3_algorithm,C4.5,1993年由Quilan提出的C4.5算法(对ID3的改进) 信息增益率 连续值属性 缺失值 后剪枝 基于错误剪枝EBP(Error-Based Pruning),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%被分配到另一个分支。这些片断样例（fractional examples）的目的是计算信息增益，另外，如果有第二个缺少值的属性必须被测试，这些样例可以在后继的树分支中被进一步细分。(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的子节点 源码：/Personal/,C4.5,C4.5算法优点： 产生的分类规则易于理解 准确率较高。 C4.5算法缺点： 在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。,C5.0,思想：加入Boosting算法框架 特点： 更快 内存使用更有效 更小的决策树 商业机密 C5.0教程：/see5-unix.html 裁剪版：/download.html,CART,分类回归树CART(Classification and Regression Trees) 1984 L.Breiman，J.Friedman，R.Olshen和C.Stone /breiman/ /jhf/ /olshen/ 目标变量是类别的 - 分类树 目标变量是连续的 - 回归树,CART,二元划分 二叉树不易产生数据碎片，精确度往往也会高于多叉树，所以在CART算法中，采用了二元划分 不纯性度量 分类目标：Gini指标、Towing、order Towing 连续目标：最小平方残差、最小绝对残差 剪枝： 用独立的验证数据集对训练集生长的树进行剪枝,Gini指标 (Gini index),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_R featureList, alpha) 将节点C_L和C_R添加为R的左右子节点,CART - 分类树算法步骤示意,CART- 回归树,样本： (X, y) y为分类 = 分类树 y为实数 = 回归树 设t代表树的某个节点，t中的样本集合为：(X1,y1), (X2,y2) ，应变量为实数，N(t)是节点t中的样本个数。节点t的应变量的均值： 节点t内的平方残差最小化 (squared residuals minimization algorithm)：,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_R featureList, alpha, delta) 将节点C_L和C_R添加为R的左右子节点,CART- 回归树算法步骤示意,CART,后剪枝： 代价-复杂度剪枝CCP(Cost-Complexity Pruning) CART-回归树 与 多元线性回归的区别： 空间划分！非线性/线性,其他决策树,Quest(quick unbiased efficient statistical tree)算法 Gini系数 SLIQ (Supervised Learning In Quest)算法 Gini系数 SPRINT (Scalable Parallelizable Induction of Classification Tree)算法 Gini系数 并行 PUBLIC(Pruning and Building Integrated in Classification)算法 Gini系数 预剪枝、MDL剪枝算法 CHAID(Chi-squared Automatic Interaction Detector)算法 Chi-square,决策树剪枝,数据噪音 训练数据量少 过拟合,决策树剪枝,预剪枝（前剪枝） 通过提前停止树的构造来对决策树进行剪枝 一旦停止该节点下树的继续构造，该节点就成了叶节点。 该叶节点持有其数据集中样本最多的类或者其概率分布 后剪枝 首先构造完整的决策树，允许决策树过度拟合训练数据， 然后对那些置信度不够的结点的子树用叶结点来替代 该叶节点持有其子树的数据集中样本最多的类或者其概率分布,预剪枝,预剪枝判断停止树生长的方法可以归纳为以下几种： 最为简单的方法就是在决策树到达一定高度的情况下就停止树的生长； 到达此结点的实例个数小于某一个阈值也可停止树的生长； 到达此结点的实例具有相同的特征向量，而不必一定属于同一类，也可停止生长。这种情况可以处理数据中的数据冲突问题； 计算每次生长对系统性能的增益，如果这个增益值小于某个阈值则不进行生长。如果在最好情况下的生长增益都小于阈值，即使有些叶子结点的实例不属于同一类，也停止树的增长。,后剪枝,降低错误剪枝 REP ( Reduced Error Pruning) 悲观错误剪枝 PEP (Pessimistic Error Pruning) 基于错误剪枝 EBP (Error-Based Pruning) 代价-复杂度剪枝 CCP (Cost-Complexity Pruning) 最小错误剪枝 MEP (Minimum Error Pruning) ,降低错误剪枝REP( Reduced Error Pruning),Quinlan 独立的剪枝集D 基本思路: 对于决策树 T 的每棵非叶子树s, 用叶子替代这棵子树. 如果s 被叶子替代后形成的新树关于D 的误差等于或小于s关于D 所产生的误差, 则用叶子替代子树s 优点： 计算复杂性低 对未知示例预测偏差较小,悲观错误剪枝PEP( Pessimistic Error Pruning ),Quinlan 克服REP需要独立剪枝集的缺点 误差估计的连续性校正 自上而下 悲观： 基于训练集建立的树，对训练集合的错误率，对于未知集合来说是不可信的,设原始决策树T，叶节点z，z节点训练实例个数为n_z，其中错分个数为e_z 定义误差率为： 偏向性（训练数据） 增加连续性校正： 相应的误差数：E_z = e_z + 0.5 对于子树t，误差数： 标准错误: 剪枝条件：,符合此条件，剪掉t,基于错误剪枝EBP(Error-Based Pruning),Quinlan PEP的改进（C4.5中应用） 更加悲观 自下而上 无需独立剪枝集 概率角度,置信区间,描述一个随机变量的可能的值域范畴 可能的取值范围 可能性：置信水平 取值范围：置信区间 例如：x 有95%的可能取值在25,75中 25,75中，25是 置信区间下限 25,75中，75是 置信区间上限 从概率角度描述错分样本率 统计检验,概率角度 错分样本率r(t)可看成是n(t)次试验中某事件发生e(t)次的概率-二项分布 得到关于错分样本率在置信水平为CF的置信区间 计算置信区间上限：,二项式置信区间的最简单和最常用的公式依赖于逼近二项式分布的正态分布 C4.5中使用 Wilson score interval: /wiki/Binomial_proportion_confidence_interval#Normal_approximation_interval,EBP步骤,第一步：计算叶节点的错分样本率估计的置信区间上限U 第二步：计算叶节点的预测错分样本数 叶节点的预测错分样本数=到达该叶节点的样本数*该叶节点的预测错分样本率U 第三步：判断是否剪枝及如何剪枝 分别计算三种预测错分样本数： 计算子树t的所有叶节点预测错分样本数之和，记为E1 计算子树t被剪枝以叶节点代替时的预测错分样本数，记为E2 计算子树t的最大分枝的预测错分样本数，记为E3 比较E1，E2，E3，如下： E1最小时，不剪枝 E2最小时，进行剪枝，以一个叶节点代替t E3最小时，采用“嫁接”(grafting)策略，即用这个最大分枝代替t,代价-复杂度剪枝CCP(Cost-Complexity Pruning),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剪枝步骤： 第一步： 计算完全决策树T_max的每个非叶节点的值； 循环剪掉具有最小值的子树，直到剩下根节点 得到一系列剪枝(嵌套)树T_0,T_1,T_2,