一、前言
决策树是最经典的机器学习模型之一。它的预测结果容易理解，易于向业务部门解释，预测速度快，可以处理类别型数据和连续型数据。在机器学习的数据挖掘类求职面试中，决策树是面试官最喜欢的面试题之一。通过本章读者可以掌握以下内容：
1.信息熵及信息增益的概念，以及决策树的分裂的原则；
2.决策树的创建及剪枝算法；
3.scikit-learn中决策树算法的相关参数；
4.使用决策树预测泰坦尼克号幸存者实例；
5.scikit-learn中模型参数选择的工具及使用方法。
二、算法原理
决策树是一个类似于流程图的树结构，分支节点表示对一个特征进行测试，根据测试结果进行分类，数叶节点代表一个类别。如下图所示，我们用决策树来决定下班后的安排。
我们分别对精力指数和情绪指数两个特征进行测试，并根据测试结果决定行为的类别。每选择一个特征进行测试，数据集就被划分成多个数据集。接着继续在子数据集上选择特征，并进行数据集划分，直到创建出一个完整的决策树。创建好决策树模型后，只要根据下班后的精力和情绪情况，从根节点一路往下即可预测出下班后的行为。
问题来了，在创建决策树的过程中，要先对哪个特征进行分裂？比如对上图中的例子，先判断精力指数进行分裂还是先判断情绪指数进行分裂？要回答这个问题，我们要从信息的量化谈起。
2.1 信息增益
我们天天在谈论信息，那么信息要怎样来量化呢？1948年，香农在他著名的《通信的数学原理》中提出了信息熵的概念，从而解决了信息的量化问题。香农认为，一条信息的信息量和它的不确定性有直接关系。一个问题不确定性越大，要搞清楚这个问题，需要了解的信息就越多，其信息熵就越大。信息熵的计算公式为：
P(x)表示事件x出现的概率。回到决策树的构建问题上，当我们要构建一个决策树时，应该优先选择哪个特征来划分数据集呢？答案是：遍历所有的特征，分别计算，使用这个特征划分数据集前后信息熵的变化值，然后选择信息熵变化幅度最大的那个特征，来优先作为数据集划分依据。即选择信息增益最大的特征作为分裂节点。
比如，一个盒子里共有红、白、黑、蓝4种颜色的球共16个，其中红球2个，白球2个，黑球4个，蓝球8个。红球和黑球的体积一样，都为1个单位；白球和蓝球的体积一样，都为2个单位。红球、白球和黑球的质量一样，都是1个单位，蓝球的质量为2个单位。
我们应该优先选择体积这个特征，还是优先选择质量这个特征来作为数据集划分依据呢？根据前面介绍的结论，我们先计算基础信息熵，即划分数据集前的信息熵。从已知信息容易知道，红球、白球、黑球、蓝球出现的概率分别为2/16、2/16、4/16、8/16，因此基础信息熵为：
按照体积来划分数据集：
第一个子数据集的信息熵为：
第二个子数据集的信息熵为：
信息熵为：
信息增益为：
按照质量来划分数据集：
第一个子数据集的信息熵为：
第二个子数据集的信息熵为：
信息熵为：
信息增益为：
由于使用质量划分数据集比使用体积划分数据集得到了更高的信息增益，所以我们优先选择质量这个特征来划分数据集。
三、算法参数
scikit-learn使用sklearn.tree.DecisionTreeClassifier类来实现决策树分类算法。其中几个典型的参数解释如下。
criterion:特征选择算法。一种是基于信息熵，另外一种是基于基尼不纯度。有研究表明，这两种算法的差异性不大，对模型的准确性没有太大的影响。相对而言，信息熵运算效率会低一些，因为它有对数运算。
splitter：创建决策树分支的选项，一种是选择最优的分支创建原则，另外一种是从排名靠前的特征中，随机选择一个特征来创建分支，这个方法和正则项的效果类似，可以避免过拟合问题。
max_depth：指定决策树的最大深度。通过指定该参数，用来解决模型过拟合问题。
min_samples_split：这个参数指定能创建分支的数据集的大小，默认是2。如果一个节点的数据样本个数小于这个数值，则不再创建分支。这也是一种前剪枝的方法。
min_samples_leaf：创建分支后的样本数量必须大于等于这个数值，否则不再创建分支。这也是一种前剪枝的方法。
max_leaf_nodes：除了限制最小的样本节点个数，该参数可以限制最大的样本节点个数。
min_impurity_split：可以使用该参数来制定信息增益的阈值。决策树在创建分支时，信息增益必须大于这个阈值，否则不创建分支。
从这些参数可以看到，scikit-learn有一系列的参数用来控制决策树生成的过程，从而解决过拟合问题。其他参数请参阅scikit-learn官方文档。
四、预测泰坦尼克号幸存者
众所周知，泰坦尼克号是历史上最严重的一起海滩事故的主角。我们通过决策树模型，来预测哪些人可能成为幸存者。
4.1 数据分析
train.csv是一个892行、12列的数据表格。字段解释如下：
我们需要加载csv数据，并做一些预处理，包括：
（1）提取Survived列的数据作为模型的标注数据。
（2）丢弃不需要的特征数据。
（3）对数据进行转换，以便模型处理。比如性别数据，我们需要转换0和1。
（4）处理缺失数据。比如年龄这个特征，有很多缺失的数据。
def read_dataset(fname):
# 指定第一列作为行索引
data = pd.read_csv(fname, index_col=0)
#丢弃无用的数据
data.drop(['Name', 'Ticket', 'Cabin'], axis=1, inplace=True)
#处理性别数据
data['Sex'] = (data['Sex'] == 'male').astype('int')
#处理登船港口数据
labels = data['Embarked'].unique().tolist()
data['Embarked'] = data['Embarked'].apply(lambda n: labels.index(n))
#处理缺失数据
data = data.fillna(0)
return data
train = read_dataset('G:/train.csv')
4.2 模型训练
首先，需要把Survived列提取出来作为标签，然后在原数据集中将其丢弃。同时把数据集分成训练数据集和交叉验证数据集。
from sklearn.model_selection import train_test_split
y = train['Survived'].values
X = train.drop(['Survived'], axis=1).values
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2)
print('train dataset: {0}; test dataset: {1}'.format(
X_train.shape, X_test.shape))
笔者计算机上的输出如下：
接下来，使用scikit-learn的决策树模型对数据进行拟合。
from sklearn.tree import DecisionTreeClassifier
clf = DecisionTreeClassifier()
clf.fit(X_train, y_train)
train_score = clf.score(X_train, y_train)
test_score = clf.score(X_test, y_test)
print('train score: {0}; test score: {1}'.format(train_score, test_score))
笔者计算机上的输出如下：
4.3 优化模型参数
以模型深度max_depth为例，我们先创建一个函数，它使用不同的模型深度训练模型，并计算评分数据。
def cv_score(d):
clf = DecisionTreeClassifier(max_depth=d)
clf.fit(X_train, y_train)
tr_score = clf.score(X_train, y_train)
cv_score = clf.score(X_test, y_test)
return (tr_score, cv_score)`
接着构造参数范围，在这个范围内分别计算模型评分，并找出评分最高的模型所对应的参数。
depths = range(2, 15)
scores = [cv_score(d) for d in depths]
tr_scores = [s[0] for s in scores]
cv_scores = [s[1] for s in scores]
best_score_index = np.argmax(cv_scores)
best_score = cv_scores[best_score_index]
best_param = depths[best_score_index]
print('best param: {0}; best score: {1}'.format(best_param, best_score))
plt.figure(figsize=(10, 6), dpi=144)
plt.grid()
plt.xlabel('max depth of decision tree')
plt.ylabel('score')
plt.plot(depths, cv_scores, '.g-', label='cross-validation score')
plt.plot(depths, tr_scores, '.r--', label='training score')
plt.legend()
可以看到，针对模型深度这个参数，最优的值是3，其对应的交叉验证数据集评分为0.79888.我们还可以把模型参数和模型评分画出来，更直观地观察其变化规律。
使用同样的方法，我们可以考察参数min_impurity_split。这个参数用来指定信息熵或基尼不纯度的阈值，当决策树分裂后，其信息熵增益低于这个阈值时，则不再分裂。
# 训练模型，并计算评分
def cv_score(val):
clf = DecisionTreeClassifier(criterion='gini', min_impurity_decrease=val)
clf.fit(X_train, y_train)
tr_score = clf.score(X_train, y_train)
cv_score = clf.score(X_test, y_test)
return (tr_score, cv_score)
# 指定参数范围，分别训练模型，并计算评分
values = np.linspace(0, 0.005, 50)
scores = [cv_score(v) for v in values]
tr_scores = [s[0] for s in scores]
cv_scores = [s[1] for s in scores]
# 找出评分最高的模型参数
best_score_index = np.argmax(cv_scores)
best_score = cv_scores[best_score_index]
best_param = values[best_score_index]
print('best param: {0}; best score: {1}'.format(best_param, best_score))
# 画出模型参数与模型评分的关系
plt.figure(figsize=(10, 6), dpi=144)
plt.grid()
plt.xlabel('threshold of entropy')
plt.ylabel('score')
plt.plot(values, cv_scores, '.g-', label='cross-validation score')
plt.plot(values, tr_scores, '.r--', label='training score')
plt.legend()
笔者计算机上的输出如下：
4.4 模型参数选择工具包
前面介绍的模型参数优化方法有两个问题：
（1）数据不稳定，每次重新把数据集划分成训练数据集和交叉验证数据集后，选择出来的模型参数就不是最优的了。
（2）不能一次选择多个参数。如我们想考察max_depth和min_samples_leaf两个结合起来的最优参数就没办法实现。
scikit-learn在sklearn.model_selection包里提供了大量的模型选择和评估的工具供我们使用。我们使用GridSearchCV类来解决，下面来选择一个参数的最优值：
from sklearn.model_selection import GridSearchCV
thresholds = np.linspace(0, 0.005, 50)
# Set the parameters by cross-validation
param_grid = {'min_impurity_decrease': thresholds}
clf = GridSearchCV(DecisionTreeClassifier(), param_grid, cv=5, return_train_score=True)
clf.fit(X, y)
print("best param: {0}\nbest score: {1}".format(clf.best_params_,
clf.best_score_))
plot_curve(thresholds, clf.cv_results_, xlabel='gini thresholds')
其中关键的参数是param_grid，它是一个字典，字典关键字所对应的的值是一个列表。GridSearchCV会枚举列表里的所有制来构建模型，多次计算训练模型，并计算模型评分，最终得出指定参数值的平均评分及标准差。另一个关键的参数是cv，它用来制定交叉验证数据集的生成规则，代码中的cv=5表示每次计算都把数据集分成5份，拿其中一份作为交叉验证数据集，其他作为训练数据集。最终得出的最优参数及最优评分保存在clf.best_params_和clf.best_score_里。此外，clf.cv_results_保存了计算过程的所有中间结果。我们可以拿这个数据来画出模型参数与评分的关系图：
def plot_curve(train_sizes, cv_results, xlabel):
train_scores_mean = cv_results['mean_train_score']
train_scores_std = cv_results['std_train_score']
test_scores_mean = cv_results['mean_test_score']
test_scores_std = cv_results['std_test_score']
plt.figure(figsize=(10, 6), dpi=144)
plt.title('parameters turning')
plt.grid()
plt.xlabel(xlabel)
plt.ylabel('score')
plt.fill_between(train_sizes,
train_scores_mean - train_scores_std,
train_scores_mean + train_scores_std,
alpha=0.1, color="r")
plt.fill_between(train_sizes,
test_scores_mean - test_scores_std,
test_scores_mean + test_scores_std,
alpha=0.1, color="g")
plt.plot(train_sizes, train_scores_mean, '.--', color="r",
label="Training score")
plt.plot(train_sizes, test_scores_mean, '.-', color="g",
label="Cross-validation score")
plt.legend(loc="best")
接下来看一下如何在多组参数之间选择最优的参数：
from sklearn.model_selection import GridSearchCV
entropy_thresholds = np.linspace(0, 0.01, 50)
gini_thresholds = np.linspace(0, 0.005, 50)
# Set the parameters by cross-validation
param_grid = [{'criterion': ['entropy'],
'min_impurity_decrease': entropy_thresholds},
{'criterion': ['gini'],
'min_impurity_decrease': gini_thresholds},
{'max_depth': range(2, 10)},
{'min_samples_split': range(2, 30, 2)}]
clf = GridSearchCV(DecisionTreeClassifier(), param_grid, cv=5, return_train_score=True)
clf.fit(X, y)
print("best param: {0}\nbest score: {1}".format(clf.best_params_,
clf.best_score_))
五、 生成决策树
我们可以使用sklearn.tree.export_graphviz()函数把决策树模型参数导出到文件中，然后使用graphviz工具包生成决策树示意图。使用过程中可能出现的问题，可以参考下面的帖子：
pydotplus安装
GraphVizs安装
from sklearn import tree
import sys
import os
os.environ["PATH"] += os.pathsep + 'G:/graphviz-2.38/release/bin/' #注意修改你的路径
import pydotplus
from IPython.display import Image
clf = DecisionTreeClassifier(criterion='entropy', min_impurity_decrease=0.004897959183673469)
clf.fit(X_train, y_train)
train_score = clf.score(X_train, y_train)
test_score = clf.score(X_test, y_test)
print('train score: {0}; test score: {1}'.format(train_score, test_score))
# 导出 titanic.dot 文件
with open("G:/titanic.dot", 'w') as f:
f = export_graphviz(clf, out_file=f)
dot_data = tree.export_graphviz(clf, out_file=None,
filled=True, rounded=True,
special_characters=True)
graph = pydotplus.graph_from_dot_data(dot_data)
Image(graph.create_png())
生成决策树示意图如下
