データマイニング分野のトップ10の古典的なアルゴリズムの1つであるC4.5アルゴリズム（超詳細なコード付き）

古典的なデータマイニングアルゴリズムのトップ 10 は次のとおりです。

導入

C4.5 は決定木アルゴリズムの一種です。分類アルゴリズムとしての決定木アルゴリズムの目的は、p 次元の特徴を持つ n 個のサンプルを c 個のカテゴリに分類することです。一般的な決定木アルゴリズムには、ID3、C4.5、CART などがあります。

基本的な考え方

次の例では、C4.5 の基本的な考え方を詳しく説明します。

上記のデータセットには、属性セット A = {天気、気温、湿度、風速} の 4 つの属性と、カテゴリ セット L = {出発、キャンセル} の 2 つのカテゴリ ラベルがあります。

1. カテゴリ情報エントロピーを計算する

カテゴリ情報エントロピーは、すべてのサンプル内のさまざまなカテゴリの不確実性の合計を表します。エントロピーの概念によれば、エントロピーが大きいほど不確実性が増し、物事を明確にするために必要な情報が多くなります。

2.各属性の情報エントロピーを計算する

各属性の情報エントロピーは条件付きエントロピーと同等です。これは、特定の属性におけるさまざまなカテゴリの不確実性の合計を表します。属性の情報エントロピーが大きいほど、この属性のサンプル カテゴリの「純粋さ」は低くなります。

3. 情報ゲインを計算する

情報ゲイン = エントロピー - 条件付きエントロピー、つまりカテゴリ情報エントロピー - 属性情報エントロピー、つまり情報の不確実性の低減度合いを示します。属性の情報ゲインが大きい場合、サンプル分割にこの属性を使用すると、分割されたサンプルの不確実性をより適切に削減できることを意味します。もちろん、この属性を選択すると、分類の目標をより迅速かつ適切に達成できます。

情報ゲインは、ID3 アルゴリズムの特徴選択指標です。

ただし、各属性の各カテゴリにはサンプルが 1 つしかないと仮定すると、属性情報エントロピーはゼロになり、情報ゲインに基づいて効果的な分類機能を選択することは不可能になります。したがって、C4.5 は情報ゲイン率を使用して ID3 を改善することを選択します。

4. 属性分割情報メジャーを計算する

分割情報メトリックは、特定の属性が分割されるときに、ブランチの数とサイズ情報を考慮するために使用されます。この情報を属性の固有情報と呼びます。情報ゲイン比率は、情報ゲイン/固有情報を使用しており、固有情報が増えるほど属性の重要性が低下します（つまり、この属性自体の不確実性が非常に大きい場合は、それを選択する傾向が低くなります）。これは、情報ゲインを単純に使用することに対する補償と見なすことができます。

5. 情報利得率を計算する

(以下は誤りです。IGR = Gain / H のはずです)

天気は情報取得率が最も高いため、分割属性として選択されます。分割後、天気が「曇り」のときにカテゴリが「純粋」であることがわかったので、それをリーフ ノードとして定義し、「純粋」でないノードを選択して分割を続行しました。

子ノードでプロセス 1 から 5 を繰り返します。

この時点で、このデータセットに対する C4.5 の計算プロセスが完了し、ツリーが構築されます。

アルゴリズムのフローは次のように要約されます。

長所と短所

アドバンテージ

生成された分類ルールは理解しやすく、精度も高いです。

欠点

ツリーを構築するプロセスでは、データセットを複数回スキャンして順番にソートする必要があり、アルゴリズムの非効率性につながります。

コード

コードはgithubに実装されており、ここにも投稿されています。

テストデータセットはMNISTデータセットであり、取得アドレスはtrain.csvである。

運用結果