{决策管理}决策树讲义PPT50页

《{决策管理}决策树讲义PPT50页》由会员分享，可在线阅读，更多相关《{决策管理}决策树讲义PPT50页（50页珍藏版）》请在金锄头文库上搜索。

1、决策树-上,武承羲,内容,决策树基础 经典决策树 剪枝,决策树,决策树： 用来表示决策和相应的决策结果对应关系的树。树中每一个非叶节点表示一个决策，该决策的值导致不同的决策结果(叶节点)或者影响后面的决策选择。 示例：,决策树,决策树类型 分类树：叶节点对应于一类别 回归树：叶节点对应于一连续值 ID3, C4.5 and C5.0 ( Ross Quinlan ) CART ( L.Breiman，J.Friedman，R.Olshen和C.Stone ) 思想：空间划分！ 比如，用变量y表示因变量（分类变量），用x1, x2, x3,.,xm表示自变量。通过递归的方式把关于自变量的m维空间

2、划分为不重叠的矩形。 图示：,决策树,ID3=C4.5=C5.0,ID3/C4.5/C5.0的分类基础,信息熵 1948年，香农提出了“信息熵”的概念，解决了对系统信息的量化度量问题。 香农认为信息的准确信息量可以用下面的信息熵公式计算： 一个系统越是有序，信息熵就越低；反之，一个系统越乱，信息熵就越高。所以，信息熵也可以说是系统有序化程度的一个衡量。,信息增益（information gain） 是指期望信息或者信息熵的有效减少量。,信息增益率（information gain ratio） 由划分个数引起的偏置问题（划分越多=引起每个划分内部数据纯度的变化，分块越小，数据纯度可能越高=进而

3、引起偏置问题）： 设样本集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，将DataSe

4、t划分为不同的子集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.029 Gain(S, Hum

5、idity) = 0.151 Gain(S, Wind) = 0.048 由此选择根节点划分属性为outlook,C4.5,1993年由Quilan提出的C4.5算法(对ID3的改进) 信息增益率 连续值属性 缺失值 后剪枝 基于错误剪枝EBP(Error-Based Pruning),C4.5-连续型属性,离散化处理：将连续型的属性变量进行离散化处理，形成决策树的训练集 把需要处理的样本（对应根节点）或样本子集（对应子树）按照连续变量的大小从小到大进行排序 假设该属性对应的不同的属性值一共有N个，那么总共有N-1个可能的候选分割阈值点，每个候选的分割阈值点的值为上述排序后的属性值中两两前后连

6、续元素的中点 用信息增益率选择最佳划分,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%被分配到另一个分支。

7、这些片断样例（fractional examples）的目的是计算信息增益，另外，如果有第二个缺少值的属性必须被测试，这些样例可以在后继的树分支中被进一步细分。(C4.5中使用) 简单处理策略就是丢弃这些样本,C4.5-算法步骤示意,C4.5,C4.5算法优点： 产生的分类规则易于理解 准确率较高。 C4.5算法缺点： 在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。,C5.0,CART,CART,二元划分 二叉树不易产生数据碎片，精确度往往也会高于多叉树，所以在CART算法中，采用了二元划分 不纯性度量 分类目标：Gini指标、Towing、order Towin

8、g 连续目标：最小平方残差、最小绝对残差 剪枝： 用独立的验证数据集对训练集生长的树进行剪枝,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,

9、 sunny, overcast, rain 去除不代表任何分裂的集合：空集和全集sunny, overcast, rain。则基于Outlook的划分方式有3种： 分别计算每种划分的Gini指标：,选择划分,CART - 分类树,对于离散值属性，在算法中递归的选择该属性产生最小Gini指标的子集作为它的分裂子集。（或使用其他不纯度） 对于连续值属性，必须考虑所有可能的划分点。其策略类似于C4.5中介绍的方法，利用Gini指数最小原则，选择划分点。,CART - 分类树,节点t的类classify(t):,CART_classification(DataSet, featureList, al

10、pha,)： 创建根节点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,

11、 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将

12、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的离散化过程

13、 (以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-回

14、归树 与 多元线性回归的区别： 空间划分！非线性/线性,其他决策树,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(

15、Chi-squared Automatic Interaction Detector)算法 Chi-square,决策树剪枝,数据噪音 训练数据量少 过拟合,决策树剪枝,预剪枝（前剪枝） 通过提前停止树的构造来对决策树进行剪枝 一旦停止该节点下树的继续构造，该节点就成了叶节点。 该叶节点持有其数据集中样本最多的类或者其概率分布 后剪枝 首先构造完整的决策树，允许决策树过度拟合训练数据， 然后对那些置信度不够的结点的子树用叶结点来替代 该叶节点持有其子树的数据集中样本最多的类或者其概率分布,预剪枝,预剪枝判断停止树生长的方法可以归纳为以下几种： 最为简单的方法就是在决策树到达一定高度的情况下就停

16、止树的生长； 到达此结点的实例个数小于某一个阈值也可停止树的生长； 到达此结点的实例具有相同的特征向量，而不必一定属于同一类，也可停止生长。这种情况可以处理数据中的数据冲突问题； 计算每次生长对系统性能的增益，如果这个增益值小于某个阈值则不进行生长。如果在最好情况下的生长增益都小于阈值，即使有些叶子结点的实例不属于同一类，也停止树的增长。,后剪枝,降低错误剪枝 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 所产生的