C4.5アルゴリズム

C4.5は、ロス・クインランによって開発された決定木を生成するために使用されるアルゴリズムです。^{[ 1 ]} C4.5は、クインランの以前のID3アルゴリズムの拡張です。C4.5によって生成される決定木は分類に使用でき、このため、C4.5は統計的分類器と呼ばれることがよくあります。

2011年、Weka機械学習ソフトウェアの開発者は、C4.5アルゴリズムを「おそらく現在までに実務で最も広く使用されている機械学習の主力プログラムである画期的な決定木プログラム」と評した。^{[ 2 ]} 2008年にSpringer LNCSが発表したデータマイニングにおけるトップ10アルゴリズムの権威ある論文で1位にランクインした後、非常に人気が高まった。^{[ 3 ]}

C4.5は、 ID3と同様に、情報エントロピーの概念を用いて、トレーニングデータのセットから決定木を構築します。トレーニングデータは、${\displaystyle S={s_{1},s_{2},...}}$既に分類されたサンプルの各サンプル。$s_i$p次元ベクトルで構成される${\displaystyle (x_{1,i},x_{2,i},...,x_{p,i})}$、${\displaystyle x_{j}}$サンプルの属性値または特徴、およびクラスを表します。$s_i$落ちる。

ツリーの各ノードにおいて、C4.5は、サンプルセットを一方のクラスまたは他方のクラスが豊富なサブセットに最も効果的に分割するデータの属性を選択します。分割基準は正規化情報利得（エントロピーの差）です。正規化情報利得が最も高い属性が選択され、決定が下されます。その後、C4.5アルゴリズムは分割されたサブリストに対して再帰的に処理を行います。

このアルゴリズムにはいくつかの基本ケースがあります。

• リスト内のすべてのサンプルが同じクラスに属している場合、そのクラスを選択するように指示する決定木の葉ノードが作成されます。
• これらの機能はいずれも情報利得をもたらしません。この場合、C4.5はクラスの期待値を用いて、ツリーの上位に決定ノードを作成します。
• これまで見たことのないクラスのインスタンスが検出されました。C4.5は、期待値を使用して、ツリーの上位に決定ノードを作成します。

C4.5ではID3に多くの改良が加えられました。その一部は以下のとおりです。

• 連続属性と離散属性の両方の処理: 連続属性を処理するために、C4.5 はしきい値を作成し、属性値がしきい値を超えるものとしきい値以下のものにリストを分割します。^{[ 5 ]}
• 欠損属性値を含むトレーニングデータの処理：C4.5では、属性値を欠損値としてマークすることができます。欠損属性値は、ゲインとエントロピーの計算には使用されません。
• コストの異なる属性の取り扱い。
• 作成後のツリーの剪定: C4.5 は、ツリーが作成された後、ツリーを遡って確認し、役に立たない枝を葉ノードに置き換えることで削除を試みます。

クインランはその後、C5.0とSee5（Unix/Linux用C5.0、Windows用See5）を作成し、商用販売した。C5.0はC4.5に比べて多くの改良が施されている。その一部は以下の通りである。^{[ 6 ] [ 7 ]}

• 速度 - C5.0はC4.5よりも大幅に高速です（数桁速い）。
• メモリ使用量 - C5.0はC4.5よりもメモリ効率が良い
• より小さな決定木 - C5.0は、C4.5と同等の結果を得ながら、決定木のサイズは大幅に小さくなっています。
• ブースティングのサポート- ブースティングはツリーを改善し、精度を高めます。
• 重み付け - C5.0では、さまざまなケースや誤分類の種類に重み付けを行うことができます。
• 属性の選別 - C5.0のオプションで、不要な属性を自動的に削除します。

C5.0のシングルスレッド版Linux用ソースコードは、GNU一般公衆利用許諾契約書（GPL）に基づいて入手可能です。

• ID3アルゴリズム
• C4.5を修正して時間的ルールと因果的ルールを生成する

• オリジナルの実装はロス・クインランのホームページに掲載されています： http://www.rulequest.com/Personal/
• See5とC5.0