エントロピーと決定木の学習｜高校数学の演習を通して理解する決定木・ランダムフォレスト #4

#1〜#3では決定木やランダムフォレストについて理解するにあたってベースとなる例題についてまとめました。

#4では上記の例題を受けて、実際に決定木の学習についてまとめていければと思います。
以下、目次になります。

1. 決定木の概要と推論に関して
2. 不純度と決定木の学習に関して
3. まとめ

1. 決定木の概要と推論に関して

機械学習の分野においては決定木は予測モデルであり、ある事項に対する観察結果から、その事項の目標値に関する結論を導く。内部節点は変数に対応し、子節点への枝はその変数の取り得る値を示す。 葉（端点）は、根(root)からの経路によって表される変数値に対して、目的変数の予測値を表す。
データから決定木を作る機械学習の手法のことを決定木学習 (英: decision tree learning)、あるいはくだけた言い方では単に決定木と呼ぶ。

（決定木 - Wikipedia）

上記は決定木の概要に関してWikipediaの概説から引っ張りました。記述が若干難しいですが、決定木は意思決定を行うための予測モデルで、木構造で判断を行っていくということです。

上図もWikipediaの例ですが、こちらを元に理解するとわかりやすいかと思います。
このように表から決定木という予測モデルを作っておけば、先々の来客について予測ができ、シフトの最適化に役立てることが可能になります。
これまでが概要になり、推論も含まれていました。一方で、図のような決定木の規則はデータからどのように作れば良いのでしょうか。言い換えるなら、決定木のデータからの学習はどのように行えるのでしょうか。
こちらについては、#3で触れた不純度を元に2節で解説していきます。

2. 不純度と決定木の学習に関して
1節では決定木の概要と推論について解説しました。2節は一見難しそうに感じる決定木の学習について解説していきます。
決定木の学習にあたってまず考えるべきなのが、木の上の方にあたる変数をどのように選択するかです。決定木は条件分岐(if文)の連なりで規則を構成するので、変数を選ぶ順番さえ決まってしまえば、あとはデータに合わせて規則を作るだけになります。
では、変数の順番はどのようにして決めれば良いのでしょうか。こちらを計算を通して求めるにあたっては、基準となる何かしらの指標が必要になります。基準の指標はデータの判別度合いが高い（識別力が高い）ようにすると良さそうです。
この際に基準として用いることができるのが、#3で取り扱った不純度(Inpurity)になります。以下簡易化のため二値分類を仮定した上で下記にジニ係数と情報エントロピーの数式を記述します。
・（ジニ係数）
・（情報エントロピー）
不純度としてはどちらを用いても論理展開上大きな違いはないので、以下ではジニ係数を用いるとします。今回は二値分類なので、Aに分類される確率をpとするとBに分類される確率は余事象なので1-pとなります。まず、決定木の根にあたる場所の不純度を計算します。1節の例ではYesが9件、Noが5件なので、となります。こちらを大元の数式に代入すると、

となります。#3で描いた増減表によりI(Gini)の最大値はの際にとなるので、最大値に概ね近い値が得られていることがわかります。それでは推論の一段階目の天気に着目して分けた際はどうなるでしょうか。こちらをPhase1とし、計算してみます。

ここで、ノードが三つに分かれているため、それぞれのノードにサンプルの数分の重みを与えた加重平均で計算していることに注意です。はよりも小さい値になっており、この際に減った0.1163..を情報利得(情報ゲイン)と定義すると、情報利得は変数を選ぶ際に評価の基準とすることができます。このことにより、学習時において変数の優先度をつけることが可能になります。
決定木はこのように変数の優先度をつけ、予測のための規則を構築していきます。

3. まとめ
#4では#3で可視化した不純度の関数を用いて決定木の学習について解説を行いました。
#5では#2の内容と今回解説した決定木の学習をベースにランダムフォレストについて解説していきます。