前言
有赞大数据团队内部建立机器学习系列课程, 旨在结合实际项目重新讲解一遍核心机器学习技术. 我们始终相信技术是推动业务进步的原动力. 我们把我们学习的重点记录下来, 分享给大家, 一同学习. 和普通机器学习教程不同, 除了讲解重要理论之外, 我们结合scikit-learn源码加强对知识的理解. 文章有大量的讨论, 都是我们实践过程中遇到的问题. 

1. 决策树的基本概念

我们这里介绍一下一个比较简单的机器学习系统—- 决策树. 它的概念最容易理解, 因为人类的许多决策实际上就是一个决策树.

通常使用的分类回归树（class and regress tree）是一个二叉树。它的形式一般为：

每个方框代表一个节点. 每个非叶子节点有 2 个分支, 一个是判定 True, 一个判定 False. 分别走两个不同的分支. 叶子节点具有决策权. 任何一个输入从 root 出发, 总是会达到且唯一到达一个叶子节点. 这就是决策树的工作原理.

决策树有两种节点： 中间节点和叶子节点。
1. 每个中间节点有 4 个参数：
a) 判定函数。 是一个特征的取值。 当特征小于等于这个值得时候决策路径走左边， 当特征大于这个值得时候决策树走右边。
b) 不纯度值(impurity value). 是当前节点的不纯度值. 关于不纯度值得意义后面会讲到. 他反应了当前节点的预测能力.
c)覆盖样本个数 (n_samples). 是指参与此节点决策的样本个数. 父亲节点(p) 和两个孩子节点 (l,r) 的样本个数的关系为: n_samples(p) = n_samples(l) + n_samples(r) 覆盖样本个数越多, 说明判定函数越稳定. 实际上很容易看出来, 所有的叶子节点所对应的样本是总样本的一个划分.
d)节点取值 (node value). 节点取值是一个数组. 数组的长度为类目个数. value = [997, 1154] 表示在 2151 个样本数中, 有 997 个属于 class1, 1154 属于 class2. (这是分类树的意义, 会归数的取值规则后面会讲.)
2. 每个叶子节点有 3 个参数. 除了没有决策函数之外, 其他参数意义一样.

2. 不纯度函数 (impurity function)

决策树最重要的概念就是不纯函数 (I) 的概念. 当一个节点需要分割的时候, 实际上就是找到一个合适的特征的一个合适的取值作为阈值 (thresh) 进行分割. 那么问题来了, 怎么找到那个合适的特征的合适的取值呢? 主要的依据就是不纯度的变化(delta I). 首先我们给出不纯度函数的定义. 不纯度函数不是一个具体的函数, 它是满足一系列约束的函数的总称.

根据输出实例的取值范围不同. 决策树有不同的种类. 如果输出实例是离散的, 那么决策树是一个分类树; 如果输出实例是连续的, 那么决策树是一个回归树. 如果决策树是分类树. 那么输出空间定义为输出实例所有取值的集合. 这个集合是有限集合. 不失一般性, 使用 {1,…,k} 这可个取值. 不纯度函数 (I) 的定义为:

每一项实际上就是属于类目 c_i 的概率, 记为 p_i.

如上公式可以看出不纯度函数的定义域是长度为 k 的向量, 向量每个数的取值为 0~1, 且加和为 1. 第 i 个数是特征矩阵中属于类别 i 的特征向量个数在整个样本个数 (n_sample) 的占比. 且必须满足如下约束:
1. 当所有样本都属于同一类时候 I 取最小值. 即 I 在点 (1,0,…,0),(0,1,…,0), …, (0,..,0,1) 取最小值.
2. 当样本中每个类目下样本个数相同时 I 取最大值. 即 I 在点 (1/k,..,1/k) 取最大值.
3. I 对于定义域中每个取值 p1,…,pk 是对称的. 即 I(p1, p2,…,pk) = I(p2,p1,..,pk) 等. 从函数图像的角度理解, 就是函数一定是关于值坐标轴对称.
4. I 必须是绝度凸函数 (strickly concave) 即设 p 和 p’(注意这里是一个长度为 k 的向量)为定义域下两个可能的取值. 那么

另外一个概念是不纯度变化 (impurity reduction).

我们回到决策树的结构, 每个父节点的两个子节点都是对父节点的划分. 那么如何评价这次划分呢? 于是我们引入了不纯度变化 (impurity reduction) 的概念. 我们看着公式来理解:

