ID3

ID3は汎用目的で設計された教師あり学習アルゴリズムの一種である。その学習効率の高さと出力が決定的であることなどから、エキスパートシステムの知識獲得部分にしばしば用いられる。 ID3（Iterative Dichotomiser 3）は1979年にジョン・ロス・キンラン（John Ross Quinlan）により提案された。その学習方法はオッカムの剃刀の原理に基づいている。すなわち最低限の仮説による事象の決定を行う。出力は決定木の形で表される。 この方法は各独立変数に対し変数の値を決定した場合における平均情報量の期待値を求め、その中で最大のものを選びそれを木のノードにする操作を再帰的に行うことで実装される。 学習効率が良く、多数の例題から学習することが出来るが、「例題を一括に処理する必要があり学習結果の逐次的な改善が行えない」、「入力変数が連続値を取る場合は利用できない」などといった問題点も指摘されている。 提案者のキンランは ID3 の拡張としてC4.5と呼ばれるアルゴリズムを新たに提案しており、これは入力にあるノイズに対応することができる。 ID3のアルゴリズムの流れを以下に示す。なおここでは入力の独立変数を a1…anとおく、また取りうる出力は集合 D に格納されており例題の集合 C に於いて、 x ∈ D が起こる割合を px(C) で表すこととする。 ルートノード N を作成して全ての例題集合を N に所属させる。 もしN に所属する例題が全て同じ決定 X を与えるなら N に X とラベル付けして処理を終了する。 例題集合 C に対する平均情報量を求める、即ち以下の式を計算する。 M ( C ) = − ∑ x ∈ D p x ( C ) log ⁡ p x ( C ) {\displaystyle M(C)=-\sum _{x\in D}p_{x}(C)\log p_{x}(C)} C をある独立変数 ai の値に応じて分割する。ai が v1 … vm の m 通りの値を持つ場合は以下の通りに分割する。 C i j ⊂ C ( a i = v j ) {\displaystyle C_{ij}\subset C(a_{i}=v_{j})} 分割した Cij に応じて平均情報量を求める。 M ( C i j ) = − ∑ x ∈ D p x ( C i j ) log ⁡ p x ( C i j ) {\displaystyle \left.M(C_{ij})=-\sum _{x\in D}p_{x}(C_{ij})\log p_{x}(C_{ij})\right.} 計算した平均情報量から独立変数 ai の平均情報量の期待値 Mi を以下の式で求める。 M i = M ( C ) − ∑ j = 1 m M ( C i j ) × | C i j | | C | {\displaystyle M_{i}=M(C)-\sum _{j=1}^{m}M(C_{ij})\times {\frac {|C_{ij}|}{|C|}}} Mi が最大となる独立変数を ak とする。 N のラベルを ak として、N の子ノード Nj を作成し、それぞれにCkj を所属させる。 それぞれの子ノードに対して N = Nj, C = Ckj として、2 以下の操作を再帰的に行う。 例として以下のような動物の例題が与えられているとする。 ここから、ID3 を用いて食性、発生形態、体温から分類を決定する場合を考える。 ID3 における log の底は基本的に何でも良いが、出力が哺乳類、爬虫類、鳥類の三種類であるので平均情報量の最大値が 1.0 最小値が 0.0 になるように、ここでは 3 を底にしておく。 全体の平均情報量を計算すると、この例題での出力は哺乳類 = 2、爬虫類 = 1、鳥類 = 2 であるから、 M ( C ) = − 2 5 log 3 ⁡ 2 5 − 1 5 log 3 ⁡ 1 5 − 2 5 log 3 ⁡ 2 5 ≃ 0.960 {\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} となる、まず独立変数として食性（a1 ）を取り上げる。この変数は「草食」と「肉食」の二つの値を取りうるから、まず例題集合を以下の2つに分ける。 C 11 = { {\displaystyle C_{11}=\{} 例題1, 例題2, 例題4 } {\displaystyle \}} （食性＝肉食）のクラス。 C 12 = { {\displaystyle C_{12}=\{} 例題3, 例題5 } {\displaystyle \}} （食性＝草食）のクラス。 分割した C11 と C12 から平均情報量を求めると C11 の出力は哺乳類 = 1、爬虫類 = 1、鳥類 = 1 であるから、 M ( C 11 ) = − 1 3 log 3 ⁡ 1 3 − 1 3 log 3 ⁡ 1 3 − 1 3 log 3 ⁡ 1 3 = 1.0 {\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} 同様にC12 の出力は哺乳類 = 1、爬虫類 = 0、鳥類 = 1 であるから、 M ( C 12 ) = − 1 2 log 3 ⁡ 1 2 − 0 2 log 3 ⁡ 0 2 − 1 2 log 3 ⁡ 1 2 ≃ 0.631 {\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} よって平均情報量の期待値 M1 は M 1 = 0.960 − ( 1.0 × 3 5 + 0.667 × 2 5 ) = 0.093 {\displaystyle M_{1}=0.960-\left(1.0\times {\frac {3}{5}}+0.667\times {\frac {2}{5}}\right)=0.093} 同様にして、発生形態（a2 ）、体温（a3 ）から M2、M3 を計算すると、 M 2 = 0.612 {\displaystyle M_{2}=0.612} M 3 = 0.455 {\displaystyle M_{3}=0.455} となり、最大値は M2 である。よってノードのラベルは発生形態（a2 ）になる。 以上の操作を再帰的に繰り返すと以下のような決定木が出力される。 このとき入力変数は食性、発生形態、体温の3種類が存在していたが、出力される決定木では発生形態と体温の2種類しか使われていない。このように ID3 はその学習の過程で余分な変数を削除し最低限の仮説によって例題との関連性を学習する。 ^ Quinlan, J. Ross. "Induction of decision trees." Machine learning 1.1 (1986): 81-106. ^ Quinlan, J. Ross. C4. 5: programs for machine learning. Elsevier, 2014.