上一章中介绍了 scikit-learn 实现决策树时涉及的几个类以及着重介绍 split 的算法细节。本篇着重介绍 criterion 的算法细节，即如何（快速）计算特征规则的信息增益值。一般的教程在实现决策树时主要考虑到代码的易读性，但在真实应用环境或者说像 scikit-learn 这样的库之所以广为使用，其算法的高效性也是令我们值得学习的地方。另外主流上决策树模型一般用在分类模型，那么回归模型我们该如何“改变”信息增益的计算？公式给出的定义是一回事，但实际操作起来则是另一回事。比如：样本的权重如何体现在信息熵的计算之中、如何避免数组的创建、如何减少冗余的计算等等。

信息熵与信息增益的简单介绍

信息熵即信息的紊乱程度，对于纯数据集（全是阳性、全是阴性）信息熵最低，为 0，对于最紊乱的情况则熵最大，其计算公式如下：

$$ \sum p\cdot log_2(p) $$

对于二分类的情况，则可以简化为如下公式，该函数在 p=0.5 时达到最大值，为 1，也就是最“紊乱”的状态。

$$ Entropy(p) = -p \cdot log_2(p) - (1-p) \cdot log_2(1-p)$$

算 log 在计算上要远慢于乘法运算，因此 CART 算法用 Gini 指数代替

$$ Gini = \sum p (1 - p) = 1 - \sum p^2 $$

在二分类下公式可以简化为如下函数，该函数在 p=0.5 时达到最大，为 0.5。虽然和原来的熵运算结果不同，但趋势相同（都有点类似于抛物线，中间值为最大，最小为 0）因此不妨碍模型的优化。

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

而信息增益则是划分之前的信息熵与划分之后的信息熵的差值。

$$ IG = Gini(before) - \frac{n_{left}}{n_{total}}\cdot Gini(left) -
\frac{n_{right}}{n_{total}} \cdot Gini(right) $$

Scikit-learn 中 criterion 类的核心函数

在前面的公式中可以看出，其实计算信息增益只需要计算三个 Gini 指数，之前的、左边的以及右边的。因此在 scikit-learn 对应两个核函数：node_impurity 以及 children_impurity。而且可以发现这两函数一直到具体的 criterion 类里才会实现，这是因为比如 Entropy 和 Gini 两个类的的主要区别就是信息熵的算法不同，因此他们只需要具体实现这两个函数就行，其他都一样。这些核心类的关系如下：

1
2
3
4
5
6
7
8
9
- Criterion
| - ClassificationCriterion
| | - Entropy
| | - Gini
| - RegressionCriterion
| | - MSE
| | | - FriedmanMSE
| | - MAE
| | - Poisson

主类 Criterion 只实现了两个功能，也是最核心的功能：impurity_improvement 以及 proxy_impurity_improvement。这两个函数其实就是对应上述的 IG 值的实现：

1
2
3
4
5
6
7
8
9
cdef double impurity_improvement(self, double impurity_parent,
                                     double impurity_left,
                                     double impurity_right) nogil:
    return ((self.weighted_n_node_samples / self.weighted_n_samples) *
            (impurity_parent - (self.weighted_n_right /
                                self.weighted_n_node_samples * impurity_right)
                             - (self.weighted_n_left /
                                self.weighted_n_node_samples * impurity_left)))


看上去密密麻麻，仔细看不难发现，其实就是上述的 IG 值，当然稍有区别，为了更好的体现该节点信息的增益情况，它将上述的 IG 值乘以了 self.weighted_n_node_samples / self.weighted_n_samples，即该节点的（加权）样本数比上所有（加权）样本数，换言之如果这个节点本来样本数就不多，那么它信息增益值是不会高的，可见该增益是个面向整棵树的一个评价。

但实际在选择特征规则（split）时，是不需要计算那么多值的，原因很简单，无论选择哪个特征、哪个阈值，父节点的信息熵不会变，节点数量占比不会变，而且 self.weighted_n_node_samples 又是个可以提取公因式的分母常数，因此所有这些值对于比较哪个特征好是没有意义的，仅仅是些常数，又何必一次次放入公式中浪费计算量。于是就有了 proxy_impurity_improvement 函数：

