決策樹（Decision Tree，簡稱DT）是最經典的機器學習模型之一，它的預測結果容易理解，易于向業(yè)務部門解釋，預測速度快，可以處理離散型數(shù)據(jù)和連續(xù)型數(shù)據(jù)。

1.決策樹算法原理

決策樹是一個類似于流程圖的樹結構，分支節(jié)點表示對一個特征進行預測，根據(jù)預測結果進行分類，葉子節(jié)點代表一個類別。如下圖所示，我們用決策樹來決定下班后的安排：

figure7_1.png

我們分別對精力指數(shù)和情緒指數(shù)兩個特征進行測試，并根據(jù)測試結果決定行為的類別。每選擇一個特征進行測試，數(shù)據(jù)集就被劃分成多個子數(shù)據(jù)集。接著繼續(xù)在子數(shù)據(jù)集上選擇特征，并進行數(shù)據(jù)集劃分，直到創(chuàng)建出一個完整的決策樹。創(chuàng)建好決策樹模型后，只要根據(jù)下班后的精力和情緒情況，從根節(jié)點一路往下即可預測出下班后的行為。

問題來了，在創(chuàng)建決策樹的過程中，要先對哪個特征進行分裂？比如上圖中的例子，先判斷精力指數(shù)進行分裂還是先判斷情緒指數(shù)進行分裂？要回答這個問題，我們需要從信息的量化談起。

1.信息增益

我們天天在談論信息，那么信息要怎么樣來量化呢？1948年，香農在他著名的《通信的數(shù)學原理》中提出了信息熵（Entropy）的概念，從而解決了信息的量化問題。香農認為，一條信息的信息量和它的不確定性有直接關系。一個問題不確定性越大，要搞清楚這個問題，需要了解的信息就越多，其信息熵就越大。信息熵的計算公式如下：

其中，P(x)表示事件x出現(xiàn)的概率。例如，一個盒子里分別有5個白球和5個紅球，隨機取出一個球。問：這個球是紅色的還是白色的？這個問題的信息量多大呢？由于紅球和白球出現(xiàn)的概率都是1/2，代入信息熵公式，可以得到其信息熵為：

即，這個問題的信息量就是1bit。對，你沒有看錯，信息量的單位就是比特。我們要確定這個球是紅色的還是白色的，只需要1bit的信息就夠了。再舉一個極端的例子，一個盒子里有10個白球，隨機取出一個球，這個球是什么顏色的？這個問題的信息量是多少呢？答案是0，因為這是一個確定事件，其概率P(x)=1，代入信息熵公式，即可得到其信息熵為0。即我們不需要再獲取任何新的信息，就可知道這個球一定是白色的。

回到決策樹的構建問題上，當我們要構建一個決策樹時，應該優(yōu)先選擇哪個特征來劃分數(shù)據(jù)集呢？答案是：遍歷所有的特征，分別計算，使用這個特征劃分數(shù)據(jù)集前后信息熵的變化值，然后選擇信息熵變化幅度最大的那個特征，來優(yōu)先作為數(shù)據(jù)集劃分依據(jù)。即選擇信息增益最大的特征作為分裂節(jié)點。

比如，一個盒子里共有紅、白、黑、藍4種顏色的球共有16個，其中紅球2個，白球2個，黑球4個，藍球8個。紅球和黑球的體積一樣，都為1個單位；白球和藍球的體積一樣，都為2個單位。紅球、白球和黑球的質量一樣，都是1個單位，藍球的質量為2個單位。

我們應該優(yōu)先選擇體積這個特征還是優(yōu)先選擇質量這個特征來作為數(shù)據(jù)集劃分的依據(jù)呢？根據(jù)前面介紹的結論，我們先計算基礎信息熵，即劃分數(shù)據(jù)集前的信息熵。從已知信息容易知道，紅球、白球、黑球、藍球出現(xiàn)的概率分別為2/16，2/16，4/16，8/16，因此基礎信息熵為：

