决策树原理详解（无基础的同样可以看懂）

一. 决策树简介

决策树（Decision Tree），它是一种以树形数据结构来展示决策规则和分类结果的模型，作为一种归纳学习算法，其重点是将看似无序、杂乱的已知数据，通过某种技术手段将它们转化成可以预测未知数据的树状模型，每一条从根结点（对最终分类结果贡献最大的属性）到叶子结点（最终分类结果）的路径都代表一条决策的规则。决策树就是形如下图的结构（机器学习西瓜书的图）：

二. 决策树的基本流程

话不多说，先看图

上图就是在生成决策树的过程中经历的步骤。

1. 首先从开始位置，将所有数据划分到一个节点，即根节点。
2. 然后经历橙色的两个步骤，橙色的表示判断条件：
   若数据为空集，跳出循环。如果该节点是根节点，返回null；如果该节点是中间节点，将该节点标记为训练数据中类别最多的类
   若样本都属于同一类，跳出循环，节点标记为该类别；
3. 如果经过橙色标记的判断条件都没有跳出循环，则考虑对该节点进行划分。既然是算法，则不能随意的进行划分，要讲究效率和精度，选择当前条件下的最优属性划分（什么是最优属性，这是决策树的重点，后面会详细解释）
4. 经历上步骤划分后，生成新的节点，然后循环判断条件，不断生成新的分支节点，直到所有节点都跳出循环。
5. 结束。这样便会生成一棵决策树。

三. 划分选择，寻找最优划分属性

在介绍决策树流程的时候提到了，寻找最优划分属性是决策树过程中的重点。那么如何在众多的属性中选择最优的呢。

3.1 信息增益

在介绍信息增益之前，先介绍一下信息熵的含义。我们理科生都学过化学，热力学里有一个熵的概念，熵就是来形容系统混乱程度的，系统越混乱，熵就越大。信息熵也具有同样的意义，不过它描述的是随机变量的不确定性（也就是混乱程度）。
假设某随机变量的概率分布为：

则它的信息熵计算公式为：

突然冒出这么一个公式你可能不适应。您可以这么理解：第一，这是大师们写出来的，肯定有道理；第二，它的值确实可以体现出随机变量的不确定性，且与我们理解的一致。
为了方便解释，我们用一个简单的便于观察的例子。下图是一个只有2个取值的随机变量，假如取值只有0和1，则P(X=0)=p,P(X=1)=1-p，其中p是x=0的概率。信息熵为H§=-plogp-(1-p)log(1-p)，我们画一个p在0-1的变过过程，H§随着变化的曲线：

由上图可以看出，当p=0.5的时候，H§达到最大值。因为p=0或p=1的时候，X只有一种可能性，也就是X是确定的，因此熵最小，而随着p接近0.5的过程中，变量X的不确定性就越来越大，我们计算出来的熵也是越来越大，与实际相符。
好了，信息熵的概念了解了，我们再与决策树的场景联系起来。我们先对样本大概的定义一下。就借鉴机器学习课本里的例子，样本属性有纹理、触感、色泽，其中每个属性有若干个可取值，比如纹理（清晰，稍糊，模糊），色泽（青绿，乌黑，浅白），触感（硬滑，软粘）。样本分类有两种，好瓜和坏瓜。
假如决策树样本集为D，经过某属性划分后，样本集划分v个子集，D1,D2,…,Dv。
我们先计算划分前D的信息熵（有的地方用Ent(D)，有的用H(D)，只是一个代表信息熵的符号，如果使用不严谨，请见谅）：

这里y=2，因为只有好瓜和坏瓜两种分类。pi表示第i类别的样本数占总样本数D的比例。
然后我们计算划分后的子样本集的信息熵

其中v是该属性的可取值的数量，比如划分属性为色泽，则v=3。Di表示该属性第i个值的样本数。相当于用色泽划分样本集D，样本集D中色泽=青绿的样本数。|Di|/|D|可以想象成一个权重。H(Di)的计算方法同计算H(D)的。
终于到了该介绍的概念：信息增益

