决策树小结

决策树算法在机器学习中算是很经典的一个算法系列了。它既可以作为分类算法，也可以作为回归算法，同时也特别适合集成学习比如随机森林。

决策树的思路很简单，就是从树根开始，每次选择一个能够让样本分开的比较好的特征作为树枝的分叉点，所以其关键点在于如何衡量选择哪个特征作为分叉点是比较好的。衍生出来的主要有三种方法，下面进行一一介绍。

ID3 和 C4.5：通过信息熵度量

信息增益和 ID3

信息熵用于度量信息的大小，其本质代表了信息的不确定性。一个随机变量 $X$ 的熵的表达式为：

$H(X) = -\sum\limits_{i=1}^{n}p_i logp_i$

其中 $n$ 表示 $X$ 的不同的离散取值，而 $p_i$ 表示每种取值的概率，各种取值概率相加为 1。

两个变量的联合熵为：

$H(X, Y) = -\sum\limits_{i=1}^{n}p(x_i,y_i)logp(x_i,y_i)$

条件熵为：

$H(X|Y) = -\sum\limits_{i=1}^{n}p(x_i,y_i)logp(x_i|y_i) = \sum\limits_{j=1}^{n}p(y_j)H(X|y_j)$

条件熵表示在已知 $Y$ 的情况下，$X$ 剩下的不确定性。由此我们可以得到变量 $Y$ 对于变量 $X$ 不确定性的减少程度，也就是互信息：

$I(X, Y) = H(X) - H(X|Y)$

仔细一想，这不就是决策树需要的度量方式吗？ID3 决策树算法中就是通过这个方式来选择最优分裂的。在 ID3 中，互信息也称为信息增益。

西瓜书里面举了一个选择瓜的例子，列举了计算互信息的方式，不想看书的可以看这个：深入浅出理解决策树算法

信息增益率和 C4.5

ID3 算法存在一些不足：

ID3 没有考虑连续特征，比如长度，密度都是连续值，无法在 ID3 运用。
ID3 采用信息增益大的特征优先建立决策树的节点。在相同条件下，取值比较多的特征比取值少的特征信息增益大。比如一个变量有 2 个值，各为 1/2，另一个变量为 3 个值，各为 1/3，其实他们都是完全不确定的变量，但是取 3 个值的比取 2 个值的信息增益大。
ID3 算法对于缺失值的情况没有做考虑。
没有考虑过拟合问题。

C4.5 就是为了解决上述的问题。

对于第一个问题，C4.5 的思路很简单：离散化。将连续的值量化到不同的离散区间中。比如 $m$ 个样本的连续特征 $A$ 有 $m$ 个，从小到大排列为 ${a_1,a_2,…,a_m}$，则 C4.5 取相邻两样本值的平均数作为划分点，一共取得 $m-1$ 个划分点。然后分别以这些划分点作为二元分类点进行分类来求信息增益，选择信息增益最大的点作为该连续特征的离散分类点。

对于第二个问题，引入一个新的概念：信息增益比，它是信息增益和特征熵的比值：

$I_R(D,A) = \frac{I(A,D)}{H_A(D)}$

其中 $D$ 为样本特征输出的集合，$A$ 为样本特征。特征熵的表示如下：

$H_A(D) = -\sum\limits_{i=1}^{n}\frac{|D_i|}{|D|}log_2\frac{|D_i|}{|D|}$

其中 $n$ 为特征 $A$ 的类别数，$D_i$ 为特征 $A$ 的第 $i$ 个取值对应的样本个数，其占总样本的个数就是权重比例。$D$ 为样本的个数。可以看到，特征数越多，其对应的特征熵越大，它作为分母，可以校正信息增益容易偏向于取值较多的特征的问题。

对于第三个问题，首先考虑对于这个特征的划分选择。将数据分为两部分，一部分是有这部分的特征的样本集 $D_1$，一部分是没有这部分特征的样本集 $D_2$，对 $D_1$ 中各个样本计算加权（权重就是某个特征取值对应样本比例）的信息增益比，然后再乘以系数 $\frac{D_1}{D_1 + D_2}$。特征划分选择完毕之后，有特征的样本可以直接划分，对于没有特征的样本，将其同时划分到所有的子节点中，同时其权重按照分配样本的数量比例，也就是 $\frac{D_2}{D_1 + D_2}$ 来更新。

对于第四个问题，C4.5 引入正则化系数进行初步的剪枝。这个后续会和 CART 一起讨论。

基尼系数和 CART

利用信息熵计算决策树的最优分裂虽然有效，但是对数计算的计算量比较大，并且其只能处理分类问题，无法处理回归问题。分类和回归树（classification and regression tree, CART）算法使用基尼系数来代替信息增益比，基尼系数代表了模型的不纯度，基尼系数越小，则不纯度越低，特征越好。这和信息增益(比)是相反的。CART 分类树和回归树都是一个二叉树，其处理分类和回归的区别主要在于输出和最有特征选择算法。

