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と同じ方法でトレーニング データ セットから決定木を構築します。トレーニング データは、すでに分類されたサンプルのセットです。各サンプルはp 次元ベクトルで構成され、 はサンプルの属性値または特徴と、そのクラスを表します。 ${\displaystyle S={s_{1},s_{2},...}}$${\displaystyle s_{i}}$${\displaystyle (x_{1,i},x_{2,i},...,x_{p,i})}$${\displaystyle x_{j}}$${\displaystyle s_{i}}$

ツリーの各ノードで、C4.5 は、サンプル セットをいずれかのクラスに偏ったサブセットに最も効果的に分割するデータの属性を選択します。分割基準は、正規化された情報ゲイン(エントロピーの差) です。正規化された情報ゲインが最も高い属性が選択され、決定が下されます。次に、C4.5 アルゴリズムは、分割されたサブリストを再帰的に処理します。

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

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

擬似コードでは、決定木を構築するための一般的なアルゴリズムは次のようになります。^[4]

1. 上記の基本ケースを確認します。
2. 各属性aについて、 aでの分割からの正規化された情報ゲイン比を求めます。
3. 正規化された情報ゲインが最も高い属性をa_bestとします。
4. a_bestで分割する決定ノードを作成します。
5. a_bestで分割して得られたサブリストを再帰し、それらのノードをnodeの子として追加します。

J48 は、 Wekaデータ マイニングツールの C4.5 アルゴリズムのオープン ソース Java実装です。

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 General Public License (GPL) に基づいて入手できます。

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

• Ross Quinlan のホームページのオリジナルの実装: http://www.rulequest.com/Personal/
• See5 と C5.0