决策树原理与应用C0

1、决策树原理与应用：C5.0分类预测指通过向现有数据的学习，使模型具备对未来 新数据的预测能力。对于分类预测有这样几个重要，一是此 模型使用的方法是归纳和提炼，而不是演绎。非数据挖掘类 的软件的基本原理往往是演绎，软件能通过一系列的运算， 用已知的公式对数据进行运算或统计。分类预测的基本原理 是归纳，是学习，是发现新知识和新规律； 二是指导性学习 所谓指导性学习，指数据中包含的变量不仅有预测性变量， 还有目标变量；三是学习，模型通过归纳而不断学习。事实上，预测包含目标变量为连续型变量的预测和目标变量 为分在变量的分类预测。两者虽然都是预测，但结合决策树 算法和我们之前介绍过的时间序列算法知，二者

2、还是有明显 的差别的。Clementine决策树的特点是数据分析能力由色，分析结果易 于展示。决策树算法是应用非常广泛的分类预测算法。1.1决策树算法概述1.11什么是决策树决策树算法属于有指 导的学习，即原数据必须包含预测变量和目标变量。决策树 之所以如此命名，是因为其分析结果以一棵倒置的树的形式 呈现。决策树由上到下依次为根节点、内部节点和叶节点。 一个节点对应于数据中的一个字段，即一个字段一一即 Question 对数据进行一次划分。决策树分为分类决策树（目标变量为分类型数值）和回归决策树（目标变量为连续 型变量）。分类决策树叶节点所含样本中，其输生变量的众 数就是分类结果；回归树的叶节

3、点所含样本中，其输生变量 的平均值就是预测结果。这一点需要格外注意。与其它分类预测算法不同的是，决策树基于逻辑比较（即布 尔比较）。可以简单描述为：If （条件1） Then （结果1）; If（条件2） Then （结果2）。这样，每一个叶节点都对应于一 条布尔比较的推理规则，对新数据的预测就正是依靠这些复 杂的推理规则。在实际应用中，一个数据产生的推理规则是 极为庞大和复杂的，因此对推理规则的精简是需要关注的。 1.12决策树的几何理解将训练样本集（即操作中常说的 Training Data）看做一个n维空间上的一个点，则上面我们 提到的布尔比较后的推理规则就像是存在于这个n维空间中的“线

4、”。决策树建立的过程形象上看，就是倒置的树生长 的过程，其几何意义上是，每个分枝（每条推理规则）完成 对n维空间区域划分的过程。决策树正式生成，则 n维空间 正式划分完毕，则每一个小区域，代表一个叶节点。通常 n 维空间不易于理解，故采用倒置的树来表示此结果。需要注 意的一点是，在划分过程中，要尽量做到不同类别的结果归 于不同的“区域”。1.13决策树的核心问题：生成与修剪决策树核心问题有二。一是利用Training Data完成决策树的生成过程；二是利用Testing Data完成对决策树的精简过程。即前面我们提到的， 生成的推理规则往往过多，精简是必需的。一、决策树的生长决策树生长过程的本

5、质是对Training Data反复分组（分枝）的过程，当数据分组（分枝）不再有意义注意，什么叫分组不再有意义一一时，决策树生成过程 停止。因此，决策树生长的核心算法是确定数据分析的标准， 即分枝标准。何为有意义呢？注意，当决策树分枝后结果差异不再显著下 降，则继续分组没有意义。也就是说，我们分组的目的，是 为了让输由变量在差异上尽量小，到达叶节点时，不同叶节 点上的输生变量为相同类别，或达到用户指定的决策树停止 生成的标准。这样，分枝准则涉及到两方面问题：1、如果从众多输入变量中选择最佳分组变量；2、如果从分组变量的众多取值中 找到最佳分割点。不同的决策树算法，如C4.5、C5.0、Chai

6、d、 Quest、Cart采用了不同策略。二、决策树的修剪完整的决策树并不是一棵分类预测新数据对象的最佳树。其原因是完整的决策树对Training Data描述过于“精确”。我们知道，随着决策树的生长，决策树分枝 时所处理的样本数量在不断减少，决策树对数据总体珠代表 程度在不断下降。在对根节点进行分枝时，处理的是全部样 本，再往下分枝，则是处理的不同分组下的分组下的样本。可见随着决策树的生长和样本数量的不断减少，越深层处的 节点所体现的数据特征就越个性化，可能由现如上推理规 则：“年收入大于50000元且年龄大于50岁且姓名叫张三的 人购买了此产品”。这种过度学习从而精确反映Training

