從決策樹到隨機森林：樹型算法的原理與實現(xiàn)

2016iamkousyou 2017-08-01

展開全文

選自Github.io

作者：Sadanand Singh

機器之心編譯

基于樹（Tree based）的學(xué)習(xí)算法在數(shù)據(jù)科學(xué)競賽中是相當常見的。這些算法給預(yù)測模型賦予了準確性,、穩(wěn)定性以及易解釋性,。和線性模型不同,，它們對非線性關(guān)系也能進行很好的映射。常見的基于樹的模型有：決策樹（decision trees）,、隨機森林（random forest）和提升樹（boosted trees）,。

在本篇文章中，我們將會介紹決策樹的數(shù)學(xué)細節(jié)（以及各種 Python 示例）及其優(yōu)缺點,。你們將會發(fā)現(xiàn)它們很簡單,，并且這些內(nèi)容有助于理解。然而,，與最好的監(jiān)督學(xué)習(xí)方法相比,，它們通常是沒有競爭力的。為了克服決策樹的各種缺點,，我們將會聚焦于各種概念（附有 Python 實例）,，比如自助聚集或袋裝（Bootstrap Aggregating or Bagging），還有隨機森林（Random Forests）,。另一種廣泛使用的提升方法會在以后進行單獨討論,。每種方法都包括生成多種樹,，這些樹被聯(lián)合起來，生成一個單一的一致性預(yù)測結(jié)果,，并且經(jīng)常帶來預(yù)測精度的顯著提升,。

決策樹

決策樹是一種監(jiān)督學(xué)習(xí)算法。它適用于類別和連續(xù)輸入（特征）和輸出（預(yù)測）變量,?；跇涞姆椒ò烟卣骺臻g劃分成一系列矩形，然后給每一個矩形安置一個簡單的模型（像一個常數(shù)）,。從概念上來講,，它們是簡單且有效的。首先我們通過一個例子來理解決策樹,。然后用一種正規(guī)分析方法來分析創(chuàng)建決策樹的過程,。考慮一個簡單的借貸公司顧客的數(shù)據(jù)集合,。我們給定了所有客戶的查詢賬戶余額,、信用記錄、任職年限和先前貸款狀況,。相關(guān)任務(wù)是預(yù)測顧客的風(fēng)險等級是否可信,。該問題可以使用下列決策樹來解決：

分類和回歸樹（簡稱 CART）是 Leo Breiman 引入的術(shù)語，指用來解決分類或回歸預(yù)測建模問題的決策樹算法,。它常使用 scikit 生成并實現(xiàn)決策樹： sklearn.tree.DecisionTreeClassifier 和 sklearn.tree.DecisionTreeRegressor 分別構(gòu)建分類和回歸樹,。

CART 模型

CART 模型包括選擇輸入變量和那些變量上的分割點，直到創(chuàng)建出適當?shù)臉?。使用貪婪算法（greedy algorithm）選擇使用哪個輸入變量和分割點,，以使成本函數(shù)（cost function）最小化。

樹建造的結(jié)尾使用了一個預(yù)定義的停止準則,，比如分配到樹上每一個葉結(jié)點的訓(xùn)練樣本達到最小數(shù)量,。

其他決策樹算法：

ID3：Iterative Dichotomiser 3
C4.5：ID3 算法的改進
CHAID：Chi-squared Automatic Interaction Detector
MARS：決策樹的擴展式，以更好地解決數(shù)值型預(yù)測,。
條件推斷樹

回歸樹

我們現(xiàn)在關(guān)注一下回歸樹的 CART 算法的細節(jié),。簡要來說，創(chuàng)建一個決策樹包含兩步：

1. 把預(yù)測器空間,，即一系列可能值 X_1,，X_2，...,，X_p 分成 J 個不同的且非重疊的區(qū)域 R_1，R_2,，...,，R_J。

2. 對進入?yún)^(qū)域 R_J 的每一個樣本觀測值都進行相同的預(yù)測，該預(yù)測就是 R_J 中訓(xùn)練樣本預(yù)測值的均值,。

