决策树（Decision Tree）是一种基本的分类与回归方法。在分类问题中，表示基于特征对实例进行分类的过程，可认为是if-then规则的集合，是定义在特征空间与类空间上的条件概率分布。利用训练数据，根据损失函数最小化的原则建立决策树模型，预测时，对新的数据利用决策树模型进行分类，包括三个步骤：特征选择、决策树生成、决策树修剪。（李航《统计学习方法：决策树》）[1]

分类决策树

分类决策树定义

分类决策树模型是一种描述对实例进行分类的树形结构，决策树由节点（node）和有向边（directed edge）组成，结点有两种类型：内部结点（internal node）和叶结点（leaf node），内部结点表示一个特征或属性，叶结点表示一个类。[1]

如下图挑选西瓜的决策树模型（判断一个西瓜好坏）：

决策树结构

一棵决策树包含一个根节点、若干个内部节点和若干个叶子节点；叶子节点对应最终的决策结果，其它每个节点则对应与一个属性的测试。最终划分到同一个叶子节点上的样本，具有相同的决策属性，可以对这些样本的值求平均值来实现回归，对这些样本进行投票（选取样本数量最多的类别）实现分类。

决策树构建

决策树算法

决策树的构建，就是不断选取好的特征作为决策节点，构建一颗泛化能力较强的树结构，算法描述如下：

决策树的构建是一个递归的过程，核心问题：

  1. 选取特征作为分裂点。决策树构建的每一步，选取最优的特征，使决策对数据集划分效果最好；
  2. 何时停止分裂子节点；

决策树特征选择

①信息熵

信息熵（information entropy）是度量样本集合纯度的常用指标，该值越大，表示该集合纯度越低（或越混乱），该值越小，表示该集合纯度越高（或越有序）. 信息熵定义：
$$
H = -\sum_{i=1}^{n}{P(x_i)log_2P(x_i)}
$$

其中，$P(x_i)$表示集合中第i类样本所占比例，当$P(x_i)$为1时（只有一个类别，比例为100%）, $log_2P(x_i)$的值为0，整个系统信息熵为0；当类别越多，则$P(x_i)$的值越接近于0，$log_2P(x_i)$趋近去负无穷大，整个系统信息熵就越大。以下代码，展示了类别数量从1…10的集合信息熵变化：

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
28
29
30
31
32
33
34
35
# 信息熵计算演示
import math
import numpy as np
import matplotlib.pyplot as mp

class_num = 10  # 类别最大数量

def entropy_calc(n):
    p = 1.0 / n  # 计算每个类别的概率
    entropy_value = 0.0  # 信息熵
    for i in range(n):
        p_i = p * math.log(p)
        entropy_value += p_i
    return -entropy_value  # 返回熵值

entropies = []
for i in range(1, class_num + 1):
    entropy = entropy_calc(i)  # 计算类别为i的熵值
    entropies.append(entropy)

print(entropies)

# 可视化回归曲线
mp.figure('Entropy', facecolor='lightgray')
mp.title('Entropy', fontsize=20)
mp.xlabel('Class Num', fontsize=14)
mp.ylabel('Entropy', fontsize=14)
mp.tick_params(labelsize=10)
mp.grid(linestyle='-')
x = np.arange(0, 10, 1)
print(x)
mp.plot(x, entropies, c='orangered', label='entropy')

mp.legend()
mp.show()

执行结果：
信息熵变化

随着决策树的节点划分，纯度是在不断的提升，熵值不断的减小

②信息增益

决策树根据属性进行判断，将具有相同属性的样本划分到相同节点下，此时，样本比划分之前更加有序（混乱程度降低），信息熵的值有所降低。用划分前的信息熵减去划分后的信息熵，就是决策树获得的信息增益。可以用以下表达式表示：
$$
Gain(D, a) = Ent(D) - \sum_{v=1}^{V} \frac{|D^v|}{|D|} Ent(D^v)
$$
其中，D表示样本集合，a表示属性，v表示属性可能的取值${v^1, v^2,…,v^n}$, $\frac{|D^v|}{|D|}$表示权重，样本越多的分支对分类结果影响更大，赋予更高的权重, $Gain(D, a)$表示在样本集合D上使用属性a来划分子节点所获得的信息增益。