7、Data特征，失去一般代表性而无法应用于新数据分类预测的现 象，叫过度拟合(Overfitting )或过度学习。那我们应该怎么 办呢？修剪！常用的修剪技术有预修剪(Pre-Pruning)和后修剪 (Post-Pruning)。Pre-Pruning可以事先指定决策树的最大深 度，或最小样本量，以防止决策树过度生长。前提是用户对 变量聚会有较为清晰的把握，且要反复尝试调整，否则无法 给由一个合理值。注意，决策树生长过深无法预测新数据， 生长过浅亦无法预测新数据。Post-pruning是一个边修剪边检验的过程，即在决策树充分生长的基础上，设定一个允许的最大错误率，然后一边修剪子 树，一边计算

8、输由结果的精度或误差。当错误率高于最大值 后，立即停止剪枝。基于 Training Data的Post-Pruning应该 使用 Testing Data。决策树中的 C4.5、C5.0、CHAID、CART 和QUEST都使用了不同 剪枝策略。2.2Clementine的C5.0的算法及应用 C5.0是C4.5的商业化版 本，因此算法细节因版权问题尚未公开，本节讨论的是与 C5.0算法核心相同的 C4.5算法。C4.5是在决策树老鼻祖算法ID3算法的基础上发展起来的，ID3算法自1979年由 Quinlan提由，经不断改善形成具有决策树里程碑意义的C4.5算法。需要注意的是C5.0用于生成多

9、分支决策树，输入变量可以是 分类型，也可以是数值型，输由变量为分类型。注意不同的 决策树算法对输入和输由数据类型的要求。正如1.1节提到的，决策树的核心问题之一是决策树分枝准则的确定。C5.0以信息增益率为标准确定最佳分组变量和最 佳分割点。其核心概念是信息嫡。1.2.1信息嫡和信息增益一、信息嫡信息嫡是信息论中的基本 概念。信息论由 Shannon于1948年提由并发展起来，用于 解决信息传递过程中的问题，也称统计通信理论。它认为：1、信息传递由信源、信道和信宿组成；2、传递系统存在于一个随机干扰环境中，因此传递系统对信息的传递是随机误差的。 如果把发送信息记为 U而接收到 信息记V,由信道

10、可记为通信模型， 为P(U|V)。信道模型是 一个条件概率矩阵 P(U|V) o信道模型可以看作是一个条件概率矩阵，信源也往往被理解为莫种随机序列，也具有莫种发生概率，且其概率求和为1。 在实际通信前，信宿信源会发生什么信息不可能知道，称为信宿对信源状态具有不确定性，由于这种不确定性是发生在 通信之前的，故称为先验不确定性。在收到信息后的不确定性，称为后验不确定性。如果先验不确定性等于后验不确定 性，则表示信息量为零；如果后验不确定性等于零，则表示 信宿收到了信源的全部信息。可见：信息是指对不确定性的消除。信息量由消除的不确定性来确定。数据定义为：-Log2P(Ui)。信息量单位是 bit,是

11、以2为 底的对数形式。信息嫡是信息量的数学期望，其表示式由于 过于复杂而不写。如果P (U)差别越小，信息嫡越大，平均不确定性越大； P(U)差别越在，信息嫡越小，平均不确定性越小。如：信息 嫡等于0,则表示只存在一种信息发送可能，没有发送的不 确定性。如果P(U) =1/K,即K个信源概率相同，则信息嫡 差别最大，不确定性最大。二、信息增益信息嫡又称为先验嫡，是在信息发送前信息量 的数学期望；后验嫡指在信息发送后，人信宿角度对信息量 的数学期望。一般先验嫡大于后验嫡， 先验嫡与后验嫡估差， 即所谓的信息增益。信息增益，反映的是信息消除随机不确 定性的程度。2.2.2 C5.0的决策树生长算法