為了創(chuàng)建 J 個區(qū)域 R_1,，R_2，...,，R_J,，預(yù)測器區(qū)域被分為高維度的矩形或盒形。其目的在于通過下列式子找到能夠使 RSS 最小化的盒形區(qū)域 R_1,，R_2,，...，R_J,，

其中,，yhat_Rj 即是第 j 個盒形中訓(xùn)練觀測的平均預(yù)測值。

鑒于這種空間分割在計算上是不可行的,，因此我們常使用貪婪方法（greedy approach）來劃分區(qū)域,，叫做遞歸二元分割（recursive binary splitting）。

它是貪婪的（greedy）,，這是因為在創(chuàng)建樹過程中的每一步驟,，最佳分割都會在每個特定步驟選定，而不是對未來進行預(yù)測,，并選取一個將會在未來步驟中出現(xiàn)且有助于創(chuàng)建更好的樹的分隔,。注意所有的劃分區(qū)域 R_j 都是矩形。為了進行遞歸二元分割,，首先選取預(yù)測器 X_j 和切割點 s

其中 yhat_R1 為區(qū)域 R_1(j,s) 中觀察樣本的平均預(yù)測值,，yhat_R2 為區(qū)域 R_2(j,s) 的觀察樣本預(yù)測均值。這一過程不斷重復(fù)以搜尋最好的預(yù)測器和切分點,，并進一步分隔數(shù)據(jù)以使每一個子區(qū)域內(nèi)的 RSS 最小化,。然而，我們不會分割整個預(yù)測器空間,，我們只會分割一個或兩個前面已經(jīng)認定的區(qū)域,。這一過程會一直持續(xù)，直到達到停止準則,，例如我們可以設(shè)定停止準則為每一個區(qū)域最多包含 m 個觀察樣本,。一旦我們創(chuàng)建了區(qū)域 R_1、R_2,、...,、R_J，給定一個測試樣本,，我們就可以用該區(qū)域所有訓(xùn)練樣本的平均預(yù)測值來預(yù)測該測試樣本的值,。

分類樹

分類樹和回歸樹十分相似,，只不過它是定性地預(yù)測響應(yīng)值而非定量預(yù)測。從上文可知,，回歸樹對一個觀察值所預(yù)測的連續(xù)型數(shù)值就是屬于同一葉結(jié)點訓(xùn)練樣本觀察值的均值,。但是對于分類樹來說，我們所預(yù)測的類別是訓(xùn)練樣本觀察值在某區(qū)域下最常見的類別,，即訓(xùn)練觀察值的模式響應(yīng)（mode response）,。為了達到分類目的，很多時候系統(tǒng)并不會只預(yù)測一個類別,，它常常預(yù)測一組類別及其出現(xiàn)的概率,。

分類樹的生成和回歸樹的生成十分相似。正如在回歸樹中那樣,，我們一般使用遞歸性的二元分割來生成分類樹,。然而在分類樹中，RSS 不能作為二元分割的標準,。我們需要定義葉結(jié)點的不純度量 Q_m 來替代 RSS,，即一種可以在子集區(qū)域 R_1,R_2,...,R_j 度量目標變量同質(zhì)性的方法。在結(jié)點 m 中,，我們可以通過 N_m 個樣本觀察值表示一個區(qū)域 R_m 所出現(xiàn)類別的頻率,，第 k 個類別在第 m 個區(qū)域下訓(xùn)練所出現(xiàn)的頻率可表示為：

其中，I(y_i=k) 為指示函數(shù),，即如果 y_i = k,，則取 1，否則取零,。

不純性度量 Q_m 一個比較自然的方法是分類誤差率,。分類誤差率描述的是訓(xùn)練觀察值在某個區(qū)域內(nèi)不屬于最常見類別的概率：

考慮到該函數(shù)不可微，因此它不能實現(xiàn)數(shù)值優(yōu)化,。此外,，該函數(shù)在結(jié)點概率改變上并不敏感，因此這種分類誤差率對于生成樹十分低效,。我們一般使用 Gini 指數(shù)和交叉熵函數(shù)來衡量結(jié)點的誤差度量,。