③增益率

增益率不直接采用信息增益，而采用信息增益与熵值的比率来作为衡量特征优劣的标准。C4.5算法就是使用增益率作为标准来划分属性。增益率定义为：
$$
Gain_ratio(D, a) = \frac{Gain(D, a)}{IV(a)}
$$
其中
$$
IV(a) = - \sum_{v=1}^{V} \frac{|D^v|}{|D|} log_2 \frac{|D^v|}{|D|}
$$

④基尼系数

信息熵越大，数据越混乱，信息熵越小，数据越纯。

Gini系数越大，数据越混乱，Gini系数越小，数据越纯。

基尼系数定义为：
$$
Gini(p) = \sum_{k=1}^{k} p_k (1-p_k) = 1 - \sum_{k=1}^{k} p_k^2
$$

基尼系数反映了从数据集D中随机抽取两个样本，类别标记不一致的概率。因此，基尼系数越小，数据集的纯度越高。CART决策树（Classification And Regression Tree）使用基尼系数来选择划分属性，选择属性时，选择划分后基尼值最小的属性作为最优属性。采用和上式相同的符号表示，数据集D下属性a的基尼系数定义为：
$$
Gini_index(D, a) = \sum_{v=1}^{V} \frac{|D^v|}{|D|} Gini(D^v)
$$

决策树算法 属性划分系数
Cart 回归：均方误差mse
Cart 分类：Gini系数
ID3 信息增益
C4.5 增益率

决策树停止分裂

以下几种情况会停止决策树子节点的构建：

  • 当前节点所有样本属于同一个类别，无需划分；
  • 当前属性集为空，或者所有样本取值相同，无法划分；
  • 当前节点包含的样本集合为空，不能划分；
  • 当前节点样本数量少于指定数量；

决策树实现

scikit-learn中决策树相关API：

1
2
3
4
5
6
7
8
# 模型
model = st.DecisionTreeRegressor(max_depth=4)  # 决策树回归器
model = st.DecisionTreeClassifier(max_depth=4)

# 训练
model.fit(train_x, train_y)
# 预测
pre_test_y = model.predict(test_x)

波士顿房价预测

数据集介绍：该数据集为一个开放房价数据集，包含506个样本，每个样本包含13个特征和1个标签，具体如下所示：

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
28
29
30
31
32
33
34
# 决策树回归示例
# 使用决策树预测波士顿房价

import sklearn.datasets as sd
import sklearn.utils as su
import sklearn.tree as st
import sklearn.ensemble as se
import sklearn.metrics as sm

boston = sd.load_boston()  # 加载boston地区房价数据
print(boston.feature_names)
print(boston.data.shape)
print(boston.target.shape)

random_seed = 7  # 随机种子，计算随机值，相同的随机种子得到的随机值一样
x, y = su.shuffle(boston.data, boston.target, random_state = random_seed)
# 计算训练数据的数量
train_size = int(len(x) * 0.8) # 以boston.data中80%的数据作为训练数据
# 构建训练数据、测试数据
train_x = x[:train_size]  # 训练输入, x前面80%的数据
test_x = x[train_size:]   # 测试输入, x后面20%的数据
train_y = y[:train_size]  # 训练输出
test_y = y[train_size:]   # 测试输出

######## 单棵树进行预测 ########
# 模型
model = st.DecisionTreeRegressor(max_depth=4)  # 决策回归器

# 训练
model.fit(train_x, train_y)
# 预测
pre_test_y = model.predict(test_x)
# 打印预测输出和实际输出的R2值
print(sm.r2_score(test_y, pre_test_y))

执行结果：

1
2
3
4
5
['CRIM' 'ZN' 'INDUS' 'CHAS' 'NOX' 'RM' 'AGE' 'DIS' 'RAD' 'TAX' 'PTRATIO'
 'B' 'LSTAT']
(506, 13)
(506,)
0.8202560889408634

特征重要性：

