Chap9_决策树

1、第九章 决策树第九章 决策树9.1 决策树算法基本原理9.2 C5.0算法及应用9.3 分类回归树算法（CART）及应用9.4 CHAID算法及应用9.5 QUEST算法及应用9.1 决策树算法基本原理o决策树最早源于人工智能的机器学习技术，用以实现数据内在规律的探究和新数据对象的分类预测。o其核心算法较为成熟，很早就被各类智能决策系统所采纳。o由于决策树算法具有出色的数据分析能力和直观易懂的结果展示等特点，因此被纳入数据挖掘范畴，成为备受广大数据挖掘用户青睐、使用最为广泛的分类预测算法之一。分类和预测 o分类和预测是两种数据分析形式，可以用于提取描述重要数据类的模型或预测未来的数据趋势。然而

2、，分类是预测分类标号（或离散值），而预测建立连续值函数模型。o数据分类(data classfication)是一个两步过程：n第一步：建立一个模型，描述预定的数据类集或概念集。n第二步：使用模型进行分类。首先评估模型的预测准确率，如果认为模型的准确率可以接受，就可以用它对类标号未知的数据元组或对象进行分类。什么是决策树o决策树是一个类似于流程图的树结构，其中内部节点表示在一个属性上的测试，每个分枝代表一个测试输出，而每个树叶节点代表类或类分布。o为了对未知的样本分类，样本的属性值在决策树上测试。路径由根到存放该样本预测的叶结点。决策树很容易转换成分类规则。相关基本概念o根节点o叶结点o中间节

3、点o同层节点（兄弟节点）o父节点o子节点o二叉树和多叉树o分类树与回归树决策树的几何理解o决策树建立的过程就是决策树各个分枝依次形成的过程，从几何意义上理解，就是决策树的每个分枝在一定规则下完成对n维特征空间的区域划分o决策树建立好后，n维特征空间会被划分成若干个小的矩形区域，矩形区域的边界平行或垂直于坐标轴o决策树在确定每一步的特征空间划分标准时，同时兼顾由此形成的两个区域，希望同在一个区域中的观测，其数据变量尽可能取同一类值o对于回归树，其本质也是特征空间的区域划分，划分原则与分类树类似，是使同一区域中输出变量值的离散程度尽可能低决策树的核心问题o决策树的生长n从众多输入变量中确定最佳分组

4、变量n从分组变量的众多取值中找到一个最佳的分割点o决策树的剪枝树剪枝o当判定树创建时，由于数据中的噪声和孤立点，许多分支反映的是训练数据中的异常。剪枝方法处理这种过分适应数据问题。o通常这种方法使用统计度量，剪去最不可靠的分枝，这将导致较快的分类，提高树独立于测试数据正确分类的能力。先剪枝o通过提前停止树的构造而对树剪枝。一旦停止，节点成为树叶。该树叶可能持有子集样本中最频繁的类，或这些样本的概率分布。o在构造树时，如统计意义下的2、信息增益等度量，可以用于评估分裂的优良性。如果在一个节点划分样本将导致低于预定义阀值的分裂，则给定子集的进一步划分将停止。然而，选取一个适当的阀值是困难的。较高的

5、阀值可能导致过分简化的树，而较低的阀值可能使得树的化简太少。后剪枝o由“完全生长”的树剪去分枝，通过删除节点的分枝，剪掉树节点。o代价复杂性剪枝算法是后剪枝方法的一个实例。最下面的未被剪枝节点成为树叶，并用它先前分枝中最频繁的类标记。对于树中每个非树叶节点，算法计算该节点上的子树被剪枝可能出现的期望错误率。o可以交叉使用先剪枝和后剪枝，形成组合式方法。后剪枝所需的计算比先剪枝多，但通常产生更可靠的树。气象数据集序号序号天气天气气温气温湿度湿度有风有风打网球打网球1晴热高无No2晴热高有No3多云热高无Yes4雨温暖高无Yes5雨凉爽正常无Yes6雨凉爽正常有No7多云凉爽正常有Yes8晴温暖高