Gini 指數(shù)可以衡量 k 個類別的總方差，它一般定義為：

較小的 Gini 指數(shù)值表示結(jié)點包含了某個類別大多數(shù)樣本觀察值,。

在信息論里面,，交叉熵函數(shù)用來衡量系統(tǒng)的混亂度。對于二元系統(tǒng)來說,，如果系統(tǒng)包含了一個類別的所有內(nèi)容,，那么它的值為零，而如果兩個類別的數(shù)量一樣多,，那么交叉熵達到最大為 1,。因此,，和 Gini 指數(shù)一樣,，交叉熵函數(shù)同樣能用于度量結(jié)點的不純度：

和 G 一樣,，較小的 S 值表示區(qū)域內(nèi)結(jié)點包含了單個類別中的大多數(shù)觀察值。

決策樹常見參數(shù)和概念

如果我們希望以數(shù)學(xué)的方式理解決策樹,，我們首先需要了解決策樹和樹型學(xué)習(xí)算法的一般概念,。理解以下的術(shù)語同樣能幫助我們調(diào)整模型。

根結(jié)點：表示所有數(shù)據(jù)樣本并可以進一步劃分為兩個或多個子結(jié)點的父結(jié)點,。
分裂（Splitting）：將一個結(jié)點劃分為兩個或多個子結(jié)點的過程,。
決策結(jié)點：當一個子結(jié)點可進一步分裂為多個子結(jié)點，那么該結(jié)點就稱之為決策結(jié)點,。
葉/終止結(jié)點：不會往下進一步分裂的結(jié)點,，在分類樹中代表類別。
分枝/子樹：整棵決策樹的一部分,。
父結(jié)點和子結(jié)點：如果一個結(jié)點往下分裂,，該結(jié)點稱之為父結(jié)點而父結(jié)點所分裂出來的結(jié)點稱之為子結(jié)點。
結(jié)點分裂的最小樣本數(shù)：在結(jié)點分裂中所要求的最小樣本數(shù)量（或觀察值數(shù)量）,。這種方法通?？梢杂脕矸乐惯^擬合，較大的最小樣本數(shù)可以防止模型對特定的樣本學(xué)習(xí)過于具體的關(guān)系,，該超參數(shù)應(yīng)該需要使用驗證集來調(diào)整,。
葉結(jié)點最小樣本數(shù)：葉結(jié)點所要求的最小樣本數(shù)。和結(jié)點分裂的最小樣本數(shù)一樣,，該超參數(shù)同樣也可以用來控制過擬合,。對于不平衡類別問題來說，我們應(yīng)該取較小的值,，因為屬于較少類別的樣本可能數(shù)量上非常少,。
樹的最大深度（垂直深度）：該超參數(shù)同樣可以用來控制過擬合問題，較小的深度可以防止模型對特定的樣本學(xué)習(xí)過于具體的關(guān)系,，該超參數(shù)同樣需要在驗證集中調(diào)整,。
葉結(jié)點的最大數(shù)量：葉結(jié)點的最大個數(shù)可以替代數(shù)的最大深度這一設(shè)定。因為生成一棵深度為 n 的二叉樹,，它所能產(chǎn)生的最大葉結(jié)點個數(shù)為 2^n,。
分裂所需要考慮的最大特征數(shù)：即當我們搜索更好分離方案時所需要考慮的特征數(shù)量，我們常用的方法是取可用特征總數(shù)的平方根為最大特征數(shù),。

分類樹的實現(xiàn)

為了展示不同的前文所述的決策樹模型,，我們將使用 Kaggle 上的美國收入數(shù)據(jù)集，我們都可以在 Kaggle.com 上下載該數(shù)據(jù)集,。下面的代碼可以展示該數(shù)據(jù)集的導(dǎo)入過程和部分內(nèi)容：

