ランダムフォレストの理論とフルスクラッチ実装とその解説

はじめに

前回、決定木の記事を投稿したので、次はランダムフォレストの記事を書こうと思います。決定木自体の理論は、前回行ったので、今回登場する数式はとても少なくなると思います。
ランダムフォレスト自体は、決定木さえ分かってしまえば、理論的にはすごく簡単で、理解しやすいモデルです。なぜそんな簡単なモデルが現在も使用され続けているかというと、ランダムフォレストは説明変数がとても多いデータに対して、ロバストという点が挙げられます。説明変数が非常に多くても、線形回帰で言う正則化の様に、重要でない変数は全く分岐条件に登場することが無く、線形回帰で言うところの回帰係数が0に近づくのような、動作になる。要は変数選択的な動作を内部的に持っているという部分が、ランダムフォレストにはあるわけです。そういった意味で、いつ書くかわからないですが、ランダムフォレスト-lernerのようなモデルがあるのだと思います(meta-learnerの手法の一つ)
以上まとめると、ランダムフォレストは、ある程度精度の高い予測精度を誇り、そのうえ特徴量次元が大きい場合に対してロバストであるという点で、現在も使われ続けているモデルということです。

ランダムフォレストとは

ランダムフォレストの説明において、決定木の解説は省こうと思います。詳しくは以下の記事を参照ください。

tomtom58.hatenablog.com

1. ブーストラップサンプリング

ブートストラップサンプリングは、ランダムフォレストアルゴリズムの重要な要素であり、モデルの多様性と汎化能力を高めるために使用されます。

基本概念

ブーストラップサンプルの数： $B$

各サンプルのサイズ： $N$ （元のデータセットと同じ）

ここで、 $B$ は通常、大きな値（例：100, 500, 1000など）に設定されます。 $N$ は元のデータセットと同じサイズです。

サンプリングプロセス

元のデータセットから、ランダムに1つのデータポイントを選択します。
選択したデータポイントを記録し、元のデータセットに戻します（置換）。

3. この過程を $N$ 回繰り返します。

理論的背景

ブートストラップサンプリングにおいて、あるデータポイントが選ばれる確率は以下のように計算できます。

$P(\text{選ばれる}) = 1 - (1 - \frac{1}{N})^N$

$N$ が大きい場合、この確率は約63.2%（ $1 - \frac{1}{e}$ ）に収束します。

特徴と利点

データの多様性: 各ブートストラップサンプルは元のデータセットとは異なる分布を持ちます。これにより、各決定木が異なるデータセットで学習することになり、モデルの多様性が増します。
オーバーフィッティングの軽減: 一部のデータポイントが選ばれず、他のデータポイントが複数回選ばれることで、各決定木は元のデータセットの完全なコピーではなく、わずかに異なるバージョンで学習します。これがオーバーフィッティングを軽減する効果があります。
Out-of-Bag (OOB) サンプル: 各ブートストラップサンプルに含まれないデータポイント（約37%）は、その決定木の性能を独立にテストするのに使用できます。これがOOBエラー推定の基礎となります。
　　
数学的に表現すると

ブートストラップサンプル $S_b$ は以下のように表現できます。

$S_b = {x_1^, x_2^, ..., x_N^*}$

ここで、 $x_i^*$ は元のデータセット $X = {x_1, x_2, ..., x_N}$ からランダムに（置換して）選ばれたデータポイントです。

2. 特徴量のランダム選択

基本概念

特徴量の総数： $M$

各ノードで選択する特徴量の数： $m$

一般的に、分類問題では $m = \sqrt{M}$ 、回帰問題では $m = M/3$ が使用されますが、これらは経験則であり、問題に応じて調整することがあります。

選択プロセス

1. 決定木の各ノードで分割を行う際に、全 $M$ 個の特徴量から $m$ 個をランダムに選択します。

2. 選択された $m$ 個の特徴量の中から、最適な分割基準を見つけます。

3. このプロセスを木の各ノードで繰り返します。

理論的背景

特徴量のランダム選択は、以下の確率で行われます。

$P(\text{特徴量が選ばれる}) = \frac{m}{M}$

