C4.5

C4.5はロス・キンランが開発した決定木を生成するためのアルゴリズムである。C4.5はキンランのID3アルゴリズムの拡張である。C4.5が生成する決定木はクラス分けのために使うことができ、このため、C4.5はしばしば統計学的クラス分類器とみなされている。

アルゴリズム

C4.5はID3と同じ方法で情報エントロピーの概念を用いて教師データのセットから決定木を生成する。教師データは $S={s_{1},s_{2},...}$ すでにクラス分けがされているサンプルである。それぞれのサンプル $s_{i}={x_{1},x_{2},...}$ は属性や特徴を表現するベクトル $x_{1},x_{2},...$ である。教師データはそれぞれのサンプルが属するクラスを表現しているベクトル $C={c_{1},c_{2},...}$ で拡張される。

C4.5はそれぞれのデータの属性はデータを更に小さな部分集合に分割する決定に使用できるという事実を利用している。C4.5はデータを分割するための属性を選択した結果による正規化されたインフォメーション・ゲイン(エントロピーの違い)を調査する。最も大きな正規化されたインフォメーション・ゲインを示す属性は決定を行うために使うものである。アルゴリズムはより小さなサブリストに再帰的に適用される。

このアルゴリズムはベースとなるケースが数個であり、最も一般的なベースケースはリスト内のすべてのサンプルが同じクラスに属する場合である。この場合、そのクラスを選択するように示すリーフノードを決定木を生成する。どの特徴もインフォメーション・ゲインにつながらない場合も起こりうり、この場合C4.5ではクラスの期待値を使ってツリーの上に決定ノードを生成する。クラスのインスタンスが一つも生成されない場合もあり、この場合も期待値を使ってツリーの上に決定ノードを生成する。

アルゴリズムの疑似コードは以下のようになる。

Check for base cases
For each attribute a
 Find the normalized information gain from splitting on a
Let a_best be the attribute with the highest normalized information gain
Create a decision node node that splits on a_best
recur on the sublists obtained by splitting on a_best and add those nodes as children of node

インフォメーション・ゲインと情報エントロピー

それぞれの項目で更に説明されているが $Entropy(S)$ はSの中でクラス分類がどれほどランダムなのかを示す尺度である。インフォメーション・ゲインはある属性’’a’’に付与された尺度である。属性’’a’’は’’S’’を部分集合 $S_{a}1,S_{a}2,S_{a}3,...,S_{a}n$ に分割することができ、そのインフォメーション・ゲインは $Entropy(S)-Entropy(S_{a}1)-Entropy(S_{a}2)-...-Entropy(S_{a}n)$ となる。インフォメーション・ゲインはそれぞれの属性値のエントロピーとその選択が持つ属性値の比率とを掛け合わせることで正規化される。

C4.5と ID3

C4.5はID3から多くの改良が施されている。以下にその一部を列挙する。

連続値と離散値の双方の取り扱い

連続値の属性を扱うために、C4.5は閾値を生成し、リストをその閾値以上か以下か、あるいは等しいか否かで分割する。[Quinlan, 96]

属性値が欠損している教師データの取り扱い

C4.5は属性値が欠損している場合「？」とマークすることを許している。欠損した属性値は単にゲインとエントロピーの計算に使われないだけである。

コストが異なる属性の扱い
生成後の枝打ち

C4.5では生成された後、木を遡り役に立たない枝をリーフノードと置き換えることで取り除こうとする。

C4.5 と C5.0/See5

キンランは続けてC5.0とSee5（C5.0はUnix/Linux用、See5はウィンドウズ用）を商業用に製作した。C5.0はC4.5から多くの改良点がある。以下にその一部を列挙する。

スピード

C5.0はC4.5に比べて著しく（数桁ほど）高速である。

メモリー使用

C5.0はC4.5に比べてより効率的にメモリを使用する。

決定木の小型化

C5.0ではC4.5に比べてかなり小さな決定木で同じような結果を出せる。

ブースティングのサポート

ブースティングはツリーを改良し精密さを向上させる。

重み付け

C5.0は異なる属性と誤ってクラス分けされたタイプに重みを付けることができる。

ふるい分け

C5.0では自動的にノイズを減らすのに役立つデータをふるい分ける。

C5.0およびSee5は商業利用を目的にし、ソースが公開されていないがフリーのソースコードがインタープリッティングに利用可能であり、出力された決定木とルールを使用することができる。

参考文献

Quinlan, J. R. C4.5: Programs for Machine Learning. Morgan Kaufmann Publishers, 1993.
J. R. Quinlan. Improved use of continuous attributes in c4.5. Journal of Artificial Intelligence Research, 4:77-90, 1996.

外部リンク

Original implementation on Ross Quinlan's homepage: http://www.rulequest.com/Personal/