很简单，就是划分前的信息熵减去划分后的信息熵。其中a代表的此次划分中所使用的属性。
如果决策树使用信息增益准则来选择最优划分属性的话，在划分前会针对每个属性都计算信息增益，选择能使得信息增益最大的属性作为最优划分属性。ID3算法就是使用的信息增益划分方法，决策树是一个基础理论，实际落地的算法有多种，ID3是其中一种。

3.2增益比

信息增益虽然在理论上可以找到最优的划分属性，但在某些情况下会存在问题。信息增益比较偏好可取值较多的属性，比如我们的样本有一个属性叫序号，每一个样本都具有一个单独的序号，因此使用序号划分后，每个子结点只有一个样本，熵为0。这样的话信息增益最大，算法就会以此属性作为最优划分属性。这显然与我们的意愿不同。因此引申出了增益比的思想。
可以这么说，增益比就是为了矫正信息增益偏好的问题。为了使算法不偏向可取值较多的属性。

其中

可以看出，增益比就是信息增益除以IV(a)，IV(a)是属性a的固有属性，当属性a可取值增多的时候，IV(a)一般也增大，因此在一定程度上能抑制信息增益偏好取值多的属性的特点，但是增益比偏好取值较少的属性。
算法C4.5是算法ID3的改进版，它使用了信息增益和增益比两种选择算法，先选出信息增益高于平均水平的属性，然后再在这些属性中选择增益比最高的，作为最优划分属性。这样综合了信息增益和增益比的优点，可以取得较好的效果。

3.3 基尼指数

基尼指数也是一个寻找最优划分属性的准则。公式如下：

通俗的可以这么理解，基尼指数就是在样本集中随机抽出两个样本不同类别的概率。当样本集越不纯的时候，这个概率也就越大，即基尼指数也越大。这个规律与信息熵的相同，还是以刚才的只有两个取值的随机变量为例，我们这次纵坐标除了有信息熵外，再加上基尼指数。

可以看出，基尼指数与信息熵虽然值不同，但是趋势一致。同样的，使用基尼指数来选择最优划分属性也是对比不同属性划分后基尼指数的差值，选择使样本集基尼指数减小最多的属性。

和信息增益计算方式类似，就是使用划分前样本集D的基尼指数减去划分后子样本集Di的基尼指数加权和。
著名的CART决策树就是使用基尼指数来作为划分准则。谈到这，顺便提一下CART决策树与ID3和C4.5的区别。

1. 划分准则不同，如刚才所说，CART决策树使用基尼指数。
2. ID3、C4.5划分时，一个节点可以划分为多个子结点，子结点数量根据属性可取值的数量决定。而CART决策树是严格的二叉树结构，就是说1个节点最多划分为2子结点。用下图可以浅显的解释
   
   这是ID3和C4.5可以生成的决策树，比如根节点根据属性（纹理）划分成了3个子结点。如果是CART决策树，它只能生成2个子结点，结果可能就是将红圈圈起的部分合并称为一个节点。你可能会问这样纹理模糊和稍糊的不就分不开了么，不用担心，如果分开效果更好的话，在该节点继续划分的时候就会将纹理的两个取值分开。因为同一个属性可以不只使用一次。

3.4 小结(1)

到这里我们的划分选择的几种方法就讲完了。我们可以看出，对于每种决策树算法，他们的基本流程是一样的。不同的是，虽然决策树基本流程中的每一步骤的目的一样，但不同算法实现的方式不同。

四. 剪枝处理

如果按照我们之前的方法形成决策树后，会存在一定的问题。决策树会无休止的生长，直到训练样本中所有样本都被划分到正确的分类。实际上训练样本中含有异常点，当决策树节点样本越少的时候，异常点就可能使得该结点划分错误。另外，我们的样本属性并不一定能完全代表分类的标准，可能有漏掉的特征，也可能有不准确的特征。这样就会导致决策树在训练集上准确率超高，但是在测试集上效果不好，模型过拟合，泛化能力弱。因此我们需要适当控制决策树的生长。
剪枝处理是防止决策树过拟合的有效手段。剪枝，其实就是把决策树里不该生长的枝叶剪掉，也就是不该划分的节点就不要继续划分了。剪枝分为“预剪枝”和“后剪枝”。两种操作在决策树生辰步骤的位置如下图：

