「决策树算法」带你搞懂决策树算法原理

决策树算法

一、决策树是什么？

顾名思义，决策树是由一个个“决策”组成的树，学过数据结构的同学对树一定不陌生。决策树中，结点分为两种，放“决策依据”的是非叶结点，放“决策结果”的是叶结点。

那么决策是什么呢？很好理解，和人一样，决策就是对于一个问题，有多个答案，选择答案的过程就是决策。在决策树中，通常有两种类型的问题，一种是离散值的问题，一种是连续值的问题。拿选一个好西瓜来比喻，西瓜的纹路是清晰的、稍稍模糊的、还是很模糊的，这是一个离散值的问题，西瓜的密度（质量与体积的比值）是个连续值的问题。决策树就是由一个个的问题与答案生成的。　　

决策树实际上是一个if-then规则的集合。还是拿西瓜问题举例，拿到一个西瓜，先判断它的纹路，如果很模糊，就认为这不是好瓜，如果它清晰，就认为它是一个好瓜，如果它稍稍模糊，就考虑它的密度，密度大于某个值，就认为它是好瓜，否则就是坏瓜。

二、如何生成决策树？

1.经典的ID3算法

熵是描述信息的不确定度的，是随机变量不确定度的度量。公式是这样的：

H(D)=−∑k=1K|Ck||D|log2|Ck||D|" role="presentation" style="position: relative;"> $H (D) = - \sum_{k = 1}^{K} \frac{| C_{k} |}{| D |} l o g_{2} \frac{| C_{k} |}{| D |}$

其中， |Ck|" role="presentation" style="position: relative;"> $| C_{k} |$ 是 D" role="presentation" style="position: relative;"> $D$ 中属于 Ck" role="presentation" style="position: relative;"> $C_{k}$ 类的样本数， |D|" role="presentation" style="position: relative;"> $| D |$ 是样本总数。熵越大，信息的不确定度越大，信息越“混乱”，越不符合决策树分类的需求。所以，我们奔着减小熵的目标来选择分类的依据和分类的结果。

为了衡量熵的变化，我们引入信息增益的概念。公式是这样的：

H(D|A)=−∑i=1N|Di|D∑k=1K|Dik||Di|log2|Dik||Di|" role="presentation" style="position: relative;"> $H (D | A) = - \sum_{i = 1}^{N} \frac{| D_{i} |}{D} \sum_{k = 1}^{K} \frac{| D_{i k} |}{| D_{i} |} l o g_{2} \frac{| D_{i k} |}{| D_{i} |}$

g(D,A)=H(D)−H(D|A)" role="presentation" style="position: relative;"> $g (D, A) = H (D) - H (D | A)$

其中，根据特征A将样本划分为N个子集，D1,D2,⋯,DN" role="presentation" style="position: relative;"> $D_{1}, D_{2}, \dots, D_{N}$ ， |Di|" role="presentation" style="position: relative;"> $| D_{i} |$ 是子集 Di" role="presentation" style="position: relative;"> $D_{i}$ 的样本数，|Dik|" role="presentation" style="position: relative;"> $| D_{i k} |$ 是子集中属于 Ck" role="presentation" style="position: relative;"> $C_{k}$ 类的样本数

信息增益的含义就是在选定特征A之后，数据的不确定度的下降。信息增益越大，意味着这个特征分类的能力越强，我们就要优先选择这个特征。　　

选择信息增益最大的特征，根据它的属性划分该结点。如果一个子结点中只有一个分类的样本，那么这个结点就不需要再分，这个叶结点的类别就是这个分类的类别；如果所有的特征都已经参与过分类，那么决策树也不需要往下生成，样本数最多的类别就是叶结点的类别。

ID3算法的局限性

（1）不支持连续特征

（2）采用信息增益大的特征优先建立决策树的节点。在相同条件下，取值比较多的特征比取值少的特征信息增益大。

（3）不支持缺失值处理

（4）没有应对过拟合的策略

2. 改进的C4.5算法

C4.5与ID3针对ID3的四个局限性进行了改进

连续特征：C4.5的思路是将连续的特征离散化。比如m个样本的连续特征A的取值有m个，从小到大排列为a1,a2,⋯,am" role="presentation" style="position: relative;"> $a_{1}, a_{2}, \dots, a_{m}$ ,取相邻两个取值的平均值作为划分点，一共有m-1个划分点，分别计算以这些点作为二元分类点时的信息增益比。要注意的是，与离散属性不同的是，如果当前节点为连续属性，则该属性后面还可以参与子节点的产生选择过程。

