从决策树到随机森林：树型算法的原理与实现

转载自：https://www.jiqizhixin.com/articles/2017-07-31-3

翻译
发表于 | 分类于

基于树（Tree based）的学习算法在数据科学竞赛中是相当常见的。这些算法给预测模型赋予了准确性、稳定性以及易解释性。和线性模型不同，它们对非线性关系也能进行很好的映射。常见的基于树的模型有：决策树（decision trees），随机森林（random forest）和提升树（boosted trees）。

在本篇文章中，我们将会介绍决策树的数学细节（以及各种 Python 示例）及其优缺点。你们将会发现它们是很简单的，并且这些内容是有助于理解的。然而，与最好的监督学习方法相比，它们通常是没有竞争力的。为了克服决策树的各种缺点，我们将会聚焦于各种概念（附有 Python 实例），比如自助聚集或袋装（Bootstrap Aggregating or Bagging），还有随机森林（Random Forests）。另一种广泛使用的提升方法会在以后进行单独讨论。每种方法都包括生成多种树，这些树被联合起来，生成一个单一的一致性预测结果，并且经常带来预测精度的显著提升。

决策树

决策树是一种监督学习算法。它适用于类别和连续输入（特征）和输出（预测）变量。基于树的方法把特征空间划分成一系列矩形，然后给每一个矩形安置一个简单的模型（像一个常数）。从概念上来讲，它们是简单且有效的。首先我们通过一个例子来理解决策树。然后用一种正规分析方法来分析创建决策树的过程。考虑一个简单的借贷公司顾客的数据集合。我们给定了所有客户的查询账户余额、信用记录、任职年限和先前贷款状况。相关任务是预测顾客的风险等级是否可信。该问题可以使用下列决策树来解决：

分类和回归树（简称 CART）是 Leo Breiman 引入的术语，指用来解决分类或回归预测建模问题的决策树算法。它常使用 scikit 生成并实现决策树： sklearn.tree.DecisionTreeClassifier 和 sklearn.tree.DecisionTreeRegressor 分别构建分类和回归树。

CART 模型

CART 模型包括选择输入变量和那些变量上的分割点，直到创建出适当的树。使用贪婪算法（greedy algorithm）选择使用哪个输入变量和分割点，以使成本函数（cost function）最小化。

树建造的结尾使用了一个预定义的停止准则，比如分配到树上每一个叶结点的训练样本达到最小数量。

其他决策树算法：

  • ID3：Iterative Dichotomiser 3
  • C4.5：ID3 算法的改进
  • CHAID：Chi-squared Automatic Interaction Detector
  • MARS：决策树的扩展式，以更好地解决数值型预测。
  • 条件推断树 回归树

我们现在关注一下回归树的 CART 算法的细节。简要来说，创建一个决策树包含两步：

1. 把预测器空间，即一系列可能值 X_1，X_2，…，X_p 分成 J 个不同的且非重叠的区域 R_1，R_2，…，R_J。

2. 对进入区域 R_J 的每一个样本观测值都进行相同的预测，该预测就是 R_J 中训练样本预测值的均值。

为了创建 J 个区域 R_1，R_2，…，R_J，预测器区域被分为高维度的矩形或盒形。其目的在于通过下列式子找到能够使 RSS 最小化的盒形区域 R_1，R_2，…，R_J，

其中，yhat_Rj 即是第 j 个盒形中训练观测的平均预测值。

鉴于这种空间分割在计算上是不可行的，因此我们常使用贪婪方法（greedy approach）来划分区域，叫做递归二元分割（recursive binary splitting）。

它是贪婪的（greedy），这是因为在创建树过程中的每一步骤，最佳分割都会在每个特定步骤选定，而不是对未来进行预测，并选取一个将会在未来步骤中出现且有助于创建更好的树的分隔。注意所有的划分区域 R_j 都是矩形。为了进行递归二元分割，首先选取预测器 X_j 和切割点 s 

其中 yhat_R1 为区域 R_1(j,s) 中观察样本的平均预测值，yhat_R2 为区域 R_2(j,s) 的观察样本预测均值。这一过程不断重复以搜寻最好的预测器和切分点，并进一步分隔数据以使每一个子区域内的 RSS 最小化。然而，我们不会分割整个预测器空间，我们只会分割一个或两个前面已经认定的区域。这一过程会一直持续，直到达到停止准则，例如我们可以设定停止准则为每一个区域最多包含 m 个观察样本。一旦我们创建了区域 R_1、R_2、…、R_J，给定一个测试样本，我们就可以用该区域所有训练样本的平均预测值来预测该测试样本的值。

