<script type="text/javascript" src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=default"></script>
基本概念
决策树（decision tree）是一种常见的机器学习方法，它是基于树结构来进行决策的，这恰是人类在面临决策问题时一种很自然的处理机制。人类在对一个问题进行决策时，通常会进行一系列的“子决策”，最后得出最终决策。
它既可以作为分类算法，也可以作为回归算法，同时也特别适合集成学习比如随机森林。
先来了解一下决策树的基本流程：
这个例子中要根据房产、婚姻情况、年收入这三个特征（属性）对10个样本数据进行决策，判断一个人是否能够偿还债务，可以构建如下的决策树：
一般的，一棵决策树包含一个根结点、若干个内部结点和若干个叶结点。叶结点对应于最终决策结果（该例中为“可以偿还”和“无法偿还”），其他每个结点则对应于一个属性测试，根结点包含样本全集（该例中为“拥有房产”）。
决策树学习的目的是为了产生一颗泛化能力强，即处理未见事例能力强的决策树。
划分选择
决策树学习的难点，就是如何选择最优划分属性，特别是当特征比较多的时候，到底应该拿哪个特征当根结点呢？这就要求我们选取一个衡量标准。
热力学熵
熵最早来原于物理学，用于度量一个热力学系统的无序程度，可以测量一个粒子移动的自由程度。拿水的三态举例:
- 固态冰中的粒子活动空间较小，其结构比较稳固，粒子大都固定不动。
- 液态水的粒子结构稳固程度次之，粒子有一定的活动空间。
- 水蒸气的结构则处于另一个极端，一个粒子的去向有多种可能性，可经常移动。
因此，固态冰的熵很低，液态水的熵居中，水蒸气的熵最高。
信息熵
熵的概念也可以用概率解释，看下面这个例子：
上图的三个水桶中各有四个球，这些球除了颜色不一样，其它完全无法进行区分，因此，如果将这些小球全部放成一条直线，熵就是这些球移动的自由程度。
- 第一个桶的结构较为固定，无论如何摆放小球，它们总是处于同一状态，因此它的熵最低。
- 第二个桶中，我们有4种方式摆放小球，因此它的熵居中。
- 第三个桶中，有6中重组球的方法，因此其熵最高。
以上并不是熵最准确的定义，但它给我我们这样一个观点：集合越稳固或越具有同类性，其熵越低，反之亦然。
另一种看待熵的方式是依据知识，再来看水桶这个例子：
如果我们要从水桶中随机选出一个球，我们有多大可能知道球的颜色？
- 第一个桶中，我们知道该球的颜色必然是红色的，所以其知识较高。
- 第二个桶中，该球为红色的可能性很大，而为蓝色的可能性较小，若我们认定该球为红色，那绝大多数情况下，结果是对的，因此我们对该球的颜色的知识居中。
- 第三个桶中，该球颜色为红色和蓝色的可能性一样大，因此其知识较低。
结果显示，熵和知识相反，一个集合的知识越高，其熵越低，反之亦然。
现在还是回到上面这三个水桶，我们来玩个游戏，游戏规则是：我们重复地从桶中取出四个球，每次将球放回，尽量使取出的四个球的颜色与桶中起初的四个球的颜色一致。
举个例子，对第二个三红一蓝的水桶来说，若左边取出的四个小球的颜色和顺序与原来桶中一模一样，则该桶赢得比赛，反之，则输了比赛。
现在的问题是，若我们要赢得这个比赛，以上三个水桶哪个是最佳选择？
我们来计算一下每个水桶赢得比赛的概率，由于每次取小球都是相互独立的，我们可以计算出：
P(1)=1\times1\times1\times1=1
P(2)=\frac{3}{4}\times\frac{3}{4}\times\frac{3}{4}\times\frac{1}{4}=0.105
P(3)=\frac{1}{2}\times\frac{1}{2}\times\frac{1}{2}\times\frac{1}{2}=0.0625
因此，第一个水桶赢得比赛的概率最高，第二个次之，第三个最低。
当有1000个小球时，概率的计算结果有可能会非常小，而且稍微改变其中一个因素，就会对最后的积产生极大的影响，为了使得结果更加可控，我们采用log函数将积转换为和（信息论中采用底数为2的对数函数）。
-\log_2{P(1)}=-(\log_2{1}+\log_2{1}+\log_2{1}+\log_2{1})=0
-\log_2{P(2)}=-(\log_2{0.75}+\log_2{0.75}+\log_2{0.75}+\log_2{0.25})=3.245
-\log_2{P(3)}=-(\log_2{0.5}+\log_2{0.5}+\log_2{0.5}+\log_2{0.5})=4
使用熵的定义为以我们赢得游戏的方式取出球的概率的对数的平均值，因此，第一个水桶的熵为0，第二个水桶的熵为0.81，第三个水桶的熵为1。
假设第4个水桶中有5个红球和3个篮球：
计算这个水桶的熵：
Entropy=-\frac{5}{8}\log_2\left(\frac{5}{8}\right)-\frac{3}{8}\log_2\left(\frac{3}{8}\right)=0.9544
当有m个红球和n个蓝球：
Entropy=-\frac{m}{m+n}\log_2\left(\frac{m}{m+n}\right)-\frac{n}{m+n}\log_2\left(\frac{n}{m+n}\right)
信息熵（information entropy）是度量样本集合纯度最常用的一种指标，假定当前样本集合D中第k类样本所占的比例为p_k(k=1,2,...,|y|)，则D的信息熵定义为：
Ent(D)=-\sum_{k=1}^{|y|}p_k\log_2p_k
Ent(D)的值越小，样本集合D的纯度越高，越具有同类性。
决策树ID3算法
信息增益计算方法：
information \ gain=Entropy(parent)-0.5\left[Entropy(child1)+Entropy(child2)\right]
根据信息熵公式，我们可以计算：
Entropy(parent)=-\frac{10}{20}\log_2\left(\frac{10}{20}\right)-\frac{10}{20}\log_2\left(\frac{10}{20}\right)=1
Entropy(child1)=-\frac{2}{10}\log_2\left(\frac{2}{10}\right)-\frac{8}{10}\log_2\left(\frac{8}{10}\right)=0.72
Entropy(child2)=-\frac{8}{10}\log_2\left(\frac{8}{10}\right)-\frac{2}{10}\log_2\left(\frac{2}{10}\right)=0.72
information \ gain=1-0.72=0.28
假定离散属性a有V个可能的取值\{a^1, a^2, ...,a^V\}，若使用a来对样本集合D进行划分，则会产生V个分支结点，可以根据信息熵公式计算出每个分支结点的信息熵，考虑到不同分支结点所包含的样本数的不同，给分支结点赋予权重\frac{|D^v|}{|D|}，于是可以计算出用属性a对样本集D进行划分所获得的信息增益：
Gain(D,a)=Ent(D)-\sum_{v=1}^{V}\frac{|D^v|}{|D|}Ent(D^v)
一般而言，信息增益越大，则意味着使用属性a来进行划分所获得的“纯度提升”越大。因此，在进行决策树的划分属性选择时，选择属性a_* =\underset{a\in A}{\operatorname{argmax} }Gain(D,a)，著名的ID3决策树学习算法[Quinlan,1986]就是以信息增益为准则来选择划分属性。
下面我们看看具体算法过程大概是怎么样的。
假设输入的是m个样本，样本输出集合为D，每个样本有n个离散特征，特征集合即为A，输出为决策树T，算法的过程为：
- 初始化信息增益的阈ϵ。
- 判断样本是否为同一类输出D_i，如果是则返回单节点树T，标记类别为D_i。
- 判断特征是否为空，如果是则返回单节点树T，标记类别为样本中输出类别D实例数最多的类别。
- 计算特征集合A中的各个特征（一共n个）对输出D的信息增益，选择信息增益最大的特征A_g
- 如果A_g的信息增益小于阈值ϵ，则返回单节点树T，标记类别为样本中输出类别D实例数最多的类别。
- 否则，按特征A_g的不同取值A_{gi}将对应的样本输出D分成不同的类别Di，每个类别产生一个子节点，对应特征值为 A_{gi}，返回增加了节点的树T。
- 对于所有的子节点，令D=D_i , A=A-\{A_g\}递归调用2-6步，得到子树Ti并返回。
决策树ID3算法的不足
ID3算法虽然提出了新思路，但是还是有很多值得改进的地方：
- ID3没有考虑连续特征，比如长度、密度都是连续值，无法在ID3运用，这大大限制了ID3的用途。
- ID3采用信息增益大的特征优先建立决策树的节点，但信息增益准则对可取值数目较多的属性有所偏好。
- 算法对于缺失值的情况没有做考虑。
- 没有考虑过拟合的问题。
决策树C4.5算法
ID3 算法的作者昆兰基于上述不足，对ID3算法做了改进，这就是C4.5算法[Quinlan,1993]，针对上述的第二个问题，它使用“增益率”（gain ratio）来选择最后划分属性，其定义为：
Gain\_ratio(D,a)=\frac{Gain(D,a)}{IV(a)}
其中，IV(a)称为属性a的“固有值”（intrinsic value），其定义为：
IV(a)=-\sum_{v=1}^{V}\frac{|D^v|}{|D|}\log_2\frac{|D^v|}{|D|}
属性a的可能取值数目越多，则IV(a)的值通常会越大。
需要注意的是，增益率准则对可取数值数目较少的属性有所偏好，因此，C4.5算法并不是直接选择增益率最大的候选划分属性，而是先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。
针对上述第一个问题，不能处理连续特征，C4.5的思路是采用二分法（bi-partition）将连续的特征离散化。比如m个样本的连续特征A有m个，从小到大排列为a_1,a_2,...,a_m,则C4.5取相邻两样本值的平均数，一共取得m-1个划分点，其中第i个划分点T_i表示为：T_i=\frac{a_i + a_{i+1}}{2}。对于这m-1个点，分别计算以该点作为二元分类点时的信息增益，选择信息增益最大的点作为该连续特征的二元离散分类点。
要注意的是，与离散属性不同的是，如果当前节点为连续属性，则该属性后面还可以参与子节点的产生选择过程。
对于第三个缺失值处理的问题，主要需要解决的是两个问题，一是在样本某些特征缺失的情况下选择划分的属性；二是选定了划分属性，对于在该属性上缺失特征的样本的处理。
对于第一个子问题，对于某一个有缺失特征值的特征A ，C4.5的思路是将数据分成两部分，对每个样本设置一个权重（初始可以都为1），然后划分数据，一部分是有特征值A的数据D_1，另一部分是没有特征A的数据D_2。然后对于没有缺失特征A的数据集D_1来和对应的A特征的各个特征值一起计算加权重后的增益率
，最后乘上一个系数，这个系数是无特征A缺失的样本加权后所占加权总样本的比例。
对于第二个子问题，可以将缺失特征的样本同时划分入所有的子节点，不过将该样本的权重按各个子节点样本的数量比例来分配。比如缺失特征A的样本a之前权重为1，特征A有3个特征值A_1 ,A_2,A_3，3个特征值对应的无缺失A特征的样本个数为2,3,4，则a同时划分入A_1,A_2,A_3，对应权重调节为\frac{2}{9},\frac{3}{9},\frac{4}{9}。
对于第4个问题，C4.5引入了正则化系数进行初步的剪枝。
除了上面的4点，C4.5和ID3的思路区别不大。
C5.0是 Quinlan 根据专有许可证发布的最新版本，它使用更少的内存，并建立比 C4.5 更小的规则集，同时更准确。
决策树C4.5算法的不足
C4.5虽然改进或者改善了ID3算法的几个主要的问题，仍然有优化的空间：
- 由于决策树算法非常容易过拟合，因此对于生成的决策树必须要进行剪枝。剪枝的算法有非常多，C4.5的剪枝方法有优化的空间。
- C4.5生成的是多叉树，即一个父节点可以有多个节点。很多时候，在计算机中二叉树模型会比多叉树运算效率高。如果采用二叉树，可以提高效率。
- C4.5只能用于分类，如果能将决策树用于回归的话可以扩大它的使用范围。
- C4.5由于使用了熵模型，里面有大量的耗时的对数运算，如果是连续值还有大量的排序运算。如果能够加以模型简化可以减少运算强度但又不牺牲太多准确性的话，那就更好了。
决策树CART算法
CART（Classification and Regression Trees （分类和回归树））与 C4.5 非常相似，但它不同之处在于它支持数值目标变量（回归），并且不计算规则集。
CART决策树采用“基尼指数”（Gini index）来选择划分属性，其定义为：
Gini(D)=\sum_{k=1}^{|y|}\sum_{k'\neq{1}}p_kp_{k'}=1-\sum_{k=1}^{|y|}p_k^2
Gini(D)越小，则数据集的纯度越高。
属性a的基尼指数定义为：
Gini\_index(D,a)=\sum_{v=1}^{V}\frac{|D^v|}{|D|}Gini(D^v)
在候选属性集合中，选择使得划分后基尼指数最小的属性作为最优划分属性。
同时，为了进一步简化，CART分类树算法每次仅仅对某个特征的值进行二分，而不是多分，这样CART分类树算法建立起来的是二叉树，而不是多叉树。这样一可以进一步简化基尼系数的计算，二可以建立一个更加优雅的二叉树模型，比如：
如果某个特征A被选取建立决策树节点，如果它有A_1,A_2,A_3三种类别，CART分类树会考虑把A分成\{A_1\}和\{A_2,A_3\}, \{A_2\}和\{A_1,A_3\}, \{A_3\}和\{A_1,A_2\}三种情况，找到基尼系数最小的组合，比如\{A_2\}和\{A_1,A_3\},然后建立二叉树节点，一个节点是A_2对应的样本，另一个节点是\{A_1,A_3\}对应的节点。
CART采用后剪枝法进行剪枝（pruning），即先生成决策树，然后产生所有可能的剪枝后的CART树，然后使用交叉验证来检验各种剪枝的效果，选择泛化能力最好的剪枝策略。
决策树CART算法的不足
- 无论是ID3, C4.5还是CART，在做特征选择的时候都是选择最优的一个特征来做分类决策，所形成的分类边界的每一段都是与坐标轴平行的，当学习任务的真实分类边界比较复杂时，必须使用很多段划分才能获得较好的近似，此时预测时间开销会很大。使用多变量决策树(multi-variate decision tree)可大大简化模型，它在学习过程中，不是为每个非叶结点寻找一个最优划分属性，而是试图建立一个合适的线性分类器。主要算法有OC1。
- 如果样本发生一点点的改动，就会导致树结构的剧烈改变。这个可以通过集成学习里面的随机森林之类的方法解决。
决策树算法小结
下表给出了ID3，C4.5和CART的一个比较：
| 算法 | 支持模型 | 树结构 | 特征选择 | 连续值处理 | 缺失值处理 | 剪枝 |
|---|---|---|---|---|---|---|
| ID3 | 分类 | 多叉树 | 信息增益 | 不支持 | 不支持 | 不支持 |
| C4.5 | 分类 | 多叉树 | 信息增益比 | 支持 | 支持 | 支持 |
| CART | 分类，回归 | 二叉树 | 基尼系数，均方差 | 支持 | 支持 | 支持 |
决策树算法优点：
- 简单直观，在逻辑上可以得到很好的解释。
- 训练需要的数据少，基本不需要预处理，不需要提前归一化、处理缺失值。
- 使用决策树预测的代价是O(log_2m)，m为样本数。
- 既可以处理离散值也可以处理连续值。
- 可以处理多维度输出的分类问题。
- 可以交叉验证的剪枝来选择模型，从而提高泛化能力。
- 对于异常点的容错能力好，健壮性高。
决策树算法缺点：
- 决策树算法非常容易过拟合，导致泛化能力不强。这个问题可以通过剪枝、设置节点最少样本数量和限制决策树深度来改进。
- 决策树可能是不稳定的，因为数据中的微小变化可能会导致完全不同的树生成。这个问题可以通过集成学习之类的方法解决。
- 在多方面性能最优和简单化概念的要求下，学习一棵最优决策树通常是一个NP难问题。因此，实际的决策树学习算法是基于启发式算法，例如在每个节点进 行局部最优决策的贪心算法。这样的算法不能保证返回全局最优决策树。这个问题可以通过集成学习来训练多棵决策树来缓解，这多棵决策树一般通过对特征和样本有放回的随机采样来生成。
- 有些比较复杂的关系，决策树很难学习，比如异或 ，一般这种关系可以换神经网络分类方法来解决。
- 如果某些类在问题中占主导地位会使得创建的决策树有偏差。因此，建议在拟合前先对数据集进行平衡。
Reference:
[1]周志华.机器学习[M].北京：清华大学出版社，2016：73-95.
[2]http://sklearn.apachecn.org/cn/latest/modules/tree.html#tree-algorithms.
[3]http://www.cnblogs.com/pinard/p/6050306.html.
[4]http://www.cnblogs.com/pinard/p/6053344.html.
[5]https://www.cnblogs.com/nowgood/p/Latexstart.html.