考虑一般性我们设 X1,X2…Xs 是特征空间 X 的一个划分. 不纯度变化定义为:

这个公式很好理解, 令 s=2, 那么 X1,X2 是对于原空间的一个划分. 按理说, 一个好的划分应该让不纯度变低, 以便让类目归属更加清晰. 公式后面一个累加和实际上就是这两个划分的不纯度的期望. 原不纯度减去划分后的不纯度的期望就是减少的不纯度的差值. 显然这个差值越大说明划分让子节点的纯度更 "纯".

另外, 需要强调一点, 根据不纯度函数的第三个约束, 即不纯度函数是定义域下的凸函数, 可以保证不纯度变化 (impurity reduction) 大于等于 0. 当且仅当所有划分的样本数相当取 0.

可这么说, 分类决策树节点划分的依据是找到一个特征的一个取值, 根据这个划分是的不纯度缩减量最大.

下面我们介绍两个常用不纯度函数, 信息熵 (info entropy) 和基尼指数(gini index).

2.1 信息熵 (info entropy)

首先介绍一下信息熵的概念. 我们把样本抽取过程当做一次随机试验 A, 那么 A 有 k 个可能的输出 A1,A2,…,Ak . 对应于 k 个分类. 那么 A 的信息熵定义为:

信息熵满足不纯度函数的定义. 所以我们定义:

把这个不纯度函数的定义带入到不纯度函数的公式中就可以得到相应的不纯度变化函数.

这个函数很出名, 我们把它写出来 (后面的基尼指数就不写了.)

按照教课书的习惯, 当不纯度函数为信息熵时不纯度变化又叫做信息增益 (info gain).

2.2 基尼指数 (Gini Index)

这里强调一下不管是信息熵还是基尼指数, 他们都是不纯函数的一种表达, 不纯度变化的计算没有任何变化. 我们也可以自己撰写不纯度函数. 当 k=2 时候, 我们可以吧信息熵和基尼指数在二维坐标上图形画出来.

可以看出来这两个方法的区别很小. 实际过程中使用哪个方法作为不纯度函数效果不会有太大变化.

我们现在了解了分类决策树在每次分割过程中如何评价分割的好坏, 一遍每次找到最佳分割点. 下面我们继续介绍回归树是如何定义不纯度函数的.

3. 回归树

我们考虑一下会归树的构建过程. 当决策树只有一个节点的时候 (root 节点), 这个节点包含所有待测试样本. 如果我们需要选择一个数来预测函数的取值, 我们会选哪个? 由于我们没有任何多余的信息, 根据最大似然原则, 我们取所有样本取值的均值, 作为预测值.

同样的道理随着决策树的建立, 所有的叶子节点是 root 节点的一个划分. 每个叶子节点都充当一个预测器的角色. 每个叶子节点的预测值是每个节点包含的样本取值的均值.

那么对于回归决策树来说, 我们的任务是如何有效的划分让每个叶子节点更具有代表性. 如果让一个叶子节点更具有代表性, 我们直观的感受是这个节点的样本都趋同于均值 (期望), 实际上就是方差较小. 这正是回归决策树不纯度函数的定义的理论依据.

对于给定的训练集:

Y 是连续变量. 考虑如何生成回归树. 考虑一颗分类树, 每个叶子节点都对应一组概率值, 表示达到这个叶子节点的样本分到每个类目下的概率. 回归树基本结构和分类数一样, 不同的是每个叶子节点都表示对于到达这个叶子节点的样本的预测值 (f(x)). f(x) 等于这个叶子节点所有输入实例 xi 对应的输出 yi 的均值. 有的叶子节点是对样本的一个划分 R1, R2, …, Rm

举个例子:

这颗回归树是对抛物线 y=1-x^2 (-1 < x < 1) 模拟, 我们把原函数和预测函数画在同一个坐标系统.

我看观察图形可以看出, 回归树的特点是使用连续的折线来拟合曲线. 因为在每个叶子节点的取值是固定的, 而这颗回归树只有 8 个叶子节点.

回归树的构建和分类数构建方法类似. 同样是需要找个一个划分, 使得不纯函数的缩减最大. 但是上面所介绍的不纯度函数是根据分类树定义的. 我们需要定义适应回归树的不纯度函数.

