从零开始的随机森林（2）：决策树

Attention: This blog is a reading note of Tree - Decision Tree with sklearn source code in Chinese, which is written in English. As missing or misunderstanding might be included, please reference the original text if needed. We believe that the original text containing some misunderstandings on information theory itself, and we correct it in our version.

在上一篇博客中，我们介绍了有关信息论的原理和一些直观的理解，这是构建决策树（Decision Tree）算法的基础。在本篇中，我们将介绍分类决策树和回归决策树，以及在 Scikit-learn 开源库中其对应的实现。由于 sk-learn 使用 CART 算法构建决策树，我们也将主要聚焦于这个算法，同时会提及另外两种常用算法：ID3 和 C4.5 算法的原理和优劣。

构建决策树

开始之前，我们稍微回顾一下决策树的定义。决策树是一种树形结构，其中每个内部节点表示一个属性上的测试，每个分支代表一个测试输出，每个叶节点代表一种类别。在实际运行中，一组数据自决策树根结点出发，在每个内部节点通过测试后，最后归结到相应的叶节点，从而被判定为叶节点的类别，或者被赋予叶节点的常数值（回归树）。对于一颗理想的决策树，其叶节点应只包含一种类别的数据（分类树）或者一个常数值（回归树）。尽管我们通常不能（也不会）达到理想状态，但这是我们训练模型的方向。训练过程的本质是通过节点数据的分裂，使得子节点中同类数据（分类树）或同值（或近似值）数据（回归树）的比例增加，这也就是我们在前一篇中所说的“纯度增加”。最终在叶子节点中（由于不是理想树，其中样本仍可能由不同值和不同类构成），取样本最多的类（分类树）或平均值（回归树）为所有节点内样本的预测值。

分裂标准（Criterion）

在前面我们讲到了如何使用一个构建好的决策树进行预测，为了构建一颗决策树，我们需要解决的一个核心问题是：怎么样决定每个节点的数据如何被分到数个子节点上呢？

对于分类树而言，我们需要回忆一下前一篇所提到的熵的概念。在决策树中，我们希望通过分裂节点来“纯化”数据，最小化数据的“不纯度”（其实就是熵）。在前一篇，我们通过“信息增益”来衡量引入一个新的随机变量（此处为基于数据的特征的分裂）所确定（即纯化）的信息量。由于在信息增益公式 $IG=H(Y)-H(Y,X)$ 中，$H(Y)$ 是一个不变量，所以 Ross 教授在 1986 年提出的经典算法：ID3，在决策树中实际上使用的是交叉熵 $H(Y,X)$ 来衡量引入一个（基于特征 $X$ 的）分裂所带来的数据纯化效果，其中对字段概率 $p$ 的估计为：

$$\hat{p}_{k}=\frac{1}{N}\sum I(y_i=k)$$

即节点中类 k 数据的比例，N 为节点内数据总量。在每个分裂子问题中，我们的目标就是找到：

$$\underset{X}{argmax}(IG(Y, X))=\underset{X}{argmin}(H(Y,X))$$

这个公式也隐式地指出了，ID3 的分支数量由 $X$ 的可能取值数量决定。而这可能导致 ID3 会优先选择分支较多的特征，而这种特征有可能是实际上无意义的（比如用户 ID，其信息增益最大并非因为其和分类在意义上相关，仅仅只是分支众多）。为了避免这种情况，Ross 又在 1993 年提出了 C4.5 算法。

C4.5 算法是对 ID3 的改进，其引入了一个新的标准：信息增益比率（Gain Ratio），这个标准通过分裂信息（Split Information）来惩罚拥有过多分支的项的得分，来达到权衡分支数量和纯化效果的效果：

$$SplitInformation(Y, A) = -\sum_{i=1}^{n_A}\frac{Y_i}{Y}log\frac{Y_i}{Y}$$

$$GainRatio=\frac{IG(Y, X)}{SplitInformation(Y, A)}$$

其中，$n_A$ 是 A 的可能取值数量，$Y_i$ 是第 i 个分支内的样本数。这样一来，当分支数量过大时，由于 $SplitInformation$ 的增加，尽管 $IG(Y, X)$ 会增长，但是最终评判标准 $GainRatio$ 却可能降低，从而实现了对于过大数目分支的抑制。虽然 C4.5 解决了分支数量问题，但是大大增加了计算复杂度，导致算法运行缓慢。作为修正，在 1984 年，L.Breiman 等人提出了 CART 算法。

