Randomized Decision Tree, Extremely Randomized Tree

　今回はRandomized Decision Tree と Extremely Randomized Treeの紹介をします。前回の記事で基本的なDecisionTree（DT）の解説は行ったため、今回の記事は短めです。

Randomized Decision Tree：RDT

　このアルゴリズムはRandomForest（後日解説）で用いられているものです。CARTとの違いは

Treeで用いるサンプルが復元抽出したもの
各ノードで利用する特徴量が全体の一部

の２点です。

コード

　１点目は単に根ノードに渡すサンプルインデックスのリストを復元抽出したものに置き換えればよいだけです。

# I = range(N_SAMPLES) # 変更前
I = np.random.randint(N_SAMPLES)

　２点目の分割部分の変更点は以下です。

# C=クラス数
# M=現在のノードのサンプル数
# class_counter_p=親ノードのクラスごとのカウント
# max_features=各ノードで用いる最大の特徴量数
best_gain = -sys.maxsize # 最もよいInformationGain。システム的に最も小さい値で初期化

y   = np.zeros(M)
for i, index in enumerate(I):
    y[i] = Y[index]

# 変更点　ここから
feature_indices = range(len(D))
feature_indices_random_permutation = np.permutation(feature_indices)
for feature_id in feature_indices_random_permutation[:max_features]:
# 変更点　ここまで
    class_counter_l = np.zeros(C)
    x_d = np.zeros(M)
    for i, index in enumerate(I):
        x_d[i] = X[index, feature_id]
    index_x_d_sort = np.argsort(x_d)
    x_d_sorted = x_d[index_x_d_sort]
    y_sorted = y[index_x_d_sort]

    for j in range(len(I)-1):
        label = y_sorted[j]
        class_counter_l[j] += y_sorted[j]
        if x_d_sorted[j] != x_d_sorted[j+1]:
            class_counter_r = class_counter_p - class_counter_l
            M_L = np.sum(class_counter_l)
            M_R = np.sum(class_counter_r)
            gain = gini(class_counter_p) - gini(class_counter_l) * M_L/M - gini(class_counter_r) * M_R/M
            if best_gain < gain:
               best_gain = gain
               best_threshold =  (x_d_sorted[j] + x_d_sorted[j+1]) / 2

　ランダムに並び替えた最初のmax_features個の特徴量のうちに分割可能なものがなければ（例：すべてのサンプルで特徴量の値が同じだった）、それ以降もスキャンし、最初に分割可能な点を選びます。各特徴量についてはDTと同じ計算量を持ちますが、実際に同じデータで各特徴量当たりの処理時間を確認すると、RDTのほうが20%程速くなっていたことがあります。これは、インデックスの復元抽出によるものだと思われます。ソート関数の処理時間はデータ数のみでなく、データのユニークな値の数からも影響を受けます（少ないほうが速くなる）。復元抽出を行うと、およそ3割のデータは使われません。復元抽出ではRDTに投入されるデータは重複が多くなり、その結果ソート処理が少し速く終わるためです。

Extremely Randomized Tree

　短縮してExtraTreeとも呼ばれます。こちらのCARTとの相違点は

全特徴量のそれぞれランダムな分割点を選択、最もよい分割点でノードを分割する

具体的には、

各特徴量の最小値、最大値を取得
一様分布でその間のランダムな点を選択、Criterionで評価
各特徴量の内、最もよい分割点を選ぶ

サンプルの復元抽出もできますが、行わないことが多いようです。

コード

　CART、Randomized Decision Treeより簡単に書くことができます。

# C=クラス数
# M=現在のノードのサンプル数
# class_counter_p=親ノードのクラスごとのカウント
# max_features=各ノードで用いる最大の特徴量数
best_gain = -sys.maxsize # 最もよいInformationGain。システム的に最も小さい値で初期化

y   = np.zeros(M)
for i, index in enumerate(I):
    y[i] = Y[index]

