KEIBA-ROBOs 開発奮闘記（仮）

_ [データマイニング] 決定木 その三

決定木その二では、決定木学習の概要を説明しました。今回は生成される分類ルールの善し悪しを決める、分類に使用する属性選択指標について説明します。決定木のロジックの心臓部と言えるこの指標は多種多様な指標が考案されていて、タキ型１号で用いている分析ツールでも29種類の指標が用意されています。

（この分析ツールに関しては機会を改めてご紹介する予定です。）

さて、ここでは代表的な4種類の属性選択指標を説明したいと思います。

指標自体の説明の前に説明に使う言葉と変数の定義をしておきます。まず、決定木学習によって出来る、ある属性によって分割されたデータのサブセットをノードとよび、最終的に到達するノードをリーフと呼びます。

決定木の学習に用いるデータについて、目的とする分類属性Cの属性値をC_i (1 ≤ i ≤ n_C)とします。このとき、全てのデータ又は各ノードそれぞれについて、次のような数が決められます。

　N 　: データのサンプル数
　ni• : Ciを取るデータのサンプル数。

　ここで、分類に使用する属性選択の指標は属性毎に同じ形式で定義できるため、ある一つの属性に関してまず考えるとさらに以下のような数が定義できます。

　n•j : 与えられた一つの属性に関してjの属性値を持つデータのサンプル数
　nij : Ciの値を取りかつ、jの属性値を持つデータのサンプル数を持つデータのサンプル数

　つまり、iは分類の目的に関する属性値、jはデータを分割する属性値に関する添字になります。以上から対応する頻度の比を用いた以下の確率、

　pij=nij/N
　pi•=ni•/N
　p•j=n•j/N
　pi|j=nij/n•j

_ が算出できます。これでようやく属性選択の指標のための基礎量が定義できました。

最初に紹介するのは一番古くから使用されている指標の一つで、情報理論で定義されている情報量を基にした指標です。

ある事象Eが生じる確率をP(E)とするとき、情報量は-log₂P(E)で定義されます。複数の事象に対する情報量は、その期待値で見積もられ、平均情報量（エントロピー）と呼ばれています。そこで、上記の分類と属性に関するサンプル数の頻度から算出した確率を用いて以下のエントロピーを考えます。

　分類を試す属性Aに関しての情報量の変化を次の情報量利得で計算します。

_ このGainが情報量に基づく属性選択指標で、Gainを最大にする属性が選ばれます。この指標は決定木の代表的な学習アルゴリズムである、ID3で用いられています。式から判るようにGainが最大となるのは、H_C|Aが最小の時なので、目的とする属性の分布が最も偏るような指標が選ばれます。

この指標の改良版として、次の比の値、

_ が提案されており、現在最も良く使用されている学習アルゴリズムであるC4.5でも使われています。

ようやく1つめが終わったところですが、長くなってきましたので次回へ。