统计学习方法笔记七----决策树

前言

　　决策树是通过一系列规则对数据进行分类的过程。它提供一种在什么条件下会得到什么值的类似规则（if-then）的方法。决策树分为分类树和回归树两种，分类数对离散变量做决策树，回归树对连续变量做决策树。本节主要讨论用于分类的决策树。
　　在分类问题中，表示基于特征对实例进行分类的过程。它可以认为是定义在特征空间与类空间上的条件概率分布。其主要优点是模型具有可读性，分类速度快。学习时，利用训练数据，根据损失函数最小化的原则建立决策树模型。预测时，对新的数据，利用决策树模型进行分类。
　　决策树适用于数值型和标称型（离散型数据，变量的结果只在有限目标集中取值），能够读取数据集合，提取一些列数据中蕴含的规则。在分类问题中使用决策树模型有很多的优点，决策树计算复杂度不高、便于使用、而且高效，决策树可处理具有不相关特征的数据、可很容易地构造出易于理解的规则，而规则通常易于解释和理解。决策树模型也有一些缺点，比如处理缺失数据时的困难、过度拟合以及忽略数据集中属性之间的相关性等。

决策树的定义

　　　决策树（decision tree）是一种树结构（可以是二叉树或者非二叉树）。每个非叶结点表示一个特征属性上的测试，每个分支代表这个特征属性在某个值域上的输出，而每个叶节点存放一个类别。使用决策树进行决策的过程就是从根节点开始，测试待分类项中相应的特征属性，并按照其值选择输出分支，直到到达叶子节点，将叶子节点存在的类别作为决策结果。

决策树的学习过程

　　　一棵决策树的生成过程主要分为以下三个部分：

• 特征选择： 特征选择是指从训练数据中众多的特征中选择一个特征作为当前节点的分裂标准，如何选择特征有着很多不同量化评估标准（比如，信息增益，信息增益比等），从而衍生出不同的决策树算法。
• 决策树的生成：根据选择的特征评估标准，从上至下递归的生成子节点，直到数据集不可分则停止生长。
• 剪枝： 决策树的生成容易造成过拟合，一般需要剪枝，来缩小树结构规模、缓解过拟合。剪枝技术有预剪枝和后剪枝两种。

分裂属性可以分为三种不同的情况:

1、属性是离散值并且不要求生成二叉决策树。此时用属性的每一个划分作为一个分支。
2、属性是离散值且要求生成二叉决策树。此时使用属性划分的一个子集进行测试，按照“属于此子集”和“不属于此子集”分成两个分支。
3、属性是连续的。此时确定一个值作为分裂点split_point，按照>split_point和<=split_point生成两个分支。

决策树学习本质上是从训练数据集中归纳出一组分类规则，与训练数据集不相矛盾的决策树（即能对训练数据进行正确分类的决策树）可能有多个，也可能一个也没有。我们需要的是一个与训练数据矛盾较小的决策树，同时具有很好的泛化能力。从另一个角度上看，决策树学习是由训练数据集估计条件概率模型。基于特征空间划分的类的条件概率模型有无穷多个。我们选择的条件概率模型应该不仅对训练数据有很好的拟合，而且对于未知数据有很好的预测。

决策树学习使用损失函数表示这一目标。如下所述：决策树学习的损失函数通常是正则化的极大似然函数。决策树学习的策略是以损失函数为目标函数的最小化。

当损失函数确定以后，学习问题就变成在损失函数意义下选择最优决策树的问题。因为从所有可能的决策树中选取最优决策树是NP完全问题，所以现实中决策树学习算法通常采用启发式方法。

如果特征数量很多，也可以在决策树学习开始的时候，对特征进行选择，只留下对训练数据有足够分类能力的特征。

由于决策树表示一个条件概率分布，所以深浅不同的决策树对应着不同复杂度的概率模型。决策树的生成对应于模型的局部选择，决策树的剪枝对应于模型的全局选择。决策树的生成只考虑局部最优，相对地，决策树的剪枝则考虑全局最优。

基于信息论的三种决策树算法

基于信息论的决策树算法有ID3、CART和C4.5等算法，其中C4.5和CART两种算法从ID3算法中衍生而来。