これにより、各特徴量が選ばれる機会が均等化され、特定の強い特徴量に過度に依存することを防ぎます。
　　

特徴と利点

多様性の向上: 各ノードで異なる特徴量サブセットを使用することで、木ごとに異なる構造が生まれ、森全体の多様性が増します。
過学習の防止: 全ての特徴量を常に使用すると、強い特徴量に依存しすぎる傾向があります。ランダム選択により、より多様な特徴量の組み合わせを探索し、過学習を軽減します。
計算効率の向上: 各ノードで考慮する特徴量が少なくなるため、計算量が削減され、大規模なデータセットでも効率的に動作します。
特徴量間の相関の影響軽減: 相関の高い特徴量がある場合、ランダム選択によりその影響を分散させることができます。
特徴量の重要度: この方法により、全ての特徴量が森全体で使用される機会を得るため、特徴量の重要度をより正確に評価できます。
次元の呪い: 高次元データにおいて、このアプローチは「次元の呪い」の影響を軽減する効果があります。
　　
数式で表現してみると

ノード $t$ での分割に使用する特徴量集合 $F_t$ は以下のように表現できます。

$F_t = {f_1, f_2, ..., f_m} \subset {1, 2, ..., M}$

ここで、 $|F_t| = m$ であり、 $F_t$ の要素はランダムに選ばれています。

実践における考慮すべき点

$m$ の選択: $m$ の値は、問題の性質や特徴量の数によって調整することがあります。 $m$ が小さいほど木の多様性は増しますが、個々の木の予測精度は低下する可能性があります。

3. 決定木の構築

各ブーストラップサンプルに対して、決定木を構築します。各ノードの分岐には特徴量のランダム選択が用いられます。

$\Delta I = I(parent) - \sum_{j=1}^k \frac{N_j}{N} I(j)$

ここで、 $I$ は不純度measure、 $k$ は子ノードの数、 $N_j$ は子ノード $j$ のサンプル数、 $N$ は親ノードのサンプル数です。

4. アンサンブル予測

全ての木の予測を集約して、最終的な予測を行う部分です。
分類問題の場合：2段階のプロセスを踏みます
1. 各決定木からの確率予測

$P_i(y=k|x) = \frac{\text{クラス}k\text{のサンプル数}}{\text{葉ノードの総サンプル数}}$

2. 確率の集約

$P(y=k|x) = \frac{1}{B} \sum_{i=1}^B P_i(y=k|x)$

ここで、 $B$ は木の総数、 $P(y=k|x)$ はランダムフォレスト全体としての各クラスの予測確率です。

　　
回帰問題の場合：平均値

$\hat{y} = \frac{1}{B} \sum_{i=1}^B y_i$

ここで、 $y_i$ は $i$ 番目の木の予測、 $B$ は木の総数です。

5. Out-of-Bag (OOB) エラー推定

基本概念

OOBサンプル：各決定木の訓練に使用されなかったデータポイント
OOBエラー：OOBサンプルを使用して計算されたモデルの誤差
　　

OOBエラーの計算プロセス

1. 各データポイント $i$ に対して：a. そのデータポイントをOOBサンプルとして持つ決定木のみを使用して予測を行います。b. これらの予測を集約して $\hat{y}_i^{OOB}$ を得ます。

2. すべてのデータポイントに対して、予測 $\hat{y}_i^{OOB}$ と実際の値 $y_i$ を比較します。

3. エラーの割合を計算します：]

$\text{OOBエラー} = \frac{1}{N} \sum_{i=1}^N I(\hat{y}_i^{OOB} \neq y_i)$

ここで、 $N$ は全データポイント数、 $I$ は指示関数で、条件が真のとき1、偽のとき0を返します。

数学的な話

分類問題の場合：OOBエラーは誤分類率を表します。
回帰問題の場合：平均二乗誤差（MSE）などを使用することがあります：

$\text{OOB MSE} = \frac{1}{N} \sum_{i=1}^N (\hat{y}_i^{OOB} - y_i)^2$

OOBエラー推定の利点

