ID3のソースを表示

{{Otheruses|機械学習手法のID3|MP3のタグ|ID3タグ}}
'''ID3'''<ref>Quinlan, J. Ross. "Induction of decision trees." Machine learning 1.1 (1986): 81-106.</ref>は汎用目的で設計された[[教師あり学習]][[アルゴリズム]]の一種である。その学習効率の高さと出力が決定的であることなどから、[[エキスパートシステム]]の知識獲得部分にしばしば用いられる。

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

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

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

提案者のキンランは ID3 の拡張として[[C4.5]]と呼ばれるアルゴリズムを新たに提案しており、これは入力にあるノイズに対応することができる<ref>Quinlan, J. Ross. C4. 5: programs for machine learning. Elsevier, 2014.</ref>。

== アルゴリズムの流れ ==
ID3のアルゴリズムの流れを以下に示す。なおここでは入力の独立変数を ''a<sub>1</sub>''…''a<sub>n</sub>''とおく、また取りうる出力は集合 ''D'' に格納されており例題の集合 ''C'' に於いて、 ''x'' ∈ ''D'' が起こる割合を ''p<sub>x</sub>(C)'' で表すこととする。
# ルートノード ''N'' を作成して全ての例題集合を ''N'' に所属させる。
# もし''N'' に所属する例題が全て同じ決定 ''X'' を与えるなら ''N'' に ''X'' とラベル付けして処理を終了する。
# 例題集合 ''C'' に対する平均情報量を求める、即ち以下の式を計算する。
#: <math>M(C) = -\sum _{x \in D} p_x(C)\log p_x(C)</math>
# ''C'' をある独立変数 ''a<sub>i</sub>'' の値に応じて分割する。''a<sub>i</sub>'' が ''v<sub>1</sub>'' … ''v<sub>m</sub>'' の ''m'' 通りの値を持つ場合は以下の通りに分割する。
#: <math>C_{ij} \subset C(a_i = v_j)</math>
# 分割した ''C<sub>ij</sub>'' に応じて平均情報量を求める。
#: <math>\left.M(C_{ij}) = -\sum _{x \in D} p_x(C_{ij})\log p_x(C_{ij})\right.</math>
# 計算した平均情報量から独立変数 ''a<sub>i</sub>'' の平均情報量の期待値 ''M<sub>i</sub>'' を以下の式で求める。
#: <math>M_i = M(C) - \sum_{j = 1}^{m}M(C_{ij})\times\frac{|C_{ij}|}{|C|}</math>
# ''M<sub>i</sub>'' が最大となる独立変数を ''a<sub>k</sub>'' とする。
# ''N'' のラベルを ''a<sub>k</sub>'' として、''N'' の子ノード ''N<sub>j</sub>'' を作成し、それぞれに''C<sub>kj</sub>'' を所属させる。
# それぞれの子ノードに対して ''N'' = ''N<sub>j</sub>'', ''C'' = ''C<sub>kj</sub>'' として、2 以下の操作を再帰的に行う。

== 実行例 ==
例として以下のような動物の例題が与えられているとする。
{| border="1" cellpadding="3" align="center" class="wikitable"
|-align=center
! 例題
! 食性（''a<sub>1</sub>'' ）
! 発生形態（''a<sub>2</sub>'' ）
! 体温（''a<sub>3</sub>'' ）
! 分類
|-align=center
| 例題1（ペンギン）
| 肉食
| 卵生
| 恒温
! 鳥類
|-align=center
| 例題2（ライオン）
| 肉食
| 胎生
| 恒温
! 哺乳類
|-align=center
| 例題3（ウシ）
| 草食
| 胎生
| 恒温
! 哺乳類
|-align=center
| 例題4（トカゲ）
| 肉食
| 卵生
| 変温
! 爬虫類
|-align=center
| 例題5（ブンチョウ）
| 草食
| 卵生
| 恒温
! 鳥類
|}
ここから、ID3 を用いて食性、発生形態、体温から分類を決定する場合を考える。

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

全体の平均情報量を計算すると、この例題での出力は哺乳類 = 2、爬虫類 = 1、鳥類 = 2 であるから、
:<math>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</math>
となる、まず独立変数として食性（''a<sub>1</sub>'' ）を取り上げる。この変数は「草食」と「肉食」の二つの値を取りうるから、まず例題集合を以下の2つに分ける。
: <math>C_{11} =\{</math>例題1, 例題2, 例題4 <math>\}</math>（食性＝肉食）のクラス。
: <math>C_{12} =\{</math> 例題3, 例題5 <math>\}</math>（食性＝草食）のクラス。
分割した ''C<sub>11</sub>'' と ''C<sub>12</sub>'' から平均情報量を求めると ''C<sub>11</sub>'' の出力は哺乳類 = 1、爬虫類 = 1、鳥類 = 1 であるから、 
:<math>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</math>
同様に''C<sub>12</sub>'' の出力は哺乳類 = 1、爬虫類 = 0、鳥類 = 1 であるから、 
:<math>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</math>

よって平均情報量の期待値 ''M<sub>1</sub>'' は
:<math>M_1 = 0.960 - \left( 1.0\times \frac{3}{5} + 0.667\times\frac{2}{5} \right) = 0.093</math>
同様にして、発生形態（''a<sub>2</sub>'' ）、体温（''a<sub>3</sub>'' ）から ''M<sub>2</sub>''、''M<sub>3</sub>'' を計算すると、
:<math>M_2 = 0.612</math>
:<math>M_3 = 0.455</math>
となり、最大値は ''M<sub>2</sub>'' である。よってノードのラベルは発生形態（''a<sub>2</sub>'' ）になる。

以上の操作を再帰的に繰り返すと以下のような決定木が出力される。
[[ファイル:id3_result.gif|center|200px]]

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


== 脚注 ==
<references />

{{Computer-stub}}
{{DEFAULTSORT:ID3}}

[[Category:決定木]]
[[Category:分類アルゴリズム]]
[[Category:機械学習アルゴリズム]]
[[Category:教師あり学習]]
[[Category:人工知能]]