CART和C4.5支持数据特征为连续分布时的处理，主要通过使用二元切分来处理连续型变量，即求一个特定的值-分裂值：特征值大于分裂值就走左子树，或者就走右子树。这个分裂值的选取原则是使得划分后的子树中的“混乱程度”降低，具体到C4.5和CART算法则有不同的定义方式。

ID3算法中根据信息论的信息增益评估和选择特征，每次选择信息增益最大的特征做判断模块。ID3算法可用于划分标称型数据集，没有剪枝的过程，为了去除过度数据匹配的问题，可通过裁剪合并相邻的无法产生大量信息增益的叶子节点（例如设置信息增益阀值）。使用信息增益有一个缺点，那就是它偏向于具有大量值的属性–就是说在训练集中，某个属性所取的不同值的个数越多，那么越有可能拿它来作为分裂属性，而这样做有时候是没有意义的，另外ID3不能处理连续分布的数据特征，于是就有了C4.5算法。CART算法也支持连续分布的数据特征。

C4.5算法用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足;在树构造过程中进行剪枝；能够完成对连续属性的离散化处理；能够对不完整数据进行处理。C4.5算法产生的分类规则易于理解、准确率较高；但效率低，因树构造过程中，需要对数据集进行多次的顺序扫描和排序。也是因为必须多次数据集扫描，C4.5只适合于能够驻留于内存的数据集。

CART算法的全称是Classification And Regression Tree，采用的是Gini指数（选Gini指数最小的特征s）作为分裂标准,同时它也是包含后剪枝操作。ID3算法和C4.5算法虽然在对训练样本集的学习中可以尽可能多地挖掘信息，但其生成的决策树分支较大，规模较大。为了简化决策树的规模，提高生成决策树的效率，就出现了根据GINI系数来选择测试属性的决策树算法CART。

ID3

我们统计了14天的气象数据(指标包括outlook，temperature，humidity，windy)，并已知这些天气是否打球(play)。如果给出新一天的气象指标数据:sunny,cool,high,TRUE，判断一下会不会去打球。
我们利用ID3决策树方法来求解该问题：

ID3算法中根据信息论的信息增益评估和选择特征，每次选择信息增益最大的特征做判断模块。

构造树的基本想法是随着树深度的增加，节点的熵迅速地降低。熵降低的速度越快越好，这样我们就有望得到一颗高度最矮的决策树。

在没有给定任何天气信息时，根据历史数据，我们只知道新的一天打球的概率是9/14，不打的概率是5/14。此时的熵为：

属性有4个：outlook，temperature，humidity，windy。我们首先要决定哪个属性作树的根节点。

对每项指标分别统计：在不同的取值下打球和不打球的次数。

下面我们计算当已知变量outlook的值时的信息熵。

同理可得：

gain(outlook)最大（即outlook在第一步使系统的信息熵下降得最快），所以决策树的根节点就取outlook。

在本实例中，N2节点为“纯”的，都属于play=yes类；接下来要确定N1和N3取temperature、humidity还是windy?在已知outlook=sunny和outlook=rainy的情况，根据历史数据，我们作出类似table 2的一张表，分别计算gain(temperature)、gain(humidity)和gain(windy)，选最大者为N1和N3的划分属性。

依此类推，构造决策树。当系统的信息熵降为0时，就没有必要再往下构造决策树了，此时叶子节点都是纯的–这是理想情况。最坏的情况下，决策树的高度为属性（决策变量）的个数，叶子节点不纯（这意味着我们要以一定的概率来作出决策）。
最终的决策树如下：

C4.5

C4.5决策树在ID3决策树的基础之上稍作改进，其实就是把选择特征的方法由信息增益改成了信息增益比。

C4.5克服了ID3的2个缺点：
1、用信息增益选择属性的时候偏向于选择分支比较多的属性值，即取值多的属性。
2、不能处理连贯属性。

utlook和Windy取离散值，Temperature和Humidity则取连续值。

对于离散属性V，ID3中计算的是“信息增益”，C4.5中则计算“信息增益率”:

vj表示属性V的各种取值，在ID3中用信息增益选择属性时偏向于选择分枝比较多的属性值，即取值多的属性，在C4.5中由于除以了H(V)，可以削弱这种作用。

