ID3

ID3のアルゴリズムの流れを以下に示す。なおここでは入力の独立変数を a₁…a_nとおく、また取りうる出力は集合 D に格納されており例題の集合 C に於いて、 x ∈ D が起こる割合を p_x(C) で表すこととする。

1. ルートノード N を作成して全ての例題集合を N に所属させる。
2. もしN に所属する例題が全て同じ決定 X を与えるなら N に X とラベル付けして処理を終了する。
3. 例題集合 C に対する平均情報量を求める、即ち以下の式を計算する。

   ${\displaystyle M(C)=-\sum _{x\in D}p_{x}(C)\log p_{x}(C)}$

4. C をある独立変数 a_i の値に応じて分割する。a_i が v₁ … v_m の m 通りの値を持つ場合は以下の通りに分割する。

   ${\displaystyle C_{ij}\subset C(a_{i}=v_{j})}$

5. 分割した C_ij に応じて平均情報量を求める。

   ${\displaystyle \left.M(C_{ij})=-\sum _{x\in D}p_{x}(C_{ij})\log p_{x}(C_{ij})\right.}$

6. 計算した平均情報量から独立変数 a_i の平均情報量の期待値 M_i を以下の式で求める。

   ${\displaystyle M_{i}=M(C)-\sum _{j=1}^{m}M(C_{ij})\times {\frac {|C_{ij}|}{|C|}}}$

7. M_i が最大となる独立変数を a_k とする。
8. N のラベルを a_k として、N の子ノード N_j を作成し、それぞれにC_kj を所属させる。
9. それぞれの子ノードに対して N = N_j, C = C_kj として、2 以下の操作を再帰的に行う。

例として以下のような動物の例題が与えられているとする。

例題	食性（a1 ）	発生形態（a2 ）	体温（a3 ）	分類
例題1（ペンギン）	肉食	卵生	恒温	鳥類
例題2（ライオン）	肉食	胎生	恒温	哺乳類
例題3（ウシ）	草食	胎生	恒温	哺乳類
例題4（トカゲ）	肉食	卵生	変温	爬虫類
例題5（ブンチョウ）	草食	卵生	恒温	鳥類

ここから、ID3を用いて食性、発生形態、体温から分類を決定する場合を考える。

ID3 における log の底は基本的に何でも良いが、出力が哺乳類、爬虫類、鳥類の三種類であるので平均情報量の最大値が 1.0 最小値が 0.0 になるように、ここでは 3 を底にしておく。

全体の平均情報量を計算すると、この例題での出力は哺乳類 = 2、爬虫類 = 1、鳥類 = 2 であるから、

${\displaystyle M(C)=-{\frac {2}{5}}\log _{3}{\frac {2}{5}}-{\frac {1}{5}}\log _{3}{\frac {1}{5}}-{\frac {2}{5}}\log _{3}{\frac {2}{5}}\simeq 0.960}$

となる、まず独立変数として食性（a₁ ）を取り上げる。この変数は「草食」と「肉食」の二つの値を取りうるから、まず例題集合を以下の2つに分ける。

${\displaystyle C_{11}=\{}$例題1, 例題2, 例題4 ${\displaystyle \}}$（食性＝肉食）のクラス。

${\displaystyle C_{12}=\{}$ 例題3, 例題5 ${\displaystyle \}}$（食性＝草食）のクラス。

分割した C₁₁ と C₁₂ から平均情報量を求めると C₁₁ の出力は哺乳類 = 1、爬虫類 = 1、鳥類 = 1 であるから、

${\displaystyle M(C_{11})=-{\frac {1}{3}}\log _{3}{\frac {1}{3}}-{\frac {1}{3}}\log _{3}{\frac {1}{3}}-{\frac {1}{3}}\log _{3}{\frac {1}{3}}=1.0}$

同様にC₁₂ の出力は哺乳類 = 1、爬虫類 = 0、鳥類 = 1 であるから、

${\displaystyle M(C_{12})=-{\frac {1}{2}}\log _{3}{\frac {1}{2}}-{\frac {0}{2}}\log _{3}{\frac {0}{2}}-{\frac {1}{2}}\log _{3}{\frac {1}{2}}\simeq 0.631}$

よって平均情報量の期待値 M₁ は

${\displaystyle M_{1}=0.960-\left(1.0\times {\frac {3}{5}}+0.667\times {\frac {2}{5}}\right)=0.093}$

同様にして、発生形態（a₂ ）、体温（a₃ ）から M₂、M₃ を計算すると、

${\displaystyle M_{2}=0.612}$

${\displaystyle M_{3}=0.455}$

となり、最大値は M₂ である。よってノードのラベルは発生形態（a₂ ）になる。

以上の操作を再帰的に繰り返すと以下のような決定木が出力される。

このとき入力変数は食性、発生形態、体温の3種類が存在していたが、出力される決定木では発生形態と体温の2種類しか使われていない。このように ID3 はその学習の過程で余分な変数を削除し最低限の仮説によって例題との関連性を学習する。

1. ↑ Quinlan, J. Ross. "Induction of decision trees." Machine learning 1.1 (1986): 81-106.^{[要文献特定詳細情報]}
2. ↑ Quinlan, J. Ross. C4. 5: programs for machine learning. Elsevier, 2014.^{[要文献特定詳細情報]}