ID3アルゴリズム

決定木学習において、ID3（Iterative Dichotomiser 3）は、ロス・クインラン^[1]によって発明された、データセットから決定木を生成するために使用されるアルゴリズムです。ID3はC4.5アルゴリズムの前身であり、機械学習や自然言語処理の分野でよく使用されます。

ID3 アルゴリズムは、元のセットをルート ノードとして開始します。アルゴリズムの各反復では、セットのすべての未使用の属性を反復し、その属性のエントロピーまたは情報ゲインを計算します。次に、最小のエントロピー (または最大の情報ゲイン) 値を持つ属性を選択します。次に、セットは選択された属性によって分割またはパーティション化され、データのサブセットが生成されます。(たとえば、ノードは、年齢が 50 歳未満、50 歳から 100 歳、および 100 歳を超える人口のサブセットに基づいて子ノードに分割できます。) アルゴリズムは、以前に選択されたことのない属性のみを考慮しながら、各サブセットを再帰的に処理し続けます。 ${\displaystyle S}$${\displaystyle S}$ ${\displaystyle \mathrm {H} {(S)}}$ ${\displaystyle IG(S)}$${\displaystyle S}$

サブセットの再帰は、次のいずれかの場合に 停止することがあります。

• サブセット内のすべての要素は同じクラスに属します。その場合、ノードはリーフ ノードに変換され、例のクラスでラベル付けされます。
• 選択する属性はもうありませんが、例はまだ同じクラスに属していません。この場合、ノードはリーフ ノードになり、サブセット内の例の最も一般的なクラスでラベル付けされます。
• サブセットに例がありません。これは、親セットに、選択した属性の特定の値に一致する例が見つからない場合に発生します。例としては、人口の中に100歳を超える人がいないことが挙げられます。次に、リーフ ノードが作成され、親ノードのセット内の例の最も一般的なクラスでラベル付けされます。

アルゴリズム全体を通じて、データが分割された選択された属性を表す各非終端ノード (内部ノード)と、このブランチの最終サブセットのクラス ラベルを表す終端ノード (リーフ ノード) を使用して決定木が構築されます。

1. データ セットのすべての属性のエントロピーを計算します。 ${\displaystyle a}$${\displaystyle S}$
2. 分割後のエントロピーが最小化される属性、つまり情報ゲインが最大になる属性を使用して、セットをサブセットに分割します。${\displaystyle S}$
3. その属性を含む決定木ノードを作成します。
4. 残りの属性を使用してサブセットを再帰します。

ID3 は最適なソリューションを保証するものではありません。局所最適に収束する可能性があります。各反復でデータセットを分割するために局所的に最適な属性を選択する貪欲な戦略を使用します。アルゴリズムの最適性は、最適な決定木の検索中にバックトラッキングを使用することで向上できますが、時間がかかる可能性があります。

ID3 はトレーニング データを過剰に適合させる可能性があります。過剰適合を回避するには、大きな決定木よりも小さな決定木を優先する必要があります。 ^{[詳細な説明が必要]} このアルゴリズムは通常、小さな木を生成しますが、常に可能な限り小さな決定木を生成するとは限りません。

ID3 は、因数分解されたデータよりも連続データで使用するのが困難です (因数分解されたデータには離散的な数の可能な値があるため、可能な分岐点が少なくなります)。特定の属性の値が連続している場合、この属性でデータを分割する場所がさらに多くなり、分割する最適な値の検索に時間がかかることがあります。

ID3 アルゴリズムは、データ セットをトレーニングして、 メモリに保存される決定木を生成するために使用されます。実行時に、この決定木は、データの特徴を使用して決定木をトラバースし、リーフ ノードに到達することで、 新しいテスト ケース (特徴ベクトル)を分類するために使用されます。${\displaystyle S}$

エントロピーは、 （データ）セット内の不確実性の量を測る尺度です（つまり、エントロピーは（データ）セットを特徴づけます）。 ${\displaystyle \mathrm {H} {(S)}}$${\displaystyle S}$${\displaystyle S}$

