一、前言
決策樹是最經(jīng)典的機器學習模型之一。它的預測結(jié)果容易理解，易于向業(yè)務部門解釋，預測速度快，可以處理類別型數(shù)據(jù)和連續(xù)型數(shù)據(jù)。在機器學習的數(shù)據(jù)挖掘類求職面試中，決策樹是面試官最喜歡的面試題之一。通過本章讀者可以掌握以下內(nèi)容：
1.信息熵及信息增益的概念，以及決策樹的分裂的原則；
2.決策樹的創(chuàng)建及剪枝算法；
3.scikit-learn中決策樹算法的相關(guān)參數(shù)；
4.使用決策樹預測泰坦尼克號幸存者實例；
5.scikit-learn中模型參數(shù)選擇的工具及使用方法。
二、算法原理
決策樹是一個類似于流程圖的樹結(jié)構(gòu)，分支節(jié)點表示對一個特征進行測試，根據(jù)測試結(jié)果進行分類，數(shù)葉節(jié)點代表一個類別。如下圖所示，我們用決策樹來決定下班后的安排。
我們分別對精力指數(shù)和情緒指數(shù)兩個特征進行測試，并根據(jù)測試結(jié)果決定行為的類別。每選擇一個特征進行測試，數(shù)據(jù)集就被劃分成多個數(shù)據(jù)集。接著繼續(xù)在子數(shù)據(jù)集上選擇特征，并進行數(shù)據(jù)集劃分，直到創(chuàng)建出一個完整的決策樹。創(chuàng)建好決策樹模型后，只要根據(jù)下班后的精力和情緒情況，從根節(jié)點一路往下即可預測出下班后的行為。
問題來了，在創(chuàng)建決策樹的過程中，要先對哪個特征進行分裂？比如對上圖中的例子，先判斷精力指數(shù)進行分裂還是先判斷情緒指數(shù)進行分裂？要回答這個問題，我們要從信息的量化談起。
2.1 信息增益
我們天天在談論信息，那么信息要怎樣來量化呢？1948年，香農(nóng)在他著名的《通信的數(shù)學原理》中提出了信息熵的概念，從而解決了信息的量化問題。香農(nóng)認為，一條信息的信息量和它的不確定性有直接關(guān)系。一個問題不確定性越大，要搞清楚這個問題，需要了解的信息就越多，其信息熵就越大。信息熵的計算公式為：
P(x)表示事件x出現(xiàn)的概率。回到?jīng)Q策樹的構(gòu)建問題上，當我們要構(gòu)建一個決策樹時，應該優(yōu)先選擇哪個特征來劃分數(shù)據(jù)集呢？答案是：遍歷所有的特征，分別計算，使用這個特征劃分數(shù)據(jù)集前后信息熵的變化值，然后選擇信息熵變化幅度最大的那個特征，來優(yōu)先作為數(shù)據(jù)集劃分依據(jù)。即選擇信息增益最大的特征作為分裂節(jié)點。
比如，一個盒子里共有紅、白、黑、藍4種顏色的球共16個，其中紅球2個，白球2個，黑球4個，藍球8個。紅球和黑球的體積一樣，都為1個單位；白球和藍球的體積一樣，都為2個單位。紅球、白球和黑球的質(zhì)量一樣，都是1個單位，藍球的質(zhì)量為2個單位。
我們應該優(yōu)先選擇體積這個特征，還是優(yōu)先選擇質(zhì)量這個特征來作為數(shù)據(jù)集劃分依據(jù)呢？根據(jù)前面介紹的結(jié)論，我們先計算基礎信息熵，即劃分數(shù)據(jù)集前的信息熵。從已知信息容易知道，紅球、白球、黑球、藍球出現(xiàn)的概率分別為2/16、2/16、4/16、8/16，因此基礎信息熵為：
按照體積來劃分數(shù)據(jù)集：
第一個子數(shù)據(jù)集的信息熵為：
第二個子數(shù)據(jù)集的信息熵為：
信息熵為：
信息增益為：
按照質(zhì)量來劃分數(shù)據(jù)集：
第一個子數(shù)據(jù)集的信息熵為：
第二個子數(shù)據(jù)集的信息熵為：
信息熵為：
信息增益為：
由于使用質(zhì)量劃分數(shù)據(jù)集比使用體積劃分數(shù)據(jù)集得到了更高的信息增益，所以我們優(yōu)先選擇質(zhì)量這個特征來劃分數(shù)據(jù)集。
三、算法參數(shù)
scikit-learn使用sklearn.tree.DecisionTreeClassifier類來實現(xiàn)決策樹分類算法。其中幾個典型的參數(shù)解釋如下。
criterion:特征選擇算法。一種是基于信息熵，另外一種是基于基尼不純度。有研究表明，這兩種算法的差異性不大，對模型的準確性沒有太大的影響。相對而言，信息熵運算效率會低一些，因為它有對數(shù)運算。
splitter：創(chuàng)建決策樹分支的選項，一種是選擇最優(yōu)的分支創(chuàng)建原則，另外一種是從排名靠前的特征中，隨機選擇一個特征來創(chuàng)建分支，這個方法和正則項的效果類似，可以避免過擬合問題。
max_depth：指定決策樹的最大深度。通過指定該參數(shù)，用來解決模型過擬合問題。
min_samples_split：這個參數(shù)指定能創(chuàng)建分支的數(shù)據(jù)集的大小，默認是2。如果一個節(jié)點的數(shù)據(jù)樣本個數(shù)小于這個數(shù)值，則不再創(chuàng)建分支。這也是一種前剪枝的方法。
min_samples_leaf：創(chuàng)建分支后的樣本數(shù)量必須大于等于這個數(shù)值，否則不再創(chuàng)建分支。這也是一種前剪枝的方法。
max_leaf_nodes：除了限制最小的樣本節(jié)點個數(shù)，該參數(shù)可以限制最大的樣本節(jié)點個數(shù)。
min_impurity_split：可以使用該參數(shù)來制定信息增益的閾值。決策樹在創(chuàng)建分支時，信息增益必須大于這個閾值，否則不創(chuàng)建分支。
從這些參數(shù)可以看到，scikit-learn有一系列的參數(shù)用來控制決策樹生成的過程，從而解決過擬合問題。其他參數(shù)請參閱scikit-learn官方文檔。
四、預測泰坦尼克號幸存者
眾所周知，泰坦尼克號是歷史上最嚴重的一起海灘事故的主角。我們通過決策樹模型，來預測哪些人可能成為幸存者。
4.1 數(shù)據(jù)分析
train.csv是一個892行、12列的數(shù)據(jù)表格。字段解釋如下：
我們需要加載csv數(shù)據(jù)，并做一些預處理，包括：
（1）提取Survived列的數(shù)據(jù)作為模型的標注數(shù)據(jù)。
（2）丟棄不需要的特征數(shù)據(jù)。
（3）對數(shù)據(jù)進行轉(zhuǎn)換，以便模型處理。比如性別數(shù)據(jù)，我們需要轉(zhuǎn)換0和1。
（4）處理缺失數(shù)據(jù)。比如年齡這個特征，有很多缺失的數(shù)據(jù)。
def read_dataset(fname):
# 指定第一列作為行索引
data = pd.read_csv(fname, index_col=0)
#丟棄無用的數(shù)據(jù)
data.drop(['Name', 'Ticket', 'Cabin'], axis=1, inplace=True)
#處理性別數(shù)據(jù)
data['Sex'] = (data['Sex'] == 'male').astype('int')
#處理登船港口數(shù)據(jù)
labels = data['Embarked'].unique().tolist()
data['Embarked'] = data['Embarked'].apply(lambda n: labels.index(n))
#處理缺失數(shù)據(jù)
data = data.fillna(0)
return data
train = read_dataset('G:/train.csv')
4.2 模型訓練
首先，需要把Survived列提取出來作為標簽，然后在原數(shù)據(jù)集中將其丟棄。同時把數(shù)據(jù)集分成訓練數(shù)據(jù)集和交叉驗證數(shù)據(jù)集。
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的決策樹模型對數(shù)據(jù)進行擬合。
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 優(yōu)化模型參數(shù)
以模型深度max_depth為例，我們先創(chuàng)建一個函數(shù)，它使用不同的模型深度訓練模型，并計算評分數(shù)據(jù)。
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)`
接著構(gòu)造參數(shù)范圍，在這個范圍內(nèi)分別計算模型評分，并找出評分最高的模型所對應的參數(shù)。
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()
可以看到，針對模型深度這個參數(shù)，最優(yōu)的值是3，其對應的交叉驗證數(shù)據(jù)集評分為0.79888.我們還可以把模型參數(shù)和模型評分畫出來，更直觀地觀察其變化規(guī)律。
使用同樣的方法，我們可以考察參數(shù)min_impurity_split。這個參數(shù)用來指定信息熵或基尼不純度的閾值，當決策樹分裂后，其信息熵增益低于這個閾值時，則不再分裂。
# 訓練模型，并計算評分
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)
# 指定參數(shù)范圍，分別訓練模型，并計算評分
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]
# 找出評分最高的模型參數(shù)
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))
# 畫出模型參數(shù)與模型評分的關(guān)系
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 模型參數(shù)選擇工具包
前面介紹的模型參數(shù)優(yōu)化方法有兩個問題：
（1）數(shù)據(jù)不穩(wěn)定，每次重新把數(shù)據(jù)集劃分成訓練數(shù)據(jù)集和交叉驗證數(shù)據(jù)集后，選擇出來的模型參數(shù)就不是最優(yōu)的了。
（2）不能一次選擇多個參數(shù)。如我們想考察max_depth和min_samples_leaf兩個結(jié)合起來的最優(yōu)參數(shù)就沒辦法實現(xiàn)。
scikit-learn在sklearn.model_selection包里提供了大量的模型選擇和評估的工具供我們使用。我們使用GridSearchCV類來解決，下面來選擇一個參數(shù)的最優(yōu)值：
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')
其中關(guān)鍵的參數(shù)是param_grid，它是一個字典，字典關(guān)鍵字所對應的的值是一個列表。GridSearchCV會枚舉列表里的所有制來構(gòu)建模型，多次計算訓練模型，并計算模型評分，最終得出指定參數(shù)值的平均評分及標準差。另一個關(guān)鍵的參數(shù)是cv，它用來制定交叉驗證數(shù)據(jù)集的生成規(guī)則，代碼中的cv=5表示每次計算都把數(shù)據(jù)集分成5份，拿其中一份作為交叉驗證數(shù)據(jù)集，其他作為訓練數(shù)據(jù)集。最終得出的最優(yōu)參數(shù)及最優(yōu)評分保存在clf.best_params_和clf.best_score_里。此外，clf.cv_results_保存了計算過程的所有中間結(jié)果。我們可以拿這個數(shù)據(jù)來畫出模型參數(shù)與評分的關(guān)系圖：
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")
接下來看一下如何在多組參數(shù)之間選擇最優(yōu)的參數(shù)：
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()函數(shù)把決策樹模型參數(shù)導出到文件中，然后使用graphviz工具包生成決策樹示意圖。使用過程中可能出現(xiàn)的問題，可以參考下面的帖子：
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())
生成決策樹示意圖如下
