[ML] 機器學習技法：第十講 Random Forest

ML：基礎技法學習
Package：scikit-learn
課程：機器學習技法
簡介：第十講 Random Forest

Random Forest Algorithm

RF = bagging + random-combination C&RT — randomness everywhere

function RandomForest( $D$ )

for $t = 1, 2, \dots, T$

利用 bootstrapping 從 $D$ 取出 size-N' 的 ${\tilde{D}}_{t}$
$g_{t} =$ $DTree ({\tilde{D}}_{t})$

function $DTree ({\tilde{D}}_{t})$

if(滿足終止條件)

回傳 $g_{t}$

else

學習 $b (Φ (x))$ 並用此切割 $D$ 為 $D_{c}$

$Φ (x) = P \cdot x$

$P$ 為低維度投影矩陣
row i of $P$ 是隨機挑選 feature 組合

$G_{c} = DTree (D_{c})$
回傳 $G (x) = \sum_{c = 1}^{C} [b (x) = c] G_{c} (x)$

回傳 $G (x) = Uniform ({g_{t}})$

Bagging 可以降低變異量，Decision Tree 對於不同的資料又非常敏感
特別是 fully-grown Tree 變異量相當大
那為何不把兩者合在一起呢？
於是 random forest (RF) = bagging + fully-grown C&RT decision tree

理論上越多樣化，bagging 越好
所以改為只從

x

取