在回归树中每个非叶子节点都是样本空间的一个子集的处理单元. 某个子集为 Xm 每个样本 x 有 2 个属性, 一个是实际输出 y, 另一个是预测输出 hat(y). 上面介绍过 hat(y) 是通过这个节点下所有 y 的均值算出来的, hat(y) 这个节点下所有 y 的期望. 反应的是总体上的拟合程度. 那么另外一个衡量集合稳定性的指标是方差, 它衡量 hat(y) 的代表性. 方差越小, 说明 hat(y) 越具有代表性. 因此我们可以定义一种不纯度函数, 就是这个节点下输出值的方差.

这种方法又叫做 "最小二乘法". 同样的带入不纯度变化的公式, 经过必要的化简我们得到:

值得注意的是, 公式中有 2 处对于当前节点来说是常数. 只有最小二乘有实际意义. 我们最大化不纯度变化, 就是最小化最小二乘函数.

一般的教科书直接写成这样的公式:

在本文中我们给出一个符合不纯度函数定义的解释. 这样保证回归树和决策树在实现上是统一的.

4. 小结

上面介绍了决策树一个重要概念, 不纯函数. 不纯函数不仅是分类树的概念, 也是回归树的概念. 它们在形式上是统一的. 这点很有意义, 下面我们分析 sklearn 源码时候可以发现, 在设计决策树时候没有区分分类和回归树, 他们的不同都被封装在不纯函数的定义和计算节点的输出中了.

5. 决策树的构建

上面一章介绍了分类和回归树在某个节点如何选择合适的特征和特征取值进行分裂. 这一章介绍决策树的构建方法, 即如何决定每步应该分裂的节点. 决策树的构建一般有 2 种方法:
1. 深度优先
2. 广度优先

名称	图像	说明
广度优先		广度优先按照层次来构建树的. 首先根据合适的不纯度函数来分裂 root 成 2 个节点; 然后依次分裂第二层的 2 个节点; 依次递推.
深度优先		深度优先采用递归的思想, 在每个节点都是优先有左边的子树建好, 再建右边子树

不管是深度优先还是广度优先, 决策树算法都需要知道什么时候一个节点应该作为叶子节点. 如果没有约束决策树会一直建设下去知道节点只有一个类目 (或者只有一个取值) 才停止. 这样会导致决策树变得非常庞大, 引发过拟合问题.

一般来说, 当如下条件其中之一满足的时候, 当前节点停止构建, 作为决策树的叶子节点.

这些控制条件可以控制数的规模, 因为根据不纯度变化的定义, 将所有的节点都放在唯一的叶子节点 (这样每个叶子节点不纯度都是 0) 中不纯度变化最大. 这显然不是我们想要的.

6. 决策树的预测

通过上述的说明, 决策树的预测就非常的简单了. 决策树中只有叶子节点有预测功能. 一个测试样本从 root 出发选择正确的路径, 一定会走到一个叶子节点. 叶子节点的值即为决策树对这个样本的预测.

1. 如果是分类树. 叶子节点给出每个类别的占比. 概率最大的类别作为这个叶子节点的预测值. 其概率值为置信度.
2. 如果是回归树. 叶子节点的所有样本的输出的平均值作为这个测试样本的预测值.

7. sckit-learn 决策树源码分析

本文的结构实际上就是按照 sckit-learn 中的决策树进行设计的. 源代码在: https://github.com/scikit-learn/scikit-learn/tree/master/sklearn/tree .
首先介绍一下主要文件:

criterion.py*

criterion.py* 主要定义了各种不纯度函数及其计算和转化方法.

import numpy as np
from sklearn.tree import DecisionTreeRegressor
import matplotlib.pyplot as plt

# Create a random dataset
rng = np.random.RandomState(1)
X = np.sort(5 * rng.rand(80, 1), axis=0)
y = np.sin(X).ravel()
y[::5] += 3 * (0.5 - rng.rand(16))

# Fit regression model
regr_1 = DecisionTreeRegressor(max_depth=2)
regr_1.fit(X, y)

# Predict
X_test = np.arange(0.0, 5.0, 0.01)[:, np.newaxis]
y_1 = regr_1.predict(X_test)

# Plot the results
plt.figure()
plt.scatter(X, y, c="k", label="data")
plt.plot(X_test, y_1, c="g", label="max_depth=2", linewidth=2)
plt.xlabel("data")
plt.ylabel("target")
plt.title("Decision Tree Regression")
plt.legend()
plt.show()