预剪枝：在决策树生成过程中，对每个结点在划分前先进性估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点。它的位置在每一次生成分支节点前，先判断有没有必要生成，如没有必要，则停止划分。
后剪枝：先从训练集生成一棵完整的决策树（相当于结束位置），然后自底向上的对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点，相当于将子树剪去。值得注意的是，后剪枝时要用到一个测试数据集合，如果存在某个叶子剪去后能使得在测试集上的准确度或其他测度不降低（不变得更坏），则剪去该叶子。
理论上讲，后剪枝生成的决策树要比预剪枝生成的效果好，但是后剪枝在计算复杂度上比预剪枝高。

五. 特殊类型数据处理

5.1 连续值处理

我们之前使用的例子都是离散型数据，比如纹理（清晰，稍糊，模糊），色泽（青绿，乌黑，浅白），触感（硬滑，软粘），实际上我们的数据还有可能是连续值，比如西瓜的含糖率是0-1之间的连续值。这种情况下，属性的可取值无穷多，就无法直接划分节点，需要先将连续值离散化。
我们这里讲一下最简单的二分法策略对连续值进行处理，C4.5算法就是使用的这个方法，其他的算法等找到资料后我再补充到这里。
定义如下：
给定样本集D和连续属性a，假定a在D上出现了n个不同的取值，将这些值从小到大进行排序，记为{a1，a2,…,an}。基于划分点t可将D分为子集Dt-和Dt+，其中Dt-包含那些在属性a上取值不大于t的样本，而Dt+包含那些在属性a上取值大于t的样本。显然，对相邻的属性取值ai和ai+1来说，t在区间[ai,ai+1]中取任意值所产生的划分结果相同，我们就把区间[ai,ai+1]的中位点作为候选划分点好了。

这样我们就得到了n-1个候选划分点。
定义看着如此麻烦，其实很简单，比如属性a的取值为{1.2, 2, 4,6, 7.0}，我们选择两两值取中位数，就得到{(1.2+2)/2, (2+4.6)/2, (4.6+7.0)/2}三个候选点。（对于很多人来说我写的是啰嗦了点，我刚刚入门时看到定义就发蒙，可能会有和我一样的同志）

**【注意】**这里我们要注意一下，对于连续值的属性来说，离散化后再进行划分选择的过程不同。
离散化后，当选择最优划分属性时，对于该属性，并不是划分为候选点数量的子节点，而是选择其中一个候选点，将样本集D二分，小于候选点的分为一类，记为D-，另一类记为D+，然后计算信息增益。循环所有候选点后，选择信息增益最大的候选点来与其他属性带来的信息增益对比，如果该候选点带来的信息增益最大，就将该候选点所在属性作为最优划分属性，并以该候选点将原节点分为2个子节点。

上图是对于离散化后的属性计算信息增益的公式，最右侧的求和就是使用某个候选点将样本集2分后的加权信息熵。

**【注意】**另一个值得注意的是，对于连续值离散化的属性，在进行决策树生成的过程中可能不止使用1次。以下图为例

密度和含糖率都是连续属性，他们都被使用了两次。

5.2 缺失值处理

由于各种原因，我们得到的数据经常含有缺失值。当然如果一条样本缺失值太多，我们可以直接舍弃。但对于只缺失少量数据的样本，我们丢弃就有些可惜，尤其是对于不方便收集的数据样本。我们谈一下决策树算法中对于缺失值怎么处理的。
这里还是要放上公式（显得专业一些）。千万不要被这复杂的公式吓到，实际上意义超级简单。

有些符号在这里打不出来，我就把文字也截图了。
对属性a，ρ表示无缺失值的样本所占的比例，