6、无No9晴凉爽正常无Yes10雨温暖正常无Yes11晴温暖正常有Yes12多云温暖高有Yes13多云热正常无Yes14雨温暖高有No决策树的算法oC5.0：以信息增益率为标准确定决策树的分枝准则，寻找最佳分组变量和分割点。oCART：以基尼系数和方差确定最佳分组变量和分割点，目标变量可以是分类型也可以是数值型，只能建立二叉树。oCHAID：从统计显著性角度确定当前最佳分组变量和分割点。oQUEST：最佳分组变量和分割点的确定方式吸纳了许多统计学的经典方法。第九章 决策树9.1 决策树算法基本原理9.2 C5.0算法及应用9.3 分类回归树算法（CART）及应用9.4 CHAID算法及应用9.5

7、 QUEST算法及应用9.2 C5.0算法及其应用o 基本概念n 信息熵n 信息增益n 信息增益率o 算法n ID3n C4.5信息增益的计算o气象数据集的决策树构造（ID3）oyesno合计合计晴235多云404雨325合计9514C4.5方法oC5.0的学生参加公益活动分析o具体操作nModel选项卡设置nAnalyze选项卡设置o模型计算结果n模型选项卡n查看器选项卡o预测结果n预测分类值n预测置信度n倾向性得分具体操作oModel选项卡设置nOutput type：指定分析结果的类型nGroup symbolics：选中表示利用ChiMerge分箱法检查当前分组变量的各个类别能否合并。

8、nUse boosting：表示采用推进方式建立模型以提高模型预测的稳健性nCross-validate：表示采用交叉验证法建立模型nMode：指定决策树建模中的参数设置方式oSimple：自动调整参数nFavor选项用来指定参数设置的原则Accuracy：以追求高的预测精度或低的错误率为原则设置模型参数，可能导致过度拟合问题Generality：设置为默认参数，以减少模型对数据的过度“依赖”nExpected noise：指定数据所含噪声样本的比例，通常可不指定oExpert：手动调整参数nPruning sevrity：输入鞠策树修剪时的置信度，默认为75=100-25nMinimum r

9、ecords per child branch：每个节点允许的最少样本量具体操作（续一）oAnalyze选项卡设置nCalculate variable importance：选中表示以图形方式显示输入变量对建模的重要性nPropensity Scores（valid only for flag targets）：用于指定计算变量的倾向性得分的方法oCalculate raw propensity scores：选中表示对每个观测，分类模型给出预测值为真的概率，此概率是基于训练样本集的oCalculate adjusted propensity scores：选中表示对每个观测，分类模型给出预

10、测值为真的调整概率，此概率是基于测试样本集或验证样本集的。具体操作（续二）oCost选项卡设置n选中Use misclassification costs选项n给出损失矩阵的单位损失值n损失矩阵的使用策略o数据建模阶段使用损失矩阵。C5.0采用这种策略，但损失矩阵并不影响决策树的生长，而是在修剪过程中予以考虑。o样本预测时使用损失矩阵。节点的预测分类结果不再由众数决定，即不再单纯以置信度为为依据，而将错判损失也考虑进来，在损失和置信区间之间取得适当的平衡。模型计算结果o模型选项卡n查看每个节点包含的样本量及置信度n显示相关详细信息n查看输入变量的倾向性得分o查看器选项卡预测结果o预测分类值：以

11、$C开头的变量为模型给出的预测分类值，是从决策树上得到的，符合相应的推理规则。o预测置信度：置信度$CC是相应规则的置信度经过拉普拉斯估计器调整后得到的o倾向性得分：以$CRP开头的变量，存储各个样本的倾向性得分n如果预测值为真（这里为Yes），且预测置信度为0.808，则该观测的倾向性得分为0.808n如果某观测的观测值为假（这里为No），且预测置信度为0.906，则该观测倾向性得分为1-0.906=0.094N折交叉验证oN折交叉验证可使模型误差的估计相对准确oN折交叉验证的设置n选择Cross-validate项nNumber of bids：指定折数n如果同时选中了Use partit

