Algorisme ID3

Fig.1 Exemple d'arbre de decisió creat amb l'algorisme ID3

L'algorisme ID3 (acrònim anglès d'Iterative Dichotomiser 3), en l'àmbit de la intel·ligència artificial, és un algorisme inventat per Ross Quinlan l'any 1975 emprat per a generar un arbre de decisió a partir d'un conjunt de dades. ID3 és el precursor de l'algorisme C4.5 i s'utilitza en l'aprenentatge automàtic i el processament de llenguatge natural.

Propietats

L'algorisme ID3 té la següent seqüència de càlcul :

1. Es pren el conjunt inicial de dades $S$ com a node arrel.
2. En cada iteracció de l'algorisme, es pren cada atribut no emprat del conjunt de dades i es calcula l'entropia $H(S)$ d'aquest atribut.
3. Es divideixen les dades en subconjunts segons l'entropia mínima.
4. Es torna a escollir un altre atribut fins que estiguin tots utilitzats.

Avantatges :

• Construeix l'arbre més ràoid i més curt.
• S'empra tot el conjunt de dades per a deduir l'arbre.