追加のテストセット不要: 訓練データのみを使用してモデルの性能を評価できます。
計算効率: 別途クロスバリデーションを行う必要がないため、計算コストが削減されます。
偏りの少ない推定: 各データポイントが複数の木のOOBサンプルとなるため、安定した推定が可能です。
過学習の検出: 訓練エラーとOOBエラーを比較することで、過学習の程度を評価できます。

OOBに関する実践上の考慮事項

OOBエラーは、ランダムフォレストの木の数が増えるにつれて安定します。
OOBエラーは、クロスバリデーションと比較して若干悲観的な推定を与える傾向があります（つまり、実際の性能よりも少し悪く推定されることがあります）。
OOBサンプルは特徴量の重要度の計算にも使用されます。

フルスクラッチ実装

以下がフルスクラッチのコードです。

import numpy as np
from collections import Counter

class DecisionTree:
    def __init__(self, max_depth=None, min_samples_split=2):
        self.max_depth = max_depth
        self.min_samples_split = min_samples_split
        self.tree = None

    def fit(self, X, y, depth=0):
        n_samples, n_features = X.shape
        n_classes = len(np.unique(y))

        # 停止条件
        if (self.max_depth is not None and depth >= self.max_depth) or \
           n_samples < self.min_samples_split or \
           n_classes == 1:
            return {'class': Counter(y).most_common(1)[0][0]}

        # 特徴量のランダム選択 (特徴量バギング)
        feature_idx = np.random.choice(n_features, size=min(int(np.sqrt(n_features)), n_features), replace=False)

        # 最適な分割を見つける
        best_feature, best_threshold = self._find_best_split(X, y, feature_idx)

        # 分割できない場合は葉ノードとする
        if best_feature is None:
            return {'class': Counter(y).most_common(1)[0][0]}

        # データを分割
        left_idx = X[:, best_feature] < best_threshold
        right_idx = ~left_idx

        # 分割後のいずれかのノードにサンプルがない場合は分割しない
        if np.sum(left_idx) == 0 or np.sum(right_idx) == 0:
            return {'class': Counter(y).most_common(1)[0][0]}

        # 子ノードを再帰的に構築
        left_subtree = self.fit(X[left_idx], y[left_idx], depth + 1)
        right_subtree = self.fit(X[right_idx], y[right_idx], depth + 1)

        return {
            'feature': best_feature,
            'threshold': best_threshold,
            'left': left_subtree,
            'right': right_subtree,
            'class': Counter(y).most_common(1)[0][0]
        }

    def _find_best_split(self, X, y, feature_idx):
        best_gain = -1
        best_feature = None
        best_threshold = None

        for feature in feature_idx:
            thresholds = np.unique(X[:, feature])
            if len(thresholds) <= 1:  # 特徴量の値が1つしかない場合はスキップ
                continue
            for threshold in thresholds[:-1]:  # 最後の閾値はスキップ（全てのサンプルが同じ側に行くため）
                left_y = y[X[:, feature] < threshold]
                right_y = y[X[:, feature] >= threshold]
                if len(left_y) == 0 or len(right_y) == 0:  # どちらかの子ノードにサンプルがない場合はスキップ
                    continue
                gain = self._calculate_gain(y, left_y, right_y)
                if gain > best_gain:
                    best_gain = gain
                    best_feature = feature
                    best_threshold = threshold

        return best_feature, best_threshold

    def _calculate_gain(self, parent, left_child, right_child):
        # 情報利得の計算（簡略化のため、エントロピーではなく誤分類率を使用）
        def error(y):
            return 1 - np.max([np.sum(y == c) / len(y) for c in np.unique(y)])

        n = len(parent)
        n_l, n_r = len(left_child), len(right_child)
        
        return error(parent) - (n_l / n * error(left_child) + n_r / n * error(right_child))

    def predict(self, X):
        # 決定木を使用して予測
        return np.array([self._predict_tree(x, self.tree) for x in X])

    def _predict_tree(self, x, tree):
        # 再帰的に木を下り、予測クラスを返す
        if 'feature' not in tree:
            return tree['class']

        if x[tree['feature']] < tree['threshold']:
            return self._predict_tree(x, tree['left'])
        else:
            return self._predict_tree(x, tree['right'])