接著使用體積來劃分數(shù)據(jù)集，此時會劃分出兩個數(shù)據(jù)集，第一個子數(shù)據(jù)集里是紅球和黑球，第二個子數(shù)據(jù)集里是白球和藍球，我們計算這種劃分方式的信息熵。其中，第一個子數(shù)據(jù)集里，紅球2個，黑球4個，其概率分別為2/6，4/6，因此第一個子數(shù)據(jù)集的信息熵為：

第二個子數(shù)據(jù)集里，白球2個，藍球8個，其概率分別是2/10，8/10，因此第二個子數(shù)據(jù)集的信息熵為：

因此，使用體積來劃分數(shù)據(jù)集后，其信息熵為，其信息增益為，如下圖(a)所示：

figure7_2.png

下面來討論信息增益的物理意義。我們以概率P(x)為橫坐標，以信息熵Entropy為縱坐標，把信息熵和概率的函數(shù)關系，在二維坐標軸上畫出來，如下圖所示：

figure7_3.png

熵是熱力學中表征物質狀態(tài)的參量之一，其物理意義是體系混亂程度的度量，被香農借用過來，作為信息量的度量。著名的信息熵增原理是這樣描述的：熵增原理就是孤立熱力學系統(tǒng)的熵不減少，總是增大或者不變。一個孤立的系統(tǒng)不可能朝低熵的狀態(tài)發(fā)展，即不會變的有序。

用白話講就是，如果沒有外力的作用，這個世界將是越來越無序的。人活著，在于盡量讓熵變低，即讓世界變得更有序，降低不確定性。當我們在消費資源時，是一個增熵的過程。我們把有序的事物變成了無序的垃圾。例如我們在寫書或者看書的過程，可以理解為減熵的過程。我們通過寫作和閱讀，減少了不確定的信息，從而實現(xiàn)了減熵的過程。人生價值的實現(xiàn)，在于消費資源（增熵過程）來獲取能量，經過自己的勞動付出（減熵過程），讓世界變得更加純凈有序，信息增益（減熵量 - 增熵量）即是衡量人生價值的尺度。希望我們每個人在暮年之時，回首往事，能自信地說，我給這個世界帶來的信息增益是正數(shù)，且已經盡力做到最大了。

2.決策樹的創(chuàng)建

決策樹的構建過程，就是從訓練數(shù)據(jù)集中歸納出一組分類規(guī)則，使它與訓練數(shù)據(jù)矛盾較小的同時具有較強的泛化能力。有了信息增益來量化地選擇數(shù)據(jù)集的劃分特征，使決策樹的創(chuàng)建過程變得容易了。決策樹的創(chuàng)建基本上分為以下幾個步驟：
（1）計算數(shù)據(jù)集劃分前的信息熵。
（2）遍歷所有未作為劃分條件的特征，分別計算根據(jù)每個特征劃分數(shù)據(jù)集后的信息熵。
（3）選擇信息增益最大的特征，并使用這個特征作為數(shù)據(jù)劃分節(jié)點來劃分數(shù)據(jù)。
（4）遞歸地處理被劃分后的所有子數(shù)據(jù)集，從未被選擇的特征里繼續(xù)選擇最優(yōu)數(shù)據(jù)劃分特征來劃分子數(shù)據(jù)集。

問題來了，遞歸過程什么時候結束呢？一般來講，有兩個終止條件：一是所有的特征都用完了，即沒有新的特征可以用來進一步劃分數(shù)據(jù)集。二是劃分后的信息增益足夠小了，這個時候就可以停止遞歸劃分了。針對這個停止條件，需要事先選擇信息增益的閾值來作為結束遞歸地條件。

使用信息增益作為特征選擇指標的決策樹構建算法，稱為ID3算法。