${\displaystyle \mathrm {H} {(S)}=\sum _{x\in X}{-p(x)\log _{2}p(x)}}$

どこ、

• ${\displaystyle S}$–エントロピーが計算されている 現在のデータセット
  • これは、ID3 アルゴリズムの各ステップで変更され、属性で分割する場合は前のセットのサブセットに変更され、再帰が以前に終了した場合は親の「兄弟」パーティションに変更されます。
• ${\displaystyle X}$– クラスの集合${\displaystyle S}$
• ${\displaystyle p(x)}$–クラス内の要素数とセット内の要素数の比率${\displaystyle x}$${\displaystyle S}$

のとき、集合は完全に分類されます（つまり、 内のすべての要素は同じクラスです）。 ${\displaystyle \mathrm {H} {(S)}=0}$${\displaystyle S}$${\displaystyle S}$

ID3 では、残りの各属性のエントロピーが計算されます。この反復でセットを分割するには、エントロピーが最も小さい属性が使用されます。情報理論におけるエントロピーは、ランダム変数を測定することで得られると予想される情報量を測定し、したがって、量の値の分布が不明な量を定量化するためにも使用できます。定数のエントロピーは、その分布が完全にわかっているため、ゼロです。対照的に、均一に分布したランダム変数 (離散的または連続的に均一) はエントロピーを最大化します。したがって、ノードのエントロピーが大きいほど、ツリーのこの段階でのデータの分類についてわかっている情報が少なくなり、したがって、ここでの分類を改善する可能性が高くなります。 ${\displaystyle S}$

ID3 は、局所的に最適なエントロピー値を求める最良優先検索を実行する貪欲な ヒューリスティックです。データの前処理によって精度を向上させることができます。

情報ゲインは 、セットが属性 で分割される前と分割された後のエントロピーの差の尺度です。言い換えると、セットを属性 で分割した後で、 の不確実性がどれだけ減少したかということです。 ${\displaystyle IG(A)}$${\displaystyle S}$${\displaystyle A}$${\displaystyle S}$${\displaystyle S}$${\displaystyle A}$

${\displaystyle IG(S,A)=\mathrm {H} {(S)}-\sum _{t\in T}p(t)\mathrm {H} {(t)}=\mathrm {H} {(S)}-\mathrm {H} {(S|A)}.}$

どこ、

• ${\displaystyle \mathrm {H} (S)}$– 集合のエントロピー${\displaystyle S}$
• ${\displaystyle T}$–属性ごとに分割して作成されたサブセットは、${\displaystyle S}$${\displaystyle A}$${\displaystyle S=\bigcup _{t\in T}t}$
• ${\displaystyle p(t)}$– 集合内の要素数に対する集合内の要素数の比率${\displaystyle t}$${\displaystyle S}$
• ${\displaystyle \mathrm {H} (t)}$– サブセットのエントロピー${\displaystyle t}$

ID3 では、残りの各属性について、エントロピーの代わりに情報ゲインを計算できます。情報ゲインが最も大きい属性が、この反復で セットを分割するために使用されます。${\displaystyle S}$

• 分類と回帰ツリー(CART)
• C4.5アルゴリズム
• 決定木学習
  • 決定木モデル

• ミッチェル、トム・マイケル (1997)。機械学習。ニューヨーク、NY:マグロウヒル。pp. 55–58。ISBN 0070428077. OCLC  36417892.
• Grzymala-Busse, Jerzy W. (1993 年 2 月)。「例から選んだ機械学習アルゴリズム」(PDF)。Fundamenta Informaticae。18 (2): 193–207 – ResearchGate 経由。

• セミナー – http://www2.cs.uregina.ca/
• 説明と例 – http://www.cise.ufl.edu/
• 説明と例 – http://www.cis.temple.edu/
• 決定木と政党分類