12、ioned data项，那么N折交叉验证只在训练样本上进行o计算结果n系统并没有给出N折交叉验证中各模型的情况，以及相应的误差估计，只是在模型计算结果的Summary选项卡中，输出了N个模型预测精度的分布参数n由于系统不允许N折交叉验证中样本的随机划分结果重复出现，因此，每次建模的样本不同，平均预测精度和标准差也会有所不同Boosting技术oBoosting技术用于机器学习中的有指导学习算法，包括建模和投票两个阶段o建模阶段n建立第一个模型时，训练样本集中的每个观测有相同的权重，即每个观测对模型的影响程度是相同的。模型建立后，需要调整各个观测的权重，对第一个模型未能正确预测的样本给予较高的权

13、重，正确预测的样本给以较低的权重n准备建立第二个模型，根据权重重新构造训练样本集，权重越大的样本出现在训练样本集中的可能性越高。因此，第二个模型重点关注的是第一个模型未能正确预测的样本n同理，准备建立第三个模型，着重考虑第二个模型未能正确预测的样本。依次进行下去。o投票阶段n不同的模型具有不同的权重，权重的大小与模型的误差成反比。n误差较小的模型有较高的投票权重，误差较大的模型有较低的投票权重n权重越高的模型，对决策结果的影响越大Boosting技术oBoosting的具体操作n选择Use BoostingnNumber of trials中输入迭代次数o结果分析n系统给出了各个决策模型的推理

14、结果，每个模型都有自己的预测精度n迭代过程中，每个训练样本集是不完全相同的，因此，每次计算过程所选择的最佳分组变量也会变化。n系统没有给出各个模型具体预测和权重等信息，boost后显现的是基于原样本的预测精度。n应用Boosting策略后，预测分类是过个模型的投票结果，更加稳健，预测置信度也会更加全面客观。第九章 决策树9.1 决策树算法基本原理9.2 C5.0算法及应用9.3 分类回归树算法（CART）及应用9.4 CHAID算法及应用9.5 QUEST算法及应用9.3 分类回归树及应用分类回归树算法同样包括决策树生长和修剪两个过程，这点与C5.0算法的思路相同，其主要差别体现在以下方面：o

15、C5.0中是输出变量只能是分类型，即只能建立分类树。而CART中输出变量可以是分类型，也可以是数值型。即CART既可以建立分类树也可以建立回归树。oC5.0可以建立多叉树，而CART只能建立二叉树。oC5.0以信息熵为基础，确定最佳分组变量和分割点，而CART以Gini系数和方差作为选择依据。oC5.0依据训练样本集，通过近似正态分布确定决策树的标准，而CART则依据测试样本进行修剪。CART使用的不纯性度量 o分类的目标变量nGINIn双化n有序双化（对于有序目标）o连续的目标变量（回归树）n最小二乘偏差n最小绝对偏差GINI指数o气象数据的基尼指数计算oyesno合计合计晴235多云404

16、雨325合计9514Twoing策略（双化）o节点输出变量差异性的测度仍采用Gini系数o将目标类别划分成双超类，然后基于这些双超类找出被预测变量上的最佳划分。o不同的是，不再以Gini系数减小最快为原则，而是要找到是合并的左右子节点（两个超类）中Gini系数差异足够大的合并点。Ordered策略（有序双化）o是双化指数的修改，用于有序目标变量。o限定只有两个连续的类别才可以合并成超类，因此可选择的超类合并点会大大缩减。回归树oClementine分类回归树的应用示例o具体操作nModel选项卡nExpert选项卡o分析结论Clementine分类回归树的应用示例o具体操作n构建选项卡n模型选

17、项卡o分析结论构建选项选项卡o先验：用来指定先验分布n这里的先验概率不同于贝叶斯估计中的先验概率，其本质是给样本以不同的权重，且权重取决于输出变量的类别，从而对分类回归树的简历产生影响，是模型偏向高权重的变量。第九章 决策树9.1 决策树算法基本原理9.2 C5.0算法及应用9.3 分类回归树算法（CART）及应用9.4 CHAID算法及应用9.5 QUEST算法及应用9.4 CHAID算法及应用作为一种决策树算法，CHAID的主要特点是:o输入变量和输出变量可以是分类型也可以是数值型。o能够建立多叉树。o从统计显著性角度确定当前最佳分组变量和分割点。输入变量的预处理o数值型输入变量的预处理是