12、一、如何从众多的分组变量中选择一个最佳的分组变量C5.0以信息论为指导，以信息增益率为标准确定最佳分组变量和 分割点。决策树将输生变量(是否购买)看做信源发生的信 息U ,将输入变量看成信宿收到的信息 Vo则在实际通信之前，也即是决策树建立之前， 输由变量做为信源发生的信息， 完全随机，具平均不确定性即为P0.在实际通信过程中添加变量1后，其平均不确定性为 P1,则添加变量1产生的信息 增益为P0-P1,其它变量如此。则根据信息增益大小判断哪 个变量为最佳分组变量。这里有个问题，即类别值多的输入 变量较类别值少的输入变量更有机会成为最佳分组变量。为 解决此问题，提由将信息增益量除以信息嫡，由抵

13、消了类别 值的影响，即有信息增益率来表征。那么，如何评价数值型输入变量消除平均不确定性的能力 呢？ 一般对其进行分箱处理，然后根据上述方法判定。分箱 不采用了 MDLP的嫡分组方法，Clementine中C5.0节点本 身包含了 MDLP算法，它将自动完成数值型输入变量的分箱 处理。二、输入变量带有缺失值时如何选择最佳分组变量C5.0在选择最佳分组变量时，通常将带有缺失值的样本当作临时剔除 样本看待，并进行权数调整处理。三、如何从分组变量的众多取值中找到一个最佳的分割点在确定了最佳分组变量后，C5.0将继续确定最佳分组变量的分 割点。如果分组变量是分类型变量，由按分组变量的K个取值进行分组，形

14、成K个分枝。如果分组变量是数值型变量，则先通过MDLP分箱法或ChiMerge分箱法进行分箱处理，然后分组。如果分组变量中存在缺失值，那怎么办呢？你无法判定此样 本分到哪个组中去，C5.0的处理是将其分到所有组中去。但 其权重不再为1,而为此组样本数占总样本数的比例。2.2.3 C5.0的剪枝算法 C5.0采用Post-Pruning法从叶节点向 上逐层剪枝，其关键是误差的估计及剪枝标准的设置。一、误差估计一般决策树的检验应该使用 Testing Data,但 C5.0使用了统计的置信区间的估计方法，直接在 Training Data中估计误差。二、剪枝标准在得到误差的估计后，C5.0将按照“

15、减少误差” 判断是否剪枝。首先，计算待剪子树中叶节点的加权误差， 然后与父节点的误差进行比较，如果大于则可以剪掉，否则 不能剪掉。2.2.4 C5.0的推理规则集 C5.0不有够构建决策树，同时还可 以生成推理规则集。但是从决策树导入推理规则集非常烦锁，推理规则集通常有自己生成算法，即 PRISM o该算法 gf1987rh 提由，是一种“覆盖”算法，对 Training Data100% 正确。2.2.5 C5.0的基本应用示例下面对一个使用了C5.0的挖掘案例进行介绍，这里不再像之前介绍案例似的步步介绍，现在只对重点部分进行介绍。主要是C5.0的面板设置及C5.0呈现的结果。下图为 C5.

16、0的面板设置。模型名称：可以自动，亦可以自定义。在平时练习时默认自动即可，在商业活动中为避免重名或混乱，一律要自定义命 名，这是数据挖掘的基本规范。使用分区数据：英文 Use Partitioned data。勾选表示利用 Partition变量将样本集进行分割。 但C5.0并不在Testing Data 上进行模型检验，还需要 Partition吗？需要，Partition的目 的是比较同一模型在不同样本集上的稳健性。输由类型：英文 Output Type。Decision Tree表示得不到成决 策树和由决策树得到的推理规则；Rule Set表示输由推理规则集，这个推理规则集并非由Deci

17、sion Tree生成，而是由PRISM法生成的。这里首先输由决策树。 组符号：英文Group Symbolics。选中表示使用 ChiMerge分箱法检查当前分组变 量的各个类别能否合并，如果可以应先合并再分枝，此方法 得到的Decision Tree相对精简。否则，对K个分类型分组变 量将生成K叉树，对数值型分组变量将生成二叉树。使用推进：英文 Use Boosting o表示采用推进方法建立模型 以提高模型预测的稳健性。交叉验证：英文 Cross-validate。表示将采用交叉验证的方法 构建模型。模式：英文Mode。决定决策树的剪枝策略。Simple 表示系统自动调整参数值，此时支持

