C4.5アルゴリズム - Ciallo Wiki

決定木 学習の概要

決定木学習は、教師あり機械学習の一種であり、特徴空間を再帰的に分割することで分類または回帰のための木構造モデルを構築する手法である。各内部ノードは属性に対するテストを表し、各分岐はテストの結果、各葉ノードはクラスラベルまたは回帰値を保持する。決定木は解釈性が高く、データの前処理が比較的少なくて済むという利点を持つ。代表的なアルゴリズムとしてID3、C4.5、CARTがある。

C4.5の背景とID3からの進化

C4.5はRoss Quinlanにより1993年に発表された決定木学習アルゴリズムであり、彼が1986年に提案したID3アルゴリズムの拡張版である。ID3は情報利得を分割基準として用い、離散値属性のみを扱い、枝刈り機能を持たなかった。C4.5はこれらの制約を解消するために、情報利得比の採用、連続値属性の離散化、欠損値への対応、エラー率に基づく枝刈りの導入など、実用的な改良を施した。これにより、C4.5はより頑健で現実世界のデータセットに適用しやすいアルゴリズムとなった。

分割基準

情報利得比

C4.5は情報利得比(Gain Ratio)を分割基準として使用する。情報利得は多数値を持つ属性に偏りやすいというID3の欠点を補うため、分割情報量(Split Information)で情報利得を正規化する。情報利得比は以下の式で定義される：

GainRatio(A) = Gain(A) / SplitInfo(A)

ここで、SplitInfo(A)は属性Aによって分割された際のデータの分布エントロピーである。この基準により、C4.5はバランスの取れた分割を好む傾向がある。

連続値属性の離散化

C4.5は連続値属性を扱うために、二分法による離散化を採用する。データを値の昇順にソートし、隣接する異なるクラスラベルを持つ事例間の境界を候補分割点とする。各候補点で情報利得比を計算し、最適な分割点を選択する。このプロセスにより、連続値属性を離散的な二分岐に変換する。

欠損値の処理

事例の重み付け

C4.5は欠損値を含む事例を破棄せず、重みを調整することで扱う。各事例には初期重み1が与えられ、欠損値が発生するたびに、その事例が各分岐に分割される割合に応じて重みが比例配分される。これにより、欠損値の情報を部分的に活用する。

分割時の補完戦略

分割属性の選択時には、欠損値を持つ事例を除外して情報利得比を計算し、その後に事例の重みを考慮して分割を行う。新しい分岐を作成する際、欠損値を持つ事例は、既知の事例の分布に基づいて各子ノードに重み付きで割り当てられる。テスト時にも同様に、欠損値属性がある場合は複数の分岐を重み付きで通過する。

枝刈り

エラー率推定に基づく枝刈り

C4.5はエラー率推定に基づく枝刈り(Error-Based Pruning)を採用する。木の構築後、各内部ノードで、そのノードを葉ノードに置き換えた場合の推定誤差率と、そのノード以下を維持した場合の推定誤差率を比較する。推定には連続補正付き二項分布を用い、信頼区間の上限を誤差率の悲観的な推定値とする。置換後の誤差率が元の誤差率よりも小さい場合、そのノードを剪定する。

剪定後の木の評価

剪定後の木は、未知のデータに対する汎化性能が向上する。C4.5は剪定により過学習を抑制し、木のサイズを小さく保つことで、解釈性と予測精度のバランスを取る。剪定の程度は信頼レベルパラメータ（デフォルトは25%）で調整でき、この値を小さくするとより積極的な剪定が行われる。

典型的な使用事例

医療診断

C4.5は医療診断分野で広く利用されている。例えば、症状や検査結果から患者の疾患を分類するモデルを構築する。決定木は医師が直感的に理解しやすいルールを提供するため、診断支援システムの一部として採用されることが多い。ただし、医療データには欠損値や連続値属性が多く含まれるため、C4.5のこれらの処理機能が有用となる。

顧客分類

マーケティング分野では、顧客属性（年齢、収入、購買履歴など）に基づいて顧客セグメントを分類するためにC4.5が使われる。例えば、キャンペーンへの反応予測や離脱顧客の特定に応用される。決定木はルールベースの分類を提供するため、マーケティング担当者が戦略を立案する際に参照しやすい。

他のアルゴリズムとの比較

CARTとの違い

CART(Classification and Regression Trees)はBreimanらにより1984年に提案された決定木アルゴリズムである。C4.5との主な違いは、分割基準に情報利得比ではなくジニ不純度（分類の場合）または二乗誤差（回帰の場合）を用いる点、二分木のみを生成する点、欠損値の代理分割による処理を行う点である。C4.5は多分岐を許容し、欠損値を重み付きで扱う。また、CARTは回帰問題にも対応するが、C4.5は分類に特化している。

C5.0への発展

C4.5の後継であるC5.0は、Quinlanにより開発された商用版およびオープンソース版のアルゴリズムである。C5.0はC4.5と比較して、メモリ使用量の削減、実行速度の向上、ブースティングのサポート、より洗練された枝刈り手法（グローバル剪定など）、ルールセットの生成機能などの改良が加えられている。C5.0はC4.5の限界を克服し、大規模データセットへの適用性を高めている。

オープンソース実装

C4.5のオープンソース実装として最も有名なものは、Quinlan自身が提供したC4.5Release8ソースコード（C言語）である。また、R言語のパッケージRWekaはWeka（機械学習ツールキット）のC4.5実装（J48）をラップしている。Pythonではscikit-learnのDecisionTreeClassifierはCARTベースであるが、C4.5の純粋な実装はOrangeライブラリなどに存在する。これらの実装により、ユーザーは比較的容易にC4.5を試すことができる。

主要パラメータの解説

C4.5の主要なパラメータには以下がある：

信頼レベル(Confidence Level)：枝刈りに用いる信頼区間のパラメータ。デフォルトは0.25。小さな値ほど積極的な剪定を行う。
最小事例数(Minimum Instances per Leaf)：葉ノードが持つべき最小事例数。過学習を防ぐために設定する。
枝刈り有無(Pruning)：枝刈りを有効にするかどうか。
サブセット分割(Subset Partition)：多値離散属性に対する分割戦略（すべての値で分岐するか、二値分割するか）を制御する。

これらのパラメータを調整することで、モデルの複雑さと汎化性能のバランスを取ることができる。