Random Forest, Extra Trees

　今日はRandom ForestとExtra Treesについて紹介いたします。決定木の基本的な解説は済んでいるため、短い記事になってしまうかと思います。

Random Forest

　まずはRandom Forestについての解説です。

　このアルゴリズムはかなり有名なものだとおもいます。（決定木内で行っていることは除いて）非常に単純な改良でかなりの精度改善をしてくれるからです。まず、CARTと異なる点は単一の学習済みモデルを用いるモデルではなく、複数の異なる学習済みの結果の多数決や平均をとることで精度を向上させるアンサンブルモデルだということです。しかし単純にCARTを同じデータと同じハイパーパラメータで学習してもほぼ同じ結果しか返さないため、意味がありません。

　さらなる相違点は、BaggingとRandom Subsapceです。

　Bagging(Bootstrap AGGregatINGの略、復元抽出)は、サンプルN個から各CARTへの入力として重複を許してN個のサンプルの集団をそれぞれ作成することです。こうすることで各CARTが受け付ける入力は少しずつ異なります。当然その学習結果も異なります。サンプルが選ばれない確率は大体 $1/e \approx $ 0.37 = 37%となります。$N$が十分に大きい数としたときに、一度の抽選でとあるサンプルが選ばれない確率は$1-1/N$となります。したがって、それをN回繰り返した際には以下のような関係が成り立ちます。

\left( 1 - \frac{1}{N} \right)^N \approx \frac{1}{e}

実際に以下のスクリプトで試してみるとそんな感じの値になりました。

import numpy as np
N = 100000 # サンプル数
ITER = 1000 # 繰り返し回数
counter = []
for _ in range(ITER):
    rnd_idx = np.random.randint(0, N, N) # 復元抽出。重複を許したランダムな整数の生成と同じ
    unq_idx = np.unique(rnd_idx)         # ユニークな整数の配列を取得
    counter.append(len(unq_idx))         # ユニークな整数の数を格納
1 - np.mean(counter) / N # 0.36783645.　実行ごとに異なる。

　次にRandom Subsapceです。こちらもその名前の通りすべての特徴量を用いるのではなく、ランダムに特徴量を選択し、その中で最も良い分割条件を見つけます。一部しか利用しないため、ランダム性が増します。
ランダムに選択した特徴量がすべて同じ値だったりした場合はscikit-learnのドキュメントには以下のようにあります。

Note: the search for a split does not stop until at least one valid partition of the node samples is found, even if it requires to effectively inspect more than max_features features.
https://scikit-learn.org/stable/modules/generated/sklearn.ensemble.RandomForestClassifier.html#sklearn.ensemble.RandomForestClassifier

Random Subsapceは木の中のノードごとで行うか、それとも木ごとで行うかが考えられます。scikit-learnではノードごとしかない（多分）ですが、LightGBMは木ごとでも設定することができます。
またこれを用いると学習が非常に高速になります。CARTでは全特徴量を用いていたところを一部（scikit-learnではデフォルトが入力特徴量数の平方根）しか用いないからです。たとえば100個の特徴量だった場合には、10個の特徴量しか用いないのでCARTの学習は大雑把には10倍になります。

　実はBaggingでもある程度高速化します。ためしに、scikit-learnのRandomForestClassifierとDecisionTreeClassifierをくらべてみます。RandomForestClassifierはmax_estimator=1とし、bootstrapをTrue/Falseそれぞれで学習時間を計測するため、以下のスクリプトを実行してみました。

from sklearn.ensemble import RandomForestClassifier
from sklearn.tree import DecisionTreeClassifier
from sklearn.datasets import make_classification

# データセット生成
N = 100000 # サンプル数 
D = 50     # 全特徴量数
D_ = 10    # 意味のある特徴量数
X, y = make_classification(n_samples=N, n_features=D, n_informative=D_)

rf_1tree_T = RandomForestClassifier(max_depth=6, n_estimators=1, max_features=D, bootstrap=True,  random_state=42) # bootstrap=True
rf_1tree_F = RandomForestClassifier(max_depth=6, n_estimators=1, max_features=D, bootstrap=False, random_state=42) # bootstrap=False
dt = DecisionTreeClassifier(max_depth=6) # 通常の決定木

%timeit rf_1tree_T.fit(X, y) # 2.73 s ± 67.1 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
%timeit rf_1tree_F.fit(X, y) # 4.28 s ± 35.5 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
%timeit dt.fit(X, y)         # 4.24 s ± 59.2 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

# 下側二つは同じスコアになっている
print(rf_1tree_T.score(X, y)) # 0.8641
print(rf_1tree_F.score(X, y)) # 0.86256
print(dt.score(X, y))         # 0.86256

DecisionTreeClassifierとbootstrap=FalseのRandomForestClassifierはほぼ同じ処理時間ですが、bootstrap=TrueのRandomForestClassifierは3割以上計算時間が削減されています。以下は私の推測です。CARTでの処理時間はほぼソートで占められます。ソート関数を実装したことのある方はよくご存知かと思いますが、ソートの処理時間は要素数のみでは決まりません。配列内の値のユニーク数にも影響されます。QuickSortの各分割の要素数が一定値を下回った際にはInsertionSortに切り替えますが、ユニーク値が少なければInsertionSortに渡される配列は同じ値しか入っていない確率が高く、処理がすぐに終わってくれます。速度向上はこれが原因かと思います。

ちなみに元論文を見てみると、Forest-RIとForest-RCと二つのモデルが提案されています。Forest-RIのRIはRandomInputの略で、RandomForestClassifierとほぼ同一のものです。一方RCはRandom Combinationの略でCART-LCというOblique Treeをベースとして用いたアルゴリズムです。正直ちゃんと文献を見るまで存在を知りませんでした。

Extra Trees

　次にExtra Treesについての解説です。

　といってもこちらは特に解説することがありません。単純にExtraTreeをアンサンブルするのみです。

その他のアンサンブルモデル

　その他のアンサンブルモデルについて紹介いたします。実装はしていないものばかりです。

6. Random Forest, Extra Trees

Random Forest, Extra Trees

Random Forest

Extra Trees

その他のアンサンブルモデル

Rotation Forest

Canonical Correlation Forests

Sparse Projection Oblique Randomer Forests