ID3

ID3は汎用目的で設計された教師あり学習アルゴリズムの一種である。その学習効率の高さと出力が決定的であることなどから、エキスパートシステムの知識獲得部分にしばしば用いられる。

概要

ID3︵Iterative Dichotomiser 3︶は1979年にジョン・ロス・キンラン︵John Ross Quinlan︶により提案された。その学習方法はオッカムの剃刀の原理に基づいている。すなわち最低限の仮説による事象の決定を行う。出力は決定木の形で表される。

この方法は各独立変数に対し変数の値を決定した場合における平均情報量の期待値を求め、その中で最大のものを選びそれを木のノードにする操作を再帰的に行うことで実装される。

学習効率が良く、多数の例題から学習することが出来るが、﹁例題を一括に処理する必要があり学習結果の逐次的な改善が行えない﹂、﹁入力変数が連続値を取る場合は利用できない﹂などといった問題点も指摘されている。

提案者のキンランは ID3 の拡張としてC4.5と呼ばれるアルゴリズムを新たに提案しており、これは入力にあるノイズに対応することができる。

アルゴリズムの流れ

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

(一)ルートノード Nを作成して全ての例題集合を Nに所属させる。

(二)もしN に所属する例題が全て同じ決定 Xを与えるなら Nに Xとラベル付けして処理を終了する。

(三)例題集合 Cに対する平均情報量を求める、即ち以下の式を計算する。
${\displaystyle M($C)=-\sum _{x\in D}p_{x}(C)\log p_{x}(C)} $M(C)=-\sum _{x\in D}p_{x}(C)\log p_{x}(C)$
(四)C をある独立変数 a_iの値に応じて分割する。a_i が v₁… v_mの m通りの値を持つ場合は以下の通りに分割する。
$C_{ij}\subset C(a_{i}=v_{j})$$C_{ij}\subset C(a_{i}=v_{j})$
(五)分割した C_ijに応じて平均情報量を求める。
$\left.M(C_{ij})=-\sum _{x\in D}p_{x}(C_{ij})\log p_{x}(C_{ij})\right.$$\left.M(C_{ij})=-\sum _{x\in D}p_{x}(C_{ij})\log p_{x}(C_{ij})\right.$
(六)計算した平均情報量から独立変数 a_iの平均情報量の期待値 M_iを以下の式で求める。
${\displaystyle M_{i}=M($C)-\sum _{j=1}^{m}M(C_{ij})\times {\frac {|C_{ij}|}{|C|}}} $M_{i}=M(C)-\sum _{j=1}^{m}M(C_{ij})\times {\frac {|C_{ij}|}{|C|}}$
(七)M_i が最大となる独立変数を a_kとする。

(八)N のラベルを a_kとして、N の子ノード N_jを作成し、それぞれにC_kj を所属させる。

(九)それぞれの子ノードに対して 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} $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つに分ける。

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

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

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

$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$$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 であるから、 

$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(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₁は

$M_{1}=0.960-\left(1.0\times {\frac {3}{5}}+0.667\times {\frac {2}{5}}\right)=0.093$$M_{1}=0.960-\left(1.0\times {\frac {3}{5}}+0.667\times {\frac {2}{5}}\right)=0.093$
同様にして、発生形態︵a₂ ︶、体温︵a₃ ︶から M₂、M₃ を計算すると、

$M_{2}=0.612$$M_{2}=0.612$
$M_{3}=0.455$$M_{3}=0.455$
となり、最大値は M₂である。よってノードのラベルは発生形態︵a₂ ︶になる。

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

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