目次
決定木分析とは
決定木分析とはデータ群をカテゴリ分けする「分類問題」に対する手法の一つです。
例えばアヤメデータセットでは、変数であるsepal_length, sepal_width, petal_length, petal_widthを元にアヤメの種類を分類します。
決定木分析は以下のように変数一つ一つについて閾値との大小によってどんどん細かくデータセットを分けていく手法です。
分類の方法
前節と重なりますが決定木分析では各変数の値に応じてデータ群を分類分けしていきます。
それぞれのノードでは上から降りてきたデータ群を1つの特徴量をもとに2つのグループに分けます。
例えば最初のノードではpetal_lengthが0.7より小さいものは左のノード、大きいものは右のノードというように2つのグループに分けています。
この図ではノードの色がそのノードに含まれるデータの種類（＝アヤメの種類）を表しており、ノードに含まれるデータが同じ種類であるほど色が濃くなっています。
最終的に終端ノードの色が、次の表のように対応しています。
| 色 | species |
|---|---|
| オレンジ | setosa |
| 紫 | virginica |
| 緑 | versicolo |
パラメータ学習の仕組み
ではどのようにして特徴量とするデータやその閾値を決めるのかを見ていきましょう。
決定木分析では各ノードでデータの「不純度」が低くなるように2つのグループに分割します。
この不純度を定量的に計算する特徴量として、「ジニ不純度」を使用します。
ジニ不純度とは、
I_{Gini} = 1 - \sum_{i=1}^m{\left(\frac{n_i}{N_{0}}\right)}^2
ここで$N_{0}$はデータの総数、$n_i$は$i$番目に分類される（つまりsetosaやversicolorやvirginica）データ数です。
つまり、1から各分類の割合の2乗を引いた値ということです。
例えばA,Bの2つのデータが混合しているデータ群のジニ不純度は以下のようになります。
横軸は全体に対するデータAの割合です。$n_A/N_{AB}=0, 1$のときはAまたはBのデータしかないのでジニ不純度は0、$n_A/N_{AB}=0.5$のときはAとBのデータが半分ずつなので不純度が最大となっています。
ではここで、$N_0$のデータを$N_1$のデータと$N_2$のデータ（つまり $N_1+N_2=N_0$ ）に分割するとします。
このとき分類後のジニ不純度は、次のようになります。
\begin{align}
I_{Gini}^{12} &= I_{Gini}^{1} + I_{Gini}^{2}\\
&= \frac{N_1}{N_0}\left[1-\sum_{i=1}^m{\frac{n_i}{N_{1}}}\right] + \frac{N_2}{N_0}\left[1-\sum_{i=1}^m{\frac{n_i}{N_{2}}}\right]
\end{align}
したがってこの分類により、データ全体$N_0$のジニ不純度は
\Delta I_{Gini} = I_{Gini}^0 - I_{Gini}^{12}
だけ減少したことになります。
例えばA,Bが半分ずつ含まれているデータ群$N_0$を、Aのみのグループ$N_1$とBのみのグループ$N_2$に分けたとすると、
分類前のジニ不純度は
\begin{align}
I_{Gini}^0 &= 1 - \left[ \left(\frac{1}{2}\right)^2+\left(\frac{1}{2}\right)^2\right]\\
&=\frac{1}{2}
\end{align}
分類後の不純度は
\begin{align}
I_{Gini}^{12} &= \frac{1}{2}\left[1 - \left( 1^2+0^2\right)\right] + \frac{1}{2}\left[1 - \left( 0^2+1^2\right)\right]\\
&=0
\end{align}
よってジニ不純度の減少量は$\Delta I_{Gini}=1/2 - 0 = 1/2$となります。
決定木分析ではこのジニ不純度の減少量$\Delta I_{Gini}$が最大となるように各ノードで分類する特徴量やその閾値を決定します。
$\Delta I_{Gini}$を最大化する特徴量や閾値を探索する手法についてですが、これはシンプルに全探索です。
例えば、まずsepal_lengthの値で2つに分類するとします。
このとき閾値は、入力されたデータ群のすべてのsepal_lengthの値を昇順（または降順）に並び替え、その間の値を一つ一つ閾値として分類していきます。
上の表ではsepal_lengthの値が4.3, 4.4, 4.5, ...となっているので、この間の値を閾値として順番に試していきます。
これをsepal_lengthだけでなく、すべての特徴量で試し、その中で最もジニ不純度の減少量が大きい特徴量と閾値を求めます。
重要度の計算
決定木分析では、分類をする際にそれぞれ特徴量がどれだけ分類に寄与しているのかを評価する指標があります。これを「重要度」と呼びます。
重要度は前節で示したジニ不純度を用いて計算します。
特徴量$X_i$の重要度$M(X_i)$は、
\begin{align}
M(X_i) &= \frac{X_iによる分類のジニ不純度の減少量}
{分類前のデータ群と完全に分類した後のデータ群のジニ不純度の減少量}\\
&= \frac{\sum^{X_i}_{j}{\frac{N_j}{N_{all}}\Delta I_{Gini}^j}}
{\sum^{all node}_{j}{\frac{N_j}{N_{all}}\Delta I_{Gini}^j}}
\end{align}
となります。
なので、すべての特徴量の重要度の和は必ず1になります。
\sum_i^{all feature}{M(X_i)} = 1
先程のアヤメデータセットの例では次のようになります。
おわり
scikit-learnを用いた実装例はこちらで公開しています。
今後、他の統計・機械学習手法についてもまとめていく予定なので気になる方は是非ご覧ください。
また、間違っている点の指摘や質問・コメント等はいつでも歓迎しています。