决策树和随机森林

决策树（Decision Tree）是一种特殊的树结构，代表的是样本特征与样本标签之间的一种映射关系。

决策树举例如下，分叉路径则代表某个可能的属性值，而终结节点代表最终决策：

信息增益

定义

为了引入决策树分类的算法，先介绍决策树学习中的重要概念：信息增益（Information Gain）。

这个指标可以衡量分类给数据中带来信息的程度。若分类带来的信息增益越大，就越能减少数据的无序度。

信息增益的表示如下，为父节点和子节点中的不纯度（Inpurity）差值：

$$\begin{align} IG(D_p, f) = I(D_p) - \sum_{j=1}^m \cfrac {N_i} {N_p} I(D_j) \end{align}$$

其中 $f$ 代表对应的特征，$D_p$ 和 $D_j$ 分别表示父节点的数据和第 $j$ 个子节点的数据集，$N_p$ 和 $N_i$ 分别表示父节点的数据和第 $j$ 个子节点的样本数量，$I()$ 代表不纯度的函数。

不纯度的计算有以下几种方法：

• 熵（Entropy）：$I_H(t) = -\sum_{j=1}^c p(i \mid t) \cdot \log_2 p(i \mid t)$
• Gini 不纯度（Gini Impurity）：$I_G(t) = 1- \sum_{j=1}^c p(i \mid t)^2$
• 分类错误（Classification Error）：$I_E(t) = 1- \max p(i \mid t)$

在实际应用中，熵和 Gini 不纯度的结果非常相似，不必纠结于这两个计算标准的选择。
而分类错误对节点概率的变化较不敏感，不推荐在决策树增长时使用。

计算示例

以如下决策树演示不纯度的计算，其中 $(a, b)$ 代表节点中所属分类的样本数量。

例如父节点，包含 40 个属于类 1 的样本、40 个 属于类 2 的样本；其他节点同理。

决策树 A 的熵：

$$\begin{align} I_H(D_p) & = -({\cfrac 1 2} \log{\cfrac 1 2} + {\cfrac 1 2} \log{\cfrac 1 2}) = 1 \\ I_H(D_{left}) & = -({\cfrac 3 4} \log{\cfrac 3 4} + {\cfrac 1 4} \log{\cfrac 1 4}) = 0.81 \\ I_H(D_{right}) & = -({\cfrac 1 4} \log{\cfrac 1 4} + {\cfrac 3 4} \log{\cfrac 3 4}) = 0.81 \\ IG_H & = 1 - {\cfrac 1 2} 0.81 - {\cfrac 1 2} 0.81 = 0.19 \end{align}$$

决策树 B 的熵：

$$\begin{align} I_H(D_p) & = -({\cfrac 1 2} \log{\cfrac 1 2} + {\cfrac 1 2} \log{\cfrac 1 2}) = 1 \\ I_H(D_{left}) & = -({\cfrac 1 3} \log{\cfrac 1 3} + {\cfrac 2 3} \log{\cfrac 2 3}) = 0.92 \\ I_H(D_{right}) & = 0 \\ IG_H & = 1 - {\cfrac 3 4} 0.92 - 0 = 0.31 \end{align}$$

决策树 A 的 Gini 不纯度：

$$\begin{align} I_G(D_p) & = 1 - ({\cfrac 1 2})^2 - ({\cfrac 1 2})^2 = \cfrac 1 2 \\ I_G(D_{left}) & = 1 - ({\cfrac 3 4})^2 - ({\cfrac 1 4})^2 = \cfrac 3 8 \\ I_G(D_{right}) & = 1 - ({\cfrac 1 4})^2 - ({\cfrac 3 4})^2 = \cfrac 3 8 \\ IG_G & = 1 - {\cfrac 1 2} \cdot {\cfrac 3 8} - {\cfrac 1 2} \cdot {\cfrac 3 8} = 0.125 \end{align}$$

决策树 B 的 Gini 不纯度：

$$\begin{align} I_G(D_p) & = 1 - ({\cfrac 1 2})^2 - ({\cfrac 1 2})^2 = \cfrac 1 2 \\ I_G(D_{left}) & = 1 - ({\cfrac 2 3})^2 - ({\cfrac 1 3})^2 = \cfrac 4 9 \\ I_G(D_{right}) & = 1 - 1^2 - 0^2 = 0 \\ IG_G & = \cfrac 1 2 - {\cfrac 3 4} \cdot {\cfrac 4 9} - 0 = 0.167 \end{align}$$

决策树 A 的分类错误：

$$\begin{align} I_E(D_p) & = 1 - {\cfrac 1 2} = \cfrac 1 2 \\ I_E(D_{left}) & = 1 - {\cfrac 3 4} = \cfrac 1 4 \\ I_E(D_{right}) & = 1 - {\cfrac 3 4} = \cfrac 1 4 \\ IG_E & = {\cfrac 1 2} - {\cfrac 1 2} \cdot {\cfrac 1 4} - {\cfrac 1 2} \cdot {\cfrac 1 4} = 0.25 \end{align}$$

决策树 B 的分类错误：

$$\begin{align} I_E(D_p) & = 1 - {\cfrac 1 2} = \cfrac 1 2 \\ I_E(D_{left}) & = 1 - {\cfrac 1 3} = \cfrac 1 3 \\ I_E(D_{right}) & = 1 - 1 = 0 \\ IG_E & = {\cfrac 1 2} - {\cfrac 3 4} \cdot {\cfrac 1 3} - 0 = 0.25 \end{align}$$