1.離散化
如果一個特征是連續(xù)值怎么辦呢？就像開頭我們舉過的例子，假如我們有個精力測試儀器，測出來的是一個0到100的數(shù)字，這是個連續(xù)值，這個時候怎么用決策樹來建模呢？答案是：離散化。我們需要對數(shù)據(jù)進行離散化處理。例如：當精力指數(shù)小于等于40時標識為低，當大于40且小于等于70時標識為中，當大于70時標識為高。經過離散處理后，就可以用來構建決策樹了。要離散化成幾個類別，這個往往和具體的業(yè)務相關。

2.正則項
最大化信息增益來選擇特征，在決策樹的構建過程中，容易造成優(yōu)先選擇類別最多的特征來進行分類。舉一個極端的例子，我們把某個產品的唯一標識符ID作為特征之一加入到數(shù)據(jù)集中，那么構建決策樹時，就會優(yōu)先選擇產品ID來作為劃分特征，因為這樣劃分出來的數(shù)據(jù)，每個葉子節(jié)點只有一個樣本，劃分后的子數(shù)據(jù)集最“純凈”，其信息增益最大。

這不是我們希望看到的結果。解決辦法是計算劃分后的子數(shù)據(jù)集的信息熵時，加上一個與類別個數(shù)成正比的正則項來作為最后的信息熵。這樣當算法選擇的某個類別較多的特征，使信息熵較小時，由于受到類別個數(shù)的正則項懲罰，導致最終的信息熵也比較大。這樣通過合適的參數(shù)，可以使算法訓練得到某種程度的平衡。
另外一個解決辦法是使用信息增益比來作為特征選擇的標準。具體可以參考擴展部分的內容。

3.基尼不純度
我們知道，信息熵是衡量信息不確定性的指標，實際上也是衡量信息“純度”的指標。除此之外，基尼不純度（Gini impurity）也是衡量信息不純度的指標，其計算公式是：

其中，是樣本屬于這個類別的概率。如果所有的樣本都屬于一個類別，此時，則，即數(shù)據(jù)不純度最低，純度最高。我們以概率作為橫坐標，以這個類別的基尼不純度作為縱坐標，在坐標軸上畫出其函數(shù)關系，如圖所示：

figure7_4.png

3.剪枝算法

使用決策樹模型擬合數(shù)據(jù)時，容易造成過擬合。解決過擬合的方法是對決策樹進行剪枝處理。決策樹的剪枝有兩種思路：前剪枝（Pre-Pruning）和后剪枝（Post-Pruning）。

1.前剪枝（Pre-Pruning）
前剪枝是在構造決策樹的同時進行剪枝。在決策樹的構建過程中，如果無法進一步降低信息熵，就會停止創(chuàng)建分支。為了避免過擬合，可以設定一個閾值，即使可以繼續(xù)降低信息熵，也停止繼續(xù)創(chuàng)建分支。這種方法稱為前剪枝。還有一些簡單的前剪枝方法，如限制葉子節(jié)點的樣本個數(shù)，當樣本個數(shù)小于一定的閾值時，即不再繼續(xù)創(chuàng)建分支。

2.后剪枝（Post-Pruning）
后剪枝是指決策樹構建完成之后進行剪枝。剪枝的過程是對擁有同樣父節(jié)點的一組節(jié)點進行檢查，判斷如果將其合并，信息熵的增加量是否小于某一閾值。如果小于閾值，則這一組節(jié)點可以合并成一個節(jié)點。后剪枝是目前較普遍的做法。后剪枝的過程是刪除一些子樹，然后用子樹的根節(jié)點代替，來作為新的葉子結點。這個新的葉子節(jié)點所標識的類別通過大多數(shù)原則來確定，即把這個葉子節(jié)點里樣本最多的類別，作為這個葉子節(jié)點的類別。

后剪枝算法有很多種，其中常用的一種稱為降低錯誤率剪枝法（Reduced-Error Pruning）。其思路是，自底向上，從已經構建好的完全決策樹中找出一棵子樹，然后用子樹的根代替這棵子樹，作為新的葉子節(jié)點。葉子節(jié)點所標識的類別通過大多數(shù)原則來確定。這樣就構建出了一個新的簡化版的決策樹。然后使用交叉驗證數(shù)據(jù)集來檢測這棵簡化版的決策樹，看其錯誤率是否降低了。如果錯誤率降低了，則可以使用這個簡化版的決策樹代替完全決策樹。否則，還是采用原來的決策樹。通過遍歷所有的子樹，直到針對交叉驗證數(shù)據(jù)集，無法進一步降低錯誤率為止。