信息增益：由于信息增益偏向于取值比较多的特征，所以C4.5引入了信息增益比,n是特征A的取值个数

gR(D,A)=g(D,A)HA(D)" role="presentation" style="position: relative;"> $g_{R} (D, A) = \frac{g (D, A)}{H_{A} (D)}$

HA(D)=−∑i=1n|Di||D|log2|Di||D|" role="presentation" style="position: relative;"> $H_{A} (D) = - \sum_{i = 1}^{n} \frac{| D_{i} |}{| D |} l o g_{2} \frac{| D_{i} |}{| D |}$

其中 A" role="presentation" style="position: relative;"> $A$ 为样本特征，HA(D)" role="presentation" style="position: relative;"> $H_{A} (D)$ 为特征熵，Di" role="presentation" style="position: relative;"> $D_{i}$ 为特征 A" role="presentation" style="position: relative;"> $A$ 第 i" role="presentation" style="position: relative;"> $i$ 个取值对应的样本个数

缺失值：对于缺失值处理的问题，一是如何在属性值缺失的情况下进行划分属性选择，二是给定划分属性，如果样本在该属性上缺失，如何对样本进行划分

第一个问题，对于某一个有缺失特征值的特征A。C4.5的思路是将数据分成两部分，对每个样本设置一个权重（初始可以都为1），然后划分数据，一部分是有特征值 A" role="presentation" style="position: relative;"> $A$ 的数据 D1" role="presentation" style="position: relative;"> $D_{1}$ ，另一部分是没有特征 A" role="presentation" style="position: relative;"> $A$ 的数据 D2" role="presentation" style="position: relative;"> $D_{2}$ 。然后对于没有缺失特征 A" role="presentation" style="position: relative;"> $A$ 的数据集 D1" role="presentation" style="position: relative;"> $D_{1}$ 来和对应的 A" role="presentation" style="position: relative;"> $A$ 特征的各个特征值一起计算加权重后的信息增益比，最后乘上一个系数，这个系数是无特征 A" role="presentation" style="position: relative;"> $A$ 缺失的样本加权后所占加权总样本的比例。

第二个问题，可以将缺失特征的样本同时划分入所有的子节点，且在与属性值对应的的子结点中调整样本权值。比如缺失特征 A" role="presentation" style="position: relative;"> $A$ 的样本 a" role="presentation" style="position: relative;"> $a$ 之前权重为1，特征 A" role="presentation" style="position: relative;"> $A$ 有3个特征值 A1,A2,A3" role="presentation" style="position: relative;"> $A_{1}, A_{2}, A_{3}$ 。 3个特征值对应的无缺失A特征的样本个数为2,3,4.则 a" role="presentation" style="position: relative;"> $a$ 同时划分入A1,A2,A3" role="presentation" style="position: relative;"> $A_{1}, A_{2}, A_{3}$ 。对应权重调节为2/9, 3/9, 4/9。这实际上是让同一个样本已不同的概率划入到不同的子结点中。

过拟合策略：C4.5引入了正则化系数进行剪枝（下面有详细描述）

C4.5的局限性

（1）剪枝的算法有非常多，C4.5的剪枝方法有优化的空间

（2）C4.5生成的是多叉树，很多时候，在计算机中二叉树模型会比多叉树运算效率高。如果采用二叉树，可以提高效率

（3）C4.5只能用于分类

（4）C4.5使用了熵模型，里面有大量的耗时的对数运算,如果是连续值还有大量的排序运算

3. 强大的CART算法

CART树里面对C4.5中存在的问题进行了改进。CART假设决策树是二叉树，并且可以分类也可以回归，而且用基尼指数代替了熵模型进行特征选择，也提供了优化的剪枝策略。

3.1 回归树：划分的准则是平方误差最小化

step1:对于当前节点的数据集为D，如果样本个数小于阈值或者没有特征，则返回决策子树，当前节点停止递归。

step2:计算样本集D的平方误差，如果平方误差小于阈值，则返回决策树子树，当前节点停止递归。

step3:选择最优切分变量 j" role="presentation" style="position: relative;"> $j$ 和切分点 s" role="presentation" style="position: relative;"> $s$ ，具体操作是求解使

