木を育てる その3：正解ラベルなしのデータを入れて予測を行う（ジコリューで行こう！#3）
この木なんの木？気になる木。 とっても不思議な木ですから。*1
前回・前々回に引き続き，決定木の実装を行なっていきます。
前回では既知のデータと正解ラベルを元に学習を行う部分ができましたので，今回は新しいデータを入れて予測する部分を作っていきたいと思います。
指針
前回までのあらすじと今回やること
関数go_on_dividingに特徴量ベクトルXと正解ラベルyを入れることで，木を深めながら最適な分割を探索していきます。
i_node = 0 go_on_dividing(X, y) ''' === node 0 (depth 1): arg_div -> 2, x_div -> 1.9 === [(1, 0, 2, 1.9, 0)] 0 === node 2 (depth 2): arg_div -> 3, x_div -> 1.7 === === node 3 (depth 3): arg_div -> 2, x_div -> 4.9 === [(1, 0, 2, 1.9, 1), (2, 2, 3, 1.7, 0), (3, 3, 2, 4.9, 0)] 1 [(1, 0, 2, 1.9, 1), (2, 2, 3, 1.7, 0), (3, 3, 2, 4.9, 1)] 2 [(1, 0, 2, 1.9, 1), (2, 2, 3, 1.7, 1)] 2 '''
これにより，
- どの特徴量を，
- どの値で分割し，
- どこまで分割を繰り返せば良いか
が決まりましたので，今度はその情報を元に，正解ラベルなしの特徴量ベクトルを入れて，正解ラベルを予測したいと思います。
各ノードでの分割・予測の情報をどう持つか？
データの分割，もしくはクラス判定を行う部分を「ノード」と呼ぶことにしましたが，特に前者を「中間ノード」，後者を「葉ノード」と呼ぶことにします。
予測を行うにあたっては，各ノードにおいて以下の情報が必要になります。
中間ノードの場合
- 自身のノード番号
- 分割に用いる特徴量のindex
- 分割の閾値
- True, Falseそれぞれの場合の次のノード番号
葉ノードの場合
- 自身のノード番号
- クラスラベル（予測結果）
ここでは，ノードクラスを新たに作成してこれらの情報を格納していきたいと思います。
実装
ノードクラスを定義する
以下のようにして，中間ノードクラスnode_internalと葉ノードクラスnode_leafを作成しました。
両ノードに共通する部分はnode_basisとして定義し，継承させてあります。
class node_basis(): def __init__(self, i_node, depth): self.i_node = i_node self.depth = depth class node_internal(node_basis): def __init__(self, i_node, depth, i_feature, threshold): super().__init__(i_node, depth) self.i_feature = i_feature self.threshold = threshold self.node_child = {0:None, 1:None} def set_node_child(self, lr, i): self.node_child[lr] = i class node_leaf(node_basis): def __init__(self, i_node, depth, k): super().__init__(i_node, depth) self.k_decided = k
上記では挙げませんでしたが，念の為木の深さdepthも持たせてあります。
中間ノードクラスnode_internalでは，分割する特徴量のindexをi_feature，分割の閾値をthresholdとしています。
そして，子ノードの番号をnode_childとして辞書型にして持たせています。
x[i_feature] <= thresholdならば次はnode_child[0]番目のノードに，
x[i_feature] > thresholdならばnode_child[1]番目のノードに行きます。
これらは，学習の際にset_node_childメソッドを使って記録するようにします。
学習結果をノードクラスに記録していく
上述のように作成したノードクラスを，go_on_dividing関数に組み込んでいきます。
def go_on_dividing(X, y, depth=0, threshold_gini=0.05, min_node_size=5, max_depth=3): global i_node, dict_nodes depth += 1 arg_div, x_div = divide_tree(X, y) node_current = node_internal(i_node, depth, arg_div, x_div) dict_nodes[i_node] = node_current print("=== node {} (depth {}): arg_div -> {}, x_div -> {} ===".format(i_node, depth, arg_div, x_div)) mask = X[:, arg_div] > x_div X_right, X_left = X[mask], X[~mask] y_right, y_left = y[mask], y[~mask] gini_left = gini(y_left) gini_right = gini(y_right) list_divided = [(X_left, y_left, gini_left), (X_right, y_right, gini_right)] for lr, divided in enumerate(list_divided): i_node +=1 X_i, y_i, gini_i = divided if gini_i > threshold_gini and len(y_i)>min_node_size and depth+1 <= max_depth: node_current.set_node_child(lr, i_node) go_on_dividing(X_i, y_i, depth=depth) else: node_current.set_node_child(lr, i_node) feature_majority = np.bincount(np.array(y_i)).argmax() node_terminal = node_leaf(i_node, depth, feature_majority) dict_nodes[i_node] = node_terminal
大きく変わったのは，今までdiv_setにリストとして記録していた分割の過程を，辞書型のグローバル変数dict_nodesに入れるようにした部分です。
keyにはノード番号を，valueにはノードクラスのインスタンスを入れています。
このdict_nodesに新しいノードを加えていくのは，次のタイミングです。
1: 新しい分割を行った時
arg_div, x_div = divide_tree(X, y) node_current = node_internal(i_node, depth, arg_div, x_div) dict_nodes[i_node] = node_current
2 : 分割を止め，葉ノードを作成する時
feature_majority = np.bincount(np.array(y_i)).argmax() node_terminal = node_leaf(i_node, depth, feature_majority) dict_nodes[i_node] = node_terminal
予測を行う
これで学習結果を記録できるようになりました。実際にやってみますと，
i_node=0 dict_nodes = {} go_on_dividing(X, y) ''' === node 0 (depth 1): arg_div -> 2, x_div -> 1.9 === === node 2 (depth 2): arg_div -> 3, x_div -> 1.7 === === node 3 (depth 3): arg_div -> 2, x_div -> 4.9 === '''
こうすると，グローバル変数として定義したdict_nodesは以下のようにkeyとvalueが追加されます。
dict_nodes ''' {0: <__main__.node_internal at 0x1222dcfd0>, 1: <__main__.node_leaf at 0x1222dccf8>, 2: <__main__.node_internal at 0x1222dc9b0>, 3: <__main__.node_internal at 0x1222dc908>, 4: <__main__.node_leaf at 0x1222dcc88>, 5: <__main__.node_leaf at 0x1222dc828>, 6: <__main__.node_leaf at 0x1222dceb8>} '''
中間ノードであれば，以下のようにして
- 分割する特徴量のindexと閾値
- 子ノードの番号
を確認できます：
dict_nodes[2].i_feature, dict_nodes[2].threshold ''' (3, 1.7) ''' dict_nodes[2].node_child ''' {0: 3, 1: 6} '''
葉ノードであればk_decidedで割り当てられたクラスを確認できます：
dict_nodes[1].k_decided ''' 0 '''
これを使って，新しいデータが入ってきた場合は以下のように予測を行います。
現在いるノードnode_currentが中間ノードだとして，
x[node_current.i_feature] > node_current.thresholdを判定- Trueなら，
i_node_next = node_current.node_chile[1]番目のノードへ - Falseなら，
i_node_next = node_current.node_chile[0]番目のノードへ
- Trueなら，
node_next = dict_nodes[i_node_next]により次のノードを取得- 中間ノードなら，
node_currentをnode_nextに置き換えて上記を繰り返す - 葉ノードなら
node_next.k_decidedを予測結果として出力する
- 中間ノードなら，
ここで問題になるのが，node_nextが中間ノードか葉ノードかをどうやって判定するかです。
pythonではクラスの名前を.__class__.__name__によって取得することができるので，これで判定してしまいます。
if node_next.__class__.__name__ == 'node_leaf': print(node_next.k_decided)
以上を実装すると，以下のようになります：
def pred_at_node(x, node): lr = int(x[node.i_feature] > node.threshold) i_node_next = node.node_child[lr] return i_node_next def pred_each_vector(x, dict_nodes): node_current = dict_nodes[0] while True: node_next = dict_nodes[pred_at_node(x, node_current)] if node_next.__class__.__name__ == 'node_leaf': return node_next.k_decided else: node_current = node_next
試しに，特徴量ベクトルXから0番目のデータを取り出して適用してみます。
x_sample = X[0] pred_each_vector(x_sample, dict_nodes) ''' 0 '''
さらに全データにこの関数を適用するために，前々回にも出てきたnumpyのapply_alogn_axis関数を使います。
y_pred = np.apply_along_axis(func1d=pred_each_vector, axis=1, arr=X, dict_nodes=dict_nodes)
ただし，ここでは学習に使ったのと同じデータで予測を行なっていることに注意してください。 本来は学習データとは異なるデータで予測を行うべきであり，ここで精度が高かったとしてもあまり意味はありません。
まとめ
以上までの学習・予測の流れを整理して，MyTreeクラスにまとめました。
詳細はGitHubにJupyter notebookをアップしましたのでそちらを参考にしてください。
これを使って，データを訓練用・テスト用に分けて学習し，精度を見てみたいと思います。
from sklearn.model_selection import train_test_split X_train, X_test, y_train, y_test = train_test_split(X, y) tree = MyTree() tree.fit(X_train, y_train) ''' === node 0 (depth 1): arg_div -> 2, x_div -> 1.9 === === node 2 (depth 2): arg_div -> 2, x_div -> 4.8 === === node 3 (depth 3): arg_div -> 3, x_div -> 1.6 === === node 6 (depth 3): arg_div -> 3, x_div -> 1.7 === ''' y_pred = tree.predict(X_test) (y_pred == y_test).sum() / len(y_test) ''' 0.9473684210526315 '''
なんだか機械学習やってる感じが出てきましたね。
以上で決定木による分類の実装は一通りできましたので，次回は複数の決定木を構築して多数決を行うランダムフォレストの実装を行いたいと思います。
*1:次の時代に新しい課税を。MISOJI Expire the Next!