18、选项中往往选择“精准 性”，表示以预测精度做为修剪依据。此时默认置信度为0.75。Expert选项表示自行调整参数进行剪枝。下图为选择Expert后的设置面板。在修剪严重性( Pruning Severity )中输入置信度，默认范围为0.25到1.在每个分支的最小纪录数中设置每个节点允许的最少样本量，亦可自行设置。Clementine分别以文字和决策树图形的形式展示C5.0决策树的分析结果。打开结果页面得如下图。在“模型”面板中，展示了从决策 树上直接获得的推理规则集。我们发现，在家长是否豉励节 点中，不豉励的含 30个样本，93.3%的选择不参加社会公益 活动。在家长是否豉励中豉励的节点分

19、支中，当在校综合测 评小于等于48时，含15个样本且有0.8比例的为不参加公 益活动，其余的为参加公益活动。在下面有“历史”“频数”的选项卡，点击可以查看每一条推理规则的具体信息。三、 预测结果那么，我们如何预测结果呢？将新生成的数学模型“添加到流”，并添加到“类型”节点上，执行，得到我们 的预测结果，如下图。在下图中新生成了两个字然，分别为“C-是否参与”与“ CC-是否参与"。第一个字段表示的是从 决策树上得到的预测分类值，符合相应的推理规则。第二个 字段表示的是得到此预测结果的置信度。此置信度是相应规 则的置信信经拉普拉斯估计器(Laplace Estimator)调整后的结果

20、。Laplace Estimator是Laplace于18世纪发明的经典方 法。注意，如果输生变量为数值型变量，不存在 Laplace Estimator o C5.0的数值类型要求是：输入数据是分类型数据 或数值型数据皆可，输由数据必须是分类型数据。C5的损失矩阵和Boosting技术一、损失矩阵前面的分析有个缺点，即没有考虑商业上的损失问题。事实上，当我们使用 Clementine对相关商业问题进行分析探讨时，做由的决策是 要背负很大的商业期望的。如果预测失败，就要承担相当的 损失。当然，我们说数据挖掘中误差是不可避免的，但显然,把可能由现的误差及其导致的损失反映由来，也是对商业客 户的另

21、外一种服务，也是极为重要的。本文将在前面探讨的 基础上，引入实际的商业问题，不仅引入了损失矩阵，也引 入了 Boosting 技术。事实上，以二分问题为例，我们往往会选择那些置信低但损 失小的决策，而不选择那些置信度高而损失高昂的决策，因 为只有这样才可以有效地规避损失期望值。在分类预测问题 中往往由现两类问题，一是实际为真却预测为假，我们称之 为弃真错误；一是实际假却预测为真，我们称之为取伪。弃 真取伪错误在传统的统计分析中也存在，典型的就是我们的 假设检验。损失矩阵是处理此类问题的有效手段，损失矩阵可以把可能 导致的损失引入到系统分析过程，从而得由更加符合商业实 际的结果。损失矩阵的用法一

22、般分为两种，一是在数据建模 阶段使用损失矩阵；一是在样本预测时使用损失矩阵。Clementine5.0采用的是第一种损失矩阵使用法，而不是第二种。1、数据建模过程的损失矩阵。前面我介介绍到，在数据建模过程中涉及到修剪的过程，修剪时的标准是什么？是“Reduce-Error”，即当此节点层的 Error大于其父节点的 Error时，则修剪掉，否则不予以修剪。引入损失矩阵后，修 剪方法由原先的“ Reduce-Error”转变为“ Reduce-Cost”法, 即当叶节点的损失大于其父节点的损失时，则进行修剪，否 则不予以修剪。2、样本预测阶段。在前面介绍中，我们提到，新数据的预 测由预测分类结果

23、的众数给由，置信度也是一个重要的考量 标准。加入损失矩阵的因素后，我们将结合莫种分类预测的 错判损失进行考量。这样，如果一种决策虽然有较高的置信 水平而它的错判损失较大，我们宁可选择置信度较低而具错 判较小的决策。下图为C5.0中的损失矩阵设置页面，我们将弃真的错判损失 自定义为1,而将取伪的错判损失自定义为 2.这样得生的预 测结果中，Yes的置信度都较高。C5的损失矩阵和 Boosting技术一、损失矩阵前面的分析有个缺点，即没有考虑商业上的损失问题。事实上，当我们使用 Clementine对相关商业问题进 行分析探讨时，做由的决策是要背负很大的商业期望的。如 果预测失败，就要承担相当的损

