ID3アルゴリズム

1 背景と歴史

1.1 概念学習における決定木の位置づけ

決定木は、機械学習において「概念学習」を実現する代表的な手法の一つである。与えられた事例集合から、各属性に基づいて事例を分類するルールを木構造で表現する。決定木は、人間が理解しやすいif-thenルールの形式に変換できるため、説明可能な人工知能（XAI）の先駆けとも位置づけられる。ID3は、この決定木を情報理論の観点から効率的に構築する最初の実用的アルゴリズムとして登場した。

1.2 クインランによる提案と初期の応用

ID3（Iterative Dichotomiser 3）は、1986年にオーストラリアの計算機科学者ジョン・ロス・クインラン（John Ross Quinlan）によって発表された。クインランは、以前に提案されたCLS（Concept Learning System）を改良し、属性選択にエントロピーと情報利得を導入することで、より小さく正確な決定木を生成できるようにした。初期の応用としては、チェスの終盤戦略の学習や医療診断データの分類などが行われ、その実用性が広く認められた。

2 理論的基礎

2.1 エントロピー

2.1.1 情報量の定義

情報理論において、エントロピーは確率変数の不確かさを測る指標である。クラスラベルが2値（例：はい/いいえ）の場合、データ集合\( S \)のエントロピー\( H(S) \)は次式で定義される：

\[ H(S) = -\sum_{i=1}^{n} p_i \log_2 p_i \]

ここで\( p_i \)はクラス\( i \)の出現確率である。エントロピーが高いほどデータの不純度が高く、分類が困難であることを示す。

2.1.2 属性選択におけるエントロピーの役割

ID3では、各属性でデータを分割した後のエントロピーの変化を評価する。良い属性とは、分割後のデータ集合のエントロピーを最も減少させるものである。この考え方が、情報利得の計算の基礎となる。

2.2 情報利得

2.2.1 情報利得の計算式

属性\( A \)による情報利得\( Gain(S, A) \)は、元のデータ集合\( S \)のエントロピーと、属性\( A \)で分割した後の各サブ集合のエントロピーの重み付き平均との差として定義される：

\[

Gain(S, A) = H(S) - \sum_{v \in Values(A)} \frac{	S_v	}{	S	} H(S_v)

\]

ここで\( S_v \)は属性\( A \)の値\( v \)を持つ事例の集合である。

2.2.2 情報利得最大化の原理

ID3は、各分割ステップで情報利得が最大となる属性を選択する。これにより、現在のデータを最もよく分類できる属性から順に木の上位ノードに配置される。この貪欲法（greedy approach）は、局所最適ではあるが、実用的な決定木を高速に構築できる。

3 アルゴリズムの流れ

3.1 データの前処理

ID3は離散値属性のみを扱う。連続値属性がある場合は、事前に離散化（例えば等間隔ビニングや等頻度ビニング）を行う必要がある。また、欠損値を含む事例は削除するか、特別な処理（後述）が必要となる。データは属性とクラスラベルからなる表形式で与えられる。

3.2 再帰的な木構築

3.2.1 停止条件と葉ノードの決定

再帰的な木構築は、以下のいずれかの条件で停止する：

• ノード内の全事例が同一クラスに属する場合 → そのクラスを葉とする。
• 使用可能な属性がなくなった場合 → 多数決でクラスを決定する。
• ある属性で分割しても情報利得が0の場合 → その時点での多数クラスを葉とする。

3.2.2 枝刈りの有無

ID3の基本形は、枝刈り（pruning）を行わない。そのため、訓練データに完全に適合するまで木を成長させ、過学習を起こしやすい。後継のC4.5では、枝刈りが導入された。ID3では実装時に簡易な枝刈り（例：最小分割事例数の設定）を追加することが多い。

3.3 属性選択の例

例えば、「天気」「気温」「湿度」「風」の属性で「テニスをするかどうか」を分類するデータがあるとする。ID3は各属性の情報利得を計算し、最も高い「天気」をルートノードに選ぶ。次に、天気が「晴れ」の場合のサブセットで再び情報利得を計算し、「湿度」を選択する、というように再帰的に木を構築する。