1
2
3
4
cdef double proxy_impurity_improvement(self) nogil:
    self.children_impurity(&impurity_left, &impurity_right)
    return (- self.weighted_n_right * impurity_right
            - self.weighted_n_left * impurity_left)

该函数就两句话：计算左边和右边的信息熵，让他们分别乘以对应（加权）样本数量。对于第一章说的各个特征各个阈值，只需要比较这个值就可以，无需算出真正的信息熵。

回归模型的信息熵计算

其实对于回归模型就不太好用信息熵这个词，只是决策树最初被用来解决分类问题并用信息熵作为判断特征的依据，回归模型作为一种衍生自然也就保留叫信息熵这个词吧。但理念还是差不多的，分类模型中我们希望在划分数据集后左边和右边的纯度都有所提高（比如二分类中一个偏阳性一个偏阴性），体现在信息熵上就是信息熵变低，信息增益变高。而回归模型则是希望划分之后左边和右边分的更开，且每个节点的 y 值都离它们的均值（即预测值）更近，所以我们能比较他们 y 值的绝对误差（mean absolute error, MAE）或者均方差（mean squared error, MSE）。如果把它类比于其他回归模型，那么 criterion 就类似于如神经网络的损失函数，MSE 对应 L2 范式， MAE 对应 L1 范式，而分类模型里的信息增益就可以类比于交叉熵的优化，这样看来似乎理解机器学习算法本是一家，大家都是在优化损失函数。

我们以 MSE 为例，毕竟那是 scikit-learn 的默认值。因为回归树的预测值定义为每个节点的预测值为该节点所有 y 的均值，所以根据如下公式，要计算 RMS 其实只要知道（y 的）平方和以及均值平方即可，(公式中的 i 为样本，j 为任务)。

$$ \sum_j\sum_i (y_{i,j} - \overline{y_j})^2 = \sum_j\sum_iy_{i,j}^2 - \sum_j\overline{y_j}^2 $$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
cdef void children_impurity(self, double* impurity_left,
                                double* impurity_right) nogil:
    # 上一章提过，pos是分割点，所以只需计算start-pos之间的样本
    for p in range(start, pos):
        i = samples[p]

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

        for k in range(self.n_outputs):
            y_ik = self.y[i, k]
            # 核心处： MSE += w * y^2 
            sq_sum_left += w * y_ik * y_ik

    # 一个非常巧妙的地方，右边的平方和等于总平方和和减去左边，所以无需重复计算右边
    sq_sum_right = self.sq_sum_total - sq_sum_left

    impurity_left[0] = sq_sum_left / self.weighted_n_left
    impurity_right[0] = sq_sum_right / self.weighted_n_right

    # sklearn 支持多任务模型，因此 y 可能是多个数组，n_output 就是总任务数
    for k in range(self.n_outputs):
        impurity_left[0] -= (sum_left[k] / self.weighted_n_left) ** 2.0
        impurity_right[0] -= (sum_right[k] / self.weighted_n_right) ** 2.0

    impurity_left[0] /= self.n_outputs
    impurity_right[0] /= self.n_outputs

同样再回去看 node_impurity 函数，就发现其实和算 Gini 一样，只是一个负责算 Gini(before)，一个负责算 Gini(left) 和 Gini(right)。为什么下面代码如此简洁？因为 sq_sum_total，即所有 y 的平方和是个常数，早在初始化时就被计算完。

1
2
3
4
5
6
cdef double node_impurity(self) nogil:
    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

    return impurity / self.n_outputs

小结

由于 _criterion.pyx 都是信息增益（或者更宽泛的叫损失函数）的计算，研究起来并不费力，只要先搞清楚那些类的关系以及比较重要的函数，慢慢理解其本质就是实现最上面所介绍的几个公式。刚开始看一头雾水主要是真正调用它的地方在 split，于是可能不知道从哪里入手。另外从中学习到 scikit-learn 是如何处处考虑一些运算的简化（比如用 proxy_impurity_improvement 代替真正的信息增益计算）。同样，要是我们想要自定义损失函数，则可以直接继承诸如 ClassificationCriterion 类并实现具体 impurity 计算即可，当然记得去 _classes.py 里了解到 criterion 如何实例化并作为决策树的参数的，否则光创建了新的算法不知道如何使用也是无济于事。

相关链接

决策树与信息增益的算法细节[上]