C4.5是如何处理连续属性的呢？实际上它先把连续属性转换为离散属性再进行处理。虽然本质上属性的取值是连续的，但对于有限的采样数据它是离散的，如果有N条样本，那么我们有N-1种离散化的方法：<=vj的分到左子树，>vj的分到右子树。计算这N-1种情况下最大的信息增益率。

在离散属性上只需要计算1次信息增益率，而在连续属性上却需要计算N-1次，计算量是相当大的。有办法可以减少计算量。对于连续属性先进行排序，只有在决策属性发生改变的地方才需要切开。
比如对temperature进行排序，本来有13种离散化的情况，现在只需要计算7种。

PS: 如果利用增益率来选择连续值属性的分界点会导致一些副作用！

分界点将样本分成数量相等的两个子集的时候（我们称此时的分界点为等分界点），增益率的抑制会被最大化，因为此等分分界点被过分抑制了。子集样本个数能够影响分界点，显然不合理。因此在决定分界点时还是采用信息增益这个指标，而在选择属性的时候才是用信息增益率这个指标。
这个改进能够很好得抑制连续值属性的倾向，当然还有其他方法也可以抑制这种倾向，比如MDL.

Tree-Growth终止的条件以及剪枝策略很多，在CART树中已讲了一些。每个叶子上都是“纯的”不见得就是好事，那样会过拟合。还有一个方法是叶子节点上覆盖的样本个数小于一个阈值时停止Tree-Growth。

在《CART树》中介绍了基于代价复杂性的剪枝法，剪枝的目的也是为了避免过拟合。

第一种方法，也是最简单的方法，称之为基于误判的剪枝。这个思路很直接，完全的决策树不是过拟合么，那么我就再搞一个测试数据集来纠正它。对于完全决策树中的每一个非叶子节点的子树，我们尝试着把它替换成一个叶子节点，该叶子节点的类别我们用子树所覆盖训练样本中存在最多的那个类来代替，这样就产生了一个简化决策树，然后比较这两个决策树在测试数据集中的表现，如果简化决策树在测试数据集中的错误比较少，并且该子树里面没有包含另一个类似特性的子树（所谓类似的特性，指的是把子树替换成叶子节点后，其测试数据集误判率降低的特征），那么该子树就可以替换成叶子节点。该算法以自下至上的方式遍历所有的子树，直至没有任何子树可以替换使得测试数据集的表现得以改进时，算法就可以终止。

第一种方法很直接，但是需要一个额外的测试数据集，能不能不要这个额外的数据集呢？为了解决这个问题，于是就提出了悲观剪枝，悲观剪枝就是递归的估计每个内部节点所覆盖样本节点的误判率。剪枝后该内部节点会变成一个叶子节点，该叶子节点的类别为原内部节点的最优子节点所决定，然后比较剪枝前后该节点的错误率来决定是否进行剪枝，该方法和前面提到的第一种方法思路是一致的，不同之处在于如何估计剪枝前分类树内部节点的错误率。

把一颗子树（具有多个叶子节点）的分类用一个叶子节点来替代的话，在训练集上的误判率肯定是上升的，但是在新数据上不一定。于是我们需要把子树的误判计算加上一个经验性的惩罚因子。对于一颗叶子结点，它覆盖了N个样本，其中有E个错误，那么该叶子节点的错误率为（E+0.5）/N，这个0.5就是惩罚因子，那么，一颗子树，它有L个叶子节点那么该子树的误判率为。这样的话，我们就可以看到一颗子树虽然具有多个子节点，但由于加上了惩罚因子，所以子树的误判率计算未必站到便宜。剪枝后内部节点变成子节点，其误判个数J也需要加上一个惩罚因子，变成J+0.5。那么子树是否可以被剪枝就取决于剪枝后的错误J+0.5在的标准误差内。对于样本的误差率e，我们可以根据经验把它估计成各种各样的分布模型，比如二项式分布，正态分布等。
那么一棵树错误分类一个样本值为1，正确分类一个样本值为0，该树错误分类的概率为e(e为分布的固有属性，可以通过统计出来)，那么树的误判次数就是伯努利分布，我们可以估计出该树的误判次数均值和标准差：