作为决策树模型训练过程中的副产品，根据每个特征划分子表前后信息熵减少量就标志了该特征的重要程度，此即为该特征重要性的指标。训练后得到的模型对象提供了属性feature_importances_来存储每个特征的重要性。在工程应用上，可以对决策树做一些优化，不必让每一个特征都参与子表划分，而只选择其中较重要的（或者说影响因素较大的）的特征作为子表划分依据。特征重要性的评价指标，就是根据该特征划分子表后所带来的信息熵减少量，熵减越大的就越重要，也就越优先参与子表的划分。

在上述示例中加入如下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import matplotlib.pyplot as mp
import numpy as np
fi = model.feature_importances_  # 获取特征重要性
print("fi:", fi)

# 特征重要性可视化
mp.figure("Feature importances", facecolor="lightgray")
mp.plot()
mp.title("DT Feature", fontsize=16)
mp.ylabel("Feature importances", fontsize=14)
mp.grid(linestyle=":", axis=1)
x = np.arange(fi.size)
sorted_idx = fi.argsort()[::-1]  # 重要性排序(倒序)
fi = fi[sorted_idx]  # 根据排序索引重新排特征值
mp.xticks(x, boston.feature_names[sorted_idx])
mp.bar(x, fi, 0.4, color="dodgerblue", label="DT Feature importances")

mp.legend()
mp.tight_layout()
mp.show()

执行结果：

决策树的剪枝

剪枝（pruning）是决策树学习算法对付“过拟合”的主要手段. 在决策树学习中，为了尽可能正确分类训练样本，节点划分过程将不断重复，有时会造成决策树分支过多，这时就可能因训练样本学的“太好了”，以至于把训练集本身的一些特点当做数据所具有的一般性质而导致过拟合. 因此，可通过主动去掉一些分支来降低过拟合风险.

（1）预剪枝. 决策树生成过程中，对每个节点在划分前进行评估，若当前节点不能带来决策树泛化性能的提升，则停止划分并将当前节点标记为叶子节点.

（2）后剪枝. 先训练为一颗完整的决策树，然后自低向上对非叶子节点进行考察，若将该节点对应的子树替换为叶节点能带来决策树泛化能力提升，则将该子树替换为叶节点.

集成学习与随机森林

集成学习

集成学习（ensemble learning）通过构建并合并多个模型来完成学习任务，从而获得比单一学习模型更显著优越的泛化性能，简言之，集成学习就是利用模型的“集体智慧”，提升预测的准确率. 根据单个模型方式，集成学习可以分为两大类：

  • 个体间存在强依赖关系，必须串行生成的序列化方法，其代表为Boosting算法；
  • 个体之间不存在强依赖关系，可同时生成的并行化方法，代表是Bagging和随机森林算法.

Boosting

Boosting定义

Boosting（直译为推进、提升）是一族可以将弱学习器提升为强学习器的算法，其工作原理是：

  • 先训练出一个初始模型；
  • 根据模型的表现进行调整，使得模型预测错误的数据获得更多的关注，再重新训练下一个模型；
  • 不断重复第二步，直到模型数量达到预先设定的数目T，最终将这T个模型加权结合.

AdaBoosting是Boosting算法族中最著名的算法，它根据每次训练集之中每个样本的分类是否正确，以及上次的总体分类的准确率，来确定每个样本的权值。将修改过权值的新数据集送给下层分类器进行训练，最后将每次训练得到的分类器最后融合起来，作为最后的决策分类器。

Boosting实现

sklearn中，AdaBoosting相关API：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import sklearn.tree as st
import sklearn.ensemble as se

# model: 决策树模型（单个模型，基学习器）
model = st.DecisionTreeRegressor(max_depth=4)

# n_estimators：构建400棵不同权重的决策树，训练模型
model = se.AdaBoostRegressor(model, # 单模型
                             n_estimators=400, # 决策树数量
                             random_state=7)# 随机种子

# 训练模型
model.fit(train_x, train_y)

# 测试模型
pred_test_y = model.predict(test_x)

代码：

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
28
29
30
31
32
# AdaBoosting示例
# 使用AdaBoosting预测波士顿房价
import sklearn.datasets as sd
import sklearn.utils as su
import sklearn.tree as st
import sklearn.ensemble as se
import sklearn.metrics as sm