2.決策樹算法參數(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：葉子節(jié)點的最小樣本數(shù)量，葉子節(jié)點的樣本數(shù)量必須大于等于這個值。這也是上面介紹的另一種前剪枝的方法。
• max_leaf_nodes：最大葉子節(jié)點個數(shù)，即數(shù)據(jù)集最多能劃分成幾個類別。
• min_impurity_split：信息增益必須大于等于這個閾值才可以繼續(xù)分支，否則不創(chuàng)建分支。
  從這些參數(shù)可以看出，scikit-learn有一系列的參數(shù)用來控制決策樹的生成過程，從而解決過擬合問題。其他參數(shù)請參閱scikit-learn的官方文檔。

3.實例：預測泰坦尼克號幸存者

眾所周知，泰坦尼克號是歷史上最嚴重的一起海難事故。我們通過決策樹模型，來預測哪些人可能成為幸存者。數(shù)據(jù)集下載https://www.kaggle.com/c/titanic。

數(shù)據(jù)集中總共有兩個文件，都是csv格式的數(shù)據(jù)。其中，train.csv是訓練數(shù)據(jù)集，包含已標注的訓練樣本數(shù)據(jù)。test.csv是模型進行幸存者預測的測試數(shù)據(jù)。我們的任務就是根據(jù)train.csv里的數(shù)據(jù)訓練出決策樹模型，然后使用該模型來預測test.csv里的數(shù)據(jù)，并查看模型的預測效果。

1.數(shù)據(jù)分析

train.csv是一個892行、12列的數(shù)據(jù)表格。意味著我們有891個訓練樣本（扣除表頭），每個樣本有12個特征。我們需要先分析這些特征，以便決定哪些特征可以用來進行模型訓練。

• PassengerId：乘客的ID號，這個是順序編號，用來唯一地標識一名乘客。這個特征和幸存與否無關，丟棄這個特征。
• Survived：1表示幸存，0表示遇難。這是標注數(shù)據(jù)。
• Pclass：倉位等級。這是個很重要的特征，高倉位的乘客能更快的到達甲板，從而更容易獲救。
• Name：乘客的名字，這個特征和幸存與否無關，丟棄這個特征。
• Sex：乘客性別。由于救生艇數(shù)量不夠，船長讓婦女和兒童先上救生艇。所以這也是個很重要的特征。
• Age：乘客的年齡。兒童會優(yōu)先上救生艇，身強力壯者幸存概率也會高一些。所以這也是個很重要的特征。
• SibSp：兄弟姐妹同在船上的數(shù)量。
• Parch：同船的父輩人員的數(shù)量。
• Ticket：乘客的票號。這個特征和幸存與否無關，丟棄這個特征。
• Fare：乘客的體熱指標。
• Cabin：乘客所在的船艙號。實際上這個特征和幸存與否有一定的關系，比如最早被水淹沒的船艙位置，其乘客的幸存概率要低一些。但由于這個特征有大量的丟失數(shù)據(jù)，而且沒有更多的數(shù)據(jù)來對船艙進行歸類，因此我們丟棄這個特征的數(shù)據(jù)。
• Embarked：乘客登船的港口。我們需要把港口數(shù)據(jù)轉換為數(shù)值類型的數(shù)據(jù)。

我們需要加載csv數(shù)據(jù)。并做一些預處理，包括：

• 提取Survived列的數(shù)據(jù)作為模型的標注數(shù)據(jù)。
• 丟棄不需要的特征數(shù)據(jù)。
• 對數(shù)據(jù)進行轉換，以便模型處理。比如把性別數(shù)據(jù)轉換為0和1.
• 處理缺失的數(shù)據(jù)。比如年齡這個特征，有很多缺失的數(shù)據(jù)。

Pandas是完成這些任務的理想軟件包，我們先把數(shù)據(jù)從文件里讀取出來：

import pandas as pd
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('../titanic/train.csv')
train.head()

處理完的數(shù)據(jù)如下：

figure7_5.png

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))

