决策树培训讲义 二

决策树-上武承羲内容决策树基础经典决策树剪枝决策树决策树：用来表示决策和相应的决策结果对应关系的树。树中每一个非叶节点表示一个决策，该决策的值导致不同的决策结果(叶节点)或者影响后面的决策选择。示例：天气风阳光不玩玩不玩玩玩雨晴阴强弱强弱决策树决策树类型分类树：叶节点对应于一类别回归树：叶节点对应于一连续值ID3,C4.5andC5.0(RossQuinlan)CART(L.Breiman，J.Friedman，R.Olshen和C.Stone)思想：空间划分！比如，用变量y表示因变量（分类变量），用x1,x2,x3,...,xm表示自变量。通过递归的方式把关于自变量的m维空间划分为不重叠的矩形。图示：决策树ID3=>C4.5=>C5.0ID3/C4.5/C5.0的分类基础信息熵1948年，香农提出了“信息熵”的概念，解决了对系统信息的量化度量问题。香农认为信息的准确信息量可以用下面的信息熵公式计算：一个系统越是有序，信息熵就越低；反之，一个系统越乱，信息熵就越高。所以，信息熵也可以说是系统有序化程度的一个衡量。信息增益（informationgain）是指期望信息或者信息熵的有效减少量。信息增益率（informationgainratio）由划分个数引起的偏置问题（划分越多=>引起每个划分内部数据纯度的变化，分块越小，数据纯度可能越高=>进而引起偏置问题）：设样本集S按离散属性F的V个不同的取值划分为，共V个子集定义Split(S,F)：则用F对S进行划分的信息增益率为：ID31986年由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源码：：/DayOutlookTemperatureHumidityWindPlayballD1SunnyHotHighWeakNoD2SunnyHotHighStrongNoD3OvercastHotHighWeakYesD4RainMildHighWeakYesD5RainCoolNormalWeakYesD6RainCoolNormalStrongNoD7OvercastCoolNormalStrongYesD8SunnyMildHighWeakNoD9SunnyCoolNormalWeakYesD10RainMildNormalWeakYesD11SunnyMildNormalStrongYesD12OvercastMildHighStrongYesD13OvercastHotNormalWeakYesD14RainMildHighStrongNo示例-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由此选择择根节节点划划分属属性为为outlookC4.51993年由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.5C4.5算法优点：产生的分类规规则易于理理解准确率较高。C4.5算法缺点：在构造树的过过程中，需需要对数据据集进行多多次的顺序序扫描和排排序，因而而导致算法法的低效。。C5.0CARTCART二元划分二叉树不易易产生数据据碎片，精精确度往往往也会高于于多叉树，，所以在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:/wiki/Binomial_proportion_confidence_interval#Normal_approximation_intervalEBP步骤第一步：：计算叶叶节点的的错分样样本率估估计的置置信区间间上限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中最优叶叶