分类树

分类树和回归树十分相似，只不过它是定性地预测响应值而非定量预测。从上文可知，回归树对一个观察值所预测的连续型数值就是属于同一叶结点训练样本观察值的均值。但是对于分类树来说，我们所预测的类别是训练样本观察值在某区域下最常见的类别，即训练观察值的模式响应（mode response）。为了达到分类目的，很多时候系统并不会只预测一个类别，它常常预测一组类别及其出现的概率。

分类树的生成和回归树的生成十分相似。正如在回归树中那样，我们一般使用递归性的二元分割来生成分类树。然而在分类树中，RSS 不能作为二元分割的标准。我们需要定义叶结点的不纯度量 Q_m 来替代 RSS，即一种可以在子集区域 R_1,R_2,…,R_j 度量目标变量同质性的方法。在结点 m 中，我们可以通过 N_m 个样本观察值表示一个区域 R_m 所出现类别的频率，第 k 个类别在第 m 个区域下训练所出现的频率可表示为：

其中，I(y_i=k) 为指示函数，即如果 y_i = k，则取 1，否则取零。

不纯性度量 Q_m 一个比较自然的方法是分类误差率。分类误差率描述的是训练观察值在某个区域内不属于最常见类别的概率：

考虑到该函数不可微，因此它不能实现数值优化。此外，该函数在结点概率改变上并不敏感，因此这种分类误差率对于生成树十分低效。我们一般使用 Gini 指数和交叉熵函数来衡量结点的误差度量。

Gini 指数可以衡量 k 个类别的总方差，它一般定义为：

较小的 Gini 指数值表示结点包含了某个类别大多数样本观察值。

在信息论里面，交叉熵函数用来衡量系统的混乱度。对于二元系统来说，如果系统包含了一个类别的所有内容，那么它的值为零，而如果两个类别的数量一样多，那么交叉熵达到最大为 1。因此，和 Gini 指数一样，交叉熵函数同样能用于度量结点的不纯度：

和 G 一样，较小的 S 值表示区域内结点包含了单个类别中的大多数观察值。

决策树常见参数和概念

如果我们希望以数学的方式理解决策树，我们首先需要了解决策树和树型学习算法的一般概念。理解以下的术语同样能帮助我们调整模型。

  • 根结点：表示所有数据样本并可以进一步划分为两个或多个子结点的父结点。
  • 分裂（Splitting）：将一个结点划分为两个或多个子结点的过程。
  • 决策结点：当一个子结点可进一步分裂为多个子结点，那么该结点就称之为决策结点。
  • 叶/终止结点：不会往下进一步分裂的结点，在分类树中代表类别。
  • 分枝/子树：整棵决策树的一部分。
  • 父结点和子结点：如果一个结点往下分裂，该结点称之为父结点而父结点所分裂出来的结点称之为子结点。
  • 结点分裂的最小样本数：在结点分裂中所要求的最小样本数量（或观察值数量）。这种方法通常可以用来防止过拟合，较大的最小样本数可以防止模型对特定的样本学习过于具体的关系，该超参数应该需要使用验证集来调整。
  • 叶结点最小样本数：叶结点所要求的最小样本数。和结点分裂的最小样本数一样，该超参数同样也可以用来控制过拟合。对于不平衡类别问题来说，我们应该取较小的值，因为属于较少类别的样本可能数量上非常少。
  • 树的最大深度（垂直深度）：该超参数同样可以用来控制过拟合问题，较小的深度可以防止模型对特定的样本学习过于具体的关系，该超参数同样需要在验证集中调整。
  • 叶结点的最大数量：叶结点的最大个数可以替代数的最大深度这一设定。因为生成一棵深度为 n 的二叉树，它所能产生的最大叶结点个数为 2^n。
  • 分裂所需要考虑的最大特征数：即当我们搜索更好分离方案时所需要考虑的特征数量，我们常用的方法是取可用特征总数的平方根为最大特征数。 分类树的实现

为了展示不同的前文所述的决策树模型，我们将使用 Kaggle 上的美国收入数据集，我们都可以在 Kaggle.com 上下载该数据集。下面的代码可以展示该数据集的导入过程和部分内容：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import pandas as pd
import numpy as np
from plotnine import *
import matplotlib.pyplot as plt
from sklearn.preprocessing import LabelEncoder
from sklearn_pandas import DataFrameMapper
from sklearn.tree import DecisionTreeClassifier
from sklearn.ensemble import RandomForestClassifier