18、分箱，即首先按分位点分箱，然后根据统计检验结果，合并对输出结果取值没有显著影响的组o分类型输入变量的预处理是通过统计检验，在其多个分类水平中找到对输出变量取值影响不显著的类别并合并它们，形成超类。o输出变量为分类型的采用卡方检验；输出变量为数值型的采用F检验。输入变量的预处理（续一）o输出变量为分类型，输入变量为数值型，采用ChiMerge分组法。n将输入变量按变量值升序排列n定义初始区间，使输入变量的每个取值均落入一个区间内n计算输入变量相邻两组与输出变量的列联表n在列联表的基础上计算卡方观测值，输入变量在该相邻区间上的分组对输出变量没有显著影响，则可以合并。n重复以上步骤，直到任何两个相邻

19、组无法合并。o输出变量为分类型，输入变量为分类型，采用卡方检验的方法，反复检验与合并，形成超类，直到输入变量的超类无法在合并为止。对于顺序型分类输入变量，只能合并相同的类。o输出变量为数值型，输入变量为数值型，采用方差分析方法。将经过初始分组的输入变量作为方差分析中的控制变量，输出变量为观测变量，检验输入变量初始分组下的输出变量的分布是否存在显著差异，并进行多重比较检验，合并分布不存在显著差异的相邻类别，形成超类。o输出变量为数值型，输入变量为分类型，采用方差分析方法。最佳分组变量的选择o分组变量确定的依据是：输入变量与输出变量之间的相关程度o将与输出变量最相关的输入变量作为最佳分组变量o将分

20、组变量的各个类别作为树的分枝，长出多个分叉。ExhaustiveCHAID算法o在计算检验统计量的概率P-值时，将继续合并输入变量的分组，直到最终形成两个组或两个超类，确保所有输入变量的检验统计量的自由度都相同。o比较概率P-值，取概率P-值最小的输入变量为当前最佳分组变量。o但在决策树分枝生长时，仍保持CHAID算法的原有分组结果。CHAID的修剪CHAID采用预修剪策略，通过参数控制决策树的充分生长，基本参数包括：o 决策树最大深度o 树中父节点和子节点的最少样本量和比或比例o 当输入变量和输出变量的相关性小于一个指定值时，则不必进行分组。将CHAID用于气象数据o 计算响应变量在根节点的

21、分布o 对于每个预测变量X，找出关于Y在该节点的分布差别最不显著的类别对。o 天气与目标变量之间的交叉表 由于天气有三个类别，因此有3个2*2的 子交叉表需要考虑。o 由于，天气=“晴”和天气=“雨”的p值最大 因此合并这些类别，并计算交叉表。o 利用Bonferroni乘子计算调整的p值， p=0.3786o 同理，计算气温和湿度的p值，取最小的湿度为分枝变量。类别类别实例数实例数% %Play=yes964.29Play=no535.71天气天气(X1)(X1)YesYesNoNo合计合计晴235多云404雨325合计9514天气天气(X1)(X1)YesYesNoNo晴23多云40卡方=

22、3.6d.f =1P值=0.0578天气天气(X1)(X1)YesYesNoNo晴23雨32卡方=4d.f =1P值=0.5271天气天气(X1)(X1)YesYesNoNo晴23多云40卡方=2.857d.f =1P值=0.0909天气天气(X1)(X1)YesYesNoNo晴或雨55多云40卡方=3.111d.f =1P值=0.0777CHAID算法应用o具体操作nModel选项卡nExpert选项卡o结果分析第九章 决策树9.1 决策树算法基本原理9.2 C5.0算法及应用9.3 分类回归树算法（CART）及应用9.4 CHAID算法及应用9.5 QUEST算法及应用9.5 QUEST算法及应用QUEST算法的特点是：o输入变量可以是分类型也可以是数值型，输出变量为分类型。o用于建立二叉树。o最佳分组变量和分割点的确定方式吸纳了许多统计学的经典方法。确定当前最佳分组变量oQUEST确定最佳分组变量方法的基本原理与CHAID方法非常相似，不同点在于，QUEST不对输入变量进行预