24、失。当然，我们说数据挖掘 中误差是不可避免的，但显然，把可能由现的误差及其导致 的损失反映由来，也是对商业客户的另外一种服务，也是极为重要的。本文将在前面探讨的基础上，引入实际的商业问题，不仅引入了损失矩阵，也引入了Boosting技术。事实上，以二分问题为例，我们往往会选择那些置信低但损 失小的决策，而不选择那些置信度高而损失高昂的决策，因 为只有这样才可以有效地规避损失期望值。在分类预测问题 中往往由现两类问题，一是实际为真却预测为假，我们称之 为弃真错误；一是实际假却预测为真，我们称之为取伪。弃 真取伪错误在传统的统计分析中也存在，典型的就是我们的 假设检验。损失矩阵是处理此类问题的有效

25、手段，损失矩阵可以把可能 导致的损失引入到系统分析过程，从而得由更加符合商业实 际的结果。损失矩阵的用法一般分为两种，一是在数据建模 阶段使用损失矩阵；一是在样本预测时使用损失矩阵。Clementine5.0采用的是第一种损失矩阵使用法，而不是第二种。1、数据建模过程的损失矩阵。前面我介介绍到，在数据建 模过程中涉及到修剪的过程，修剪时的标准是什么？是“Reduce-Error”，即当此节点层的 Error大于其父节点的 Error时，则修剪掉，否则不予以修剪。引入损失矩阵后，修 剪方法由原先的“ Reduce-Error”转变为“ Reduce-Cost”法, 即当叶节点的损失大于其父节点的

26、损失时，则进行修剪，否 则不予以修剪。2、样本预测阶段。在前面介绍中，我们提到，新数据的预 测由预测分类结果的众数给由，置信度也是一个重要的考量 标准。加入损失矩阵的因素后，我们将结合莫种分类预测的 错判损失进行考量。这样，如果一种决策虽然有较高的置信 水平而它的错判损失较大，我们宁可选择置信度较低而具错 判较小的决策。下图为C5.0中的损失矩阵设置页面，我们将弃真的错判损失 自定义为1,而将取伪的错判损失自定义为 2.这样得生的预 测结果中，Yes的置信度都较高。二、Boosting技术没有哪 个模型能百分百进行分类预测，一个模型给由的预测结论有 误差是常见的。因为预测结果一方面取决于模型，

27、一方面取 决于样本。不同的模型拥有不同的学习原理，其拟合偏差也 不一样。同时样本抽取时也会产生随机误差。一般模型本身 导致的误差我们称之为偏差，要降低偏差，就需要更换模型 或者增加、减少参数设置，这是以牺牲模型简洁性为代价的。 我们将样本的随机抽取产生的误差称为方差，此方差的分布 服从正态分布（只要莫因素受多个独立叠加的元因素影响， 则其分布服从正态分布）。要想减少方差，则需要增加几组 独立样本并尝试建立多个模型，让多个模型对预测结果进行 投票。对于分类问题，以模型分类结果的众数类别作为最终 分类；对于预测问题，以多个模型预测的均值作为最终的预 测。事实上，多增加几组独立样本要考虑数据获取的成

28、本和可行 性；不同模型在投票中的同等的地位也过粗糙，而且也要考 虑模型预测精度。Boosting技术是解决上述问题的一处现实 有效的技术。1、建模阶段在建模过程中，Boosting技术通过对现有加权样 本的反复抽样以模拟增加样本集。整个过程需要K次迭代，或者说需要建立 K个模型。前面我们提到了一个选项“是否使用选区数据”，英文“Use Partition Data”，即模型会对数据 集抽样划分为训练样本集(Training Data)和检验样本集(Testing Data),前都用来学习训练，后者用为测试检验。由于C5.0的检验发生在 Training Data上，故Testing Data不 涉及检验。我们仍然使用分区数据，目的是为了在不同样本 集上建立模型，并测试其稳健性。使用Boosting技术建模时，第一次迭代每个样本被选入训练 样本集的概率或者说其权重相同。模型建立完毕，重新调整 各样本的权重，使它们进行第二次迭代，此次权重调整的原 则是：上次未能正确预测