training_data = './adult-training.csv'
test_data = './adult-test.csv'
columns = ['Age','Workclass','fnlgwt','Education','EdNum','MaritalStatus','Occupation','Relationship','Race','Sex','CapitalGain','CapitalLoss','HoursPerWeek','Country','Income']

df_train_set = pd.read_csv(training_data, names=columns)
df_test_set = pd.read_csv(test_data, names=columns, skiprows=1)
df_train_set.drop('fnlgwt', axis=1, inplace=True)
df_test_set.drop('fnlgwt', axis=1, inplace=True)

在上面的代码中，我们首先需要导入所有需要的库和模块，然后再读取数据和结构到训练数据和验证数据中。我们同样去除 fnlgwt 列，因为该数据行对于模型的训练并不重要。

输入以下语句可以看到训练数据的前五行：

df_train_set.head()

1
2
3

如下所示，我们还需要做一些数据清洗。我们需要将所有列的的特殊字符移除，此外任何空格或者「.」都需要移除。

df_train_set[i].replace(‘ ?’, ‘Unknown’, inplace=True) df_test_set[i].replace(‘ ?’, ‘Unknown’, inplace=True)for col in df_train_set.columns:if df_train_set[col].dtype != ‘int64’: df_train_set[col] = df_train_set[col].apply(lambda val: val.replace(“ “, “”)) df_train_set[col] = df_train_set[col].apply(lambda val: val.replace(“.”, “”)) df_test_set[col] = df_test_set[col].apply(lambda val: val.replace(“ “, “”)) df_test_set[col] = df_test_set[col].apply(lambda val: val.replace(“.”, “”))

1
2
3
正如上图所示，有两行描述了个人的教育：Eduction 和 EdNum。我们假设这两个特征十分相关，因此我们可以移除 Education 列。Country 列对预测收入并不会起到什么作用，所以我们需要移除它。

df_train_set.drop([“Country”, “Education”], axis=1, inplace=True) df_test_set.drop([“Country”, “Education”], axis=1, inplace=True)

1
2
3
Age 和 EdNum 列是数值型的，我们可以将连续数值型转化为更高效的方式，例如将年龄换为 10 年的整数倍，教育年限换为 5 年的整数倍，实现的代码如下：

colnames = list(df_train_set.columns) colnames.remove(‘Age’) colnames.remove(‘EdNum’) colnames = [‘AgeGroup’, ‘Education’] + colnames

labels = [“{0}-{1}”.format(i, i + 9) for i in range(0, 100, 10)] df_train_set[‘AgeGroup’] = pd.cut(df_train_set.Age, range(0, 101, 10), right=False, labels=labels) df_test_set[‘AgeGroup’] = pd.cut(df_test_set.Age, range(0, 101, 10), right=False, labels=labels)

labels = [“{0}-{1}”.format(i, i + 4) for i in range(0, 20, 5)] df_train_set[‘Education’] = pd.cut(df_train_set.EdNum, range(0, 21, 5), right=False, labels=labels) df_test_set[‘Education’] = pd.cut(df_test_set.EdNum, range(0, 21, 5), right=False, labels=labels)

df_train_set = df_train_set[colnames] df_test_set = df_test_set[colnames]

1
2
3
4
现在我们已经清理了数据，下面语句可以展示我们数据的概况：


df_train_set.Income.value_counts()`<=50K 24720>50K 7841Name: Income, dtype: int64``df_test_set.Income.value_counts()`<=50K 12435>50K 3846Name: Income, dtype: int64

在训练集和测试集中，我们发现 <=50K 的类别要比>50K 的多 3 倍。从这里我们就可以看出来样本数据并不是均衡的数据，但是在这里为了简化问题，我们在这里将该数据集看作常规问题。

EDA

现在，让我们以图像的形式看一下训练数据中的不同特征的分布和相互依存（inter-dependence）关系。首先看一下关系（Relationships）和婚姻状况（MaritalStatus）特征是如何相互关联的。

(ggplot(df_train_set, aes(x = “Relationship”, fill = “MaritalStatus”))+ geom_bar(position=”fill”)+ theme(axis_text_x = element_text(angle = 60, hjust = 1)))

1
2
3
4
5

让我们首先看一下不同年龄组中，教育对收入的影响（用受教育的年数进行衡量）。


(ggplot(df_train_set, aes(x = "Education", fill = "Income"))+ geom_bar(position="fill")+ theme(axis_text_x = element_text(angle = 60, hjust = 1))+ facet_wrap('~AgeGroup'))

最近，有很多关于性别对收入差距的影响的相关说法。我们可以分别看见男性和女性的教育程度和种族间的影响。

