理解决策树
前言
大家好，我是阿南，我先自我介绍一下吧。我本身并不是科班出身，本科就读的是EE，现在在香港城市大学攻读数据科学硕士学位。
在学习机器学习方法的过程之中，我也遇到了很多困难。比方说数据结构的概念不熟悉，或是数学公式的不理解。如果不彻底弄懂其算法原理及其推到，那么顶多算是一个只能念出百度百科里基本概念的半吊子，在找工作面试时只能被呛。因此，在这里，我尽量用通俗易懂的大白话帮助大家理解常见的机器学习方法，以数学公式与实际例子相结合的方式。
第一篇机器学习的博客我希望从数据结构里面的树来写起，希望我的这个自我梳理能够帮助到大家理解决策树这个方法。
决策树的直观理解
首先，从字面意思上去理解它。 “决策”就是做决定。“树”就是一个有着主干和众多分支的结构。所以”决策树“可以理解为不断地在分叉路口做出决定，最终勇敢地走到终点，找到属于自己的那个Label。
作为海南人，我举一个生活中挑选椰子的例子吧！面对众多的椰子，我们的目标是挑选出一个又大又甜的椰子。
首先我会观察椰子的大小，如果椰子足够大那么我就进行下一步判断，否则直接将目光放到下一个椰子上。
接着在大椰子的基础上，我会继续观察这个椰子的尾部。如果这个椰子的尾部是平的，即整体比较圆，那么此时可以判断出这个椰子的内核比较大，反之若尾部比较尖则内核小，但是此时还不能确定里面的椰子水的总量。
我们把椰子拎起来选择一个重量大的，然后摇一摇，再选择一个没有明显的晃动水声的椰子，这样的椰子内核水分保存相对完好。
最后，我们再用指甲掐一下椰子的表皮，若出水则说明该椰子比较嫩，其中的椰子水不会很甜，反之若皮较干则说明是一个大龄椰子，水分含糖量高。
此时，一个相对”完美“的椰子就选择完毕了。在这个过程中可以发现，我们是在许多个判断中摸索前进最终到达终点得到这个椰子的好坏结论的。观察这个图片我们不难发现，它就像一颗倒过来从上往下逐渐变得枝繁叶茂的树，这也就是决策树中”树“这个名字的来源~
这个时候问题来了，大家可能会问，那我怎么决定哪个特征用来判断呢？以及这些特征出现的先后顺序又怎么决定呢？
ID3算法
这个时候我们就要引入一个概念：熵
熵 (entropy)，是用来表示随机变量不确定性的度量。设 $X$ 是一个取有限值的离散随机变量，其概率分布为： \(P(X=x_i) = p_i, i=1,2,...,n\)
则随机变量 $X$ 的熵定义为：
\[H(X)=-\sum_{i=1}^{n}p_i\log{p_i} \tag{1}\]我们可以从公式中看出，如果变量的不确定性越大，那么其熵也就越大！
解释一下就是，如果一件事发生的概率是0或是1，那么我们就可以很确定的说这件事会不会发生。反之，如果这件事发生的概率是0.5，那么即可能发生也可能不发生，此时就存在很大的不确定性。
\[H(A|B)=\sum_{i=1}^{n}{p_iH(A|B)}=-\sum_{i=1}^{n}\frac{|C_k|}{|D|}\sum_{k=1}^{K}\frac{|D_{ik}|}{|D_i|}\log_2\frac{|D_{ik}|}{|D_i|} \tag{2}\]接着我们再引入条件熵 (conditional entropy)， 其定义为：在已知随机变量B的情况下随机变量A的不确定性
举个栗子:
\[H(椰子好坏|椰子重量) \tag{3}\]其描述的就是在已知椰子重量的条件下椰子质量的不确定性。从上面的描述我们即使知道了椰子的重量，仍然还存在许多因素影响椰子的质量，所以上式的数值会比较大。 所以如果我们能够找到一个特征能够使得其条件熵比较小的话，则说明该特征的引入减少了该数据集的“混乱程度”，换句话说就是我们可以更容易的找到正确结果。
信息增益 $g(D, A)$,表示得知特征 $A$ 之后而使得数据集 $D$ 中类别的不确定性的减少程度。
公式定义为集合D的经验熵 $H(D)$ 与特征A给定条件下D的经验条件熵 $H(D\mid A)$之差，即
\[g(D, A)=H(D) - H(D|A) \tag{4}\]结合上式以及我们之前对于熵和条件熵的定义我们可以看出，信息增益越大说明特征 $A$ 的加入能够更加准确地找到对应的类别。
此时我们就掌握了根据信息增益来选择特征去划分数据集以构建决策树的方法了！
- 判断数据集中Label的种类是否 > 1, 若数据集中所有实例同属于一种类别，则树$T$为单节点树，直接输出该类；
- 判断数据集中的特征种类是否 > 0， 若特征为空集，则将实例数最大的类别作为该节点的类标记；
- 即遍历计算数据集中各个特征的信息增益，排序，选择出信息增益最大的特征 $A_g$；
- 若数据集$A_g$的信息增益都小于阈值 $\epsilon$，我们就将该数据集中数量最多的Label作为该节点的Label；
- 否则，按照特征$A_g$的取值$a_i$, 按照$A_g=a_i$将数据集划分为若干个子数据集，构建子节点；
- 随后将子数据集中的特征 $A$ 剔除，对各个子数据集递归执行步骤 1->5。
通过观察条件熵的概念我们可以发现，若某一个特征$A_g$的取值个数较多，那么该特征的信息增益就会越大，就会导致存在偏向于选择取值较多的特征的问题。为了矫正这一个问题，我们可以选择使用 信息增益比 (information gain ratio)来作为特征选择的准则。
\[g_{R}(D, A)=\frac{g(D,A)}{H_{A}(D)} \tag{5}\]信息增益比 ： 信息增益 $g(D,A)$ 与训练数据集 $D$ 关于特征$A$的值的熵 $H_A{(D)}$ 之比。
决策树的剪枝
依照上文提到的 ID3算法 递归产生决策树直到不能继续下去为止。这样生成的决策树预测训练数据的效果非常好，但是对于从未见过的测试集可能就没有那么准确了，我们称之为 过拟合 (Overfitting)。
过拟合产生是因为在训练模型的过程中为了尽可能准确地分类训练集导致生成的模型结构过于复杂。因此为了提高模型的泛化性能，我们要对模型进行 剪枝(pruning)。 即从已经生成的决策树上裁剪掉一些子树或者叶节点，并将其的根节点或父节点作为新的叶节点，从而简化分类模型。
剪枝： 通过极小化决策树整体的 损失函数 (Loss function) 来实现。
设树 $T$ 的叶节点个数为 $\mid T \mid$, $t$ 是树 $T$ 的叶节点，该叶节点有 $N_t$ 个样本点，其中 $k$ 类的样本点有 $N_{tk}$ 个， $k=1,2,…,K, \ H(T)$ 为叶节点 $t$ 上的经验熵， $a\ge 0$为参数，则 决策树学习的损失函数 可以定义为：
\[C_a(T) = \sum_{t=1}^{|T|} N_tH_t(T) + \alpha |T| \tag{6}\]其中经验熵 $H_t(T)$ 为：
\[H_t(T) = -\sum_k \frac{N_{tk}}{N_t} \log \frac{N_{tk}}{N_t} \tag{7}\]为简洁起见，我们用 $C(T)$ 来表示式 $(6)$ 右端第一项：
\[C(T) = \sum_{t=1}^{|T|}N_tH_t(T) = -\sum_{t=1}^{|T|}\sum_{k=1}^{K}N_{tk} \log \frac{N_{tk}}{N_t} \tag{8}\]重写式 $(6)$ 为：
\[C_a(T) = C(T) + \alpha |T| \tag{9}\]式 $(9)$ 中表示的是模型对训练数据的预测误差，即模型与训练数据的拟合程度， $\mid T \mid$ 表示模型复杂度，$\alpha$ 成为调整两者影响程度的调节参数。
因为我们的目标是最小化损失函数 $(9)$，因此越大的 $\alpha$ 促使选择较为简单的模型，较小的 $\alpha$ 促使选择较为复杂的模型。$\alpha = 0$ 就意味着不考虑模型的复杂程度，只关心模型与训练集的拟合程度，与上文中的原始算法并无两样。
剪枝，就是当 $\alpha$ 确定是，选择损失函数 $(9)$ 最小的模型。可以看出，决策树生成只考虑了通过提高信息增益对训练数据进行更好的拟合。而通过剪枝操作优化损失函数的同时还考虑了减小模型复杂度。
决策树生成学习局部的模型，而决策树剪枝得到的是学习整体的模型。
剪枝算法：
输入： 生成算法所生成的决策树 $T$，自定义大小的参数 $\alpha$
输出： 修剪之后的决策树 $T_a$
- 计算每个节点 $t$ 的经验熵 $H_t(T)$
-
递归地从树的叶节点向上回缩。
设一组叶节点回缩到其父节点之前与之后的整体树分别为 $T_B$ 与 $T_A$，其对应的损失函数值分别是 $C_a(T_B)$ 与 $C_a(T_A)$，如果
\[C_a(T_A) \le C_a(T_B) \tag{10}\]则进行剪枝，将父节点变为新的叶节点。
- 返回 $(2)$，直至不能继续为止，得到损失函数最小的子树 $T_a$
式 $(10)$ 中只考虑两个树之间损失函数的差，其计算可以在局部进行。所以决策树的剪枝算法可以由 动态规划 (Dynamic Programming) 来实现。
至此，生成决策树的 ID3 算法就介绍完毕啦。
CART算法
CART算法 的全名是 Classification and Regression Tree，中文译名叫做 分类与回归决策树。
先讲一下 CART算法 和上文中的 ID3算法 之间的区别。
- 首先，CART算法 既可以用于 分类 也可以用于 回归，而 ID3算法 只能用于分类任务。
- CART算法 在选择切分点时是通过比较每个特征 $A_g$ 中的每个可能取值 $a$ 的基尼系数进行的，而 ID3算法 是通过比较特征 $A_g$ 整体的信息增益来选择切分点。
接下来讲 CART分类树 的生成：
CART算法 是利用 基尼系数 (Gini Index) 来选择最优特征以决定最优二值切分点。
现给出 基尼系数 的定义：分类问题中，加入由 $K$ 个类别，实例 $x_i$ 属于第 $k$ 类的概率为 $p_k$，则概率分布的基尼指数定义为：
\[Gini(p) = \sum_{k=1}^K p_k(1-p_k)=1-\sum_{k=1}^Kp_k^2 \tag{11}\]因此对于二分类问题来说，若第一个样本点属于第 $1$ 类的概率是 $p$，则概率分布的基尼指数为：
\[Gini(p) = 2p(1-p) \tag{12}\]对于给定的样本集合 $D$，其基尼指数为：
\[Gini(D) = 1-\sum_{k=1}^K(\frac{|C_k|}{|D|})^2 \tag{13}\]这里 $C_k$ 是 $D$ 中属于第 $k$ 类的样本子集，$K$ 是类的个数。
如果样本集合 $D$ 根据特征 $A$ 是否取某一可能值 $a$ 被分割成 $D_1$ 和 $D_2$ 两部分：
\[D_1=\{(x,y)\in D|A(x)=a\},\ \ \ \ D_2=D-D_1\]则在特征 $A$ 取值为 $a$ 的条件下，集合 $D$ 的基尼指数定义为：
\[Gini(D,A) = \frac{|D_1|}{|D|} Gini(D_1) + \frac{|D_2|}{|D|}Gini(D_2) \tag{14}\]基尼指数 $Gini(D)$ 表示集合 $D$ 的不确定性，基尼指数 $Gini(D,A)$ 表示经过特征 $A=a$ 分割之后集合 $D$ 的不确定性。基尼指数越大，样本集合的不确定性也就越大，这与 $ID3算法$ 中所介绍的 熵 的概念相似。
CART分类树生成算法
输入： 训练集 $D$，停止计算的条件：节点中的 样本数量 或 样本集基尼系数 小于阈值 $\epsilon$ 或没有更多的特征
输出： CART分类决策树
- 标记当前节点的数据集为 $D$，计算现有特征对该数据集的基尼指数。对每个特征 $A$ 的可能值 $a$ 依据 $A=a$ 的标准将数据集分别分为 $A=a$ 的数据集 $D_1$ 和 $A\ne a$ 的数据集 $D_2$。根据式 $(14)$ 计$A=a$ 的基尼系数。
- 遍历计算所有特征 $A$ 以及每个特征的可能值 $a$ 的基尼系数，选择基尼系数最小的特征以及对应的切分点作为最优特征与最优切分点。根据最优特征以及最优切分点再生成两个子节点，将训练数据集依照特征分配到两个子节点中去。
- 对两个子节点递归调用 $(1)(2)$，直至满足停止条件。
CART剪枝
CART剪枝 的步骤与之前的 ID3算法 的剪枝步骤很相似。基本步骤如下：
首先，从“完全生长”的决策树 $T_0$ 的底端减去一些子树，直到 $T_0$ 的根节点，形成一个子树序列 ${T_0,T_1,T_2,…,T_n}$
随后通过交叉验证法再独立的验证数据集上对子树序列进行测试，选出最优的子树 $T_p$
输入： CART算法生成的完全决策树 $T_0$
输出： 最优决策树 $T_p$
- 设定 $k=0,T=T_0$
- 设定 $\alpha=\infty$
- 自上而下地对内部节点 $t$ 计算 $C(T_t), \mid T_t \mid$ 以及： \(g(t) = \frac{C(t)-C(T_t)}{\mid T_t \mid - 1} \\ \alpha = \min (\alpha,g(t))\) $T_t$ 表示以 $t$ 为根节点的子树， $C(T_t)$ 是对训练数据的预测误差， $\mid T_t \mid$ 是 $T_t$ 的叶节点个数
- 对 $g(t)=\alpha$ 的内部节点 $t$ 进行剪枝，并对叶节点 $t$ 以多数表决方式决定类别，得到树 $T$
- 设 $k=k+1,\alpha_k=\alpha,T_k=T$
- 如果 $T_k$ 不是由根节点及两个叶节点构成的树，则回到步骤 $(2)$；否则令 $T_k = T_n$
- 采用交叉验证法再子树序列 $T_0,T_1,…,T_n$ 中选择最优子树 $T_p$
于是乎，我们就选择出最优的子树 $T_p$ 啦~
好啦~ 关于决策树部分的介绍就到这里，蟹蟹大家的耐心观看！欢迎大家提出意见和建议~
:)
