scikit-learnで機械学習:決定木(1)

犯罪予測における時空間分析の研究にずいぶん時間を使っていてブログが放置状態でしたが、久々の更新。
だいぶ遠のいていた機械学習の進めます。

Scikit-learnで決定木やってみます。
参考にしたのは、scikit-learnの本家、Decision Treeの項目。

アルゴリズムの理解にはじパタ(p.176-183)を補助で活用。

はじめてのパターン認識

ざっと眺めたところどうやってノードを分割するかと、どうやって木の大きさを決めるのかが分析において意味を持ちそうなので、
理論を追いかけながら、手を動かしてみます。

ノードの分割方法

ノード分割の基準になるのは不純度(impurity)と呼ばれる評価関数。
この関数は

を定義し、関数はに対して、
(1)は、すべてのにたいして、のとき、すなわちどのクラスの事後分布も一様に等しいとき最大になる。
　⇛どこで分割しても一緒やんってときが最大値。
(2)はあるについてとなり、≠のとき、すべて、すなわちただ一つのクラスに定まる時最小になる。
　⇛ここで分割すれば良いよねということを最小値で示す
(3)は、について対象な関数である。
を満たせば何でも良いとのこと。

scikit-learnではGini impurity と information gainが選べる。
Information gainの方は具体的にどの関数を具体的につかってるかイマイチよくわかんなかったので、
とりあえず、デフォルトで使われてるジニ係数の方で進めてみることにします。

ジニ係数

はじパタ p.182より、

はノードtにおける誤り率。
この誤り率が一番下がる分割を選びたい。
従って、=データがLに分類される確立、＝がRに分類される確率とすると、分割がsとしたとき、

が最大になるsを求めることになる。

木の大きさを決める

木をどこまで成長させるかには、色々な方法論があるっぽいです。

scikit-learnにおいては、主に下記のパラメータによって制御する。
max_depth : 木の大きさ(深さ)の上限
min_split : ノードにおけるデータ数の下限

またはじパタの中では誤り率と木の複雑さから構成されるコストという概念が紹介され、
誤り率を終端ノード数をとすると、

という関数でコストが定義されています。
で、この関数はが正則化パラメータの役割を果たしていて、誤り率と木の複雑さのどちらに重きをおくかを制御できると。

直感的であることが売りの決定木であれば、深さとデータ数で剪定するので良いのかもですね。

次回、実際にデータを用いてscikit-learnを走らせてみます。