輸出如下：

train dataset: (712, 7); test dataset: (179, 7)

接著，使用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))

輸出如下：

train score: 0.9845505617977528; test score: 0.7877094972067039

從輸出結果可以看出，針對訓練樣本評分很高，但是針對交叉驗證數(shù)據(jù)集評分較低，兩者差距較大。沒錯，這是過擬合現(xiàn)象。解決決策樹過擬合的方法是剪枝，包括前剪枝和后剪枝。不幸的是scikit-learn不支持后剪枝，但是提供了一系列模型參數(shù)進行前剪枝。例如，可以通過max_depth參數(shù)限定決策樹的深度，當決策樹達到限定的深度時，就不再進行分裂了。這樣就可以在一定程度上避免過擬合。

3.優(yōu)化模型參數(shù)

我們可以選擇一系列的參數(shù)值，然后分別計算指定參數(shù)訓練出來的模型的評分。還可以把參數(shù)值和模型評分通過圖形畫出來，以便直觀地發(fā)現(xiàn)兩者之間的關系。

這里以限制決策樹深度max_depth為了來介紹模型參數(shù)的優(yōu)化過程。我們先創(chuàng)建一個函數(shù)，它使用不同的max_depth來訓練模型，并計算模型評分。

# 參數(shù)選擇 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)

接著構造參數(shù)范圍，在這個范圍內分別計算模型評分，并找出評分最高的模型所對應的參數(shù)。

import numpy as np
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(scores)
print('best param: {0}； best score： {1}'.format(best_param,best_score))

輸出如下：

best param: 3； best score： 0.8435754189944135

可以看到，針對模型深度這個參數(shù)，最優(yōu)的值是3，其對應的交叉驗證數(shù)據(jù)集評分為0.84。（你的結果可能跟我不一樣，因為每次劃分數(shù)據(jù)集都是隨機的）我們還可以把模型參數(shù)和對應的模型評分畫出來，更直觀地觀察其變化規(guī)律。

import matplotlib.pyplot as plt
plt.figure(figsize=(6,4),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()

輸出如下：

figure7_6.png

使用同樣的方式，我們可以考察參數(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ù)與模型評分的關系
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()

輸出如下：

best param: 0.002653061224489796; best score: 0.8324022346368715

figure7_7.png

這里把[0,0.005]等分50份，以每個等分點作為信息增益閾值來訓練一次模型?？梢钥吹剑柧殧?shù)據(jù)集的評分急速下降，且訓練評分和測試評分都保持較低水平，說明模型欠擬合。我們可以把決策樹特征選擇的基尼不純度改為信息熵，即把參數(shù)criterion的值改為'entropy'觀察圖形的變化。

...
clf = DecisionTreeClassifier(criterion='entropy', min_impurity_decrease=val)
...

figure7_7_2.png

4.模型參數(shù)選擇工具包

上面的模型參數(shù)優(yōu)化過程存在兩個問題。其一，數(shù)據(jù)不穩(wěn)定，即數(shù)據(jù)集每次都是隨機劃分的，選擇出來的最優(yōu)參數(shù)在下一次運行時就不是最優(yōu)的了。其二，不能一次選擇多個參數(shù)，例如，想要考察max_depth和min_samples_leaf兩個結合起來的最優(yōu)參數(shù)就無法實現(xiàn)。

