决策树（下）：CART算法及其代码实现

前言

决策树上篇介绍了决策树发展过程中诞生的两种算法，但是这两种算法在都有着比较明显的缺点，所以现在业界常用的决策树算法多数是CART算法，因此本文会介绍CART算法的原理已经sklearn代码实现。

CART分类树

书接上文，上篇最后讲到C4.5算法的不足，我们继续以改进算法不足的逻辑来讲CART算法

基尼系数

C4.5算法采用的信息增益比存在大量的对数运算，有没有一个指标可以在运算复杂度低的情况下又可以很好的度量数据的不确定性呢。这里我们采用数学上的拟合来做这件事，类似于泰勒展开，用多项式去拟合对数，指数等复杂函数，这里我们也可以使用多项式去拟合信息增益比，这可以保证在可以接受的误差的情况下，降低运算复杂度，这也就是基尼系数的由来，具体定义，假设随机变量 $X$ 的分布为 $P(X=x_k)=p_k$ ，则随机变量 $X$ 的基尼系数为

\mathrm{Gini}(X)=\sum_{k=1}^Kp_k(1-p_k)=1-\sum_{k=1}^Kp_k^2

放到具体的数据集 $D$ 中，基尼系数的定义写为

\mathrm{Gini}(D)=1-\sum_{k=1}^K\left(\frac{|C_k|}{|D|}\right)^2

其中， $|D|$ 是样本总数， $|C_k|$ 是属于第 $k$ 类的样本的类别。

在使用特征 $A$ 进行分割的情况下，将数据集分割为 $D_1,D_2$ ，则基尼系数定义为

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

该基尼系数度量了使用特征 $A$ 进行分割的情况下，数据集 $D$ 的不确定性。

CART算法就是使用 $\mathrm{Gini}(D)$ 代替了信息熵，使用 $\mathrm{Gini}(D,A)$ 代替了条件熵。（好好对比一下基尼系数与信息熵的公式）

接下来让我们看看在二分类的情况下，基尼系数是如何变化的，还记得上篇中信息熵的那张图吗，这里我们加入基尼系数与分类误差率，图像如下

这里我们可以看到，基尼系数与信息熵的曲线是非常接近的，且两者都可以用于拟合分类误差率。

当然这里还有一个隐藏的问题，就是上述写的基尼系数只写了使用特征 $A$ 划分为两个子集的情况，如果特征 $A$ 有更多取值呢。这是因为CART算法生成的决策树均为二叉树，所以即使是多个取值的特征也只能划分出两个子节点，这点在接下来会讲到。

CART算法的特征处理

连续型特征

对于连续型特征，其处理方法与C4.5算法基本相同，只是将计算各划分点的信息增益比改为计算基尼系数。

离散型特征

对于离散型特征，由于CART算法需要保证生成的决策树为二叉树，故对于离散型特征均使用二分。例如，特征 $A$ 有三个取值 $\{A_1, A_2, A_3\}$ ，现在要将其划分为两个子集，则有两种划分方法，也就是划分为 $\{A_1\}$ 与 $\{A_2,A_3\}$ 以及划分为 $\{A_1,A_2\}$ 与 $\{A_3\}$ 。对这两种方法分别计算基尼系数，选取基尼系数小的划分作为最终划分，并且对于未被完全划分的子节点，其再接下来的特征选择过程中，特征 $A$ 还可以继续参与选择。比如最终选择的划分为 $\{A_1\}$ 与 $\{A_2,A_3\}$ ，则被划分为 $\{A_2,A_3\}$ 的子节点还可以根据特征 $A$ 继续划分为 $\{A_2\}$ 与 $\{A_3\}$ ，故特征 $A$ 可以参与该子节点的特征选择。

CART决策树生成算法

在C4.5算法的基础上，加入上述改进，就是CART算法，这里我们将其完整的写下来

输入：训练集 $D$ ，基尼系数的阈值，样本个数阈值。

输出：决策树 $T$ 。

对于当前节点的数据集为 $D$ ，如果样本个数小于阈值或者没有特征，则返回决策子树，当前节点停止递归。

计算样本集 $D$ 的基尼系数，如果基尼系数小于阈值，则返回决策树子树，当前节点停止递归。

计算当前节点现有的各个特征的各个特征值对数据集 $D$ 的基尼系数。

在计算出来的各个特征的各个特征值对数据集 $D$ 的基尼系数中，选择基尼系数最小的特征 $A$ 和对应的特征值 $a$ 。根这个最优特征和最优特征值，把数据集划分成两部分 $D_1$ 和 $D_2$ ，同时建立当前节点的左右节点，做节点的数据集 $D$ 为 $D_1$ ，右节点的数据集 $D$ 为 $D_2$ .