for feature_id in range(len(D)):
    class_counter_l = np.zeros(C)
    x_d = np.zeros(M)
    for i, index in enumerate(I):
        x_d[i] = X[index, feature_id]
    min_val, max_val = np.min(x_d), np.max(x_d)
    threshold = np.random.uniform(min_val, max_val)

    for j in range(len(I)):
        if x_d[j] <= threshold:
            label = y_sorted[j]
            class_counter_l[label] += y_sorted[j]
    class_counter_r = class_counter_p - class_counter_l
    M_L = np.sum(class_counter_l)
    M_R = np.sum(class_counter_r)
    gain = gini(class_counter_p) - gini(class_counter_l) * M_L/M - gini(class_counter_r) * M_R/M
    if best_gain < gain:
        best_gain = gain
        best_threshold =  (x_d_sorted[j] + x_d_sorted[j+1]) / 2

　また、

    for j in range(len(I)):
        if x_d[j] <= threshold:
            label = y_sorted[j]
            class_counter_l[label] += y_sorted[j]

は

    for j in range(len(I)):
        is_less_equal = x_d[j] <= threshold
        label = y_sorted[j]
        class_counter_l[label] += y_sorted[j] * is_less_equal

という風に書いた方が、loop内にIfを残さないために良いと思います。Fortranでは速度が目に見えて向上しました。キャッシュヒットミスが削減されるからだったと思います。上記のPython疑似コードでは確認をしていません。

　上記では分割点の評価をscikit-learnと同様に一度しか実施していませんが、Rの実装ではここを複数回実施するハイパーパラメータもあります（自分が思いついたと思ったら普通に実装されてました...）。ExtraTreeは一回一回の実行が非常に速いので、複数回に設定したほうが良いのではないかと思っています。当然十分な回数実施すればCARTの結果に収束するはずです。

なぜこれらを用いるのか？

　これらのアルゴリズムはところどころ「ランダムに」という言葉が出ることからもわかるように、CARTと予測結果を比べると、予測結果はたいていの場合には悪くなります。では、なぜこれらを用いるのでしょうか？
　基本的には、これらは単体で用いることはなく、Treeの集合、Forestとして用いるからです。よく知られるアンサンブル学習です。一つ一つの性能が悪くとも、それらは単一のタスクを複数の少しずつ異なった観点から学習し、Tree全体としてはCARTに比べると圧倒的に優れた性能を示すことが多々あります。Treeごとにすこしづつ異なった学習ができていればここが６０点しか取れていなくとも、集合として９０点をとることが可能になります。

余談１：Randomnessの向上

　Randomized Decision Tree、ExtraTreeは元のCARTからどんどんRandomnessを向上させています。これらも当然様々な派生があり、私が知っているアルゴリズムだけでも、

Random Rotation Tree
Simulated Annealing Tree
Rotation Tree
Sparse Projection Oblique Randomer Tree

などがあります。最後のSparse Projection Oblique Randomer Tree（この名前自体は確か論文で出ていなかったとおもいます。Sparse Projection Oblique Randomer Forests が元の論文のタイトルです）です。その名の通り、入力をRandom Projectionしたものを用いて学習を行います（多分）。Xgboostに匹敵する速度、精度を示しているようですが、やはり解釈性などに乏しい印象です。

余談２：ExtraTreeについて

　なぜこれらを用いるのかで記載した内容と矛盾してしまいますが、何度も同じコードを走らせていると（乱数の問題で）、ExtraTreeでもCARTの性能を上回ることがありました。scikit-learnにはありませんが、Rには特徴量の分割点の評価をn回実施する、というハイパーパラメータがあります。これを５や１０に設定した場合です。
　CARTでは、各ノードで「最もよい分割点」が選ばれますが、ExtraTreeではもちろんそうではありません。なぜこのようなことが起きるのかは私が良く理解していませんが、推測を述べると、

CARTは全体として「BestなTree」でなく、その場その場（各ノードごと）での「BestなSplitの連続」による「BetterなTree」

でしかなく、全体としてはその場では２番目や３番目、はたまた１０番目に良い分割点を選んだ方が良い場合がある、ということだと思っています。