决策树原理与应用：C5.0

机器学习AI算法工程

发布于 2018-03-13 11:17:29

4K0

发布于 2018-03-13 11:17:29

分类预测指通过向现有数据的学习，使模型具备对未来新数据的预测能力。对于分类预测有这样几个重要，一是此模型使用的方法是归纳和提炼，而不是演绎。非数据挖掘类的软件的基本原理往往是演绎，软件能通过一系列的运算，用已知的公式对数据进行运算或统计。分类预测的基本原理是归纳，是学习，是发现新知识和新规律；二是指导性学习。所谓指导性学习，指数据中包含的变量不仅有预测性变量，还有目标变量；三是学习，模型通过归纳而不断学习。

事实上，预测包含目标变量为连续型变量的预测和目标变量为分在变量的分类预测。两者虽然都是预测，但结合决策树算法和我们之前介绍过的时间序列算法知，二者还是有明显的差别的。

Clementine决策树的特点是数据分析能力出色，分析结果易于展示。决策树算法是应用非常广泛的分类预测算法。

1.1决策树算法概述

1.11什么是决策树

决策树算法属于有指导的学习，即原数据必须包含预测变量和目标变量。决策树之所以如此命名，是因为其分析结果以一棵倒置的树的形式呈现。决策树由上到下依次为根节点、内部节点和叶节点。一个节点对应于数据中的一个字段，即一个字段——即Question——对数据进行一次划分。决策树分为分类决策树（目标变量为分类型数值）和回归决策树（目标变量为连续型变量）。分类决策树叶节点所含样本中，其输出变量的众数就是分类结果；回归树的叶节点所含样本中，其输出变量的平均值就是预测结果。这一点需要格外注意。

与其它分类预测算法不同的是，决策树基于逻辑比较（即布尔比较）。可以简单描述为：If（条件1）Then（结果1）；If（条件2）Then（结果2）。这样，每一个叶节点都对应于一条布尔比较的推理规则，对新数据的预测就正是依靠这些复杂的推理规则。在实际应用中，一个数据产生的推理规则是极为庞大和复杂的，因此对推理规则的精简是需要关注的。

1.12决策树的几何理解

将训练样本集（即操作中常说的Training Data）看做一个n维空间上的一个点，则上面我们提到的布尔比较后的推理规则就像是存在于这个n维空间中的“线”。决策树建立的过程形象上看，就是倒置的树生长的过程，其几何意义上是，每个分枝（每条推理规则）完成对n维空间区域划分的过程。决策树正式生成，则n维空间正式划分完毕，则每一个小区域，代表一个叶节点。通常n维空间不易于理解，故采用倒置的树来表示此结果。

需要注意的一点是，在划分过程中，要尽量做到不同类别的结果归于不同的“区域”。

1.13决策树的核心问题：生成与修剪

决策树核心问题有二。一是利用Training Data完成决策树的生成过程；二是利用Testing Data完成对决策树的精简过程。即前面我们提到的，生成的推理规则往往过多，精简是必需的。

一、决策树的生长

决策树生长过程的本质是对Training Data反复分组（分枝）的过程，当数据分组（分枝）不再有意义——注意，什么叫分组不再有意义——时，决策树生成过程停止。因此，决策树生长的核心算法是确定数据分析的标准，即分枝标准。

何为有意义呢？注意，当决策树分枝后结果差异不再显著下降，则继续分组没有意义。也就是说，我们分组的目的，是为了让输出变量在差异上尽量小，到达叶节点时，不同叶节点上的输出变量为相同类别，或达到用户指定的决策树停止生成的标准。

这样，分枝准则涉及到两方面问题：1、如果从众多输入变量中选择最佳分组变量；2、如果从分组变量的众多取值中找到最佳分割点。不同的决策树算法，如C4.5、C5.0、Chaid、Quest、Cart采用了不同策略。

二、决策树的修剪

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

常用的修剪技术有预修剪（Pre-Pruning）和后修剪（Post-Pruning）。

Pre-Pruning可以事先指定决策树的最大深度，或最小样本量，以防止决策树过度生长。前提是用户对变量聚会有较为清晰的把握，且要反复尝试调整，否则无法给出一个合理值。注意，决策树生长过深无法预测新数据，生长过浅亦无法预测新数据。