(ggplot(df_train_set, aes(x = “Education”, fill = “Income”))+ geom_bar(position=”fill”)+ theme(axis_text_x = element_text(angle = -90, hjust = 1))+ facet_wrap(‘~Sex’))

1
2
3


(ggplot(df_train_set, aes(x = "Race", fill = "Income"))+ geom_bar(position="fill")+ theme(axis_text_x = element_text(angle = -90, hjust = 1))+ facet_wrap('~Sex'))

直到现在，我们仅关注了非数值特征（non-numeric）的相互关系。现在我们看一下资本收益（CapitalGain）和资本损失（CapitalLoss）对收入的影响。

(ggplot(df_train_set, aes(x=”Income”, y=”CapitalGain”))+ geom_jitter(position=position_jitter(0.1)))

1
2
3


(ggplot(df_train_set, aes(x="Income", y="CapitalLoss"))+ geom_jitter(position=position_jitter(0.1)))

树分类器

现在我们理解了我们数据中的一些关系，所以就可以使用 sklearn.tree.DecisionTreeClassifier 创建一个简单的树分类器模型。然而，为了使用这一模型，我们需要把所有我们的非数值数据转化成数值型数据。我们可以直接在 Pandas 数据框架中使用 sklearn.preprocessing.LabeEncoder 模块和 sklearn_pandas 模块就可以轻松地完成这一步骤。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
mapper = DataFrameMapper([('AgeGroup', LabelEncoder()),('Education', LabelEncoder()),('Workclass', LabelEncoder()),('MaritalStatus', LabelEncoder()),('Occupation', LabelEncoder()),('Relationship', LabelEncoder()),('Race', LabelEncoder()),('Sex', LabelEncoder()),('Income', LabelEncoder())], df_out=True, default=None)

cols = list(df_train_set.columns)
cols.remove("Income")
cols = cols[:-3] + ["Income"] + cols[-3:]

df_train = mapper.fit_transform(df_train_set.copy())
df_train.columns = cols

df_test = mapper.transform(df_test_set.copy())
df_test.columns = cols

cols.remove("Income")
x_train, y_train = df_train[cols].values, df_train["Income"].values
x_test, y_test = df_test[cols].values, df_test["Income"].values

现在我们用正确的形式对数据进行了训练和测试，已创建了我们的第一个模型！

1
2
3
treeClassifier = DecisionTreeClassifier()
treeClassifier.fit(x_train, y_train)
treeClassifier.score(x_test, y_test)

最简单的且没有优化的概率分类器模型可以达到 83.5% 的精度。在分类问题中，混淆矩阵（confusion matrix）是衡量模型精度的好方法。使用下列代码我们可以绘制任意基于树的模型的混淆矩阵。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import itertoolsfrom sklearn.metrics import confusion_matrixdef plot_confusion_matrix(cm, classes, normalize=False):"""
 This function prints and plots the confusion matrix.
 Normalization can be applied by setting `normalize=True`.
 """
 cmap = plt.cm.Blues
 title = "Confusion Matrix"if normalize:
 cm = cm.astype('float') / cm.sum(axis=1)[:, np.newaxis]
 cm = np.around(cm, decimals=3)

 plt.imshow(cm, interpolation='nearest', cmap=cmap)
 plt.title(title)
 plt.colorbar()
 tick_marks = np.arange(len(classes))
 plt.xticks(tick_marks, classes, rotation=45)
 plt.yticks(tick_marks, classes)

 thresh = cm.max() / 2.for i, j in itertools.product(range(cm.shape[0]), range(cm.shape[1])):
 plt.text(j, i, cm[i, j],
 horizontalalignment="center",
 color="white" if cm[i, j] > thresh else "black")

 plt.tight_layout()
 plt.ylabel('True label')
 plt.xlabel('Predicted label')

现在，我们可以看到第一个模型的混淆矩阵：

1
2
3
4
y_pred = treeClassifier.predict(x_test)
cfm = confusion_matrix(y_test, y_pred, labels=[0, 1])
plt.figure(figsize=(10,6))
plot_confusion_matrix(cfm, classes=["<=50K", ">50K"], normalize=True)

我们发现多数类别（<=50K）的精度为 90.5%，少数类别（>50K）的精度只有 60.8%。

让我们看一下调校此简单分类器的方法。我们能使用带有 5 折交叉验证的 GridSearchCV() 来调校树分类器的各种重要参数。

from sklearn.model_selection import GridSearchCVparameters = {‘max_features’:(None, 9, 6),’max_depth’:(None, 24, 16),’min_samples_split’: (2, 4, 8),’min_samples_leaf’: (16, 4, 12)} ```