相比于 ID3 或者 C4.5，CART 的两个重要改进分别是该用基尼（Gini）系数作为评判标准，以及只构建二叉决策树。其中，一个节点的基尼系数的定义如下：

$$Gini(Y)=\sum_{i=1}^{n}\frac{Y_i}{Y}（1-\frac{Y_i}{Y}）$$

取 $n=2$，并通过选取特征（划分方法）使得基尼系数增益（即父节点和子节点的基尼系数之差）最大，并如此迭代到算法终止条件，可得 CART 二叉决策树。在该算法中，基尼系数实际上是对于交叉熵的一种拟合。在二分类问题下，他们之间的误差如下图：

上面我们均在讨论决策树用于分类问题的情况，但决策树实际上也可用于回归问题，此时我们又称其为回归树。回归树与分类树最大的区别在于其评判标准。需要注意的是，我们不能单纯地使用交叉熵或者基尼系数的连续形式来评判连续量从而实现回归树，因为他们需要我们对于信息分布具有完全的了解，而在实际问题中，我们实际获得的信息只有连续量的离散取值而已。因为上面诸多限制，CART 算法引入了 方差减益（Variance Reduction） 来作为回归树的分裂标准。直观地讲，其通过计算子节点和根节点的均方差（但实际上没有用到均值差平方和）来衡量一个分裂的好坏。因为我们的回归树的理想目标是使得每个节点的信息纯度最大，方差越小的数据拥有越高的纯度。公式为：

$$
\begin{aligned}
V(S)=\frac{1}{|S|^2}\sum_{i\in S}\sum_{j\in S}\frac12(x_i-x_j)^2\\
I_V(N) = V(S) - (V(S_L) + V(S_R))
\end{aligned}
$$

其中 $S,\ S_L,\ S_R$ 分别为当前节点、左子节点、右子节点的样本集合。该算法有较高的计算时间复杂度。

Sk-learn 源码中的 Criterion

在 Sk-learn 中，对于分类决策树，开发者们实现了基尼系数和交叉熵两种方法，而对于回归树，开发者们则选择了 平均平方误差，又称 均方差（Mean Square Error, MSE），来作为评判标准（以此减少计算的时间复杂度）。均方差公式如下：

$$\frac 1{|S|}(\sum_{i\in S_L}(y_i-\overline y_L)^2+\sum_{i\in S_R}(y_i - \overline y_R)^2)$$

同样处于时间复杂度的考虑，Sk-learn 将上面的公式进一步简化：

$$\frac 1{|S|}\sum(y_i-\overline y)^2 \approx \frac{\sum y^2}{|S|}-\overline y^2$$

最终呈现在代码上，是如下的两个片段：

# ./sklearn/tree/_criterion.pyx
# @Lines: 765-777
# In class: RegressionCriterion

for p in range(start, end):
  i = samples[p]

  if sample_weight != NULL:
      w = sample_weight[i]

  for k in range(self.n_outputs):
      y_ik = self.y[i, k]
      w_y_ik = w * y_ik
      self.sum_total[k] += w_y_ik
      self.sq_sum_total += w_y_ik * y_ik

  self.weighted_n_node_samples += w

# @Lines: 893-895
# In class: MSE

impurity = self.sq_sum_total / self.weighted_n_node_samples
for k in range(self.n_outputs):
    impurity -= (sum_total[k] / self.weighted_n_node_samples)**2.0

除开算法之外，Sk-learn 还通过 Cython 实现并复用样本数组达到了更高的执行效率（减少了解释开销和分配内存开销）。

分裂（Split）

按我们前面所述，你可能会发现一个问题：如果我们每次都通过 Criterion 来选择一个最优分裂策略（Sk-learn 称之为 best-splitter），在数据量大的情况下，尤其是在回归树中，可能是一个难以完成甚至无法完成的任务。另一方面，一个最优的分裂策略以为着很大可能的过拟合。针对这些问题，研究者们提出了数种解决方案：限制叶节点的最小样本数、限制最大使用的特征数、限制决策树的最大深度，以及「随机分裂」（在 sk-learn 中也有相应的实现，主要是并非选择最佳的分裂策略，而是带有随机性地选择相对较好的策略，此处不加以赘述）和 「随机森林」。下一章，我们将一起探访随机森林的世界。

# Decision Tree, Ensemble Learning, Machine Learning