【scikit-learn文檔解析】集成方法 Ensemble Methods（上）：Bagging與隨機森林

01-25

（題圖：Piet Mondrian - Arbre）

系列鏈接：

【scikit-learn文檔解析】集成方法 Ensemble Methods（上）：Bagging與隨機森林 - 知乎專欄

【scikit-learn文檔解析】集成方法 Ensemble Methods（下）：AdaBoost，GBDT與Voting - 知乎專欄

在機器學習中，集成方法（ensemble learning）把許多個體預測器（base estimator）組合起來，從而提高整體模型的魯棒性和泛化能力。

集成方法有兩大類：

Averaging：獨立建造多個個體模型，再取它們各自預測值的平均，作為集成模型的最終預測；能夠降低variance。例子：隨機森林，bagging。
Boosting：順序建立一系列弱模型，每一個弱模型都努力降低bias，從而得到一個強模型。例子：AdaBoost，Gradient Boosting。

1. Bagging

Bagging全稱bootstrap aggregating。這種方法，把個體預測器當做黑盒子處理，不進行進一步修改，所以，它的個體預測器可以是任何機器學習演算法。它對訓練數據集進行隨機取樣，並使用取樣後的數據子集，訓練每一個個體預測器。在預測時，每一個預測器都會做出預測，整體結果則是每個預測的平均。

Bagging能降低模型的variance，所以它可以對抗過擬合。一般而言，bagging需要使用variance高、比較複雜的強個體模型。具體到常用的決策樹上，就體現在單個決策樹的層數更深。（相比之下，boosting需要使用bias高、比較簡單的弱個體模型。）

根據數據子集（用於訓練每一個個體分類器）建立方式的不同，bagging有4個種類：

Pasting：針對樣本，取所有樣本的隨機子集。[3]
Bagging：針對樣本，進行重置隨機抽樣（sample with replacement），可能會有重複樣本。[4]
Random Subspaces：針對特徵，取所有特徵的隨機子集。[5]
Random Patches：針對特徵和樣本，取所有特徵和所有樣本的隨機子集（組合了Pasting和Random Subspaces）[6]

scikit-learn代碼實現的bagging演算法，可以包括以上所有的情形。

1.1. 代碼實現

scikit-learn提供了BaggingClassifier和BaggingRegressor兩種方法：

sklearn.ensemble.BaggingClassifier - scikit-learn 0.18.1 documentation
sklearn.ensemble.BaggingRegressor - scikit-learn 0.18.1 documentation

參數解析：

base_estimator：個體預測器，需要是一個scikit-learn的分類器或回歸器。如果沒有給出，那麼默認使用決策樹（不推薦，不如RandomForest）。
n_estimators：個體預測器的數量。通常，預測器越多，整體模型的variance越低。
max_samples：每個數據子集（用於訓練個體預測器）的樣本數量。可以是浮點數（0.0至1.0，表示取樣本占所有樣本的比例），也可以是整數（表示樣本的實際數量）。注意：如果輸入了1而不是1.0，那麼每個數據子集僅包含1個樣本，會導致嚴重失誤。
max_features：每個數據子集的特徵數量。數值原理同上。
bootstrap：在隨機選取樣本時是否進行重置（sample with replacement）。
bootstrap_features：在隨機選取特徵時是否進行重置。
oob_score：是否計算out-of-bag分數。每個個體預測器，都只在原始數據集的一部分上訓練。所以，可以用它在剩下樣本上的誤差（out-of-bag error），來估計它的泛化誤差（generalization error）。
warm_start：如果是True，那麼在下一次使用fit方法時，向原有的模型再增加n_estimators個新的個體預測器，不丟棄原有的個體預測器。
n_jobs：並行計算的進程數量，如果是-1則使用全部CPU核。
random_state：隨機狀態，用於得出可復現的結果。
verbose：控制屏幕上進程記錄的冗長程度。

1.2. 例子

from sklearn.ensemble import BaggingClassifiersklearn.neighbors import KNeighborsClassifierbagging = BaggingClassifier(KNeighborsClassifier(), n_estimators=10, max_samples=0.5, max_features=0.5)

