一、基本流程决议树是一类常见的机械学习方法。以二分类为例，我们希望从给定训练数据集学得一个模型用以对新示例举行分类，这个把样天职类的任务，可看作对“当前样本属于这类吗？”这个问题的“决议”或“判断”历程。顾名思义，决议树是基于树结构来举行决议的，这恰是人类在面临决议问题时一种很自然的处置惩罚机制。

例如，我们要对“这是好瓜吗？”这样的问题举行决议时，通常会举行一系列的判断或“子决议”：我们先看“它是什么颜色？”,如果是“青绿色”，则我们再看“它的根蒂是什么形态？”，如果是“蜷缩”，我们再判断“它敲起来是什么声音？”，最后，我们得出最终决议：这是个好瓜。这个决议历程如下图所示。显然，决议历程的最终结论对应了我们希望的判断效果，例如“是”或“不是”好瓜；决议历程中提出的每个判断问题都是对某个属性的“测试”，例如“色泽=？”“根蒂=？”；每个测试效果或是导出最终结论，或是随处进一步的判断问题，其思量规模是在上次决议效果的限定规模之内，例如若在“色泽=青绿”之后判断“根蒂=？”，则仅在思量青绿色瓜的根蒂。

一般地，一棵决议树包罗一个根节点、若干个内部节点和若干个叶节点；叶节点对应于决议效果，其他每个节点则对应于一个属性测试；每个节点包罗的样本荟萃凭据属性测试的效果被划分到子结点中；根节点包罗样本全集。从根结点到每个叶结点的路径对应了一个判断测试序列。决议树学习的目的是为了发生一棵泛化能力强，即处置惩罚未见示例能力强的决议树，其基本流程遵循简朴且直观的“分而治之”计谋。

图1、决议树学习基本算法 显然，决议树的生成是一个递归历程。在决议树基本算法中，有三种情形会导致递归返回：（1）当前结点包罗的样本全属于同一种别，无需划分；（2）当前属性集为空，或是所有样本在所有属性上取值相同，无法划分；（3）当前结点包罗的样本荟萃为空，不能划分。在第（2）种情形下，我们把当前结点标志为叶节点，并将其种别设定该结点所含样本最多的种别。

在第（3）种情形下，同样把当前结点标志为叶节点，但将其种别设定为其父结点所含样本最多的种别。注意这两种情形的处置惩罚实质差别：情形（2）是在使用当前结点的后验漫衍，而情形（3）则是把父结点的样天职布作为当前结点的先验漫衍。

二、决议树的划分选择（信息增益、增益率、基尼指数）由图一可以看出，决议树学习的关键是如何选择最优划分属性（第8行）。一般而言，随着划分历程不停举行，我们希望决议树的分支结点所包罗的样本尽可能属于同一种别，即结点的“纯度”(purity)越来越高。2.1 信息增益：ID3，信息熵“信息熵”(information entropy)是怀抱样本荟萃纯度最常用的一种指标。

假定当前样本荟萃D种第k类样本所占的比例为(k=1,2,...,|y|)，则D的信息熵界说为：Ent(D)的值越小，则D的纯度越高。假定离散属性a有V个可能的取值{a1,a2,...,aV},若使用a来对样本集D举行划分，则会发生V个分支结点，其中第v个分支结点包罗了D中所有在属性a上取值为av的样本，记为Dv。我们可以凭据上式盘算出Dv的信息熵，再思量到差别的分支结点所包罗的样本数差别，给分支结点赋予权重|Dv|/|D|，即样本数越多的分支结点的影响越大，于是可盘算出用属性a对样本集D举行划分所获得的“信息增益”(information gain)。

一般而言，信息增益越大，则意味着使用属性a来举行划分所获得的“纯度提升”越大。因此，我们可以用信息增益来举行决议树的划分属性选择，著名的ID3决议树学习算法[Quinlan, 1986]就是以信息增益为准则来选择划分属性。以上表中的西瓜数据集为例，该数据集包罗17个训练样例，用以学习一棵能预测没有剖开的是不是好瓜的决议树。

显然，|y|=2。在决议树学习开始时，根结点包罗D中的所有样例，其中正例占,反例占。于是，凭据信息熵的盘算公式可盘算出根结点的信息熵为：然后，我们要盘算出当前属性荟萃{色泽、根蒂、敲声、纹理、脐部、触感}中每个属性的信息增益。