minj,s[minc1∑xi∈R1(j,s)(yi−ci)2+minc2∑xi∈R2(j,s)(yi−ci)2]" role="presentation" style="position: relative;"> $m i n_{j, s} [m i n_{c_{1}} \sum_{x_{i} \in R_{1} (j, s)} (y_{i} - c_{i})^{2} + m i n_{c_{2}} \sum_{x_{i} \in R_{2} (j, s)} (y_{i} - c_{i})^{2}]$

最小的对 (j,s)" role="presentation" style="position: relative;"> $(j, s)$

step4:用选定的 (j,s)" role="presentation" style="position: relative;"> $(j, s)$ 划分，并决定相应的输出值 c" role="presentation" style="position: relative;"> $c$

R1(j,s)={x|x(j)≤s}" role="presentation" style="position: relative;"> $R_{1} (j, s) = {x | x^{(j)} \leq s}$

R2(j,s)={x|x(j)" role="presentation" style="position: relative;"> $R_{2} (j, s) = {x | x^{(j)}$ > s}" role="presentation" style="position: relative;"> $s}$

c^m=1Nm∑xi∈Rm(j,s)yi,x∈Rm,m=1,2" role="presentation" style="position: relative;"> ${\hat{c}}_{m} = \frac{1}{N_{m}} \sum_{x_{i} \in R_{m} (j, s)} y_{i}, x \in R_{m}, m = 1, 2$

step5:对左右子结点调用step1-4直到满足停止条件

f(x)=∑m=1Mc^mI(x∈Rm)" role="presentation" style="position: relative;"> $f (x) = \sum_{m = 1}^{M} {\hat{c}}_{m} I (x \in R_{m})$

3.2 分类树:划分的准则是基尼指数最小化

step1:对于当前节点的数据集为D，如果样本个数小于阈值或者没有特征，则返回决策子树，当前节点停止递归。

step2:计算样本集D的基尼系数，如果基尼系数小于阈值，则返回决策树子树，当前节点停止递归。

step3:对每个特征A，对其可能的每个取值a，根据样本点对A=a" role="presentation" style="position: relative;"> $A = a$ 的测试为“是”或者“否”将 D" role="presentation" style="position: relative;"> $D$ 分割成D1,D2" role="presentation" style="position: relative;"> $D_{1}, D_{2}$ ，利用

Gini(D,A)=|D1||D|Gini(D1)+|D2||D|Gini(D2)" role="presentation" style="position: relative;"> $G i n i (D, A) = \frac{| D_{1} |}{| D |} G i n i (D_{1}) + \frac{| D_{2} |}{| D |} G i n i (D_{2})$

Gini(D)=1−∑k=1K(|Ck||D|)2" role="presentation" style="position: relative;"> $G i n i (D) = 1 - \sum_{k = 1}^{K} (\frac{| C_{k} |}{| D |})^{2}$

step4:选择基尼指数最小的特征及其对应的切分点作为最优特征和最优切分点

step5:对左右子结点调用step1-4生成决策树

4. CART的缺陷与优化算法

（1）做特征选择的时候都是选择最优的一个特征来做分类决策，但是大多数时候，分类决策不应该是由某一个特征决定的，而是应该由一组特征决定的。这样的决策树叫做多变量决策树(multi-variate decision tree)。在选择最优特征的时候，多变量决策树不是选择某一个最优特征，而是选择最优的一个特征线性组合来做决策。

（2）如果样本发生一点点的改动，就会导致树结构的剧烈改变。这个可以通过集成学习里面的随机森林之类的方法解决。　　　

三、决策树生成之后做什么？

决策树生成之后，我们就可以用来对分类未知的样本进行预测，这时，决策树的泛化性能就显得很重要了，一颗生成之后不加任何操作的决策树往往不是泛化性能非常好的，常用的解决办法是剪枝。

决策树的剪枝分为两种，一种是预剪枝，另一种是后剪枝，下面分别来介绍。

1. 预剪枝

预剪枝就是在完全正确分类训练集之前，较早地停止树的生长。具体在什么时候停止决策树的生长有多种不同的方法:

(1) 一种最为简单的方法就是在决策树到达一定高度的情况下就停止树的生长。

(2) 到达此结点的实例具有相同的特征向量，而不必一定属于同一类，也可停止生长。

(3) 到达此结点的实例个数小于某一个阈值也可停止树的生长。

(4) 还有一种更为普遍的做法是计算每次扩张对系统性能的增益，如果这个增益值小于某个阈值则不进行扩展。

优点&缺点

优点：由于预剪枝不必生成整棵决策树，且算法相对简单，效率很高，适合解决大规模问题。但是尽管这一方法看起来很直接，但是怎样精确地估计何时停止树的增长是相当困难的。