如此一來，我們得到了一個由10個KNNClassifier組成的集成分類器。

1.3. 比較Bagging和個體模型的bias與variance [7]

在機器學習中，誤差（error）可以被分解為bias、variance和noise三個部分。

對於任何一個有監督學習問題（目標是求出 $P(y|x)$ ），最好的模型，無疑是一個完全知道數據概率分布的先知（oracle或Bayes model）。然而，因為數據本身存在一定誤差，所以先知也會產生一定誤差，這個誤差被稱為noise或Bayes error，是所有可能情形中最低的誤差。bias是某個模型平均error與Bayes error的差距，而variance則反映了模型在同一問題的不同版本上預測的差異大小。

如上圖所示，在noise不變的情況下，單個決策樹和bagging（決策樹）的bias都很低，但是bagging能夠顯著降低模型的variance。

2. 隨機森林（random forest）

為了增加個體預測器的多樣性，隨機森林在bagging（決策樹）的基礎上更進一步，在每棵樹的建造過程中增加了隨機性。在每棵隨機樹的生長過程中，節點分裂時，所用的特徵不再是所有特徵中最好的，而是特徵的一個子集中最好的。這種隨機性降低了運算量，略微提升了bias，極大提升了決策樹的多樣性，在取平均數之後可以大幅減小variance。整體而言，隨機森林是一個非常強大的演算法。

隨機森林有若干個變體，包括extremely randomized trees（簡稱ExtraTrees，暫未找到中文翻譯，歡迎補充）。在隨機森林的基礎上，ExtraTrees在每次節點分裂的閾值（threshold for splitting）上加入了隨機性。對於任意單個特徵，ExtraTrees隨機選取一些閾值，並在其中選取最好的閾值作為分類點。和隨機森林相比，ExtraTrees的variance更低，bias更高。

在Iris數據集上的運行結果，從左到右分別是：單個決策樹、隨機森林、ExtraTrees、AdaBoost。由圖片可見，單棵決策樹預測的自信度最高，但容易過擬合；ExtraTrees預測的自信度略低於隨機森林，但它的決策邊界也更為平滑。[8]

曾經，隨機森林相比Gradient Boosting的一大優勢就是能夠並行計算，因為不同決策樹的建造是相互獨立的。然而，LightGBM和XGBoost通過不同特徵之間的並行實現了gbdt的分散式計算。所以如今，這個優勢已經沒有那麼明顯了。

2.1. 代碼實現

scikit-learn文檔鏈接：

3.2.4.3.1. sklearn.ensemble.RandomForestClassifier - scikit-learn 0.18.1 documentation
3.2.4.3.2. sklearn.ensemble.RandomForestRegressor - scikit-learn 0.18.1 documentation
3.2.4.3.3. sklearn.ensemble.ExtraTreesClassifier - scikit-learn 0.18.1 documentation
3.2.4.3.4. sklearn.ensemble.ExtraTreesRegressor - scikit-learn 0.18.1 documentation

參數解析（上文已經包括了一些參數的解釋，在此不再重複）：

n_estimators
criterion：每棵樹分裂節點時的標準，針對分類器的有gini（基尼指數）和entropy（信息熵），針對回歸器的有mse（均方差，mean squared error）和mae（mean absolute error，中文未知，歡迎補充）
max_depth：每棵樹最大的深度，（和boosting相比）一般都比較深。增大此參數可以增加模型variance。
min_samples_split：節點分裂時的最小樣本數量。增大此參數可對抗過擬合。
min_samples_leaf：每個葉上最小的樣本數量。增大此參數可對抗過擬合。
min_weight_fraction_leaf：每個葉上最小的樣本權重比例（在fit時不使用sample_weight時，每個樣本權重相同，這時權重比例的計算方法是：葉子上樣本數量/總樣本數）。增大此參數可對抗過擬合。
max_features：和普通的bagging相比，增加了auto、sqrt和log2的選項。
max_leaf_nodes：每棵樹葉子數量的限制。
min_impurity_split：節點繼續分裂時的impurity閾值。如果impurity低於這個參數，那麼該決策樹在這個節點上將停止生長，這個節點將成為一個葉子。impurity的計算方式取決於上文的criterion參數。
bootstrap
oob_score
n_jobs
random_state
verbose
warm_start
class_weight：僅用於分類器。可以不輸入，也可以輸入字元串balanced或balanced_subsample，也可以輸入dict（格式為{class_label: weight}）。這個參數通常用於調節樣本不平衡的狀況。