class RandomForest:
    def __init__(self, n_trees=100, max_depth=None, min_samples_split=2):
        self.n_trees = n_trees
        self.max_depth = max_depth
        self.min_samples_split = min_samples_split
        self.trees = []

    def fit(self, X, y):
        # ランダムフォレストの学習
        self.trees = []
        for _ in range(self.n_trees):
            # ブートストラップサンプリング
            n_samples = X.shape[0]
            idxs = np.random.choice(n_samples, size=n_samples, replace=True)
            X_sample, y_sample = X[idxs], y[idxs]

            # 決定木の構築
            tree = DecisionTree(max_depth=self.max_depth, min_samples_split=self.min_samples_split)
            tree.tree = tree.fit(X_sample, y_sample)
            self.trees.append(tree)

    def predict(self, X):
        # 全ての木の予測を集約
        tree_preds = np.array([tree.predict(X) for tree in self.trees])
        # 多数決で最終予測を決定
        return np.array([Counter(pred).most_common(1)[0][0] for pred in tree_preds.T])

以下が実際にサンプルデータを生成し、モデルを作成し、予測を行う部分です。

import numpy as np
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score, classification_report

# 前回のRandomForestとDecisionTreeクラスの実装をここに含めます
# (スペースの都合上、ここでは省略しています)

# サンプルデータの生成
np.random.seed(42)  # 再現性のために乱数シードを設定

# 特徴量を生成
n_samples = 1000
n_features = 10
X = np.random.randn(n_samples, n_features)

# ターゲット変数を生成 (2クラス分類問題)
y = (X[:, 0] + X[:, 1] - X[:, 2] - X[:, 3] + np.random.randn(n_samples) * 0.5 > 0).astype(int)

# データの分割
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)

print("データセットの形状:")
print(f"X_train: {X_train.shape}")
print(f"X_test: {X_test.shape}")
print(f"y_train: {y_train.shape}")
print(f"y_test: {y_test.shape}")

# ランダムフォレストモデルの作成と学習
rf = RandomForest(n_trees=100, max_depth=10, min_samples_split=5)
rf.fit(X_train, y_train)

# テストデータでの予測
y_pred = rf.predict(X_test)

# 精度の計算
accuracy = accuracy_score(y_test, y_pred)
print(f"\n精度: {accuracy:.4f}")

# 詳細な分類レポート
print("\n分類レポート:")
print(classification_report(y_test, y_pred))

# クラスごとの予測数を表示
unique, counts = np.unique(y_pred, return_counts=True)
print("\nクラスごとの予測数:")
for class_label, count in zip(unique, counts):
    print(f"クラス {class_label}: {count}")

最後に

どうだったでしょうか？決定木の様に完全に理論の説明であれば、もっと綺麗に纏められるのですが、ランダムフォレストは、決定木を利用した仕組み的な話の為、説明の仕方が難しく、若干とっ散らかった説明になってしまった気がします。今回は、コードの解説を完全に省きましたが、ランダムフォレスト特有の部分のコードを読み解くのはそこまで難しくないはずです。一応初心者向けに書いてはいるので、頑張ってみてください（めんどくさくなりましたすみません...）ランダムフォレストは、理論が簡単な割にある程度の予測性能と、次元の呪いに対するロバスト性など、いいモデルであり、いまでも使い続けられているモデルです。SHAPの登場により、より解釈性が高まり決定木系のモデルは使用されるようになったと感じています。最後にですが、前回の記事でも書いた通り、解釈をちゃんとしたい場合はちゃんと多重共線性に注意してください。

はじめに

ランダムフォレストとは

1. ブーストラップサンプリング

基本概念

サンプリングプロセス

理論的背景

特徴と利点

数学的に表現すると

2. 特徴量のランダム選択

基本概念

選択プロセス

理論的背景

特徴と利点

数式で表現してみると

実践における考慮すべき点

3. 決定木の構築

4. アンサンブル予測

5. Out-of-Bag (OOB) エラー推定

基本概念

OOBエラーの計算プロセス

数学的な話

OOBエラー推定の利点

OOBに関する実践上の考慮事項

フルスクラッチ実装

最後に