Algoritmo ID3
ID3 (Iterative Dichotomiser 3) risulta essere uno degli algoritmi "storici" per l'induzione di alberi di decisione. Risulta un algoritmo greedy(in ogni momento fa la "mossa" che massimizza la "bontà" dell'albero).
Concetti di base
L'albero è costruito in maniera top-down usando una politica nota come divide et impera(dividere un problema in sotto-problemi più piccoli). Algoritmo:
- Si parte con un albero costituito dalla sola radice, alla cui radice sono assegnate tutte le istanze di addestramento.
- Si sceglie un attributo(l'algoritmo ID3 lo sceglie mediante il "guadagno di informazione" e non il gain ratio).
- Si creano tanti nodi(figli della radice) quanti sono i possibili valori dell'attributo scelto. In questo caso le istanze di addestramento sono assegnate al figlio appropriato
- Si procede ricorsivamente usando come radici i nuovi nodi.
Gli step sopra definiti si adattano alla maggior parte degli algoritmi di induzione di alberi di decisione, cambia il metodo con cui si sceglie l'attributo. L'obiettivo è comunque sempre quello di ottenere un albero piccolo e preciso.
Condizioni di arresto
L'algoritmo si arresta se:
- tutte le istanze di un nodo appartengono alla stessa classe, in questo caso il nodo diventa una foglia con la corrispondente classe assegnata.
- non ci sono più attributi sui quali dividere l'albero, in questo caso il nodo diviene una foglia a cui viene assegnata la classe più comune tra le istanze ad esso assegnate.
Classi o distribuzioni di probabilità
In alternativa, invece di assegnare una classe a uno nodo, si può assegnare la distribuzione di probabilità dell'attributo classe, relativamente alle istanze a esso assegnate. Esempio: se all'ultimo nodo sono assegnate 3 istanze, con classi rispettivamente yes, yes e no, assegnamo al nodo la distribuzioen di probabilità p tale che p(yes)=2/3 e p(no)=1/3.