d^{'}

個 features，且

d^{'} ≪ d

運算更有效率
在計算每個

b (x)

時，都將之改為

b (Φ (x))

當 sampling index

i_{1}, i_{2}, \dots, i_{d^{'}}

，則

Φ (x) = (x_{i_{1}}, x_{i_{2}}, \dots, x_{i_{d^{'}}})

這樣不僅可以增加多樣性，還可提升計算效率
換個方向來看，這不就是

Φ (x) = P \cdot x

，只是

P

的每一個 row i

p_{i}

是 natural basis
但這樣只能切水平或垂直刀，若將

p_{i}

改成

d^{″}

個 features 的線性組合

p_{i}^{T} x

連斜刀也能切出來了，就更加多樣性
事實上這跟 perceptron 類似，

w

移除

(w_{0})

就是

p_{i}

而大於 threshold

(w_{0})

是一邊，小於 threshold

(w_{0})

是另一邊
也就是 decision stump 選個點切開分類，依此分類

優勢

容易平行化(bagging)
繼承 Decision Tree 的優點

容易解釋
multiclass 實現簡單
categorical features 應用簡單
missing features 處理簡單
non-linear training (and testing) 有效率

降低 fully-grown tree 的缺點

容易 overfit

Out-Of-Bag Estimate (OOB)

\begin{aligned} G_{m^{*}} & = R F_{m^{*}} (D) \\ m^{*} & = \underset{1 \leq m \leq M}{a r g m i n} E_{m} \\ E_{m} & = E_{o o b} (R F_{m} (D)) \end{aligned}

用

E_{o o b}

for self-validation—像是決定

d^{″}

(多少個 features 做線性組合)
且無需再用全部的資料重新訓練一次，得到最後的結果

從下圖，可看到不同的

g_{t}

，因為 bootstrapping 的關係，所以有些 data 並不會被挑到
那麼這些 data 是否可以拿來做為 validation 用呢？

對一個

g_{t}

而言，一個 data 完全不會被選中的機率是

(1 - \frac{1}{N})^{N^{'}}

假設

N^{'} = N

，且 N 很大時

\begin{aligned} (1 - \frac{1}{N})^{N} & = (\frac{N - 1}{N})^{N} \\ = (\frac{1}{\frac{N}{N - 1}})^{N} \\ = (\frac{1}{\frac{N - 1 + 1}{N - 1}})^{N} \\ = (\frac{1}{1 + \frac{1}{N - 1}})^{N} \\ = \frac{1}{(1 + \frac{1}{N - 1})^{N}} \\ [∵ e^{x} = \underset{n \to \infty}{l i m} (1 + \frac{x}{n})^{n}] & \approx \frac{1}{e} \end{aligned}

那麼不會被選中資料數約為

\frac{1}{e} N

，約是三分之一，甚至比做 validation 的五分之一還多
拿這些資料對

g_{t}

做 validate，當然可以，但很少這麼做，因為需要的是對

G

做 validate
那如果將擁有同樣未選中資料的

g_{t}

做 bagging 再做 validate 呢？
像是圖中的

(x_{N}, y_{N})

，其

G_{N}^{-} (x) = a v g (g_{2}, g_{3}, g_{t})

再將所有

G_{n}^{-} (x)

的錯誤做平均，感覺就是 Leave One Out，因此定義

E_{o o b} (G) = \frac{1}{N} \sum_{n = 1}^{N} e r r (y_{n}, G_{n}^{-} (x_{n}))

在實際應用，

E_{o o b}

通常也是很準確的
而且不用在跟之前一樣，特別割出

D_{v a l}

做驗證，然後最後還得對所有資料重新訓練一次，如左圖

Feature Selection

優點

令後續的演算法更有效率
移除不必要的 features，排除雜訊
剩下的 features 也許可解釋

缺點

計算量過多，從 $N$ 取 $N^{'}$ 個，共有 $C_{N^{'}}^{N}$ 個組合
假如沒做好的話，會選到看似很好其實並不然的組合

容易 overfit
無法解釋 features 的關聯性

Linear Model

w^{T} x

i m p o r t a n c e (i) = | w_{i} |

組合太多，計算量太過龐大，若如何改為只看單一項的重要性呢？ importance(i) for

i = 1, 2, \dots, d

並依此選出排名較靠前的 features
而事實上 linear model 的

w

不就具有此特性，將重要的放大，不重要的縮小
故

i m p o r t a n c e (i) = | w_{i} |

RF，實務上相當常用

i m p o r t a n c e (i) = E_{o o b} (G) - E_{o o b}^{(p)} (G)

E_{o o b}^{(p)} (G)

對於

x_{n, i}

的 permutation 來自 OOB 資料

對於 non-linear model 無法使用權重值，因為 features 是交雜在一起的，無法輕易分析
所以換個角度來看
若這個 feature 很重要，那麼加入一點 noise 應該會造成整體的表現變差
那要加入什麼樣的 noise？

uniform, Gaussian, ...

會造成原有的分佈特性跑掉，也就是 $P (x_{i})$ 被改變

bootstrap, permutation(重新洗牌順序)

維持原本的分佈特性

在此使用的是 permutation test

i m p o r t a n c e (i) = p e r f o r m a n c e (D) - p e r f o r m a n c e (D^{(p)})

D^{(p)}

來自原有的

D

對於

{x_{n, i}}

做洗牌，也就是資料不變，但位置被改變了
此方法在統計學上常用，適用任意的 non-linear models
記住，此處的 performance，指的是 validation 的結果
因此在 RF 中，

i m p o r t a n c e (i) = E_{o o b} (G) - E_{o o b} (G^{(p)})

但若是如此，還是得針對

D^{(p)}

重新訓練
若改為這樣呢？

i m p o r t a n c e (i) = E_{o o b} (G) - E_{o o b}^{(p)} (G)

G

不變，只針對 OOB 做 permutation
這樣的話，就不用再重新訓練，可直接跑

E_{o o b}

的流程

實際例子為，若資料中的第 i 項，無論是哪一個 data 皆是常數，那麼

i m p o r t a n c e (i) = 0

因為無論怎麼做 permutation 皆是一樣的值，自然重要性為 0
或換個角度來看，一個常數值，但對應的

y

都不一樣，不就表示此項無任何貢獻

實際例子

左圖為只替 C&RT 加入 features 的線性組合，也就是 random combination
右圖為 RF，但其

N^{'} = \frac{N}{2}

，也就是 bootstrapping 只抽出一半的資料量
可看到 RF 更加的 smooth 與 large margin

左圖為 t=21 的 tree
右圖為

G

，可看到 noise 的影響已被去除掉大部分

注意事項

因為 RF 本質是隨機的演算法，需要足夠的 trees，才能達到穩定
如何決定何謂足夠的 trees，看一下

G

的穩定性
像是

E_{o o b}

每次的結果，增減 tree 是否會有變化

程式碼

使用 b(x) 時的 features 不一定越少越好

import matplotlib.pyplot as plt
 
from collections import OrderedDict
from sklearn.datasets import make_classification
from sklearn.ensemble import RandomForestClassifier
 
RANDOM_STATE = 123
 
# 建立 500 筆資料，有 25 個 features，15 個重要 features，10 個雜訊 features
# 每個類別的資料個別分為兩大群，也就是分佈在兩個不同的位置
X, y = make_classification(n_samples=500, n_features=25,
                           n_clusters_per_class=2, n_informative=15,
                           random_state=RANDOM_STATE)
 
# 設定 max_features，每次做 b(x) 所看得 feature 數量
# 設定 warm_start=True，可重覆利用先前做過的 solution 加快速度
ensemble_clfs = [
    ("RandomForestClassifier, max_features='sqrt'",
        RandomForestClassifier(warm_start=True, oob_score=True,
                               max_features="sqrt",
                               random_state=RANDOM_STATE)),
    ("RandomForestClassifier, max_features='log2'",
        RandomForestClassifier(warm_start=True, max_features='log2',
                               oob_score=True,
                               random_state=RANDOM_STATE)),
    ("RandomForestClassifier, max_features=None",
        RandomForestClassifier(warm_start=True, max_features=None,
                               oob_score=True,
                               random_state=RANDOM_STATE))
]
 
# 建立一有序 dictionary for 記錄使用
error_rate = OrderedDict((label, []) for label, _ in ensemble_clfs)
 
# 設定 tree 的上下限數量
min_estimators = 15
max_estimators = 300
 
for label, clf in ensemble_clfs:
    for i in range(min_estimators, max_estimators + 1, 2):
        clf.set_params(n_estimators=i)
        clf.fit(X, y)
 
        # 記錄大小為 i 的 RF 的 oob error 
        oob_error = 1 - clf.oob_score_
        error_rate[label].append((i, oob_error))
 
# Generate the "OOB error rate" vs. "n_estimators" plot.
for label, clf_err in error_rate.items():
    xs, ys = zip(*clf_err)
    plt.plot(xs, ys, label=label)
 
plt.xlim(min_estimators, max_estimators)
plt.xlabel("n_estimators (n trees)")
plt.ylabel("OOB error rate")
plt.legend(loc="upper right")
plt.show()

feature selection 挑出的 features 可能比實際的多

import numpy as np
import matplotlib.pyplot as plt
 
from sklearn.datasets import make_classification
from sklearn.ensemble import RandomForestClassifier
 
RANDOM_STATE = 123
IMPORTANT_FEATURE = 3
 
# 建立 1000 筆資料，有 25 個 features，3 個重要 features，22 個雜訊 features
# 每個類別的資料個別分為兩大群，也就是分佈在兩個不同的位置
X, y = make_classification(n_samples=1000, n_features=25,
                           n_clusters_per_class=2, n_informative=IMPORTANT_FEATURE,
                           random_state=RANDOM_STATE)
 
# 建立一個大小為 250 顆 tree 的 RF
forest = RandomForestClassifier(n_estimators=250,
                              random_state=RANDOM_STATE)
 
forest.fit(X, y)
importances = forest.feature_importances_
# 計算所有 tree 的 feature 標準差
std = np.std([tree.feature_importances_ for tree in forest.estimators_], axis=0)
# 由小到大排序並回傳對應的 index，再將之反向，也就是改為由大到小的排序
indices = np.argsort(importances)[::-1]
 
# 印出排序後的 feature 重要性
print("Feature ranking:")
for f in range(X.shape[1]):
    print("%d. feature %d (%f)" % (f + 1, indices[f], importances[indices[f]]))
 
# 畫圖
plt.figure()
plt.title("{} Feature importances in Real".format(IMPORTANT_FEATURE))
plt.bar(range(X.shape[1]), importances[indices],
       color="r", yerr=std[indices], align="center")
plt.xticks(range(X.shape[1]), indices)
plt.xlim([-1, X.shape[1]])
plt.show()

參考

sklearn.ensemble.RandomForestClassifier
sklearn.ensemble.RandomForestRegressor
Feature importances with forests of trees

子風的知識庫

搜尋此網誌