０から決定木!

10か月前公開・10か月前更新・2 min read

Metricspython

決定木系モデルを一通り学ぶ。

1 決定木のアルゴリズム

決定木は、予測値の解釈性に優れている点で魅力的なモデルである。一連の質問に基づいて決断を下すという方法を繰り返すことでデータを分類する。

Classificationには分類木、Regressionには回帰木が対応する。

1.1 情報利得の最大化

質問によるデータの分割は、情報利得（information gain: 分割された集合の要素のばらつきの減少）が最大となる特徴量で分割する方法をとる。情報利得 $IG$ は以下のように定式化される。

IG(D_p,f)=I(D_p)-\sum^m_{j=1}\frac{N_j}{N_p}I(D_j)

$f$ は分割を行う特徴量、 $D_p$ は親（分割前）のデータセット、 $D_j$ はj番目の子ノード（分割後）のデータセット、 $I$ は不純度（impurity: 異なるクラスのサンプルがノードにどの程度でまざっているか定量化する指標）、 $N_p$ は親ノードのサンプル数、 $N_j$ はj番目の子ノードのサンプル数をそれぞれ指す。式の通り、 $IG$ は子ノードの不純度が低いほど大きくなる。**不純度指標をエントロピーとして、親ノードから3つ以上の子ノードを生み出すことを繰り返すアルゴリズムは"C4.5"と呼ばれることで有名である。**上式はm個の子ノードに分割する一般的な式だが、組み合わせ探索空間を減らすため、ほとんどのライブラリは二分決定木を実装している。つまり、親ノード $D_p$ から、子ノード $D_{left}$ ・ $D_{right}$ に分割される。よって式は以下のようになる。

IG(D_p,f)=I(D_p)-\frac{N_{left}}{N_p}I(D_{left})-\frac{N_{right}}{N_p}I(D_{right})

親ノードから左右２つの子ノードを生み出すことを繰り返すアルゴリズムは"CART"（Classfication And Regression Tree）と呼ばれることで有名である。

CARTでは分類タスクの時、twoing crietionという情報利得について別のメソッドをオプションに持っていて、

IG(Dp,f)=\frac{N_{left}}{N_p}\frac{N_{right}}{N_p}(\sum^c_{i=1}|p(i|D_{left})-p(i|D_{right})|)^2

で規定される。

note: あらゆるライブラリで実装されているfeature_importance、つまり、特徴量 $f$ の重要度は何を示しているのかというと、特徴量 $f$ で分割することでどのくらい情報利得が生じたかを表している。

1.2 不純度の指標

不純度（impurity）を表す指標は分類木では、ジニ不純度（Gini impurity）: $I_G$ 、、エントロピー（entropy）: $I_H$ 、分類誤差（classification error）: $I_E$ の３つ、回帰木では平均2乗和誤差（MSE）が存在する。

1.2.1 ジニ不純度

誤分類の確率を最小化する条件と解釈できる指標である。定義は以下。

I_G(t)=\sum^c_{i=1}p(i|t)(1-p(i|t))=1-\sum^c_{i=1}p(i|t)^2

最大になるのはクラスが完全に混合されている時である。

1.2.2 エントロピー

すべての空でないクラス $i$ を対象にしたエントロピーの定義は以下のようになる。

I_H(t)=-\sum^c_{i=1}p(i|t)log_2p(i|t)

$p(i|t)$ はノード $t$ においてラベルがクラス $i$ のサンプルの割合を指す。エントロピーは平均情報量ともいわれる。

「情報量（じょうほうりょう）やエントロピー（英: entropy）は、情報理論の概念で、あるできごと（事象）が起きた際、それがどれほど起こりにくいかを表す尺度である。ありふれたできごと（たとえば「風の音」）が起こったことを知ってもそれはたいした「情報」にはならないが、逆に珍しいできごと（たとえば「曲の演奏」）が起これば、それはより多くの「情報」を含んでいると考えられる。情報量はそのできごとが本質的にどの程度の情報を持つかの尺度であるとみなすこともできる。」(by wiki)

ここで、事象 $E$ が起こる確率を $P(E)$ とするとき、事象 $E$ が起こったことを知らされたとき受け取る（選択）情報量 $I(E)$ を

I(E)=\log \frac {1}{P(E)}=-\log P(E)

と定義される。よってエントロピーは有限集合中、起きうる全事象から受け取る情報量をそれぞれの事象が起きる確率で重みづけ平均した情報量であり、平均情報量と呼ばれる所以である。

よって今回 $I_H$ は有限集合であるノード $t$ から受け取ることのできる平均情報量を表しているのである。

2値分類の場合、 $p(i=1|t)=1or0$ でエントロピーは最小 $0$ になる。エントロピーが最大になるのはジニ不純度と同様にクラスが完全に混合されている場合、つまり $p(i=1|t)=0.5$ の時である。

1.2.3 分類誤差

以下のように定義される。

I_E(t)=1-max(p(i|t))

多数派がどれだけ大多数か示すことで純度を測っている。

以上3つの指標を比較してみよう。

ここでは2値分類を例として考える。クラス（0, 1）に対して親ノードのサンプル数を（40, 40）とする。以下の2通りの分岐を考えてみる。