对左右的子节点递归的调用1-4步，生成决策树。

CART回归树

接下来，我们来解决一个比较大的问题，如何使用决策树做回归。首先，回归问题的输出值是一个连续值，但是决策树的处理依旧简单粗暴，也就是每一个叶子节点就对应一个固定的输出值。所以本质上，回归树的输出是有限的，比如生成的回归树有100个叶子节点，则最终的输出值就是在这100个数的集合里选择一个最优的值。

回归树需要解决的问题

在分类树的基础上，回归树需要解决两个问题，第一，如何划分子节点，第二，如何确定叶子结点的输出值

现在，先放下如何划分子节点的问题，我们来看看对于一个划分好的子节点，应该如何确定这个子节点的输出值。这个问题对于分类问题当然是很简单的，采用投票法，少数服从多数，但是对于回归问题来说，这是一个优化问题。简单来说，对于一个节点中的数据集 $R$ ，要选择一个数 $c$ 来代表全体样本的输出 $y_i$ 。有没有感觉很熟悉，其实就是计算 $c$ 与 $y_i$ 的距离之和嘛，这里使用我们很熟悉的最小二乘法，用距离的平方作为度量，将优化函数写出来

\operatorname*{min}_{c}\sum_{x_i\in R}(y_i-c)^2

求解可得，最优取值 $\hat{c}$ 其实就是全体 $y_i$ 的平均值，也就是

\hat{c} = avg(y_i|x_i \in R) = \frac{1}{|R|} \sum_{x_i \in R} y_i

接下来，我们来解决划分子节点的问题，对于回归问题来说，之前使用的基尼系数一类的指标自然就失效了，所以，我们延续上面选输出值的思路。对一个划分来说，划分为两个子节点，那这两个子节点分别会有平方误差，划分出来的两个子节点的平方误差之和越小，我们就认为该划分越好。我们用数学的语言写出来，首先一个划分当然包含特征 $j$ 与划分点 $s$ ，该划分将原数据集 $R$ 划分为两个子集

\begin{aligned}R_1(j,s)=\{x|x^{(j)}\leqslant s\}\end{aligned}与R_2(j,s)=\{x|x^{(j)}>s\}

这两个子集会有各自的输出值

\hat{c_1} = avg(y_i|x_i \in R_1(j,s))与\hat{c_2} = avg(y_i|x_i \in R_2(j,s))

则两个子集的平方误差分别为

\sum_{x_i\in R_1(j,s)}(y_i-\hat{c_1})^2与\sum_{x_i\in R_2(j,s)}(y_i-\hat{c_2})^2

故选择划分的问题可以转化为求解优化函数

\begin{aligned}\min_{j,s}\left[\sum_{x_i\in R_1(j,s)}(y_i-\hat{c_1})^2 + \sum_{x_i\in R_2(j,s)}(y_i-\hat{c_2})^2\right]\end{aligned}

也可以写为

\begin{aligned}\min_{j,s}\left[\min_{c_1}\sum_{x_i\in R_1(j,s)}(y_i-c_1)^2+\min_{c_2}\sum_{x_i\in R_2(j,s)}(y_i-c_2)^2\right]\end{aligned}

就是把求解 $\hat{c_1},\hat{c_2}$ 的过程也一起写进去

求解上述优化函数，遍历所有特征，对于离散型特征，就是再遍历其所有划分方式，对于连续型数据，就是正常求解优化函数选出最佳划分点，最终可以求解出最佳特征与最佳划分点，记为 $(j,s)$ 。

CART回归树生成算法

经过上述铺垫，现在我们将回归树生成算法书面化的写出来

输入：训练集 $D$ ，平方误差的阈值，样本个数阈值。
输出：决策树 $T$ 。

对于当前节点的数据集为 $D$ ，如果样本个数小于阈值或者平方误差小于阈值或者没有特征，则返回决策子树，当前节点停止递归。

计算当前节点的最佳划分 $(j,s)$ 。

使用 $(j,s)$ 划分出左右两个子节点并确定子节点取值。

对左右的子节点递归的调用1-3步，生成决策树。

CART算法的优缺点

优点：

简单直观，是少数具有可解释性的机器学习算法。

基本不需要预处理，不需要提前归一化，处理缺失值。

对于异常点的容错能力好，健壮性高。

使用决策树预测的代价是 $O(log2m)$ ， $m$ 为样本数，时间复杂度。

缺点:

非常容易过拟合，导致泛化能力不强。

决策树会因为样本发生一点点的改动，就会导致树结构的剧烈改变。这个可以通过集成学习之类的方法解决。