問題一的原因是，每次把數(shù)據(jù)集劃分為訓練樣本和交叉驗證樣本時，是隨機劃分的，這樣導致每次的訓練數(shù)據(jù)集是有差異的，訓練出來的模型也有差異。解決這個問題的方法是多次計算，求平均值。具體來講，就是針對模型的某個特定的參數(shù)，多次劃分數(shù)據(jù)集，多次訓練模型，計算出這個參數(shù)對應的模型的最低評分、最高評分以及評價評分。問題二的解決辦法比較簡單，把代碼再優(yōu)化一下，能處理多個參數(shù)組合即可。

所幸，我們不需要從頭實現(xiàn)這些代碼。scikit-learn在sklearn.model_selection包里提供了大量模型選擇和評估工具供我們使用。針對以上問題，可以使用GridSearchCV類來解決。下面先看一下使用GridSearchCV選擇一個參數(shù)的最優(yōu)值。

from sklearn.model_selection import GridSearchCV
thresholds = np.linspace(0,0.5,50)
param_grid = {'min_impurity_split':thresholds}
clf = GridSearchCV(DecisionTreeClassifier(),param_grid,cv=5)
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')

輸出如下：

best param: {'min_impurity_split': 0.21428571428571427}
best score: 0.8215488215488216

其中關鍵的參數(shù)是param_grid，它是一個字典，鍵對應的值是一個列表。GridSearchCV會枚舉列表里的所有值來構建模型，最終得出指定參數(shù)值的平均評分及標準差。另外一個關鍵參數(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_保存了計算過程的所有中間結果。我們可以拿這個數(shù)據(jù)來畫出模型參數(shù)與模型評分的關系圖，如下所示。

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=(6,4),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')

figure7_8.png

接下來看一下如何在多組參數(shù)之間選擇最優(yōu)的參數(shù)組合：

from sklearn.model_selection import GridSearchCV
entropy_thresholds = np.linspace(0,1,50)
gini_thresholds = np.linspace(0,0.5,50)
param_grid = [{'criterion':['entropy'],'min_impurity_split':entropy_thresholds},
              {'criterion':['gini'],'min_impurity_split':gini_thresholds},
              {'max_depth':range(2,10)},
              {'min_samples_split':range(2,30,2)}]
clf=GridSearchCV(DecisionTreeClassifier(),param_grid,cv=5)
clf.fit(X,y)
print('best param: {0}\nbest score: {1}'.format(clf.best_params_,clf.best_score_))

輸出如下：

best param: {'criterion': 'entropy', 'min_impurity_split': 0.5306122448979591}
best score: 0.8260381593714927

代碼關鍵部分還是param_grid參數(shù)，它是一個列表，列表中的每個元素都是字典。例如：針對列表中的第一個字典，選擇信息熵作為決策樹特征選擇的判斷標準，同時其閾值范圍是[0,1]之間分了50等份。GridSearchCV會針對列表中的每個字典進行迭代，最終比較列表中每個字典所對應的參數(shù)組合，選擇出最優(yōu)的參數(shù)。關于GridSearchCV的更多詳情可參考官方文檔。

最后基于好奇，使用最優(yōu)參數(shù)的決策樹到底是什么樣呢？我們可以使用sklearn.tree.export_graphviz()函數(shù)把決策樹模型導出到文件中，然后使用graphviz工具包生成決策樹示意圖。

from sklearn.tree import export_graphviz
clf = DecisionTreeClassifier(criterion='entropy', min_impurity_split=0.5306122448979591)
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))

columns = train.columns[1:]
# 導出 titanic.dot 文件
with open("E:/titanic.dot", 'w') as f:
    f = export_graphviz(clf, out_file=f,feature_names=columns)

# 1. conda安裝 graphviz ：conda install python-graphviz 
# 2. 運行 `dot -Tpng titanic.dot -o titanic.png` 
# 3. 在當前目錄查看生成的決策樹 titanic.png

我們最優(yōu)參數(shù)的決策樹就長這個樣子：

titanic.png

4.拓展閱讀

1.熵和條件熵

在決策樹創(chuàng)建過程中，我們會計算以某個特征創(chuàng)建分支后的子數(shù)據(jù)集的信息熵。用數(shù)學語言描述實際上是計算條件熵，即滿足某個條件的信息熵。