以属性“色泽”为例，它有3个可能的取值：{青绿、乌黑、浅白}。若使用该属性对D举行划分，则可以获得3个子集，划分记为：D1（色泽=青绿），D2(色泽=乌黑），D3（色泽=浅白）。

子集D1包罗编号为{1，4，6，10，13，17}的6个样例，其中正例(好瓜)占，反例（坏瓜）占；D2包罗的编号为{2,3,7,8,9,15}的6个样例，其中正、反例划分占，；D3包罗编号为{5,11,12,14,16}的5个样例，其中正、反样例划分占，。凭据信息熵公式可以盘算出用“色泽”划分之后所获得的3个分支结点的信息熵为：于是，凭据信息增益公式，可盘算出属性“色泽”的信息增益为：类似的，我们可以盘算出其他属性的信息增益：Gain(D,根蒂）=0.143；Gain(D,敲声)=0.141; Gain(D,纹理)=0.381;Gain(D,脐部)=0.289; Gain(D,触感)=0.006。显然，属性“纹理”的信息增益最大，于是它被选为划分属性。

下图给出了基于“纹理”对根结点举行划分的效果，各分支结点所包罗的样例子集显示在结点中。然后，决议树学习算法将每个分支结点做进一步划分。以上图中第一个分支结点（“纹理=清晰”）为例，该结点包罗的样例荟萃D1中有编号为{1,2,3,4,5,6,8,10,15}的9个样例，可用属性荟萃为{色泽，根蒂，敲声，脐部，触感}。

基于D1盘算出各属性的信息增益：Gain(D1,色泽）=0.043；Gain(D1,根蒂)=0.458；Gain(D1,敲声)=0.331;Gain(D1,脐部)=0.458; Gain(D1,触感)=0.458.“根蒂”、“脐部”、“触感”3个属性均取得了最大的信息增益，可任选其中之一作为划分属性。类似的，对每个分支结点举行上述操作，最终获得的决议树如下图所示：2.2 增益率：在上面的先容中，我们忽略了西瓜数据集表中“编号”这一列。若把“编号”也作为一个候选划分属性，则凭据信息增益公式可以盘算出它的信息增益为0.998，远大于其他候选划分属性。

这很容易明白：“编号”将发生17个分支，每个分支结点仅包罗一个样本，这些分支结点的纯度已到达最大。然而，这样的决议树显然不具有泛化能力（generalization），无法对新的样本举行有效预测。实际上，信息增益准则对可取值数目较多的属性有所偏好，为淘汰这种偏好可能带来的倒霉影响，C4.5决议树算法[Quinlan,1993]不直接使用信息增益，而是使用“增益率”（gain ratio）来选择最优划分属性。

其中：称为属性a的“固有值”（intrinsic value)[Quinlan,1993]。属性a的可能取值数据越多（即V越大），则IV(a)的值通常会越大。例如，对西瓜数据集，有IV（触感）=0.874（V=2），IV（色泽）=1.580（V=3），IV（编号）=4.088（V=17）。

需注意的是，增益率准则对可取值数目教少的属性有所偏好，因此，C4.5算法并不是直接选择增益率最大的候选划分属性，而是使用一个启发式：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。2.3 基尼指数：CART(Classification and Regression Tree)对每个叶节点里的数据分析其均值方差，当方差小于一定值可以终止破裂，以换取盘算成本的降低。CART决议树[Breiman et al.,1984]使用“基尼指数”(Gini index)来选择划分属性。

数据集D的纯度可用基尼值来怀抱：直观来说，Gini(D)反映了从数据集D中随机抽取两个样本，其种别标志纷歧致的概率。因此Gini(D)越小，则数据集D的纯度越高。

属性a的基尼指数界说为：于是我们在候选属性荟萃A中，选择谁人使得划分后基尼指数最小的属性作为最优划分属性，即三、剪枝处置惩罚（预剪枝、后剪枝）剪枝（pruning）是决议树学习算法敷衍“过拟合”的主要手段。在决议树学习中，为了尽可能正确分类训练样本，结点划分历程将不停重复，有时会造成决议树分支过多，这时就可能因训练样本学得“太好”了，以致于把训练集自身的一些特点看成所有数据都具有的一般性质而导致过拟合。因此，可通过主动去掉一些分支来降低过拟合的风险。

决议树剪枝的基本计谋有“预剪枝”(prepruning)和“后剪枝”(postpruning)[Quilan,1993]。预剪枝是指在决议树生成历程中，对每个结点在划分前先举行预计，若当前结点的划分不能带来决议树泛化性能提升，则停止划分并将当前结点标志为叶结点；后剪枝则是先从训练集生成一棵完整的决议树，然后自底向上地对非叶结点举行考察，若将该结点对应的子树替换为叶结点能带来决议树泛化性能提升，则将该子树替换为叶结点。如何判断决议树泛化性能是否提升呢？这里接纳留出法，即预留一部门数据用作“验证集”以举行性能评估。例如对刚刚用的西瓜数据集，我们将其随机划分为两部门，编号为{1，2，3，6，7，10，14，15，16，17}的样例组成训练集，编号为{4,5,8,9,11,12,13}的样例组成验证集。

接纳信息增益准则来举行划分属性选择，则从上表的训练集将会发生一棵如下图所示的决议树。图5 未剪枝决议树 图中玄色数字表现训练集的西瓜编号，加粗有颜色的数字代表的是测试集中的西瓜编号，其中绿色表现根据这个决议树预测出的效果正确的西瓜编号，红色表现分类错误。3.1 预剪枝基于之前讨论的信息增益准则，我们会选取属性“脐部”来对训练集举行划分，并发生3个分支，如图六所示。

然而，是否应该举行这个划分呢？预剪枝要对划分前后的泛化性能举行评估。在划分前，所有样例集中在根结点。若不举行划分，则该结点将被标志为叶结点，其种别标志为训练样例数最多的种别。

在训练集中，脐部凹陷的有{1，2，3，14}，其中好瓜占3/4，所以该叶结点标志为好瓜；脐部稍凹的有{6，7，15，17}，其中好瓜占1/2，周老师给它标志为好瓜，感受这也是书内里不严谨的地方；脐部平坦的有{10，16}，其中坏瓜占2/2，所以給该叶结点标志为坏瓜。如果用图五这个决议树来给验证集举行评估，可以看到{4，11，12}划分正确（图中绿色部门），而{5，9，8，13}划分错误（图中红色部门）。可是周老师认为编号{4,5,8}是正确的，所以周老师是不是搞错了，还是我搞错了。

不外验证集的精度是一样的为。图六预剪枝决议树 在仅用属性脐部划分之后，验证集中编号为{4，5，8，11，12}的样例被分类正确，验证集精度为。于是，用“脐部”举行划分得以确定。

然后，决议树算法应该对结点②举行划分，基于信息增益准则将挑选出划分属性“色泽”。然而，在使用“色泽”划分后，编号为{5}的验证集样天职类效果会由正确转为错误，使得验证集精度下降为。

于是，预剪枝计谋将静止结点②被划分。对结点③，最优划分属性为“根蒂”，划分后验证集精度仍为71.4%。这个划分不能提升验证集精度，于是，预剪枝计谋克制结点③被划分。

对结点④，其所含训练样例已属于同一类，不再举行划分。于是，基于预剪枝计谋，凭据西瓜数据集所生成的决议树如图六所示，其验证集精度为71.4%。这是一棵仅有一层划分的决议树，亦称“决议树桩”(decision stump)。

对比图五和图六，预剪枝使得决议树的许多分支都没有“展开”，这不仅降低了过拟合的风险，还显著淘汰了决议树的训练时间开销和测试时间开销。但另一方面，有些分支的当前归化虽不能提升泛化性能、甚至可能导致泛化性能暂时下降，但在其基础上举行的后续划分却有可能导致性能显著提高；预剪枝基于“贪心”本质克制这些分支展开，给预剪枝决议树带来了欠拟合的风险。3.2 后剪枝：后剪枝先从训练集生成一棵完整决议树，例如基于西瓜数据集获得图五所示的决议树。

易知，该决议树的验证集精度为42.9%。后剪枝首先考察图五的结点⑥。若将其领衔的分支剪除，则相当于把⑥替换为叶结点。替换后的叶结点包罗编号为{7，15}的训练样本，于是，该结点的种别标志为“好瓜”，此时决议树的验证集精度提高至57.1%。

于是，后剪枝计谋决议剪枝，如图七所示。然后考察结点⑤,若将其领衔的子树替换为叶结点，则替换后的叶结点包罗编号为{6，7，15}的训练样例，叶结点种别标志为“好瓜”，此时决议树验证集精度仍为57.1%。

于是，可以不举行剪枝。对结点②，若将其领衔的子树替换为叶结点，则替换后的叶结点包罗编号为{1，2，3，14}的训练样例，叶结点种别标志为“好瓜”。此时决议树的验证集精度提高至71.4%。

于是，后剪枝计谋决议剪枝。对结点③和①，若将其领衔的子树替换为叶结点，则所得决议树的验证集精度划分为71.4%与42.9%，均未获得提高。

于是他们被保留。最终，基于后剪枝计谋从西瓜数据集所发生的决议树如图七所示，其验证集精度为71.4%。对比图七和图六可以看出，后剪枝决议树通常比预剪枝决议树保留了更多的分支。

一般情形下，后剪枝决议树的欠拟合风险很小，泛化性能往往优先于预剪枝决议树，但后剪枝历程是在生成完全决议树之后举行的，而且要自底向上地对树中的所有非叶结点举行逐一考察，因此其训练时间开销比未剪枝决议树和预剪枝决议树都要大得多。关注gzh回复“机械学习”获得周老师的西瓜书。

本文来源：kb体育官方网站-www.ygyueda.cn