寻找最优的决策树是一个NP难的问题，一般是通过启发式方法计算优化函数，容易陷入局部最优。可以通过集成学习之类的方法来改善。

有些比较复杂的关系，决策树很难学习，比如异或。一般这种关系可以换神经网络分类方法来解决。

如果某些特征的样本比例过大，生成决策树容易偏向于这些特征。这个可以通过调节样本权重来改善。

sklearn代码实现

最后，我们来简单介绍一下决策树的sklearn代码实现，运行环境为jupyter notebook，如果完全没接触过sklearn的读者可以先移步sklearn机器学习通用技术——快速入门，了解一下sklearn的基本使用。先导入必要的库

import matplotlib.pyplot as plt
import numpy as np
import pandas as pd
import seaborn as sns

from sklearn.tree import DecisionTreeClassifier  # 决策树分类
from sklearn.tree import DecisionTreeRegressor  # 决策树回归
from sklearn.tree import plot_tree  # 决策树可视化

from sklearn.datasets import load_wine  # 红酒数据集
from sklearn.datasets import load_boston  # 波士顿房价数据集

from sklearn.model_selection import train_test_split  # 切分数据

from scipy import stats

import warnings
warnings.filterwarnings("ignore")

分类树

我们使用sklearn中自带的数据集作为示例数据，首先我们使用红酒数据集作为分类树的示例数据

1 2	# 读取数据 wine = load_wine()

查看数据大小，并且打印前5个样本，大概看看数据长什么样子

1 2	# 查看数据概况 wine.data.shape

# 查看数据表
data = pd.DataFrame(wine.data)
data.columns = wine.feature_names
target = pd.DataFrame(wine.target)
target.columns = ['class']
D = pd.concat([data, target], axis=1)
D.head()

划分训练集与测试集，很基本的操作

1 2	# 划分训练集与测试集 Xtrain, Xtest, Ytrain, Ytest = train_test_split(data, target, test_size=0.2)

然后调用分类树，参数均默认，进行一次建模

# 分类树
clf = DecisionTreeClassifier()
clf.fit(Xtrain, Ytrain)
clf.score(Xtest, Ytest)

将决策树画出来

1	plot_tree(clf)

通用参数

random_state：

随机数种子，用于随机选择特征，保证每次训练得到的结果一致。注意，这里与原理部分不同，按照算法原理，进行特征选择时需要遍历所有特征，但是sklearn为考虑效率，在特征选择时会随机选择部分特征进行遍历，不会遍历所有特征，因此每次运行时产生的树才总是会有一定差异。

splitter：

用于控制特征选择过程中的随机性，有两种输入值，“best"与"random”，默认为"best"。"best"就是正常的选择最优的特征进行划分，而"random"会增加划分的随机性，其划分不一定为最优划分。可以作为防止过拟合的一种手段。

一般来说，在样本量不大的情况下，使用"best"，在样本量较大的情况下，使用"random"。

criterion：

评价指标，对于分类树来说，有两种输入值，“gini"与"entropy”，分别对应基尼系数与信息增益，默认为"gini"，因为sklearn是使用的CART树。

在调参过程中，“entropy"对于不确定性的敏感度较高，所以会比较容易过拟合，在样本量较少的情况下可以使用，一般情况下都是使用"gini”

剪枝参数

由于决策树是一个很容易过拟合的模型，所以剪枝策略对决策树调参来说至关重要。在原理部分我跳过了C4.5与CART的剪枝策略部分，这里直接结合着sklearn的剪枝参数来讲

max_depth：

现在决策树的最大深度，对大于该深度的节点全部剪掉，简单但有效。在调参过程中，一般是最优先调整的参数。

min_samples_leaf & min_samples_split：

min_samples_leaf，一个节点在分枝后的每个子节点都必须包含至少min_samples_leaf个训练样本。

min_samples_split限定，一个节点必须要包含至少min_samples_split个训练样本，这个节点才允许被分枝，也就是原理部分提到的结束条件之一。

都是限制决策树学习极端样本的参数

min_impurity_decrease：

限制信息增益的大小，信息增益小于设定数值的分枝不会发生，也是原理部分提到的结束条件之一。

max_features：

max_features限制分枝时考虑的特征个数，超过限制个数的特征都会被舍弃。常用于限制高维数据过拟合，但是本身比较暴力，不是很好调。

同时该参数的输入比较多，可以输入整数，浮点数，甚至"log2"等，这里放一段sklearn官方文档的说明:

输入一个int，则在每次分割时考虑 max_features 特征。

