C4.5

C4.5はロス・キンランが開発した決定木を生成するためのアルゴリズムである。C4.5はキンランのID3アルゴリズムの拡張である。C4.5が生成する決定木はクラス分けのために使うことができ、このため、C4.5はしばしば統計学的クラス分類器とみなされている。
アルゴリズム.
C4.5はID3と同じ方法で情報エントロピーの概念を用いて教師データのセットから決定木を生成する。教師データはformula_1すでにクラス分けがされているサンプルである。それぞれのサンプルformula_2は属性や特徴を表現するベクトルformula_3である。教師データはそれぞれのサンプルが属するクラスを表現しているベクトルformula_4 で拡張される。
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"
インフォメーション・ゲインと 情報エントロピー.
それぞれの項目で更に説明されているがformula_5は"S"の中でクラス分類がどれほどランダムなのかを示す尺度である。インフォメーション・ゲインはある属性’’a’’に付与された尺度である。属性’’a’’は’’S’’を部分集合formula_6 に分割することができ、そのインフォメーション・ゲインはformula_7となる。インフォメーション・ゲインはそれぞれの属性値のエントロピーとその選択が持つ属性値の比率とを掛け合わせることで正規化される。
C4.5と ID3.
C4.5はID3から多くの改良が施されている。以下にその一部を列挙する。
C4.5 と C5.0/See5.
キンランは続けてC5.0とSee5（C5.0はUnix/Linux用、See5はウィンドウズ用）を商業用に製作した。C5.0はC4.5から多くの改良点がある。以下にその一部を列挙する。
C5.0およびSee5は商業利用を目的にし、ソースが公開されていないがフリーのソースコードがインタープリッティングに利用可能であり、出力された決定木とルールを使用することができる。