hatunina’s blog

メモと日記です

決定木のTips的なまとめ

kaggleのhomecreditコンペに参加してkernel丸パクリlightgbmよくわからんけどアウトプットはとりあえず出せるマンになったので、レベルアップを試みとりあえず決定木についてまとめようと思います。 個人的に雰囲気で理解していた箇所をまとめています。 ふんわりな理解なので変な箇所があればご指摘いただけると嬉しいです。 ふんわりなので都度出典を書いていくスタイルです。 あと数式の書き方もよくわかっていません。誰か教えて。

不純度と情報利得

よく見るやつなので簡単に式だけ。

まず、不純度となる情報エントロピーです。

 \displaystyle I _ H(t) = - \sum_{i=1}^c p(i|t) \log _ 2 p(i|t)

ここで、 p(i|t)はノードtにおいてクラスiに属するデータの割合です。

次に、情報利得です。

 \displaystyle IG(D _ p, f) = I(D _ p) - \sum_{j=1}^m \frac{N _ j}{N _ p} I(D _ j)

fは対象となる特徴量、D _ pは親のデータ数、D _ jj番目の子ノードのデータ数です。 同様に、N _ pは親ノードのデータ数、N _ jj番目の子ノードのデータ数です。

二分決定木では下式のようになります。

 IG(D _ p, f) = I(D _ p) - \frac{N _ {left}}{N _ p} I(D _ {left}) - \frac{N _ {right}}{N _ p} I(D _ {right})

上式参考
Python機械学習プログラミング 達人データサイエンティストによる理論と実践 - インプレスブックス P77 ~ P84


どうでもいいんですけど、情報エントロピーを使った際に  p(i|t) が0になることがあります。 ノードtにおいてクラスiが存在しない場合、要は完全にクラスが分類されている場合です。
そんな時、 \log _ 2 p(i|t) \log _ 2 0みたいなわけわからんことになるわけですが、 p(i|t) pとして p \log _ 2 pという関数にロピタルの定理を使うことで、 \displaystyle \lim_{p \to 0}p \log _ 2 p = 0とすることができます。

詳細は下記へ。 science-log.com


あと、エントロピーの底が2だったりeだったり書籍や記事によってばらばらです。 気になったので調べると下記記事にこんな記載がありました。

なお、対数の底は2で無くてもよいが、分類するクラス数と一致させるとIが最大で1となるので計算しやすい。 決定木の学習

例えば、二分決定木においてクラス数が二つだった場合、ノード tにおいて不純度が最大となる状態を表したのが下式です。

 \displaystyle I _ H(t) = - p(1|t) \log _ 2 p(1|t) - p(2|t) \log _ 2 p(2|t)

 \displaystyle = - \frac{1}{2} \log _ 2 \frac{1}{2} - \frac{1}{2} \log _ 2 \frac{1}{2}

 = 1

二つに分けたノードに半々で各クラスのデータが存在するので p(i|t) \frac{1}{2}の状態です。
同様にクラス数が三つだった場合、 p(i|t) \frac{1}{3}の時に不純度が最大になり、下式のように表せます。

 \displaystyle I _ H(t) = - p(1|t) \log _ 2 p(1|t) - p(2|t) \log _ 2 p(2|t) - p(3|t) \log _ 2 p(3|t)

 \displaystyle = - \frac{1}{3} \log _ 2 \frac{1}{3} - \frac{1}{3} \log _ 2 \frac{1}{3} - \frac{1}{3} \log _ 2 \frac{1}{3}

 = 1.584962500721156

底がクラス数と一致しないため中途半端な数字になってしまいます。ここで、底に3を取ることによって不純度が最大の時、1になるようにできます。

各特徴の分割点

不純度・情報利得を使った木の構築は下記のようになります。

① 対象となる特徴の分割候補点を計算
② 各分割点で親データを分割し不純度・情報利得を計算
③ 情報利得が最大となる分割点を保存
④ 1 ~ 3を各特徴で繰り返し、情報利得が最大となる特徴・分割点を探す
⑤ 見つかった特徴・分割点でノードを作る
⑥ 1に戻る

(上記手順、ちゃんとしたソースに辿り着けなかったので正しいか不安です)

ここで、「分割候補点」の求め方が気になります。

はじパタによると、

学習データ数が Nであれば、たかだかN-1個の離散的な分割候補点があるだけである。隣り合った2点の中間を、その特徴軸の分割候補点の一つとすればよい。 はじめてのパターン認識 | 森北出版株式会社 P181


コードで表すとこんな感じです。

import numpy

uniq_feature = np.unique([5.1, 4.9, 4.7, 4.6, 5. , 5.4, 4.6, 5. , 4.4, 4.9])

uniq_feature[:-1]
# array([4.4, 4.6, 4.7, 4.9, 5. , 5.1])

uniq_feature[1:]
# array([4.6, 4.7, 4.9, 5. , 5.1, 5.4])

split_points = (uniq_feature[:-1] + uniq_feature[1:]) / 2.0

split_points
# array([4.5 , 4.65, 4.8 , 4.95, 5.05, 5.25])


コードの参考は下記
決定木による学習 | Code Craft House

darden.hatenablog.com
特徴をnp.uniqueで重複を削除・並び替えて、隣り合う数字の中間を取ればOK。 で、このsplit_pointsを分割候補点として不純度・情報利得を計算し情報利得が最大となる分割点を探せばいいわけですね。

feature importance

なんやかんやすると各特徴の重要度が計算できます。

 \displaystyle FI(f _ j) = \sum_t IG(t,f _ j) n _ t

 f _ jは対象となる特徴、 n _ tはノード tに含まれるデータ数です。 ある特徴が複数のノードで使われることもあるため、それらのノード分割時の情報利得にデータ数を掛けることで表されます。正規化するときは全特徴の重要度で対象となる特徴の重要度を割ります。
ただ、データ数を掛ける理由があまりピンとこず。。。 何か元の式があってそれを展開していくと n _ tが残るんですかね?? 元の式っぽいものが見つからずモヤモヤ。

参考は下記です。

www.slideshare.net

darden.hatenablog.com

まとめ

勾配なんとかかんとかブースティングとかは未だによくわからないのでGoogle Analytics Customer Revenue Predictionでもlightgbmよくわからんけどアウトプットはとりあえず出せるマンになりそうです。