決定木についての概要を以下の記事で解説しました。
ここでは実際にどのように決定木を作成していくのかを解説していきます。
分岐条件の決め方
決定木の作り方は
データをある条件で振り分けて分割→分割したデータを更にある条件で振り分けて分割→・・・
と、全てのデータをある程度綺麗に分類分けできるまで繰り返します。
これを実際に行おうとした場合、
「ある条件で振り分ける」の「ある条件」とはどうやって決めるのか？
という疑問が出てくるのですが、データを振り分ける際の「ある条件」とは、ずばりデータを一番綺麗に分けることができる条件となります。
そして、データが綺麗に分かれているかどうかを示す係数としてエントロピーとジニ不純度という2つの指数が用いられます。
エントロピー
エントロピーは
原子的排列および運動状態の混沌(こんとん)性・不規則性の程度を表す量。
という意味だそうです。データがどれだけごちゃごちゃしているかを表す指数と言えます。
このエントロピーですが、以下の式で算出することができます。
$$I_H(P_1,P_2,…P_n)=-\sum_{i=1}^nP_ilog_nP_i$$
\(P_i\)は現在のノードに置ける、ある分類の数が占める割合です。例えば以下のように○と×という分類があり、○が2個、×が3個だったとします。
\(P_1\)を○、\(P_2\)を×とすると、\(P_1=\frac{2}{5}\)、\(P_2=\frac{3}{5}\)となります。
また、実際にこのノードのエントロピーを計算してみると
\(I(\frac{2}{5}, \frac{3}{5})=\frac{2}{5}log_2\frac{5}{2}+\frac{3}{5}log_2\frac{5}{3}≒0.4\times1.32+0.6\times0.74=0.972\)となります。
このエントロピーを用いて、データ分割後のエントロピーが一番低くなる条件を見つけます。
例えばデータ数が10個でエントロピーが0.8のノードをある条件で分割したところ、データ数が3個でエントロピーが0.1のノードAとデータ数が7個でエントロピーが0.7のノードBに分割できたとします。
この場合、全データがノードAとノードBに対して3:7の割合で分割されたので、エントロピーも3:7の割合でまぶしてやります。そのため分割後のエントロピーは
\(0.1\times\frac{3}{10}+0.7\times\frac{7}{10}=0.52\)と計算できます。この場合、分割前が0.8で分割後が0.52なので、分割することで0.28だけエントロピーが良くなったと言えます。
この、分割前と分割後のエントロピーの差を情報利得と言い、この数値が一番高い分割条件で分割してやります。
エントロピーによる分割例
実際にエントロピーを用いてデータを分割してみます。
サンプルとして、以下のデータにて行ってみます。
分割前のエントロピーは〇が7個で×も7個と分類が半分ずつになっているのでエントロピーは1です。
そして帰宅時間と就寝時間それぞれで分割した場合の情報利得を計算すると以下の通りです。
就寝時間<=22時もしくは就寝時間<=23時で分割すると情報利得が一番高くなるので、今回の場合はこの条件で分割してやれば良いと分かります。
このようにエントロピーを用いて分割していくアルゴリズムはC4.5と呼ばれています。
ジニ不純度
データのごちゃごちゃ度を表すもう一つの指数がジニ不純度です。
ジニ不純度は以下の計算式で算出されます。
$$I_G(P_1,P_2,…P_n)=1-\sum_{i=1}^nP_i^2$$
意味合いとしてはエントロピーと似たような感じで思っておけばよいかと思います。
では実際にジニ不純度を計算してみます。使用するのはエントロピーの計算でも使用した以下のノードです。
5個のデータのうち○が2つ、×が3つなのでジニ不純度は
\(I_G(\frac{2}{5},\frac{3}{5})=1-{(\frac{2}{5})^2+(\frac{2}{5})^2}=0.48\)となります。
また、ジニ不純度による情報利得の計算は
\(ΔI_G(t)=I_G(t_B)-(w_LI_G(t_L)+w_RI_G(t_R))\)と計算します。なお、\(t_B\)は分割前のノード、\(t_L,t_R\) はそれぞれ分割後の左右のノード、 \(w_L,w_R \)はデータ数の割合を表しています。
(10のデータが3と7に分かれたならそれぞれ\(\frac{3}{10},\frac{7}{10}\))
ジニ不純度による分割例
念のためエントロピーで行ったことをジニ不純度でもやってみます。
エントロピーで行った場合と同じく就寝時間<=22時もしくは就寝時間<=23時で分割すると情報利得が一番高くなるという結果になりました。
なお、ジニ係数を用いて分割していくアルゴリズムはCARTと呼ばれています。
C4.5とCARTの違い
C4.5とCARTは以下のような特徴を持っていますらしいです。(ここはあまり理解できていないところです・・・)
C4.5
- 目的変数は離散値のみに対応
- 多分岐可能
CART
- 目的変数は離散値、連続値どちらにも対応
- 2分岐のみしかできない
コメント