boston = sd.load_boston()  # 加载boston地区房价数据
print(boston.feature_names)
print(boston.data.shape)
print(boston.target.shape)

random_seed = 7  # 随机种子，计算随机值，相同的随机种子得到的随机值一样
x, y = su.shuffle(boston.data, boston.target, random_state = random_seed)
# 计算训练数据的数量
train_size = int(len(x) * 0.8) # 以boston.data中80%的数据作为训练数据
# 构建训练数据、测试数据
train_x = x[:train_size]  # 训练输入, x前面80%的数据
test_x = x[train_size:]   # 测试输入, x后面20%的数据
train_y = y[:train_size]  # 训练输出
test_y = y[train_size:]   # 测试输出

model2 = se.AdaBoostRegressor(st.DecisionTreeRegressor(max_depth=4),
                              n_estimators=400,   # 决策树数量
                              random_state=random_seed) # 随机种子
# 训练
model2.fit(train_x, train_y)
# 预测
pre_test_y2 = model2.predict(test_x)
# 打印预测输出和实际输出的R2值
print(sm.r2_score(test_y, pre_test_y2))

执行结果：

1
2
3
4
5
['CRIM' 'ZN' 'INDUS' 'CHAS' 'NOX' 'RM' 'AGE' 'DIS' 'RAD' 'TAX' 'PTRATIO'
 'B' 'LSTAT']
(506, 13)
(506,)
0.9068598725149652

可以看到，通过AdaBoosting算法，回归模型获得了更高的R2值.

随机森林

随机森林定义

随机森林（Random Forest，简称RF）是专门为决策树设计的一种集成方法，是Bagging法的一种拓展，它是指每次构建决策树模型时，不仅随机选择部分样本，而且还随机选择部分特征来构建多棵决策树. 这样不仅规避了强势样本对预测结果的影响，而且也削弱了强势特征的影响，使模型具有更强的泛化能力.

随机森林简单、容易实现、计算开销小，在很多现实任务中展现出强大的性能，被誉为“代表集成学习技术水平的方法”.

随机森林实现

sklearn中，随机森林相关API：

1
2
3
4
5
6
import sklearn.ensemble as se

model = se.RandomForestRegressor(
    max_depth, # 决策树最大深度
    n_estimators, # 决策树数量
    min_samples_split)# 子表中最小样本数 若小于这个数字，则不再继续向下拆分

以下是利用随机森林实现波士顿房价预测的代码：

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
28
29
30
31
32
33
# 使用随机森林预测波士顿房价
import sklearn.datasets as sd
import sklearn.utils as su
import sklearn.tree as st
import sklearn.ensemble as se
import sklearn.metrics as sm

boston = sd.load_boston()  # 加载boston地区房价数据
print(boston.feature_names)
print(boston.data.shape)
print(boston.target.shape)

random_seed = 7  # 随机种子，计算随机值，相同的随机种子得到的随机值一样
x, y = su.shuffle(boston.data, boston.target, random_state=random_seed)
# 计算训练数据的数量
train_size = int(len(x) * 0.8)  # 以boston.data中80%的数据作为训练数据
# 构建训练数据、测试数据
train_x = x[:train_size]  # 训练输入, x前面80%的数据
test_x = x[train_size:]  # 测试输入, x后面20%的数据
train_y = y[:train_size]  # 训练输出
test_y = y[train_size:]  # 测试输出

# 创建随机森林回归器，并进行训练
model = se.RandomForestRegressor(max_depth=10,  # 最大深度
                                 n_estimators=1000,  # 树数量
                                 min_samples_split=2)  # 最小样本数量，小于该数就不再划分子节点
model.fit(train_x, train_y)  # 训练

# 基于天统计数据的特征重要性
fi_dy = model.feature_importances_
# print(fi_dy)
pre_test_y = model.predict(test_x)
print(sm.r2_score(test_y, pre_test_y))  # 打印r2得分

打印输出：

1
2
3
4
5
['CRIM' 'ZN' 'INDUS' 'CHAS' 'NOX' 'RM' 'AGE' 'DIS' 'RAD' 'TAX' 'PTRATIO'
 'B' 'LSTAT']
(506, 13)
(506,)
0.9271955403309159