为了更直观的比较三种信息增益计算方法的差异，对平均分布 $[0,1]$ 的样本应用并绘图：

import matplotlib.pyplot as plt
import numpy as np


def gini(p):
    return (p) * (1 - (p)) + (1 - p) * (1 - (1 - p))


def entropy(p):
    return - p * np.log2(p) - (1 - p) * np.log2((1 - p))


def error(p):
    return 1 - np.max([p, 1 - p])


x = np.arange(0.0, 1.0, 0.01)
ent = [entropy(p) if p != 0 else None for p in x]
sc_ent = [e * 0.5 if e else None for e in ent]
err = [error(i) for i in x]

ax = plt.subplot(111)
for i, lab, ls, c, in zip([ent, sc_ent, gini(x), err],
                          ['Entropy', 'Entropy (scaled)',
                           'Gini Impurity',
                           'Misclassification Error'],
                          ['-', '-', '--', '-.'],
                          ['black', 'lightgray',
                           'red', 'green', 'cyan']):
    line = ax.plot(x, i, label=lab, linestyle=ls, lw=2, color=c)
ax.legend(loc='upper center', bbox_to_anchor=(0.5, 1.15),
          ncol=5, fancybox=True, shadow=False)
ax.axhline(y=0.5, linewidth=1, color='k', linestyle='--')
ax.axhline(y=1.0, linewidth=1, color='k', linestyle='--')

plt.ylim([0, 1.1])
plt.xlabel('p(i=1)')
plt.ylabel('Impurity Index')
plt.show()

决策树

代码实现

决策树分类的思想是，从树根开始将特征上的数据分割成最大的信息增益，然后在子节点重复这个拆分过程。

在实践中，这可能会导致一个有很多节点的很深的树，很容易导致过度拟合。因此通常要通过设置树的最大深度限制来修剪树。

以 Iris 数据集为例，基于 Scikit-learn 的实现如下（其中决策边界绘制函数 plot_decision_regions 请参见之前的文章）：

import matplotlib.pyplot as plt
import numpy as np
from sklearn import datasets
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier

iris = datasets.load_iris()
X = iris.data[:, [2, 3]]
y = iris.target
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=1, stratify=y)

tree = DecisionTreeClassifier(criterion='gini', max_depth=4, random_state=1)
tree.fit(X_train, y_train)

X_combined = np.vstack((X_train, X_test))
y_combined = np.hstack((y_train, y_test))
plot_decision_regions(X_combined, y_combined, classifier=tree, test_idx=range(105, 150))
plt.xlabel('petal length [standardized]')
plt.ylabel('petal width [standardized]')
plt.legend(loc='upper left')
plt.show()

Graphviz 绘图

Windows 下的 Graphviz 需要：

1. 下载并安装 Graphviz Windows 安装包 graphviz-2.xx.msi
2. 将 C:\Program Files (x86)\Graphviz2.xx\bin\; 添加到环境变量 Path（计算机——属性——高级系统设置——环境变量）
3. Pip 安装软件包: pip install pydotplus graphviz pyparsing

对上节生成的 tree 进行绘图：

from pydotplus import graph_from_dot_data
from sklearn.tree import export_graphviz

dot_data = export_graphviz(tree,
                           filled=True,
                           rounded=True,
                           class_names=['Setosa', 'Versicolor', 'Virginica'],
                           feature_names=['petal length', 'petal width'],
                           out_file=None)
graph = graph_from_dot_data(dot_data)
graph.write_png('tree.png')

随机森林

随机森林是一个包含多个决策树的分类器，并且其输出的分类标签是由每个树的的分类标签的众数而定。

1. 从已知的样本集合（样本数 $M$，特征数 $N$）中，有放回地随机取 $n$ 个 bootstrap 样本（$n < N$）。
2. 对取得的 bootstrap 的样本生成决策树：
   a. 无放回地随机选择其中 $m$ 个特征（$m << M$）。
   b. 根据目标函数提供的最佳分割特征（如最大化信息增益）来分割节点。
3. 重复步骤 1-2 若干次数。
4. 汇总每棵树的预测标签，把其中数量最多的作为随机森林的分类标签。

import matplotlib.pyplot as plt
import numpy as np
from sklearn import datasets
from sklearn.model_selection import train_test_split
from sklearn.ensemble import RandomForestClassifier

iris = datasets.load_iris()
X = iris.data[:, [2, 3]]
y = iris.target
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=1, stratify=y)

forest = RandomForestClassifier(criterion='gini', n_estimators=25, random_state=1, n_jobs=2)
forest.fit(X_train, y_train)

X_combined = np.vstack((X_train, X_test))
y_combined = np.hstack((y_train, y_test))
plot_decision_regions(X_combined, y_combined, classifier=forest, test_idx=range(105, 150))
plt.xlabel('petal length [standardized]')
plt.ylabel('petal width [standardized]')
plt.legend(loc='upper left')
plt.show()

上面通过 n_estimators 参数从 25 个决策树中训练了一个随机森林，并使用 Gini 不纯度作为分割节点的标准。
n_jobs 参数表示可以使用计算机的多个核心（这里是两个核心）来并行化训练。