缺点：预剪枝有一个缺点，即视野效果问题。也就是说在相同的标准下，也许当前的扩展会造成过度拟合训练数据，但是更进一步的扩展能够满足要求，也有可能准确地拟合训练数据。这将使得算法过早地停止决策树的构造。

2. 后剪枝

后剪枝的通常做法是极小化决策树整体的损失函数

Cα(T)=∑t=1|T|NtHt(T)+α|T|" role="presentation" style="position: relative;"> $C_{α} (T) = \sum_{t = 1}^{| T |} N_{t} H_{t} (T) + α | T |$

其中，Ht(T)=−∑k=1KNtkNtlogNtkNt" role="presentation" style="position: relative;"> $H_{t} (T) = - \sum_{k = 1}^{K} \frac{N_{t k}}{N_{t}} l o g \frac{N_{t k}}{N_{t}}$

Cα(T)=−∑t=1|T|∑k=1KNtklogNtkNt+α|T|=C(T)+α|T|" role="presentation" style="position: relative;"> $C_{α} (T) = - \sum_{t = 1}^{| T |} \sum_{k = 1}^{K} N_{t k} l o g \frac{N_{t k}}{N_{t}} + α | T | = C (T) + α | T |$

如何理解呢，C(T)=−∑t=1|T|∑k=1KNtklogNtkNt" role="presentation" style="position: relative;"> $C (T) = - \sum_{t = 1}^{| T |} \sum_{k = 1}^{K} N_{t k} l o g \frac{N_{t k}}{N_{t}}$ 是决策树的偏差，|T|" role="presentation" style="position: relative;"> $| T |$ 是模型的复杂度，α" role="presentation" style="position: relative;"> $α$ 是控制两者权重的参数，我们极小化 Cα(T)" role="presentation" style="position: relative;"> $C_{α} (T)$ ，实际上就是在某个权重下选择最小的偏差与方差之和

CART中的剪枝

CART树的剪枝算法可以概括为两步，第一步是从原始决策树生成各种剪枝效果的决策树，第二部是用交叉验证来检验剪枝后的预测能力，选择泛化预测能力最好的剪枝后的数作为最终的CART树。

首先我们看看剪枝的损失函数度量，在剪枝的过程中，对于任意的一刻子树T,其损失函数为：

Cα(Tt)=C(Tt)+α|Tt|" role="presentation" style="position: relative;"> $C_{α} (T_{t}) = C (T_{t}) + α | T_{t} |$

如果将其剪掉，仅仅保留根节点，则损失是

Cα(T)=C(T)+α" role="presentation" style="position: relative;"> $C_{α} (T) = C (T) + α$

当 α" role="presentation" style="position: relative;"> $α$ 很小或者等于0时，

Cα(Tt)<Cα(T)" role="presentation" style="position: relative;">

C_{α} (T_{t}) < C_{α} (T)

当α" role="presentation" style="position: relative;"> $α$ 增大时，

Cα(Tt)=Cα(T)" role="presentation" style="position: relative;">

C_{α} (T_{t}) = C_{α} (T)

当 α" role="presentation" style="position: relative;"> $α$ 继续增大时，不等式反向，所以，什么时候需要剪枝呢？就是子树不剪枝的损失比剪枝的损失大，即

Cα(Tt)>Cα(T)" role="presentation" style="position: relative;">

C_{α} (T_{t}) > C_{α} (T)

即

C(Tt)+α|Tt|>C(T)+α" role="presentation" style="position: relative;">

C (T_{t}) + α | T_{t} | > C (T) + α

即

α>C(T)−C(Tt)|T−t|−1" role="presentation" style="position: relative;">

α > \frac{C (T) - C (T_{t})}{| T - t | - 1}

如果满足下式

α=C(T)−C(Tt)|Tt|−1" role="presentation" style="position: relative;"> $α = \frac{C (T) - C (T_{t})}{| T_{t} | - 1}$

Tt" role="presentation" style="position: relative;"> $T_{t}$ 和 T" role="presentation" style="position: relative;"> $T$ 有相同的损失函数，但是T" role="presentation" style="position: relative;"> $T$ 节点更少，因此可以对子树 Tt" role="presentation" style="position: relative;"> $T_{t}$ 进行剪枝，也就是将它的子节点全部剪掉，变为一个叶子节点 T" role="presentation" style="position: relative;"> $T$ 。