import pandas as pdimport numpy as npfrom plotnine import *import matplotlib.pyplot as pltfrom sklearn.preprocessing import LabelEncoderfrom sklearn_pandas import DataFrameMapperfrom sklearn.tree import DecisionTreeClassifierfrom 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)

在上面的代碼中,，我們首先需要導(dǎo)入所有需要的庫和模塊,，然后再讀取數(shù)據(jù)和結(jié)構(gòu)到訓(xùn)練數(shù)據(jù)和驗證數(shù)據(jù)中。我們同樣去除 fnlgwt 列,，因為該數(shù)據(jù)行對于模型的訓(xùn)練并不重要,。

輸入以下語句可以看到訓(xùn)練數(shù)據(jù)的前五行：

df_train_set.head()

如下所示，我們還需要做一些數(shù)據(jù)清洗,。我們需要將所有列的的特殊字符移除,，此外任何空格或者「.」都需要移除。

#replace the special character to 'Unknown'for i in df_train_set.columns: 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('.', ''))

正如上圖所示,，有兩行描述了個人的教育：Eduction 和 EdNum,。我們假設(shè)這兩個特征十分相關(guān)，因此我們可以移除 Education 列,。Country 列對預(yù)測收入并不會起到什么作用,，所以我們需要移除它。

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

Age 和 EdNum 列是數(shù)值型的,，我們可以將連續(xù)數(shù)值型轉(zhuǎn)化為更高效的方式,，例如將年齡換為 10 年的整數(shù)倍，教育年限換為 5 年的整數(shù)倍,，實現(xiàn)的代碼如下：

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]

現(xiàn)在我們已經(jīng)清理了數(shù)據(jù),，下面語句可以展示我們數(shù)據(jù)的概況：

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

在訓(xùn)練集和測試集中，我們發(fā)現(xiàn) <=50K 的類別要比>50K 的多 3 倍,。從這里我們就可以看出來樣本數(shù)據(jù)并不是均衡的數(shù)據(jù),，但是在這里為了簡化問題，我們在這里將該數(shù)據(jù)集看作常規(guī)問題,。

EDA

現(xiàn)在,，讓我們以圖像的形式看一下訓(xùn)練數(shù)據(jù)中的不同特征的分布和相互依存（inter-dependence）關(guān)系。首先看一下關(guān)系（Relationships）和婚姻狀況（MaritalStatus）特征是如何相互關(guān)聯(lián)的,。

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

讓我們首先看一下不同年齡組中,，教育對收入的影響（用受教育的年數(shù)進行衡量）。

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

最近,，有很多關(guān)于性別對收入差距的影響的相關(guān)說法,。我們可以分別看見男性和女性的教育程度和種族間的影響。

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

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

直到現(xiàn)在,，我們僅關(guān)注了非數(shù)值特征（non-numeric）的相互關(guān)系?，F(xiàn)在我們看一下資本收益（CapitalGain）和資本損失（CapitalLoss）對收入的影響。

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

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

樹分類器

現(xiàn)在我們理解了我們數(shù)據(jù)中的一些關(guān)系,，所以就可以使用 sklearn.tree.DecisionTreeClassifier 創(chuàng)建一個簡單的樹分類器模型,。然而，為了使用這一模型，我們需要把所有我們的非數(shù)值數(shù)據(jù)轉(zhuǎn)化成數(shù)值型數(shù)據(jù),。我們可以直接在 Pandas 數(shù)據(jù)框架中使用 sklearn.preprocessing.LabeEncoder 模塊和 sklearn_pandas 模塊就可以輕松地完成這一步驟,。

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

現(xiàn)在我們用正確的形式對數(shù)據(jù)進行了訓(xùn)練和測試，已創(chuàng)建了我們的第一個模型,！

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

最簡單的且沒有優(yōu)化的概率分類器模型可以達到 83.5% 的精度,。在分類問題中，混淆矩陣（confusion matrix）是衡量模型精度的好方法,。使用下列代碼我們可以繪制任意基于樹的模型的混淆矩陣,。

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

