こんにちは，木木木林（きききりん）です。

f:id:tatamiyatamiyatatatamiya:20190317194149p:plain

前回までの記事で一通りランダムフォレストの実装を行いました。

予告では今回は回帰を扱うとしていましたが，準備している最中に，分割の情報を記録するノードの構造をもう少し綺麗にできることに気がつきました。

そこで本記事では，今後の拡張性も意識して一般化つつ，木構造の実装整理をしていきたいと思います。

指針

前回までのあらすじと今回やること

前々回の記事では，決定木学習の際に各ノードで探した最適分割の情報は，ノードクラスインスタンスに保存していました。

tatamiya.hatenablog.com

その際に，中間ノードであればnode_internalクラス，葉ノードであればnode_leafクラスと２種類に分けて作成しました。それぞれのノードの役割は以下の通りです：

node_internal : 分割に用いる特徴量と閾値を保存
node_leaf : このノードにたどり着いたデータに割り当てるクラスラベルを保存

ノードにはそれぞれ固有の通し番号i_nodeを振っていました。各中間ノードには，次の行き先となる子ノードの番号も記録してあります。そして作成した全ノードは，keyをi_nodeとした辞書型オブジェクトdict_nodesとして保存していました。

予測を行う時には，i_node=0から順にデータを振り分けつつ，dict_nodeを参照しながら下流のノードへと進んでいきます。

最終的に葉ノードにたどり着けば予測値が得られますが，この際の葉ノード判定はクラスの名前を直接参照して行なっていました。

if node_next.__class__.__name__ == 'node_leaf':
    print(node_next.k_decided)

ノードクラス１種類だけでまとめられないか？

以上の方法では，以下の点で綺麗とは言い難い実装でした：

２種類のノードクラスを定義しなくてはいけない
中間ノード・葉ノードの区別はクラス名で無理やり行なっている
子ノードを参照する際にわざわざdict_nodesを解さなくてはいけない

これに対し，以下のようにノードクラスの構造を変えることで，よりスッキリした実装が実現しました：

ノードクラスを一つにまとめる
- 葉ノードかどうかの情報は，フラグ化してプロパティとして持っておく
子ノードの情報を取得する際は，ノード番号ではなくノードそのものを直接参照する

後者についてはイメージがつきにくいかもしれませんが，ノードクラスのインスタンスに別のノードクラスインスタンスを保存するという入れ子構造を取らせる形になります。

実装

実際に実装したものを見てみましょう。

class Node():
    
    def __init__(self, i_node, depth, criterion, value):

        self.i_node, self.depth = i_node, depth
        self.criterion, self.value = criterion, value
        
        self.is_leaf = False
        
        self.division = {}
        self.child = {0:None, 1:None}
        
    def set_division(self, i_feature, threshold, criterion_diff):
        
        self.division['i_feature'] = i_feature
        self.division['threshold'] = threshold
        self.division['criterion_diff'] = criterion_diff

以前中間ノード・葉ノード別々に作ったクラスと比べて，かなりスッキリしているかと思います。

大きな変更点は，

葉ノード判定用のis_leafプロパティを作成した
- デフォルトはFalseですが，葉ノードにすると決めた時点でTrueに書き換えます
分割の情報はdivisionプロパティに辞書型にしてまとめておく
- 学習の際には，set_divisionメソッドで一括して情報を入れられるようにしてあります。

そのほか，学習指標criterionも持っておくことにした。ここでいうcriterionは，今までいうと不純度の評価に使っていたGini係数です。今回このように一般化した表記に置き換えた箇所がいくつかありますが，Entropyなど別の指標への変更を見据えてこのようにしました。特に回帰だとGini係数が使えず平均二乗誤差(Mean Squared Error)や平均絶対誤差(Mean Absolute Error)などの指標に置き換えなくてはなりません。

また，今回の記事の内容では保存しておく必要はないものの，学習前後での指標値の差criterion_diffも記録します。これは特徴量の重要性を評価するfeature_importanceを計算する際に必要になります。 feature_importanceをはじめ特徴量の重要度や説明性については，また別の機会に解説したいと思います。

葉ノードor中間ノードの決定

今までのアルゴリズムは，葉ノードか中間ノードかはインスタンス生成時に決めていましたが，今回は後から決めます。

まず，今まで通りgo_on_division関数内でデータの最適な分割を探索します。そして，分割後の指標（今まででいうGini係数）の値をもとにフラグを書き換えます。

criterion_initial = node.criterion
arg_div, x_div, criterion_optimized = divide(X, y)
    
criterion_diff = criterion_initial - criterion_optimized
    
if criterion_diff < threshold_criterion:
    node.is_leaf = True

今までは分割後の値そのものに閾値を与えて分割を止めるか判断していましたが，より一般的な実装に近づけるために分割前後の指標値差で判断するように変更しました。これにより，指標自体が比較的大きい値で停留してしまう場合にも分割停止判断を下せるようになります。

子ノードの作成

上記の分割停止基準を満たなかった場合は，分割に用いた特徴量と閾値を保存し，子ノードを作成します。

node.set_division(arg_div, x_div, criterion_diff)

depth_next = node.depth + 1
list_divided = [(X_left, y_left), (X_right, y_right)]
for lr, divided in enumerate(list_divided):
    i_node += 1

    X_i, y_i = divided

    node_next = make_new_node(i_node, depth_next, y)
    node.child[lr] = node_next

ここで，あらかじめ定義しておいたmake_new_node関数を使って，子ノードの原型となる新たなNodeインスタンスnode_nextを作成しています（詳細は割愛します）。

注目すべきは，最後の行node.child[lr] = node_nextです。ここではNodeインスタンスnodeのchildプロパティに直接新しいインスタンスを入れています。

今までの実装では，

今いるnodeのプロパティに子ノードの番号を保存する
辞書型オブジェクトdict_nodesに子ノードの番号と新しく作成した子ノードインスタンスを保存する

の二段階必要でしたが，Nodeインスタンスに直接Nodeインスタンスを入れることで一回で済むようになりました。

あとは木の深さが閾値以下であれば再び分割を繰り返す，一定値に達したら先ほどと同様にis_leafフラグをTrueにして止める，という流れになります。

予測

Nodeクラスを整理したおかげで，予測の部分も比較的簡潔に書けるようになりました。

def pred_each_vector(x, node):

    node_current = node

    while node_current.is_leaf == False:
        division = node_current.division
        lr = int(x[division['i_feature']] > division['threshold'])
        node_current = node_current.child[lr]
    
    return node_current.value

一番最初のノード（根ノードともいう）から出発して，