決定木にて分類の基準によくジニ係数（Gini inpurity / Gini index）という尺度が使われる。
このジニ係数について少し考察してみたのでメモ。
ジニ係数の定義と挙動
あるデータセット\(t\)の中に\(K\)種のクラスのサンプルが含まれる場合、ジニ係数は
\[
I(t)= \sum_{i\neq j} P(C_i|t)P(C_j|t)=\sum_{i=1}^{K} P(C_i|t)(1-P(C_i|t) = 1- \sum_{i=1}^{K}P^2(C_i|t)
\]
と定義される。
ここで\(P(C_i|t)\)はデータセット\( t \)の中に含まれるクラス\( i \)のサンプル数の割合である。
この定義式を元に２つのクラス（0, 1)が含まれる２０個のデータを例にクラス0が含まれる数に応じたジニ係数の変化をプロットしたのが下図。期待通りデータセットの中に各クラスのデータが均等に含まれれば含まれるほどジニ係数の値は大きくなり、偏って含まれれる場合は小さくなり、純粋に１つのクラスしか含まれない場合はゼロになる。
ジニ係数の解釈
ジニ係数の定義は「データセットの中から無作為に２つサンプルを取り出したときに異なるクラスのサンプルが取り出される確率」と解釈するとわかりやすい。
データセット\( t \)の中から無作為に2回取り出すベルヌーイ試行
*1を考えたときに、同じクラスのサンプルが取り出される確率は\( \sum_{i=1}^{K}P^2(C_i|t) \)。その逆で異なるクラスのサンプルが取り出される確率は、\( 1- \sum_{i=1}^{K}P^2(C_i|t)\)となり、これがジニ係数の定義と一致するというわけ。
複数データセットでのジニ係数
決定木アルゴリズムでは決定木のノードで元のデータセットを２つ（\(L\)と\(R\)）に分割する。そのためこの分割後の２つのデータセット全体の不純度が小さい分割の仕方を選ばないといけない。そのため決定木アルゴリズムでは、
\[
I_{split}(t)= p_{L}I(t_{L}) + p_{R}I(t_{R})
\]
の量が最小となる分割方法を見つけることになる
*2。ここで\(p_{L}\)と\(p_{R}\)はそれぞれ分割後のデータセットのサンプル数の元のデータセットに対する割合。
ジニ係数と交差エントロピー
はじめてのパターン認識でも書かれているけど、不純度の尺度はジニ係数だけではなく、交差エントロピー
\[
I(t)= -\sum_{i=1}^{K}P(C_i|t)\log P(C_i|t)
\]
も使われることがある。ただし、
挙動がほぼ同じということと、ジニ係数であれば、
計算コストの高いLogの計算をしなくて良いため、ジニ係数が利用されることが多い様子。
ジニ係数の実装@Python3
折角なのでPythonでジニ係数を計算する関数をPythonで実装してみた。上記\( I_{split}(t)\)を計算するコードです。
ここのジニ係数を計算する関数を参考にした。ただしジニ係数の定義上、ジニ係数の計算時に存在するクラスを事前に知る必要がないはず
*3なのでデータセットだけを関数に渡す方式に変更している。
(*1): サンプルを複数回無作為に取り出す際に、一度取り出したサンプルを「戻して」再度サンプルを無作為に取り出す試行。
(*2): 初めてのパターン認識の(11.11)式。
(*3): たとえ対象のデータセットの中に現れないクラスが存在したとしてもそれはジニ係数に寄与しない。
