ID3は汎用目的で設計された教師あり学習アルゴリズムの一種である。その学習効率の高さと出力が決定的であることなどから、エキスパートシステムの知識獲得部分にしばしば用いられる。ID3（Iterative Dichotomiser 3）は1979年にジョン・ロス・キンラン（John Ross Quinlan）により提案された。その学習方法はオッカムの剃刀の原理に基づいている。すなわち最低限の仮説による事象の決定を行う。出力は決定木の形で表される。この方法は各独立変数に対し変数の値を決定した場合における平均情報量の期待値を求め、その中で最大のものを選びそれを木のノードにする操作を再帰的に行うことで実装される。学習効率が良く、多数の例題から学習することが出来るが、「例題を一括に処理する必要があり学習結果の逐次的な改善が行えない」、「入力変数が連続値を取る場合は利用できない」などといった問題点も指摘されている。提案者のキンランは ID3 の拡張としてC4.5と呼ばれるアルゴリズムを新たに提案しており、これは入力にあるノイズに対応することができる。ID3のアルゴリズムの流れを以下に示す。なおここでは入力の独立変数を "a"…"a"とおく、また取りうる出力は集合 "D" に格納されており例題の集合 "C" に於いて、 "x" ∈ "D" が起こる割合を "p(C)" で表すこととする。例として以下のような動物の例題が与えられているとする。ここから、ID3 を用いて食性、発生形態、体温から分類を決定する場合を考える。ID3 における log の底は基本的に何でも良いが、出力が哺乳類、爬虫類、鳥類の三種類であるので平均情報量の最大値が 1.0 最小値が 0.0 になるように、ここでは 3 を底にしておく。全体の平均情報量を計算すると、この例題での出力は哺乳類 = 2、爬虫類 = 1、鳥類 = 2 であるから、となる、まず独立変数として食性（"a" ）を取り上げる。この変数は「草食」と「肉食」の二つの値を取りうるから、まず例題集合を以下の2つに分ける。分割した "C" と "C" から平均情報量を求めると "C" の出力は哺乳類 = 1、爬虫類 = 1、鳥類 = 1 であるから、 同様に"C" の出力は哺乳類 = 1、爬虫類 = 0、鳥類 = 1 であるから、 よって平均情報量の期待値 "M" は同様にして、発生形態（"a" ）、体温（"a" ）から "M"、"M" を計算すると、となり、最大値は "M" である。よってノードのラベルは発生形態（"a" ）になる。以上の操作を再帰的に繰り返すと以下のような決定木が出力される。このとき入力変数は食性、発生形態、体温の3種類が存在していたが、出力される決定木では発生形態と体温の2種類しか使われていない。このように ID3 はその学習の過程で余分な変数を削除し最低限の仮説によって例題との関連性を学習する。

出典:wikipedia