把子树替换成叶子节点后，该叶子节点的误判次数也是一个伯努利分布，其概率误判率为e=（E+0.5）/N，因此叶子节点的误判次数的均值为：

这里我们采用一种保守的分裂方案，即有足够大的置信度保证分裂后准确率比不分裂时的准确率高时才分裂，否则就不分裂（也就是应该剪枝）。如果要分裂（即不剪枝）至少要保证分裂后的误判数E(subtree_err_count)要小于不分裂误判数E（leaf_err_count），而且为了保证足够高的置信度，这里甚至要使得：

这里加了一个标准差可以有95%的置信度。
反之就是不分裂—-即剪枝的条件：

CART

这里质介绍CART是怎样用于分类的。

分类CART决策树是一颗二叉树，并且每个非叶子节点都有两个孩子，所以对于第一课子树其叶子节点数比非叶子节点数多1。

上例是属性有8个，每个属性又有多少离散的值可取。在决策树的每一个节点上我们可以按任一个属性的任一个值进行划分。比如最开始我们按：

1）表面覆盖为毛发和非毛发

2）表面覆盖为鳞片和非鳞片

3）体温为恒温和非恒温

等等产生当前节点的左右两个孩子。按哪种划分最好呢？有3个标准可以用来衡量划分的好坏：GINI指数、双化指数、有序双化指数。下面我们只讲GINI指数。

GINI指数

总体内包含的类别越杂乱，GINI指数就越大了（跟熵的概念很相似），比如体温为恒温时，包含哺乳类五个，鸟类2个，则：

体温为非恒温时包含爬行类3个、鱼类3个、两栖类2个,则:

所以如果按照“体温为恒温和非恒温”进行划分的话，我们得到GINI的增益（类比信息增益）：

最好的划分就是使得GINI_Gain最小的划分。

终止条件

一个节点产生左右孩子后，递归地对左右孩子进行划分即可产生分类回归树。这里的终止条件是什么？什么时候节点就可以停止分裂了？直观的情况，当节点包含的数据记录都属于同一个类别时就可以终止分裂了。这只是一个特例，更一般的情况我们计算χ2值来判断分类条件和类别的相关程度，当χ2很小时说明分类条件和类别是独立的，即按照该分类条件进行分类是没有道理的，此时节点停止分裂。注意这里的“分类条件”是指按照GINI_Gain最小原则得到的“分类条件”。

假如在构造分类回归树的第一步我们得到的“分类条件”是：体温为恒温和非恒温。此时：

哺乳类 爬行类 鱼类  鸟类  两栖类
恒温      5   0   0   2   0
非恒温     0   3   3   0   2

我在《独立性检验》中讲述了χ2的计算方法。当选定置信水平后查表可得“体温”与动物类别是否相互独立。

还有一种方式就是，如果某一分支覆盖的样本的个数如果小于一个阈值，那么也可产生叶子节点，从而终止Tree-Growth。

剪枝

当分类回归树划分得太细时，会对噪声数据产生过拟合作用。因此我们要通过剪枝来解决。剪枝又分为前剪枝和后剪枝：前剪枝是指在构造树的过程中就知道哪些节点可以剪掉，于是干脆不对这些节点进行分裂，在N皇后问题和背包问题中用的都是前剪枝，上面的χ2方法也可以认为是一种前剪枝；后剪枝是指构造出完整的决策树之后再来考查哪些子树可以剪掉。

在分类回归树中可以使用的后剪枝方法有多种，比如：代价复杂性剪枝、最小误差剪枝、悲观误差剪枝等等。这里我们只介绍代价复杂性剪枝法。

对于分类回归树中的每一个非叶子节点计算它的表面误差率增益值α。

比如有个非叶子节点T4如图所示：

已知所有的数据总共有60条，则节点t4的节点误差代价为：

子树的误差代价为：

以T4为跟节点的子树上叶子节点有3个，最终：

找到α值最小的非叶子节点，令其左右孩子为NULL。当多个非叶子节点的α值同时达到最小时，取最大的进行剪枝。

《完》

所谓的不平凡就是平凡的N次幂。
                        ----By Ada