具体的，在分类问题中，假设有 $K$ 个类别，第 $k$ 个类别的概率为 $p_k$，则基尼系数的表达式为：

$Gini(p) = \sum\limits_{k=1}^{K}p_k(1-p_k) = 1- \sum\limits_{k=1}^{K}p_k^2$

因此，对于二分类问题，基尼系数的表达式为：

$Gini(p) = 2p(1-p)$

因此，对于统计规律而言，对于给定的样本集合 $D$，假设有 $K$ 个类别，第 $k$ 个类别的数量为 $C_k$，则样本集合 $D$ 的基尼系数表达式为：

$Gini(D) = 1-\sum\limits_{k=1}^{K}(\frac{|C_k|}{|D|})^2$

类似信息增益，如果某个特征 $A$ 将样本集合 $D$ 分为 $D_1$ 和 $D_2$ 两部分，则在特征 $A$ 的条件下，样本集合 $D$ 的基尼系数表达式为：

$Gini(D,A) = \frac{|D_1|}{|D|}Gini(D_1) + \frac{|D_2|}{|D|}Gini(D_2)$

回归树和分类树

分类树和回归树主要区别在于输出是否连续，二者建立步骤基本一样，部分处理细节不同。下面以 CART 树为例，分别简述分类树和回归树的构建步骤。

构建分类树

输入是训练集 $D$，设定基尼系数阈值，叶子节点样本个数阈值。输出是决策树 $T$。构建分类是的步骤如下：

对当前节点的数据集 $D_i$，如果样本的个数小于阈值，或者特征全部用完，或者CART树的基尼系数小于阈值，则返回决策树，当前节点停止递归；
计算当前样本集在现有的各个特征值对数据集的基尼系数，对于连续值，需要离散化，可以参见前面的方法。对于缺省值，也参见上述的处理方法。
选择基尼系数最小的特征 $A$ 和对应的特征值 $a$，然后根据最有特征和对应的特征值将数据集分类两部分，建立左右节点。
对左右节点分别递归执行上述步骤。

ID3 和 C4.5 只用于构建分类树，其构建方式和CART分类树很相似。这里特别要注意的是设定阈值。

构建回归树

对于分类树，我们通常用信息增益、信息增益率、基尼系数进行划分，这些指标对于离散值的效果很好，也比较好计算，而如果特征是连续的，我们需要进行离散化处理。但是对于回归树，这些指标就不那么有效了，最常见的是利用均方差，也就是对于任意特征 $A$ 以及其划分点，我们优化的目标是使得划分后的两个子节点 $D_1$ 和 $D_2$ 的均方差之后最小：

$\underbrace{min}_{A,s}\Bigg[\underbrace{min}_{c_1}\sum\limits_{x_i \in D_1(A,s)}(y_i - c_1)^2 + \underbrace{min}_{c_2}\sum\limits_{x_i \in D_2(A,s)}(y_i - c_2)^2\Bigg]$

其中，$c_1$ 为 $D_1$ 数据集的样本输出均值，$c_2$ 为 $D_2$ 数据集的样本输出均值。

对于决策树建立后做预测的方式，上面讲到了 CART 分类树采用叶子节点里概率最大的类别作为当前节点的预测类别。而回归树输出不是类别，它采用的是用最终叶子的均值或者中位数来预测输出结果。除了上面提到了以外，CART 回归树和 CART 分类树的建立算法和预测没有什么区别。

决策树一般都是用作分类，回归比较少见。

决策树剪枝

决策树的剪枝类似一种参数正则化的过程，其选择正则化的参数是树的叶子节点的个数。

设树 $T$ 的叶子节点个数为 $|T|$，$t$ 是树 $T$ 的叶子节点，该叶节点的 $Nt$ 个样本点，其中 $k$ 类的样本点有 $N{tk}$ 个，$H_{t}(T)$ 为叶节点 $t$ 上的经验熵，$\alpha \geqslant 0$ 为正则化系数，则包含剪枝的决策树的损失函数可以定义为：

$C_{\alpha}(T)=\sum_{t=1}^{|T|}N_tH_t(T)+\alpha|T|$

其中，经验熵为：

$H_t(T)=-\sum_{k}\frac{N_{tk}}{N_t}log\frac{N_{tk}}{N_t}$

损失函数中的第一项表示模型对训练数据的预测误差，也就是模型的拟合程度，第二项表示模型的复杂程度，通过参数 $\alpha$ 控制二者的影响力。一旦 $\alpha$ 确定，那么我们只要选择损失函数最小的模型即可。

可以看出，决策树的构建过程只考虑对于训练数据的拟合，每次特征选择也是考虑局部最优，而剪枝过程则是一个全局优化的过程，剪枝的过程利用验证集进行。