決定木の学習

トップページ研究分野と周辺記号論理不確実な推論

決定木は木構造をした決定を行うためのグラフで、与えられたデータから適切な決定木を作成する事を、決定木の学習と呼ぶ。
決定木の学習方法には様々な種類があるが、最も単純な方法の一つであるID3アルゴリズムを紹介する。

簡単な決定木の具体例

「天気」「気温」等の天候を示す属性の値の組によって、或る事を「する」「しない」を決定する例がよく説明に使われる。
図は、「天気」「風速」「湿度」の属性値の組によって、花見に「行った」(Yes)、「行かなかった」(No)の事例データが5つあるとした場合になる。
5つのデータに基づき、まず「天気」の質問をして、「晴れ」なら「風速」の質問をするという具合に枝分かれしていく。答えが全部Yes、又は全部Noになれば、そこで打ち切る。

この例では「天気」を最初の質問にしているが、「風速」を持って来てもよい。様々な質問の順番と組合せが考えられ、下手な方法では、決定木が大きくなってしまう場合もある。
ID3アルゴリズムでは、以下の方法で最も簡潔な(質問回数が少なくて済む)決定木を作る事を試みる。

属性(質問)と属性値(答え)の組合せの良し悪し

決定木は、質問を繰り返す事で、そのデータがどのグループ(上記の例ではYesかNo)に属するかを決定するものだから、答えによってデータが良く分離される質問が良い質問と言える。
上記の「天気」の質問では、「雨」の答えはデータが分離されるが、「晴れ」と「曇り」ではYesとNoが1つずつ分かれ、完全に分離されていないので、次の質問が必要になる。
図のように或る質問と答えによって、データが半々になるのが最悪で、数に偏りが出るほど良い状況(後の質問が少なくて済む)と言える。

この「或る質問(属性)と答え(属性値)の組合せ」の良さを数値で示すため、平均情報量(エントロピー)を用いる。

平均情報量(エントロピー)

データが二つのクラスに分かれ、各クラスのデータ数がm個、n個であった場合、平均情報量(I)を以下のように定義する。

各クラスの所属データ数の全体のデータ数に対する割合を用いる。データが完全に分離されていれば、この割合は1と0の組合せになる。
例えば、m/m+n=1(mの方に全データが集まり、n=0の状態)として代入すると、I=0となる(2の0乗が1である事と、対数の定義から容易に分かる)。
データが半々(m=n)の場合、代入するとI=1となる。Iはデータ数に偏りがある程、0に近づき、偏りがない程、1に近づくように出来ている。
なお、三つ以上のNクラスに分類する場合の一般式は以下のようになる。P_1は1番目のクラスのデータの割合を示す。0で割るのを避けるため、-を付けて展開している。

なお、対数の底は2で無くてもよいが、分類するクラス数と一致させるとIが最大で1となるので計算しやすい。
この場合、平均情報量(エントロピー)は、「データが纏まっているか」を表す数と言える。乱雑な部屋やボサボサの髪型は、エントロピーが高いと言えるだろう。

平均情報量に基づく質問の良し悪しの数値化

上記のエントロピーは、「或る質問の或る答え」によってデータがどの程度、纏めるかを測っている。
質問(属性)には複数の答え(属性値)があるので、それを以下のように纏める。
各答えの結果によるエントロピーを其々求め、また、その質問に割り当てられたデータ数の全体(ここでは5)に対して、各答えに該当するデータ数の比率を其々求める。
そして、各答えの結果によるエントロピーに各答えのデータ数比率を掛けたものの総和を求める。
最初の状態のエントロピーより、この総和は小さい値になっている。これは「天気」という質問によって、全体のエントロピーが減少した事を意味している。最初のエントロピーから総和を引いた得点(ここでは0.172)を、「天気」という質問の識別力(情報ゲイン)と言う。

最初の質問(属性)の決定

質問(属性)はここでは「天気」の他に「風速」「湿度」とあるから、其々について識別力を求め、識別力が最大の質問を最初の質問とする。
計算してみると、「風速」の識別力が0.423で最も高い事が分かる。従って、「天気」ではなく、「風速」を最初の質問にするべきだった事が明らかになった。

二番目以降の質問(属性)の決定

最初の質問「風速」で「強い」の場合は全データがNoに分類され終わるが、「弱い」の場合は次の質問が必要になる。
この場合、「風速」以外の質問を順番に当てはめ、其々の識別力を計算して最も高いものを次の質問とする。
試しに「天気」を持ってくると、この質問でデータは全て分類可能である事が分かる。各エントロピーの計算では、データ数は「風速:弱い」に該当するデータが3つなので、3となる。
後は、最初の質問決定のときと同様に計算するが、識別力を求めるときは、「風速:弱い」のエントロピーから引く事になる。

このデータ例の場合は、二つの質問で全て分類出来た。最初が「天気」だと、最初の図のように三つの質問が必要なので、ID3アルゴリズムで決定木が簡略化される事が分かる。
二番目の質問に「湿度」を持って来た場合も調べておく。

この場合は、「高い」の方に全データが行ってしまい、ここでも分類出来ない。第三の「天気」の質問が必要になる。
このように、二番目以降の質問は、分類出来ていない箇所の全てについて、其処に来るまでにまだ行なわれていない質問を一つずつ当てはめ、最も識別力の高い質問を付けていく。

データが空となった場合の処理

上記のように、「風速:弱い」→「湿度:低い」と進んだ場合、YesのデータもNoのデータも0件になってしまった。
このままでは、エントロピーが計算出来ないので、以下のように扱う。
一つ上の「風速:弱い」で分類されたデータのYesの件数、Noの件数の多い方に、(仮に)全てのデータが分類されたと看做す。
この例では、「風速:弱い」に該当したデータは、Yesが2件、Noが1件だった。Yesの方が多いので、「湿度:低い」は仮にYesに全データが分類されたとして、エントロピーは0とする(仮にNoの方が多くても、エントロピーは0となる)。

矛盾するデータが存在する場合

例えば、「天気:晴れ」で「風速:強い」で「湿度:高い」の場合に、花見に行ったケースと行かなかったケースと2つのデータがある場合を考える。
全ての質問に対し、全く同じ答えを取ったデータ間で、分類結果が異なる場合である。
この場合は、「天気」「風速」「湿度」以外の質問項目に基づき、データを追加しない限り、どうやっても完全な分類は出来ない。
決定木の目的は、属性値の組合せの入力から、データ分類を出力する事なので、この場合は、多数決に従い、Yesのケースが多ければYes、Noのケースが多ければNoを出力するように設定する場合もある。
決定木の学習は現在分かっているデータからの帰納推論として、不確実な推論なので、新たなデータの追加によって、矛盾が発生する可能性はある。