現(xiàn)在，我們可以看到第一個模型的混淆矩陣：

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)

我們發(fā)現(xiàn)多數(shù)類別（<=50K）的精度為 90.5%,，少數(shù)類別（>50K）的精度只有 60.8%。

讓我們看一下調(diào)校此簡單分類器的方法,。我們能使用帶有 5 折交叉驗證的 GridSearchCV() 來調(diào)校樹分類器的各種重要參數(shù),。

from sklearn.model_selection import GridSearchCV
parameters = {'max_features':(None, 9, 6),'max_depth':(None, 24, 16),'min_samples_split': (2, 4, 8),'min_samples_leaf': (16, 4, 12)}

clf = GridSearchCV(treeClassifier, parameters, cv=5, n_jobs=4)
clf.fit(x_train, y_train)
clf.best_score_, clf.score(x_test, y_test), clf.best_params_
(0.85934092933263717,
0.85897672133161351,
{'max_depth': 16,
'max_features': 9,
'min_samples_leaf': 16,
'min_samples_split': 8})

經(jīng)過優(yōu)化，我們發(fā)現(xiàn)精度上升到了 85.9%,。在上方,，我們也可以看見最優(yōu)模型的參數(shù)。現(xiàn)在,，讓我們看一下已優(yōu)化模型的混淆矩陣（confusion matrix）：

y_pred = clf.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)

經(jīng)過優(yōu)化,，我們發(fā)現(xiàn)在兩種類別下，預(yù)測精度都有所提升,。

決策樹的局限性

決策樹有很多優(yōu)點,，比如：

易于理解、易于解釋
可視化
無需大量數(shù)據(jù)準備,。不過要注意,，sklearn.tree 模塊不支持缺失值。
使用決策樹（預(yù)測數(shù)據(jù)）的成本是訓(xùn)練決策時所用數(shù)據(jù)的對數(shù)量級,。

但這些模型往往不直接使用,，決策樹一些常見的缺陷是：

構(gòu)建的樹過于復(fù)雜，無法很好地在數(shù)據(jù)上實現(xiàn)泛化,。
數(shù)據(jù)的微小變動可能導(dǎo)致生成的樹完全不同,，因此決策樹不夠穩(wěn)定。
決策樹學(xué)習(xí)算法在實踐中通?；趩l(fā)式算法,，如貪婪算法，在每一個結(jié)點作出局部最優(yōu)決策,。此類算法無法確保返回全局最優(yōu)決策樹,。
如果某些類別占據(jù)主導(dǎo)地位，則決策樹學(xué)習(xí)器構(gòu)建的決策樹會有偏差,。因此推薦做法是在數(shù)據(jù)集與決策樹擬合之前先使數(shù)據(jù)集保持均衡,。
某些類別的函數(shù)很難使用決策樹模型來建模,，如 XOR、奇偶校驗函數(shù)（parity）和數(shù)據(jù)選擇器函數(shù)（multiplexer）,。

大部分限制可以通過改善決策樹輕易解決,。在下面的內(nèi)容中，我們將介紹相關(guān)的幾個概念,，重點介紹袋裝和隨機森林,。

剪枝

由于決策樹容易對數(shù)據(jù)產(chǎn)生過擬合，因此分支更少（即減少區(qū)域 R_1, … ,R_J）的小樹雖然偏差略微高一點,，但其產(chǎn)生的方差更低,，可解釋性更強。處理上述問題的一種方法是構(gòu)建一棵樹,，每個分支超過某個（高）閾值造成葉結(jié)點誤差率 Qm 下降,，則結(jié)束構(gòu)建。但是,，由于分裂算法的貪婪本質(zhì),，它其實很短視。決策樹早期看似無用的一次分裂有可能會導(dǎo)致之后一次優(yōu)秀的分裂,，并使得 Qm 大幅下降,。