最后我们看看CART树的交叉验证策略。上面我们讲到，可以计算出每个子树是否剪枝的阈值α，如果我们把所有的节点是否剪枝的值α都计算出来，然后分别针对不同的α所对应的剪枝后的最优子树做交叉验证。这样就可以选择一个最好的α，有了这个α，我们就可以用对应的最优子树作为最终结果。

算法过程

step1:初始化αmin=∞" role="presentation" style="position: relative;"> $α_{m i n} = \infty$ ,最优子树集合为ω=T" role="presentation" style="position: relative;"> $ω = T$

step2:从叶子结点自下而上计算各内部结点t的训练误差函数Cα(T)" role="presentation" style="position: relative;"> $C_{α} (T)$ ,叶子结点数 |Tt|" role="presentation" style="position: relative;"> $| T_{t} |$ ,以及正则化阈值α=min{C(T)−C(Tt)|Tt|−1,αmin}" role="presentation" style="position: relative;"> $α = m i n {\frac{C (T) - C (T_{t})}{| T_{t} | - 1}, α_{m i n}}$ ,更新αmin=α" role="presentation" style="position: relative;"> $α_{m i n} = α$

step3:得到所有结点的α" role="presentation" style="position: relative;"> $α$ 值的集合M

step4:从M中选择最大的αk" role="presentation" style="position: relative;"> $α_{k}$ ,自上而下的访问子树t的内部结点，如果 C(T)−C(Tt)|Tt|−1≤αk" role="presentation" style="position: relative;"> $\frac{C (T) - C (T_{t})}{| T_{t} | - 1} \leq α_{k}$ ，进行剪枝，并决定叶结点 t 的值。如果是分类树，则是概率最高的类别，如果是回归树，则是所有样本输出的均值。这样得到 αk" role="presentation" style="position: relative;"> $α_{k}$ 对应的最优子树 Tk" role="presentation" style="position: relative;"> $T_{k}$

step5:最优子树集合ω=ω⋃Tk,M=M−αk" role="presentation" style="position: relative;"> $ω = ω ⋃ T_{k}, M = M - α_{k}$

step6:如果M不空，回到（4），否则就已经得到了所有的可选最优子树集合ω.

step7:采用交叉验证在 ω" role="presentation" style="position: relative;"> $ω$ 选择最优子树Tα" role="presentation" style="position: relative;"> $T_{α}$

四、决策树的优势和劣势

终于到了最后的总结阶段了，这里我们不再纠结于ID3, C4.5和 CART，我们来看看决策树算法作为一个大类别的分类回归算法的优缺点。这部分总结于scikit-learn的英文文档。

决策树算法的优点：

（1）便于理解和解释，树的结构可以可视化出来

（2）基本不需要预处理，不需要提前归一化，处理缺失值

（3）使用决策树预测的代价是O(log2m)，m为样本数

（4）能够处理数值型数据和分类数据

（5）可以处理多维度输出的分类问题

（6）可以通过数值统计测试来验证该模型，这使解释验证该模型的可靠性成为可能

（7）即使该模型假设的结果与真实模型所提供的数据有些违反，其表现依旧良好

决策树算法的缺点:

（1）决策树模型容易产生一个过于复杂的模型,这样的模型对数据的泛化性能会很差。这就是所谓的过拟合.一些策略像剪枝、设置叶节点所需的最小样本数或设置数的最大深度是避免出现该问题最为有效地方法。

（2）决策树可能是不稳定的，因为数据中的微小变化可能会导致完全不同的树生成。这个问题可以通过决策树的集成来得到缓解。

（3）在多方面性能最优和简单化概念的要求下，学习一棵最优决策树通常是一个NP难问题。因此，实际的决策树学习算法是基于启发式算法，例如在每个节点进行局部最优决策的贪心算法。这样的算法不能保证返回全局最优决策树。这个问题可以通过集成学习来训练多棵决策树来缓解,这多棵决策树一般通过对特征和样本有放回的随机采样来生成。

（4）有些概念很难被决策树学习到,因为决策树很难清楚的表述这些概念。例如XOR，奇偶或者复用器的问题。

（5）如果某些类在问题中占主导地位会使得创建的决策树有偏差。因此，我们建议在拟合前先对数据集进行平衡。

参考资料

《统计学习方法》

《机器学习》

http://www.cnblogs.com/pinard/p/6053344.html http://sklearn.apachecn.org/cn/0.19.0/modules/tree.html

有错误的话请指正。

文章最后发布于: 2018-04-15 21:59:30

带你搞懂决策树算法原理