決定木アルゴリズム
目次
はじめに
今まで何も考えずに決定木を使っていましたが、どういうアルゴリズムなのか調べてみることにしました。
決定木アルゴリズムはロジスティック回帰やサポートベクターマシン等のパーセプトロン系のアルゴリズムとは全く異なっており一連の質問を繰り返すことでトレーニングサンプルをクラス分けしていきます。
例えばアヤメの例でいうと、『がく片の長さが4cmより長いか?。それがYesの場合は花びらの長さが5cm以上か?。それもYesの場合は、このアヤメの品種はバージニカである。』というような感じです。
重みをかけて、活性化関数にいれて、さらにクォンタライザーにいれて、、みたいにするパーセプトロン系のアルゴリズムよりは、分類の意味を解釈しやすいですね。
ただ難しいのはどのように質問したら良いか?ということです。
最初の質問の『がく片の長さが4cmより長いか?』ですが、『3cmより長いか?』ではダメなのでしょうか?
ジニ不純度
先程の答えを言うと、質問をしてトレーニングサンプルを2つのグループ(ノードと呼びます)に分けたときに、それぞれのノード内のトレーニングサンプルが完全にクラス分けできているような状態が一番よい質問の仕方です。
『がく片の長さが4cmより長いか?』と質問をして分けたトレーニングサンプルのクラスが、完全にサトセとバージニカに分かれていたらそれが最良の質問ということです。
つまりノード内のトレーニングサンプルのクラスがより不純度が低くなるように分けていくわけです。
決定木アルゴリズムでは、一般的にジニ不純度という指標を使って不純度を算出してやります。
いま1つのノードに注目し、ノード内のトレーニングサンプルが全部で個あり、クラスが全部で個ある状態を考えます。
このノード内で、クラスに属するトレーニングサンプルの個数をとすると、クラスに属するトレーニングサンプルの割合は、
です。
ジニ不純度はを使って以下の式で表されます。
絵で描くと下の様に計算します。
最も不純度が低い状態は、ノードに含まれるトレーニングサンプルが全て同じクラスに属する状態で、この時のジニ不純度を計算すると、
また、最も不純度が高い状態、つまりトレーニングサンプルが全て異なるクラスに属する状態では、
となります。
ジニ不純度は、ノード内の不純度が高くなるにつれて1に漸近して大きくなるので、確かに指標として成り立っていますね。
情報エントロピー
ノード内の不純度を測る指標として、情報エントロピーを用いることもできます。
エントロピーという概念は少々難しいですが、ざっくりいうと物事の乱雑さを測る物理の指標です。
情報エントロピーとは情報量の事なのですが、物理学の一分野である統計力学で定義されているエントロピーと定義式が同じなのでこう呼ばれています。
統計力学的エントロピーと情報量が同じ式で定義され、同じ概念で表現できるというのは面白いですね。
不純度が高い乱雑な状態はそこから取り出せる情報量が多いというイメージですかね。
先ほどのジニ不純度の時と同じ条件で情報エントロピーを算出すると以下の式で表されます。
こちらも最も不純度が低い場合と、高い場合を計算してみましょう。
最も不純度が低い場合は、
また最も高い場合は、
はに対し単調増加なのでこちらも不純度が高くなるにつれて大きくなっているみたいです。
情報利得
決定木では、トレーニングサンプルのグループであるノードを質問を繰り返して行くことで分けていくわけですが、分ける前のノードを親ノード、分けた後のノードを子ノードと呼んでやります。
親ノードと子ノードの不純度を計算し、その差分である情報利得が最大になるように子ノードを分けていきます。
具体的に考えていきましょう。親ノードを2つの子ノード、に分けることを考えます。
親ノード内のトレーニングサンプルの個数を、子ノード内のトレーニングサンプルの個数をそれぞれ、、また分割する特徴量をとすると、親ノードから子ノードにトレーニングサンプルを分けたときに得られる情報利得は、
で計算します。
情報利得とはその名の通り、親ノードから子ノードへグループを分けたときにそこから得られる情報量という意味です。不純度は情報量と同じ概念として考えることができるのでこう呼ばれています。
情報利得が最大になるということは子ノードの不純度が最小になるということで、つまり子ノード内のクラスの純度が、より高くなるように分けていきます。
親ノードを子ノードに分け更にその子ノードに分け、、を繰り返しそれ以上分ける事が出来なくなったノードをリーフと呼びます。木の葉っぱということですね。
最後までノード分けを実施してしまうと、過学習状態(新しいサンプルデータに対し汎用性のない分類機になってしまう)に陥ってしまうため、実際は最後までノード分けせずにノード分割する回数(ノードの深さ)のMax値を指定したり、ノード分けで次第に小さくなっていく情報利得に閾値を設けて途中で中断するのが一般的なようです。
決定木でノードを分けていく方法は色々あるみたいですが、実数の特徴量でトレーニングサンプルを上記の様に2分木に分けていく方法はCART法と呼ばれており、scikit-learnの決定木でも採用されているみたいです。
具体例
アヤメの例をつかって、情報利得が最大となる質問を調べてみる事にしましょう。
最近知りましたが、アヤメのデータは既にscikit-learnに入っているみたいですね。
それを使って、最初の質問としてどの特徴量のどの値で分けると情報利得が最大になるか調べてみます。
まず4つある特徴量の1つに注目しその値を昇順に並べます。その後昇順に並べた値の各中間値でトレーニングサンプルを分けて行き、最大となる情報利得を計算してやります。
4つの特徴量全部でこの操作を繰り返してどの特徴量のどの値で質問するのがベストかを見てやります。
不純度指標にジニ不純度を使った場合
不純度指標にジニ不純度を使い、4つの特徴量それぞれで情報利得が最大となる値を算出しグラフにプロットしたものです。
情報利得が最大となるのはpetal length
つまり『がく片の長さ』を2.45cmで分けた場合か、petal width
『がく片の幅』を0.8cmで分けた場合ですね。
情報利得の最大値が同じ値で2つある場合はどうするんでしょうね?まあ特にこだわらなくてもクラスインデックスが小さい方でいいでしょう。
不純度指標に情報エントロピーを使った場合
sepal length
が微妙に違いますが、不純度指標に情報エントロピーを使った場合も情報利得が最大となる質問は同じですね。