因此，更好的策略是構(gòu)建一個非常大的樹 T_0,，然后再剪枝,，得到一棵子樹。剪枝可以使用多種策略,。代價復(fù)雜度剪枝（Cost complexity pruning）,，又叫最弱連接剪枝（weakest link pruning），就是其中一種行之有效的策略,。除了考慮每一個可能的子樹之外,，還需要考慮由非負調(diào)參（nonnegative tuning parameter）α 索引的樹序列。每一個 α 值都對應(yīng)一個盡可能小的子樹 T?T_0,。

這里∣T∣代表樹 T 中葉結(jié)點的數(shù)量,，R_m 代表第 m 個葉結(jié)點對應(yīng)的矩形（預(yù)測器空間的子集），yhat_Rm 是 Rm 的預(yù)測值,，即 Rm 中訓(xùn)練樣本預(yù)測值的均值（或分類樹中的模式響應(yīng)）,。調(diào)整參數(shù) α 控制子樹復(fù)雜度之間的權(quán)衡，對訓(xùn)練數(shù)據(jù)進行擬合,。當 α= 0 的時候,，子樹 T 等同于 T_0。當α的值增長時，構(gòu)建具備多個子結(jié)點的樹需要付出代價,，這樣,，要想得到更小的子樹，上述公式將達到最小化,。我們可以使用某種交叉驗證方法選擇剪枝參數(shù) α ,。

注意，目前 sklearn.tree 決策樹分類器（和回歸器）不支持剪枝,。

袋裝（Bootstrap Aggregating——Bagging）

在統(tǒng)計學(xué)中,，Bootstrap 是依靠替換隨機采樣的任意試驗或度量。我們從上文可以看見,，決策樹會受到高方差的困擾,。這意味著如果我們把訓(xùn)練數(shù)據(jù)隨機分成兩部分，并且給二者都安置一個決策樹,，我們得到的結(jié)果可能就會相當不同,。Bootstrap 聚集，或者叫做袋裝,，是減少統(tǒng)計學(xué)習(xí)方法的方差的通用過程。

