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.

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

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.