關于信息熵和條件熵的相關概念，可以閱讀吳軍老師的《數(shù)學之美》里"信息的度量和作用"一文?！稊?shù)學之美》這本書，吳軍老師用平實的語言，把復雜的數(shù)學概念解釋的入木三分，即使你只有高中的數(shù)學水平，也可以領略到數(shù)學的“優(yōu)雅”和“威力”。

2.決策樹的構建算法

本文重點介紹的決策樹構建算法是ID3算法，它是1986年由Ross Quinlan提出的。1993年，該算法作者發(fā)布了新的決策樹構建算法C4.5，作為ID3算法的改進，主要體現(xiàn)在：

• 增加了對連續(xù)值的處理，方法是使用一個閾值作為連續(xù)值的劃分條件，從而把數(shù)據(jù)離散化。
• 自動處理特征值缺失問題，處理方法是直接把這個特征拋棄，不參與計算信息增益比。
• 使用信息增益比作為特征選擇標準。
• 采用后剪枝算法處理過擬合，即在決策樹創(chuàng)建完成之后，再通過合并葉子節(jié)點的方式進行剪枝。

此后，該算法作者又發(fā)布了改進的商業(yè)版本C5.0，它運算效率更高，使用內存更小，創(chuàng)建出來的決策樹更小，并且準確性更高，適合大數(shù)據(jù)集的決策樹構建。

除了前面介紹的使用基尼不純度來構建決策樹的CART算法之外，還有其他知名的決策樹構建算法，如CHAID算法、MARS算法等。這里不再詳述。

5.集合算法

集合算法（Ensemble）是一種元算法（Meta-algorithm），它利用統(tǒng)計學采樣原理，訓練出成百上千個不同的算法模型。當需要預測一個新樣本時，使用這些模型分別對這個樣本進行預測，然后采樣少數(shù)服從多數(shù)的原則，決定新樣本的類別。集合算法可以有效地解決過擬合問題。在scikit-learn里，所有的集合算法都實現(xiàn)在sklearn.ensemble包里。

1.自助聚合算法Bagging

自助聚合（Bagging，Bootstrap Aggregating的縮寫）的核心思想是，采用有放回的采樣規(guī)則，從m個樣本的原數(shù)據(jù)集里進行n次采樣（n<=m），構成一個包含n個樣本的新訓練數(shù)據(jù)集。重復這個過程B次，得到B個模型，當有新樣本需要預測時，拿這B個模型分別對這個樣本進行預測，然后采用投票方式（回歸問題）得到新樣本的預測值。

所謂的有放回采樣規(guī)則是指，在m個數(shù)據(jù)集里，隨機取出一個樣本放到新數(shù)據(jù)集里，然后把這個樣本放回到原數(shù)據(jù)集里，繼續(xù)隨機采樣，直到到達采樣次數(shù)n為止。由此可見，隨機采樣出的數(shù)據(jù)集里可能有重復數(shù)據(jù)，并且原數(shù)據(jù)集的每一個數(shù)據(jù)不一定都出現(xiàn)在新數(shù)據(jù)集里。

單一模型往往容易對數(shù)據(jù)噪聲敏感，從而造成高方差（High Variance）。自助聚合算法可以降低對數(shù)據(jù)噪聲的敏感性，從而提高模型準確性和穩(wěn)定性。這種方法不需要額外的輸入，只是簡單地對同一個數(shù)據(jù)集訓練出多個模型即可實現(xiàn)。當然這并不是說沒有代價，自助聚合算法一般會增加模型訓練的計算量。

在scikit-learn里，由BaggingClassifier類和BaggingRegressor類分別實現(xiàn)了分類和回歸的Bagging算法。

2.正向激勵算法Boosting