4 利点と欠点

4.1 長所

4.1.1 解釈可能性の高さ

決定木はif-thenルールとして読み下せるため、専門知識のないユーザでも分類根拠を理解できる。医療や金融など説明責任が求められる分野で特に有用である。

4.1.2 計算効率の良さ

属性数\( m \)、事例数\( n \)に対して、各ノードでの情報利得計算は\( O(mn) \)で済み、木の深さが\( d \)の場合、全体の計算量は\( O(mnd) \)と小規模データには効率的である。

4.2 短所

4.2.1 連続値属性への非対応

ID3は離散値属性のみを直接扱える。連続値属性を強引に離散化すると、情報損失や不適切な分割が生じやすい。C4.5ではこの問題を連続値属性の二分法で解決した。

4.2.2 過学習のリスク

枝刈りがないため、ノイズや外れ値に敏感で、訓練データに対して完璧に適合した複雑な木が生成される。この結果、未知のデータに対する汎化性能が低下する。

4.2.3 多値属性バイアス

情報利得は、値の数が多い属性（例：一意のID）を不当に高く評価する。例えば、各事例にユニークなIDを属性として与えると、情報利得が最大となり、その属性がルートノードに選ばれるが、まったく意味のない分類となる。C4.5では、情報利得比（Gain Ratio）を用いてこのバイアスを補正した。

5 応用例

5.1 医療診断支援

患者の症状（発熱、咳、年齢など）を離散値化し、疾患の有無を分類する決定木を構築する。ID3は1980年代に初期の医療エキスパートシステムで使用された。ただし、現在はより頑健な手法が主流である。

5.2 顧客セグメンテーション

マーケティングにおいて、顧客の属性（年齢層、地域、購入履歴など）から購買行動を予測するルールを生成する。例：「年齢が若くかつ収入が高い → 高額商品を購入する傾向」といったルールが抽出できる。

5.3 ゲームAIのルール学習

チェスや三目並べなどのボードゲームにおいて、局面の特徴量（駒の配置、手番など）から最善手を選択する決定木を学習させる。クインラン自身もチェスのエンドゲーム学習にID3を適用した。

6 後継アルゴリズムとの比較

6.1 C4.5

C4.5はクインランが1993年に発表したID3の改良版である。主な改良点：

• 連続値属性への対応（二分法）
• 欠損値処理（事例の重み付け）
• 情報利得比の導入（多値属性バイアスの軽減）
• 枝刈り（誤り率に基づく剪定）
• ルール抽出機能の追加

C4.5はID3の実質的な後継として広く使われ、多くのデータマイニングツール（例：WEKAのJ48）に実装されている。

6.2 CART (Classification and Regression Trees)

CARTは1984年にBreimanらによって提案された決定木アルゴリズムである。ID3/C4.5との違い：

• 二分木のみを生成（多分岐を行わない）
• 分割基準にジニ係数（Gini index）または二乗誤差を使用
• 回帰問題も扱える（CARTの「R」はRegression）
• 枝刈りにコスト複雑度枝刈り（CCP）を用いる

CARTはscikit-learnなど現代の機械学習ライブラリで標準的に採用されている。

7 実装上の注意点

7.1 データ品質と欠損値処理

ID3は欠損値を含む事例をそのまま扱えない。実装時には欠損値を削除するか、最頻値で補完するなどの前処理が必要。また、ノイズの多いデータでは過学習が激しくなるため、データの品質管理が重要である。

7.2 大規模データへの拡張

ID3の計算量はデータサイズに線形だが、木の深さが深くなるとメモリ消費が増大する。大規模データには以下の工夫が考えられる：

• 属性数を削減する特徴選択
• 離散化ビンの数を適切に設定
• オンライン学習への拡張（例：VFDT、Hoeffding Tree）
• 並列処理（例：SPRINT、RainForest）

ただし、現代の大規模データには勾配ブースティング（XGBoost、LightGBM）やランダムフォレストの方が適している場合が多い。