決定木の学習のイメージ
決定木の学習のイメージ
決定木は、説明変数空間において、線を引いて領域を分割していくことで分類ルールを作る
線を引くというのは、「ある説明変数で、ある値より大きいかどうか」という条件を作ることと等しい
下図のように、線と条件は一対一で対応し、決定木の非終端ノードはこの「条件」に対応する
https://gyazo.com/057e388d61ccdfafa8a6247022a35044
では、この「線」はどうやって引くのか？
領域が「純粋」になるように線を引いていく
決定木のアルゴリズムでは、根ノードから順に、情報利得（information gain）が大きくなる説明変数で順次分割していく
たとえば上の例では、$ x_1の値によって分割することも、$ x_2の値によって分割することもできるが、「どの変数でどのように分割すると、分類に対する情報がたくさん得られるか」を考える
これは、言い換えると、「どの変数でどのように分割すると、領域がより純粋になるか」を考えることになる
この「純粋さ」を計算するために、不純度という指標を考える
不純度の指標はたくさんあるが、よく用いられるものに、ジニ不純度（Gini impurity）があり、以下の式で表わされる
$ 1 - \sum^c_{i=1} p(i)^2
この$ p(i)は、データ全体のうち、クラス$ iのデータが含まれる割合を示す
2クラス分類の場合は、以下を計算すればよいことになる
$ 1 - （1つ目のクラスが含まれる割合）^2 - （2つ目のクラスが含まれる割合）^2
ある領域に関して不純度を計算すると、「いろんなクラスのデータが混ざっている」ほど不純度が大きく、「どれか1つのクラスのデータに偏っている」ほど不純度が小さくなるので、できるだけ不純度が小さくなるように領域を分割していくことになる
不純度の指標には、ジニ不純度のほかにエントロピー（entropy）などがある
なお、ノードの分割の指標にジニ不純度を用いた決定木学習アルゴリズムとしてCART、エントロピーを用いたアルゴリズムとしてC4.5（C5.0）、ID3などがある
ジニ不純度による分割
ジニ不純度を用いた分割の考え方を具体的に見てみましょう
たとえば以下の状態では・・・
https://gyazo.com/1a822916d094bd81a40f5d6c7121bd96
全データが6個のうち、○が4個、×が2個なので、ジニ不純度は
$ 1 - (4/6)^2 - (2/6)^2 = 0.444\dots
と計算できる
この領域を2つに分けることを考える
たとえば、$ x_1で下のように分割した場合は・・・
https://gyazo.com/3f39e2034b4453cf0f5187a9ceab4211
左側の領域は、全データ3個のうち、○が2個、×が1個なので、ジニ不純度は
$ 1 - (2/3)^2 - (1/3)^2 = 0.444...
右側の領域も、全データ3個のうち○2個、×1個なので、ジニ不純度は同じく$ 0.444...となる
2つの領域の「平均的な」ジニ不純度は、これを領域ごとのデータ数の割合で重みづけた平均をとる
$ (3/6)×0.444... + (3/6)×0.444... = 0.444...
つまり、この分割による「平均的な」ジニ不純度は$ 0.444...となる
この場合、分割前のジニ不純度から変化がない → 分割しても各領域が「純粋」な方向に変化していないといえる
一方、同じ$ x_1でも、下のように分割した場合は・・・
https://gyazo.com/865772fe31af9cae6aec70f7a20682de
左側の領域は、全データ4個のうち、○が2個、×が2個なので・・・
$ 1 - (2/4)^2 - (2/4)^2 = 0.5
右側の領域は、全データ2個のうちいずれも○なので・・・
$ 1 - (2/2)^2 - (0/2)^2 = 0
2つの領域の「平均的な」ジニ不純度は、これを領域ごとのデータ数の割合で重みづけた平均をとって
$ (4/6)×0.5 + (2/6)×0 = 0.333...
つまり、この分割による「平均的な」ジニ不純度は$ 0.333...となる
この場合、分割前のジニ不純度から$ 0.111...減少している → 分割前よりも比較的「純粋」になっている
このように、「どこで分割するか」によって、分割前からのジニ不純度の変化量が異なる
以下のように、データに従って、変数ごとに分割の候補点は決まるので、考えうる候補点について「そこで分割した場合にどれだけジニ不純度が減少するか」を計算し、最もジニ不純度が減少する分割を選べばよい
https://gyazo.com/bfcef5b22c7b79ac84eafd5f34e76be3
このように、「最も不純度が減少する分割」をしたのちに、分割した2つの領域それぞれについて、また「最も不純度が減少する分割」を行う、・・・というのを繰り返すのが、決定木の学習アルゴリズム
ジニ不純度を用いた決定木の学習と、図示した決定木の見かた
https://gyazo.com/605769e589d0c20ffc1c0506b60ec72c
https://gyazo.com/0b20abcd758f7581c549759417cbd078
https://gyazo.com/5b5eb8564a28b8ed45eeaababfa7140e
https://gyazo.com/fcf129d7209cb7f742442b606e58af80
https://gyazo.com/85311da98e173129f16ef7f65a5078c5