乱れた森林再生委員会(学習集会)

What I cannot create, I do not understand.(作ることができないなら,理解できていないということだ) - R. Feynman(物理学者)

木を育てる その1:不純度を計算して最適な分割点を探す(ジコリューで行こう!#1)

f:id:tatamiyatamiyatatatamiya:20190217231702p:plain

どうも木多郎*1です。

今日は決定木を自己流で実装する第一回です。

基本的にこんな感じかな?でやっていくので,もしかしたらscikit-learnなどで用いられる一般的な実装とは,アルゴリズムからして異なっているかもしれません。

そこらへんはおいおい修正していくことにして,とりあえず実装してみます。

この記事では,Gini係数を計算して不純度を求め,最適なデータの分割方法を探る部分を実装します。

分割後のデータをさらに分割して枝葉を広げていくところは次回以降に行います。

アルゴリズムの全体像

ここでは以下のように学習を行なっていきます:

  1. 分割を行う特徴量を選ぶ
  2. 適当な位置で分割し,不純度を計算する
  3. 分割位置をずらしていって,不純度が最小になる点を見つける
  4. 全特徴量で同様に行い,不純度が最小になる特徴量・分割点の組み合わせを求める
  5. 分割後の断片で同じことを繰り返す

これを,適当な条件を満たすまで続けていきます。

停止の条件としては,とりあえず今は,

  • 分割後の断片のデータ数が閾値より少ない
  • 分割の深さが一定値以下
  • 不純度が一定値以下

のいずれかを満たした場合,としようと思います。

今回扱うのは1~4の部分です。

使うデータ

無難にirisデータセットを使います。 アヤメのがく片,花びらの長さと幅から品種を予測します。

読み込み

scikit-learnのサンプルのやつを読み込んできます。

from sklearn import datasets
import numpy as np

iris = datasets.load_iris()

X = iris.data
y = iris.target

データの説明

X : 各列に以下の値が入っています。

  • がく片長さ(cm)
  • がく片幅(cm)
  • 花びら長さ(cm)
  • 花びら幅(cm)

y: 3種類の品種がラベルづけされています。

  • 0 -> Iris-Setosa
  • 1 -> Iris-Versicolou
  • 2 -> Iris-Virginica

実装

不純度の計算

一般的には不純度の計算にはentropyとGini係数が使われますが, とりあえず今回はGini係数の方でやってみます。

Gini係数の定義:

\sum _ {k=1} ^{K} (1-p_k) p_k = 1 - \sum _{k=1} ^{K} p_k ^2 *2

全K個あるクラスのうちk番目のクラスの確率をp _ kと書きます。

この値は,p_kの値が全てのkで等しい時(p_k=1/K)に最大値を取り,特定のクラスしか存在しない場合0を取ります。

したがって,データセットを二分割した場合,Gini係数が小さいほど特定のクラスがマジョリティを占める綺麗な分割であることを意味します。

これを以下のように実装します。

def gini(y):
    _, counts = np.unique(y, return_counts=True)

    prob = counts / len(y)
    
    return 1 - (prob * prob).sum()

例えば,がく片幅が2.5cm以上かどうかで分割する場合,得られる不純度は0.637となります。

mask_divide = X[:, 1] > 2.5
y_upper = y[mask_divide]
y_lower = y[~mask_divide]

gini_divide = (gini(y_upper) * len(y_upper) + gini(y_lower) * len(y_lower)) / len(y)

二分割した2つの切片でそれぞれGini係数を計算し,データ数で重み付け平均を取っています。

分割しない場合の値0.666...と比べると,ほんの少ししか下がっていませんね。

分割点を動かす

上の例ではX[:, 1] > 2.5と適当に分割点を設けていましたが,今度は分割点をシステマティックに動かしながら同様に不純度を計算し,最小値をとる分割位置を探索します。

探索範囲をどう決めるかですが,適当なビン幅を決めて等分割していってもいいのですが,今回はデータの値そのものを使ってしまいます。

まずデータセットに入っているがく片幅の値X[:, 1]をユニーク化して,それぞれの値を分割の閾値にして不純度を計算していきます。

def find_optimal_division(x, y):
    list_gini = []
    x_unique = np.unique(x)

    for threshold in x_unique:

        mask_divide = x > threshold
        y_upper = y[mask_divide]
        y_lower = y[~mask_divide]

        gini_divide = (gini(y_upper) * len(y_upper) + gini(y_lower) * len(y_lower)) / len(y)

        list_gini.append(gini_divide)
        
    array_gini = np.array(list_gini)
    i_div_opt = np.argmin(array_gini)
    
    return x_unique[i_div_opt], array_gini[i_div_opt]

これにより,不純度が最小となる分割点とその時の不純度が得られました。

今回は,がく片幅3.3cmで分割するのが最適で,その際の不純度は0.540となりました。先ほどの適当な分割よりマシになりましたね。

find_optimal_division(X[:, 1], y)

全特徴量で調べる

上記ではがく片幅で分割してみましたが, 今度は他の特徴量でもみていきましょう。

Pythonのリスト内包表記を使えば一行で書けます。

[find_optimal_division(X[:, i], y) for i in range(0, X.shape[1])]

これにより,下記のような結果が得られました:

[(5.4, 0.4389063317634746),
 (3.3, 0.539743283106115),
 (1.9, 0.3333333333333333),
 (0.6, 0.3333333333333333)]

花びらの長さか幅で分割すると最も不純度が下がるようです。

numpyのapply_along_axis関数を使って下記のように書き直し,不純度が最小になる特徴量(のindex)と分割の閾値を変数に格納しておきます。

results = np.apply_along_axis(find_optimal_division, 0, X, y)

arg_div = np.argmin(results[1])
x_div = results[0, arg_div]

出力:

arg_div, x_div
#(2, 1.9)

花びらの長さと幅が同率一位ですが,便宜上先にヒットする長さの方が選択されます。


今日のところはここまで。 次回は分割を繰り返して枝を伸ばしていきます。

*1:北海道札幌市澄川にある老舗スープカレー屋の一つ。木造の店で野郎がカレーを作る店だからこの名前にした,とか。

*2:TeX表記がうまくできない。。。直せました!(参考)