A: (40,40)-->(30,10)(10,30)

B: (40,40)-->(20,40)(20,0)

それぞれのケースで情報利得はどのような値をとるのだろうか？

ジニ不純度の場合、

A: 0.125, B: 0.16666666666666669

となり、Bでの分割を優先することがわかる。実際問題そちらの方がより純粋である。

エントロピーの場合、

A: 0.1887218755408671, B: 0.31127812445913283

となり、同様にBでの分割を優先することがわかる。このように、ジニ不純度とエントロピーは非常によく似た結果になることが知られていて、2択に時間をかける優先性はあまりない。

分類誤差の場合、

A: 0.25, B: 0.25

となり、AとBを同等に評価していることがわかる。このように分類誤差はノードのクラス確率変化にあまり敏感ではないので決定木の成長に適していない。一方、過学習を防ぐため、決定木の分岐の深さに制限を設ける剪定（prune）には役立つ。

ちなみにtwoingはどうなるのか、

A: 0.25, B: 0.33333333333333337

なるほど、一応Bをうまいこと優先しているようだ。

1.2.4 最小2乗和誤差

回帰に決定木を使用するには、連続値変数に適した不純度指標が必要である。そこで、ノード $t$ の不純度指標として代わりにこの指標が使われ、

I(t)=MSE(t)=\frac{1}{N_t}\sum_{i\in D_t}(y^{(i)}-\hat{y}_t)^2

\hat{y}_t=\frac{1}{N_t}\sum_{i\in D_t}y^{(i)}

と定義される。ここで、 $N_t$ はノード $t$ のサンプル数、 $D_t$ はノード $t$ のサブセットインデックスの集合、 $y^{(i)}$ はラベル（真の目的値）、 $\hat{y}_t$ はサンプルの平均（予測された目的値）として扱う。

決定木回帰の文脈で、この指標はよく「分割後のノード分散」と呼ばれる。分割条件はこれにならってよく「分散減少」（variance reduction）と呼ばれる。

2 決定木の実装

それでは単純な1本だけの決定木を実装してみよう。ここでは単純のため分類木に焦点をあてて実装してみる。（前に作った関数を流用したいのでクラス内メソッドに書き直しません、後決定木の図示はめんどいのでSklearnに任せます..）

2.1 最適な特徴量と閾値を選択する

親ノードから左右ノードへ分岐する際に情報利得が最も大きくなるように、分岐の基準とする特徴量とその閾値を求める。

今回はSklearnのIrisデータをお試しに使う。まずはデータを読み込む。

先ほどの関数を使ってみると、

Information gain: 0.3294995369039634, Best threshold: 3.0, Best feature: petal length (cm)

petal length (cm) 特徴量で閾値を3にした時に初めのベストな分割が行えるようだ。

2.2 再帰的にノード分割を行う

ノードクラスをつくって、クラス内でsplitメソッドにより子ノードを再帰的に繰り返す。これは左右分割後に、それぞれに対応するノードクラスをleftとright変数に格納してあげることで達成できる。

具体的に、変数left.method_nameはleftに格納されたノードクラスのmethod_nameを呼び出していて、そのメソッドでさらにleftノードクラスのleftとrightに分割されたノードクラスが格納され、さらに格納されたノードクラスのmethod_nameが呼び出されるというように繰り返される。制限をつけないと無限ループするので、ストップする基準としてmax_depthに達するか、左右子ノードの不純度が０（クラスが1種類しか含まない）という条件を使うことにする。

結果として学習後にこのノードクラスが成長後のすべてのノードを蓄えていることになる。また、IG_maxを特徴量ごとに足し合わせれば各特徴量の重要度を計算できる。

2.3 All in one

最後に決定木分類器クラスを作ってデータへの学習と予測メソッドを設定する

最後にIrisデータセットで学習してみると、

Depth: 0, Sep at Feature: 2,Threshold: 3.0, Label: 2 Depth: 1, Sep at Feature: 2,Threshold: 5.0, Label: 2 Depth: 2, Sep at Feature: 2,Threshold: 5.1, Label: 2 Depth: 3, Sep at Feature: None,Threshold: None, Label: 2 Depth: 3, Sep at Feature: 0,Threshold: 6.7, Label: 2 Depth: 2, Sep at Feature: 3,Threshold: 1.7, Label: 1 Depth: 3, Sep at Feature: 1,Threshold: 3.2, Label: 2 Depth: 3, Sep at Feature: None,Threshold: None, Label: 1 Depth: 1, Sep at Feature: None,Threshold: None, Label: 0 Classification accuracy: 0.9777777777777777

のようになり、テストデータに対し98%程の正解率をだしており上手いこと成長しているのがわかる。また、左側のノードは深さが３まで、右側のノードは深さが１で止まっていることがわかる。各特徴量の重要度も求められていて、

のように図示される。petal length (cm)、つまり花びらの長さが一番分類に寄与していることがわかる。

sklearnと比較してみると、

Classification accuracy: 0.9777777777777777

となり、同様の精度まで決定木が成長していることがわかる。

またSkleanのライブラリでは決定木の可視化ツールも用意していて以下のように使える。

'iris-tree.png'