Post-pruning是一个边修剪边检验的过程，即在决策树充分生长的基础上，设定一个允许的最大错误率，然后一边修剪子树，一边计算输出结果的精度或误差。当错误率高于最大值后，立即停止剪枝。

基于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用于生成多分支决策树，输入变量可以是分类型，也可以是数值型，输出变量为分类型。注意不同的决策树算法对输入和输出数据类型的要求。

正如1.1节提到的，决策树的核心问题之一是决策树分枝准则的确定。C5.0以信息增益率为标准确定最佳分组变量和最佳分割点。其核心概念是信息熵。

1.2.1信息熵和信息增益

一、信息熵

信息熵是信息论中的基本概念。信息论由Shannon于1948年提出并发展起来，用于解决信息传递过程中的问题，也称统计通信理论。它认为：

1、信息传递由信源、信道和信宿组成；

2、传递系统存在于一个随机干扰环境中，因此传递系统对信息的传递是随机误差的。如果把发送信息记为U而接收到信息记 V，由信道可记为通信模型，为P(U|V)。信道模型是一个条件概率矩阵P(U|V)。

信道模型可以看作是一个条件概率矩阵，信源也往往被理解为某种随机序列，也具有某种发生概率，且其概率求和为1。

在实际通信前，信宿信源会发出什么信息不可能知道，称为信宿对信源状态具有不确定性，由于这种不确定性是发生在通信之前的，故称为先验不确定性。在收到信息后的不确定性，称为后验不确定性。如果先验不确定性等于后验不确定性，则表示信息量为零；如果后验不确定性等于零，则表示信宿收到了信源的全部信息。可见：

信息是指对不确定性的消除。

信息量由消除的不确定性来确定。数据定义为：-Log2P(Ui)。信息量单位是bit，是以2为底的对数形式。信息熵是信息量的数学期望，其表示式由于过于复杂而不写。