2.2. 用隨機森林評估特徵的重要性

一個特徵在決策樹上的深度，可以反映它對預測的影響力，也就是它的重要性。如果一個特徵被用於最頂層的節點分裂，那麼它的數值影響了所有的樣本，說明它對預測任務非常重要。相比之下，用於最底層節點分裂的特徵，隻影響了一兩個樣本，對最終預測的貢獻不大。

在隨機森林中，我們可以取所有隨機樹的特徵重要性的平均值，得到模型整體的特徵重要性。這一數據可以被用於特徵選擇和特徵提取。它的一大優點是，特徵重要性的計算是在模型訓練的過程中自動完成的，不需要額外的計算量（在思路上類似Lasso的自帶特徵選擇）。

如圖所示 [9]，在ExtraTrees識別面部特徵時，高亮的像素點代表更重要的特徵。

2.3. 完全隨機樹嵌入（totally random trees embedding）

利用一個隨機森林，進行無監督的特徵轉換，可以用於特徵工程製造新特徵。每一個樣本，都可以被表示為它在每一棵樹上的葉子的索引（index）。一共有n_estimators棵樹，每棵樹有2 ** max_depth個葉子（在一棵樹上，每個樣本只會屬於一個葉子），所以新特徵的維度是n_estimators * 2 ** max_depth。

相似的樣本更可能被分類到相同的葉子上。這種變換方法可以看作一種無監督、非參數（non-parametric）的密度估計方法，它和流形學習也有一定關係。

Random trees embedding的一大特點，就是把低維的非線性特徵，轉化為高維的稀疏特徵。這種特徵轉換能夠極大改善線性分類器的性能。如下圖所示，經過特徵轉換之後，樸素貝葉斯（Naive Bayes）也能生成非線性決策邊界：[10]

代碼實現：sklearn.ensemble.RandomTreesEmbedding - scikit-learn 0.18.1 documentation

參數解析：（其他參數參見隨機森林）

sparse_output：如果為True，則返回一個csr矩陣；如果為False，則返回一個密集矩陣。

2.4. 用隨機森林進行特徵轉換

基本思路：把低維度的非線性密集特徵，轉化為高維度的稀疏特徵。

上文中，我們已經使用了無監督的totally random trees embedding。事實上，我們還可以使用其他類型的決策樹集成，如隨機森林和boosted trees。下圖是各類演算法組合和ROC曲線：[11]

可見，隨機森林/boosted trees特徵轉換+線性回歸的效果普遍好於單獨的隨機森林/boosted trees。

參考資料：

[1] Reference - scikit-learn 0.18.1 documentation

[2] scikit-learn原版英文文檔：1.11. Ensemble methods

[3] L. Breiman, 「Pasting small votes for classification in large databases and on-line」, Machine Learning, 36(1), 85-103, 1999.

[4] L. Breiman, 「Bagging predictors」, Machine Learning, 24(2), 123-140, 1996.

[5] T. Ho, 「The random subspace method for constructing decision forests」, Pattern Analysis and Machine Intelligence, 20(8), 832-844, 1998.

[6] G. Louppe and P. Geurts, 「Ensembles on Random Patches」, Machine Learning and Knowledge Discovery in Databases, 346-361, 2012.

[7] Single estimator versus bagging: bias-variance decomposition

[8] Plot the decision surfaces of ensembles of trees on the iris dataset

[9] Pixel importances with a parallel forest of trees

[10] Hashing feature transformation using Totally Random Trees

[11] Feature transformations with ensembles of trees