給定一組 n 個獨立的樣本觀測值 Z_1,，Z_2,，...，Z_n,，每一個值的方差均為 *σ^*2,，樣本觀測值的均值方差為 *σ^*2/*n*。換句話說,，對一組觀測值取平均會減小方差,。因此一種減小方差的自然方式，也就是增加統(tǒng)計學(xué)習(xí)方法預(yù)測精度的方式,，就是從總體中取出很多訓(xùn)練集,，使用每一個訓(xùn)練集創(chuàng)建一個分離的預(yù)測模型，并且對預(yù)測結(jié)果求取平均值,。

這里有一個問題,，即我們不能獲取多個訓(xùn)練數(shù)據(jù)集。相反,，我們可以通過從（單一）訓(xùn)練數(shù)據(jù)集提取重復(fù)樣本進行自助法（bootstrap）操作,。在這種方法中，我們生成了 B 個不同的自助訓(xùn)練數(shù)據(jù)集,。我們隨后在第 b 個自助訓(xùn)練數(shù)據(jù)集得到了一個預(yù)測結(jié)果,，從而獲得一個聚集預(yù)測（aggregate prediction）。

這就叫做袋裝（bagging）。注意,，聚集（aggregating）在回歸和分類問題中可能有不同的均值,。當平均預(yù)測值在回歸問題中的效果很好時，我們將會需要使用多數(shù)票決（majority vote）：由于分類問題中的聚集機制,，整體預(yù)測就是在 B 個預(yù)測值中最常出現(xiàn)的那個主要類別,。

Out-of-Bag（OOB）誤差

Bagging 方法最大的優(yōu)勢是我們可以不通過交叉驗證而求得測試誤差?；叵胍幌?，Bagging 方法的精髓是多棵樹可以重復(fù)地擬合觀察樣本的自助子集。平均而言,，每一個袋裝樹可以利用 2/3 的觀察樣本,。而剩下的 1/3 觀察樣本就可以稱為 out-of-bag (OOB) 觀察樣本，它們并不會擬合一一棵給定袋裝樹,。我們可以使用每一棵樹的 OOB 觀察樣本而計算第 i 個觀察樣本的預(yù)測值,，這將會導(dǎo)致大約有 B/3 的預(yù)測值可以預(yù)測第 i 個觀察樣本。現(xiàn)在我們可以使用和 Bagging（平均回歸和大多數(shù)投票分類）類似的聚集技術(shù),，我們能獲得第 i 個觀察樣本的單一預(yù)測值,。我們可以用這種方式獲得 n 個觀察樣本的 OOB 預(yù)測，因此總體的 OOB MSE（回歸問題）和分類誤差率（分類問題）就能計算出來,。OOB 誤差結(jié)果是 Bagging 模型測試誤差的有效估計,，因為每一個樣本的預(yù)測值都是僅僅使用不會進行擬合訓(xùn)練模型的樣本。

特征重要性度量

通過使用單一樹,，Bagging 通常會提升預(yù)測的精確度,。但是，解釋最終的模型可能很困難,。當我們袋裝大量的樹時,，就不再可能使用單一的樹表征最終的統(tǒng)計學(xué)習(xí)流程，因此,，Bagging 是以犧牲闡釋性能力為代價來提升預(yù)測精確度的,。有趣的是，一個人可使用 RSS（用于 bagging 回歸樹）或者基尼指數(shù)（用于 bagging 分類樹）得到每一個預(yù)測器的整體總結(jié),。在 bagging 回歸樹的情況中,，我們可以記錄由于所有的 B 樹上平均的給定預(yù)測分子分裂而造成的 RSS 減少的所有數(shù)量。一個大的值表示一個重要的預(yù)測器,。相似地,，在 bagging 分類樹的情況下，我們可以添加由于所有的 B 樹上平均的給定預(yù)測分子分裂而造成的基尼系數(shù)降低的所有數(shù)量,。一旦訓(xùn)練完成,，sklearn 模塊的不同袋裝樹（bagged tree）學(xué)習(xí)方法可直接訪問特征的重要性數(shù)據(jù)作為屬性,。

隨機森林模型

雖然袋裝技術(shù)（Bagging）通過降低方差而提高了一般決策樹的預(yù)測性能，但它還遇到了其他缺點：Bagging 要求我們在自助樣本上生成整棵樹,，這就增加了 B 倍計算復(fù)雜度,。此外，因為基于 Bagging 的樹是相關(guān)聯(lián)的,，預(yù)測精度會根據(jù) B 而飽和,。

隨機森林通過隨機擾動而令所有的樹去相關(guān)，因此隨機森林要比 Bagging 性能更好,。隨機森林不像 Bagging,，在構(gòu)建每一棵樹時，每一個結(jié)點分割前都是采用隨機樣本預(yù)測器,。因為在核心思想上,，隨機森林還是和 Bagging 樹一樣，因此其在方差上有所減少,。此外,，隨機森林可以考慮使用大量預(yù)測器，不僅因為這種方法減少了偏差,，同時局部特征預(yù)測器在樹型結(jié)構(gòu)中充當重要的決策,。

隨機森林可以使用巨量的預(yù)測器，甚至預(yù)測器的數(shù)量比觀察樣本的數(shù)量還多,。采用隨機森林方法最顯著的優(yōu)勢是它能獲得更多的信息以減少擬合數(shù)值和估計分割的偏差,。

通常我們會有一些預(yù)測器能主導(dǎo)決策樹的擬合過程，因為它們的平均性能始終要比其他一些競爭預(yù)測器更好,。因此，其它許多對局部數(shù)據(jù)特征有用的預(yù)測器并不會選定作為分割變量,。隨著隨機森林計算了足夠多的決策樹模型,，每一個預(yù)測器都至少有幾次機會能成為定義分割的預(yù)測器。大多數(shù)情況下,，我們不僅僅只有主導(dǎo)預(yù)測器,，特征預(yù)測器也有機會定義數(shù)據(jù)集的分割。

隨機森林有三個主要的超參數(shù)調(diào)整：

結(jié)點規(guī)模：隨機森林不像決策樹,，每一棵樹葉結(jié)點所包含的觀察樣本數(shù)量可能十分少,。該超參數(shù)的目標是生成樹的時候盡可能保持小偏差。
樹的數(shù)量：在實踐中選擇數(shù)百棵樹一般是比較好的選擇,。
預(yù)測器采樣的數(shù)量：一般來說,，如果我們一共有 D 個預(yù)測器，那么我們可以在回歸任務(wù)中使用 D/3 個預(yù)測器數(shù)作為采樣數(shù),，在分類任務(wù)中使用 D^(1/2) 個預(yù)測器作為抽樣,。

隨機森林模型案例

使用和上文一樣的收入數(shù)據(jù),，現(xiàn)在我們構(gòu)建一個包含 500 棵樹的簡單隨機森林分類器模型：

rclf = RandomForestClassifier(n_estimators=500) rclf.fit(x_train, y_train) rclf.score(x_test, y_test)

即使沒有任何優(yōu)化，我們?nèi)匀话l(fā)現(xiàn)模型性能可以和已優(yōu)化決策樹分類器相媲美,，并且測試分達到了 85.1%,。按照下面的混淆矩陣，我們發(fā)現(xiàn)簡單的隨機森林和經(jīng)過優(yōu)化的樹型分類器表現(xiàn)差不多,，其在主要類別（<=50K 收入）的預(yù)測精度達到了 92.1%,，而在少數(shù)類別（>50K 收入）上達到了 62.6%。

rclf = RandomForestClassifier(n_estimators=500) rclf.fit(x_train, y_train) rclf.score(x_test, y_test)

正如前面所探討的,，隨機森林模型還提供了特征重要性的度量方法,。我們可以在下圖中看到目前模型不同特征的重要性：

importances = rclf.feature_importances_ indices = np.argsort(importances) cols = [cols[x] for x in indices] plt.figure(figsize=(10,6)) plt.title('Feature Importances') plt.barh(range(len(indices)), importances[indices], color='b', align='center') plt.yticks(range(len(indices)), cols) plt.xlabel('Relative Importance')

現(xiàn)在我們可以嘗試優(yōu)化我們的隨機森林模型，如下我們可以使用帶 5-折交叉驗證的 GridSearchCV() 操作來優(yōu)化隨機森林：

parameters = {'n_estimators':(100, 500, 1000),'max_depth':(None, 24, 16),'min_samples_split': (2, 4, 8),'min_samples_leaf': (16, 4, 12)} clf = GridSearchCV(RandomForestClassifier(), parameters, cv=5, n_jobs=8) clf.fit(x_train, y_train) clf.best_score_, clf.best_params_ 0.86606676699118579 {'max_depth': 24, 'min_samples_leaf': 4, 'min_samples_split': 4, 'n_estimators': 1000}
0.86606676699118579
{'max_depth': 24,
'min_samples_leaf': 4,
'min_samples_split': 4,
'n_estimators': 1000}

我們可以看到現(xiàn)在的模型要顯著地比前面的更好一些,，并且預(yù)測率達到了 86.6%,。按照下面的混淆矩陣，新模型在主要類別的預(yù)測精度上有顯著的提升,，并且在少數(shù)類別的預(yù)測上精度只稍微降低了一點,。這是非平衡數(shù)據(jù)普遍存在的問題。

rclf2 = RandomForestClassifier(n_estimators=1000,max_depth=24,min_samples_leaf=4,min_samples_split=8) rclf2.fit(x_train, y_train) y_pred = rclf2.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)

最后,，下面展示了對優(yōu)化后模型比較重要的特征,。

importances = rclf2.feature_importances_ indices = np.argsort(importances) cols = [cols[x] for x in indices] plt.figure(figsize=(10,6)) plt.title('Feature Importances') plt.barh(range(len(indices)), importances[indices], color='b', align='center') plt.yticks(range(len(indices)), cols) plt.xlabel('Relative Importance')

隨機森林的局限性

除了 Bagging 樹模型的一般局限性外，隨機森林還有一些局限性：