如果P（U）差别越小，信息熵越大，平均不确定性越大；P(U)差别越在，信息熵越小，平均不确定性越小。如：信息熵等于0，则表示只存在一种信息发送可能，没有发送的不确定性。如果P(U）=1/K，即K个信源概率相同，则信息熵差别最大，不确定性最大。

二、信息增益

信息熵又称为先验熵，是在信息发送前信息量的数学期望；后验熵指在信息发送后，人信宿角度对信息量的数学期望。一般先验熵大于后验熵，先验熵与后验熵估差，即所谓的信息增益。信息增益，反映的是信息消除随机不确定性的程度。

2.2.2 C5.0的决策树生长算法

一、如何从众多的分组变量中选择一个最佳的分组变量

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

那么，如何评价数值型输入变量消除平均不确定性的能力呢？一般对其进行分箱处理，然后根据上述方法判定。分箱不采用了MDLP的熵分组方法，Clementine中C5.0节点本身包含了MDLP算法，它将自动完成数值型输入变量的分箱处理。

二、输入变量带有缺失值时如何选择最佳分组变量

C5.0在选择最佳分组变量时，通常将带有缺失值的样本当作临时剔除样本看待，并进行权数调整处理。

三、如何从分组变量的众多取值中找到一个最佳的分割点

在确定了最佳分组变量后，C5.0将继续确定最佳分组变量的分割点。

如果分组变量是分类型变量，由按分组变量的K个取值进行分组，形成K个分枝。

如果分组变量是数值型变量，则先通过MDLP分箱法或ChiMerge分箱法进行分箱处理，然后分组。

如果分组变量中存在缺失值，那怎么办呢？你无法判定此样本分到哪个组中去，C5.0的处理是将其分到所有组中去。但其权重不再为1，而为此组样本数占总样本数的比例。

2.2.3 C5.0的剪枝算法

C5.0采用Post-Pruning法从叶节点向上逐层剪枝，其关键是误差的估计及剪枝标准的设置。

一、误差估计

一般决策树的检验应该使用Testing Data，但C5.0使用了统计的置信区间的估计方法，直接在Training Data中估计误差。

二、剪枝标准

在得到误差的估计后，C5.0将按照“减少误差”判断是否剪枝。首先，计算待剪子树中叶节点的加权误差，然后与父节点的误差进行比较，如果大于则可以剪掉，否则不能剪掉。

2.2.4 C5.0的推理规则集

C5.0不有够构建决策树，同时还可以生成推理规则集。但是从决策树导入推理规则集非常烦锁，推理规则集通常有自己生成算法，即PRISM。该算法gf1987rh提出，是一种“覆盖”算法，对Training Data100%正确。

2.2.5 C5.0的基本应用示例

下面对一个使用了C5.0的挖掘案例进行介绍，这里不再像之前介绍案例似的步步介绍，现在只对重点部分进行介绍。主要是C5.0的面板设置及C5.0呈现的结果。下图为C5.0的面板设置。

模型名称：可以自动，亦可以自定义。在平时练习时默认自动即可，在商业活动中为避免重名或混乱，一律要自定义命名，这是数据挖掘的基本规范。

使用分区数据：英文Use Partitioned data。勾选表示利用Partition变量将样本集进行分割。但C5.0并不在Testing Data上进行模型检验，还需要Partition吗？需要，Partition的目的是比较同一模型在不同样本集上的稳健性。

输出类型：英文Output Type。Decision Tree表示得不到成决策树和由决策树得到的推理规则；Rule Set表示输出推理规则集，这个推理规则集并非由Decision Tree生成，而是由PRISM法生成的。这里首先输出决策树。

组符号：英文Group Symbolics。选中表示使用ChiMerge分箱法检查当前分组变量的各个类别能否合并，如果可以应先合并再分枝，此方法得到的Decision Tree相对精简。否则，对K个分类型分组变量将生成K叉树，对数值型分组变量将生成二叉树。

使用推进：英文Use Boosting。表示采用推进方法建立模型以提高模型预测的稳健性。

交叉验证：英文Cross-validate。表示将采用交叉验证的方法构建模型。

模式：英文Mode。决定决策树的剪枝策略。Simple表示系统自动调整参数值，此时支持选项中往往选择“精准性”，表示以预测精度做为修剪依据。此时默认置信度为0.75。Expert选项表示自行调整参数进行剪枝。

下图为选择Expert后的设置面板。在修剪严重性（Pruning Severity）中输入置信度，默认范围为0.25到1.在每个分支的最小纪录数中设置每个节点允许的最少样本量，亦可自行设置。

Clementine分别以文字和决策树图形的形式展示C5.0决策树的分析结果。打开结果页面得如下图。在“模型”面板中，展示了从决策树上直接获得的推理规则集。我们发现，在家长是否鼓励节点中，不鼓励的含30个样本，93.3%的选择不参加社会公益活动。在家长是否鼓励中鼓励的节点分支中，当在校综合测评小于等于48时，含15个样本且有0.8比例的为不参加公益活动，其余的为参加公益活动。在下面有“历史”“频数”的选项卡，点击可以查看每一条推理规则的具体信息。

三、预测结果

那么，我们如何预测结果呢？将新生成的数学模型“添加到流”，并添加到“类型”节点上，执行，得到我们的预测结果，如下图。在下图中新生成了两个字然，分别为“C-是否参与”与“CC-是否参与”。第一个字段表示的是从决策树上得到的预测分类值，符合相应的推理规则。第二个字段表示的是得到此预测结果的置信度。此置信度是相应规则的置信信经拉普拉斯估计器（Laplace Estimator）调整后的结果。Laplace Estimator是Laplace于18世纪发明的经典方法。注意，如果输出变量为数值型变量，不存在Laplace Estimator。C5.0的数值类型要求是：输入数据是分类型数据或数值型数据皆可，输出数据必须是分类型数据。

C5的损失矩阵和Boosting技术

一、损失矩阵

前面的分析有个缺点，即没有考虑商业上的损失问题。事实上，当我们使用Clementine对相关商业问题进行分析探讨时，做出的决策是要背负很大的商业期望的。如果预测失败，就要承担相当的损失。当然，我们说数据挖掘中误差是不可避免的，但显然，把可能出现的误差及其导致的损失反映出来，也是对商业客户的另外一种服务，也是极为重要的。本文将在前面探讨的基础上，引入实际的商业问题，不仅引入了损失矩阵，也引入了Boosting技术。

事实上，以二分问题为例，我们往往会选择那些置信低但损失小的决策，而不选择那些置信度高而损失高昂的决策，因为只有这样才可以有效地规避损失期望值。在分类预测问题中往往出现两类问题，一是实际为真却预测为假，我们称之为弃真错误；一是实际假却预测为真，我们称之为取伪。弃真取伪错误在传统的统计分析中也存在，典型的就是我们的假设检验。

损失矩阵是处理此类问题的有效手段，损失矩阵可以把可能导致的损失引入到系统分析过程，从而得出更加符合商业实际的结果。损失矩阵的用法一般分为两种，一是在数据建模阶段使用损失矩阵；一是在样本预测时使用损失矩阵。Clementine5.0采用的是第一种损失矩阵使用法，而不是第二种。

1、数据建模过程的损失矩阵。前面我介介绍到，在数据建模过程中涉及到修剪的过程，修剪时的标准是什么？是“Reduce-Error”，即当此节点层的Error大于其父节点的Error时，则修剪掉，否则不予以修剪。引入损失矩阵后，修剪方法由原先的“Reduce-Error”转变为“Reduce-Cost”法，即当叶节点的损失大于其父节点的损失时，则进行修剪，否则不予以修剪。

2、样本预测阶段。在前面介绍中，我们提到，新数据的预测由预测分类结果的众数给出，置信度也是一个重要的考量标准。加入损失矩阵的因素后，我们将结合某种分类预测的错判损失进行考量。这样，如果一种决策虽然有较高的置信水平而它的错判损失较大，我们宁可选择置信度较低而其错判较小的决策。

下图为C5.0中的损失矩阵设置页面，我们将弃真的错判损失自定义为1，而将取伪的错判损失自定义为2.这样得出的预测结果中，Yes的置信度都较高。

C5的损失矩阵和Boosting技术

一、损失矩阵

下图为C5.0中的损失矩阵设置页面，我们将弃真的错判损失自定义为1，而将取伪的错判损失自定义为2.这样得出的预测结果中，Yes的置信度都较高。

二、Boosting技术

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

事实上，多增加几组独立样本要考虑数据获取的成本和可行性；不同模型在投票中的同等的地位也过粗糙，而且也要考虑模型预测精度。Boosting技术是解决上述问题的一处现实有效的技术。

1、建模阶段

在建模过程中，Boosting技术通过对现有加权样本的反复抽样以模拟增加样本集。整个过程需要K次迭代，或者说需要建立K个模型。前面我们提到了一个选项“是否使用选区数据”，英文“Use Partition Data”，即模型会对数据集抽样划分为训练样本集（Training Data）和检验样本集（Testing Data），前都用来学习训练，后者用为测试检验。由于C5.0的检验发生在Training Data上，故Testing Data不涉及检验。我们仍然使用分区数据，目的是为了在不同样本集上建立模型，并测试其稳健性。

使用Boosting技术建模时，第一次迭代每个样本被选入训练样本集的概率或者说其权重相同。模型建立完毕，重新调整各样本的权重，使它们进行第二次迭代，此次权重调整的原则是：上次未能正确预测的样本权重增大，上次天确预测的样本权重减小。第三次迭代重复第二次迭代，以此类推。

其中，样本权重越大，其被选入训练样本集的可能性越大。

由于对预测结果模棱两可的样本往往位于边界处，故多次迭代后，边界处的样本权重显著性增大。

2、投票阶段

在投票阶段，我们手中已经拥有了经过K次迭代而产生的K个模型。Boosting采用加权投票方式，不同模型按其误差大小确定权重。误差大的权重小，误差小的权重大。权重大的对结果影响大，权重小的对结果影响小。这样经过K个模型的加权投票结果，是最为稳健的。

下图为使用Boosting技术后的结果页面，此次Bossting的迭代次数为5，在每个模型后面都有两个置信度。第一个是此模型的置信度，第二个为五个模型综合后的稳健置信度，即82.6%。每个样本的预测置信度列加客观和稳健，它是多个模型的投票结果。

C5.0的模型评价

C5.0的模型的决策树生长和修剪过程均发生在训练样本集（Training Data）中，那么它所建立的模型在其它样本集上是否有同样出色的表现呢。评价模型对检验样本集（Testing Data）的预测精度，并与训练样本集进行比较是一种最直接的方法。可通过Analysis节点实现上述功能，除此之外，Analysis还可以实现不同模型之间的评估对比。

下面，我们对Analysis设置面板进行理解。

按分区分割，英文Split By Partition。选中表示显示训练样本集和检验样本休的模型评估结果。

重合矩阵又称混淆矩阵，英文Coincidence Matrixes。选中表示输出混淆矩阵或称为生命矩阵，只适应于分类型输出变量。

置信度图，英文Confidnce Figures。选中表示输出有关预测置信度的评价结果。