输入一个float，则 max_features 是一个分数，每次分割时会考虑 max(1, int(max_features * n_features_in_))个特征。

输入"sqrt"，则 max_features=sqrt(n_features)。

输入"log2"，则 max_features=log2(n_features)。

输入"none"，则 max_features=n_features。

分类树特有参数

class_weight：

指定样本各类别的的权重，可以自己输入权重列表，或者输入"balanced"，算法会自己计算权重。

主要用于样本类别的占比不平衡的情况，防止决策树偏向于占比多的类别。

简单调参

上述讲了常见的参数，还有一些其他的参数，可以参考sklearn的官方文档，下面针对红酒数据集进行一个简单调参

# 调参
clf = DecisionTreeClassifier(random_state=1008
                             ,splitter="best"
                             ,criterion="entropy"
                             ,max_depth=3
                            )
clf.fit(Xtrain, Ytrain)
score_train = clf.score(Xtrain, Ytrain)
score = clf.score(Xtest, Ytest)
print("score train:", score_train)
print("score test:", score)

由于红酒数据集样本量不大，故常用"best"与"entropy"这些比较容易使算法快速收敛的参数，然后使用max_depth来限制过拟合，最终可以在测试集上跑出97%左右的准确率。当然，这里只是一个小数据的示例，对实际使用的参考意义并不大。

重要方法

与多数机器学习算法一样，决策树可以使用predict()方法进行预测

1	clf.predict(data)

这会输出最终的预测类别。但是对于分类问题来说，还有一种专有的predict_proba()方法，对于每一个 $x$ ，其会输出一个 $1 \times K$ 的向量，其中 $K$ 为总类别数，向量的第 $k$ 列的值对应该 $x$ 被分类到第 $k$ 类的概率

1	clf.predict_proba(data)

在决策树中，其计算方法为该叶子节点中，属于第 $k$ 类的样本数。例如，在一个叶子节点中，有10个第一类的样本，2个第二类的样本，那么被分配到这个叶子节点的数据会被分类到第一类，但是其被分类到第一类的概率为 $10/12$ 。

重要属性

决策树算法是通过筛选特征来生成的，故可以输出特征的重要性，这在特征工程也可以用于筛选特征，具体属性为

1 2	# 特征重要性 clf.feature_importances_

也可以把特征名一起输出，更加直观

1	[*zip(wine.feature_names, clf.feature_importances_)]

输出值为基于选择指标对特征的评分，评分越高说明特征越重要。

回归树

参数

criterion：

回归树可以选择的评价指标有：

“squared_error”（平均平方误差），默认参数，也就是MSE，与原理部分讲的选择方法是一样的；

“absolute_error”（平均绝对误差），就是MAE，就是把原理部分讲的误差平方改为误差绝对值；

这里可以做一些额外的知识补充，一般我们在回归里，衡量误差的做法就是把误差平方再加和，因为误差有正有负，这样可以解决正负抵消的问题，写出来就是
$\sum(y_i-f(x_i))^2$
但是，大家有没有想过，为什么不能用绝对值呢，因为绝对值函数在 $x=0$ 不可导，所以优化函数写不出解析解。当然现在使用计算机，通过优化算法计算也是可行的，所以使用绝对值来衡量误差的方法也可以被使用，具体写出来为
$\sum|y_i-f(x_i)|$
下面这两个指标不细讲，仅作展示

“friedman_mse”（使用平均平方误差和弗里德曼改进分数）；

“poisson”（使用泊松偏差缩小寻找拆分）。

简单调参

使用波士顿房价数据集作为回归树的数据示例

1 2	# 读取数据 boston = load_boston()

1 2	# 查看数据概况 boston.data.shape

# 查看数据表
data = pd.DataFrame(boston.data)
data.columns = boston.feature_names
target = pd.DataFrame(boston.target)
target.columns = ['MEDV']
D = pd.concat([data, target], axis=1)
D.head()

1 2	# 划分训练集与测试集 Xtrain, Xtest, Ytrain, Ytest = train_test_split(data, target, test_size=0.2)

# 回归树
clf = DecisionTreeRegressor()
clf.fit(Xtrain, Ytrain)
clf.score(Xtest, Ytest)

1	plot_tree(clf)

# 调参
clf = DecisionTreeRegressor(random_state=1008
                            ,splitter="best"
                            ,max_depth=9
                            ,min_samples_leaf=1
                            ,min_samples_split=2
#                             ,min_impurity_decrease=2
                           )
clf.fit(Xtrain, Ytrain)
score_train = clf.score(Xtrain, Ytrain)
score = clf.score(Xtest, Ytest)
print("score train:", score_train)
print("score test:", score)