正向激勵算法（Boosting）的基本原理是，初始化時，針對有m個訓練樣本的數(shù)據(jù)集，給每個樣本都分配一個初始權重，然后使用這個帶有權重的數(shù)據(jù)集來訓練模型。訓練出模型之后，針對這個模型預測錯誤的那些樣本，增加其權重，然后拿這個更新過權重的數(shù)據(jù)集來訓練出一個新的模型。重復這個過程B次，就可以訓練出B個模型。

Boosting算法和Bagging算法的區(qū)別如下：

• 采樣規(guī)則不同：Bagging算法是采樣有放回的隨機采樣規(guī)則。而Boosting算法是使用增加預測錯誤樣本權重的方法，相當于加強了對預測錯誤的樣本的學習力度，從而提高模型的準確性。
• 訓練方式不同：Bagging算法可以并行訓練多個模型。而Boosting算法只能串行訓練，因為下一個模型依賴上一個模型的預測結果。
• 模型權重不同：Bagging算法訓練出來的B個模型的權重是一樣的。而Boosting算法訓練出來的B個模型本身帶有權重信息，在對新樣本進行預測時，每個模型的權重是不一樣的。單個模型的權重由模型訓練的效果來決定，即準確性高的模型權重更高。

Boosting算法有很多種實現(xiàn)，其中最著名的是AdaBoosting算法。在scikit-learn里由AdaBoostingClassifier類和AdaBoostingRegression類分別實現(xiàn)Boosting分類和Boosting回歸。

3.隨機森林

隨機森林（RF，Random Forest）在自助聚合算法（Bagging）的基礎上更進一步，對特征應用自助聚合算法。即，每次訓練時，不拿所有的特征來訓練，而是隨機選擇一個特征的子集來進行訓練。隨機森林算法有兩個關鍵參數(shù)，一是構建的決策樹的個數(shù)t，二是構建單棵決策樹特征的個數(shù)f。

假設，針對一個有m個樣本、n個特征的數(shù)據(jù)集，則其算法原理如下：
（1）單棵決策樹的構建

• 采用有放回采樣，從原數(shù)據(jù)集中經過m次采樣，獲取到一個m個樣本的數(shù)據(jù)集（這個數(shù)據(jù)集里可能有重復的樣本）
• 從n個特征里，采用無放回采樣規(guī)則，從中取出f個特征作為輸入特征。
• 重復上述過程t次，構建出t棵決策樹。

（2）隨機森林的分類結果
生成t棵決策樹之后，對于每個新的測試樣例，集合多棵決策樹的預測結果來作為隨機森林的預測結果。具體為，如果是回歸問題，取t棵決策樹的預測值的平均值作為隨機森林的預測結果；如果是分類問題，采取少數(shù)服從多數(shù)的原則，取單棵決策樹預測最多的那個類別作為隨機森林的分類結果。

思考：為什么隨機森林要選取特征的子集來構建決策樹？
假如某個輸入特征對預測結果是強關聯(lián)的，那么如果選擇全部的特征來構建決策樹，這個特征都會體現(xiàn)在所有的決策樹里面。由于這個特征和預測結果強關聯(lián)，會造成所有的決策樹都強烈地反映這個特征的“傾向性”，從而導致無法很好地解決過擬合問題。我們在討論線性回歸算法時，通過增加正則項來解決過擬合，它的原理就是確保每個特征都對預測結果有少量的貢獻，從而避免單個特征對預測結果有過大貢獻導致的過擬合問題。這里的原理是一樣的。

在scikit-learn里由RandomForestClassifier類和RandomForestRegression類分別實現(xiàn)隨機森林的分類算法和隨機森林的回歸算法。

4.ExtraTrees算法

ExtraTrees，叫做極限樹或者極端隨機樹。隨機森林在構建決策樹的過程中，會使用信息熵或者基尼不純度，然后選擇信息增益最大的特征來進行分裂。而ExtraTrees是直接從所有特征里隨機選擇一個特征來分裂，從而避免了過擬合問題。

在scikit-learn里，由ExtraTreesClassifier類和ExtraTreesRegression類分別實現(xiàn)ExtraTrees的分類算法和ExtraTrees的回歸算法。