Algoritmo ID3

ID3 (Iterative Dichotomiser 3) è un algoritmo greedy per l'induzione di alberi di decisione.

L'algoritmo

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.

Pseudocodice

Viene qui riportato lo pseudocodice dell'algoritmo ID3 per funzioni booleane.

Esempi:= istanze di addestramento.
Attributo_obiettivo:= l'attributo il cui valore viene predetto dall'albero.
Attributi:= lista di altri attributi.

ID3 (Esempi, Attributo_obiettivo, Attributi)
    Crea un nodo Radice.
    Se tutti gli esempi sono positivi
        restituisci un albero con un unico nodo Radice ed etichetta = +
    Se tutti gli esempi sono negativi
        restituisci un albero con un unico nodo Radice ed etichetta = -
    Se Attributi è vuoto
        restituisci un albero con un unico nodo Radice ed etichetta = il valore di Attributo_obiettivo più comune tra le istanze di Esempi.
    Altrimenti
        A ← L'elemento di Attributi che riduce maggiormente l'entropia.
        Per ogni valore v di A,
            Aggiungi un nuovo ramo sotto Radice corrispondente al test A = v.
            Esempi(v) ← sottoinsieme di Esempi che hanno valore v per A.
            Se Esempi(v) è vuoto
                Aggiungi una foglia con etichetta = valore di Attributo_obiettivo più comune tra gli esempi.
            Altrimenti
                Aggiungi sotto Radice il sottoalbero ID3 (Esempi(v), Attributo_obiettivo, Attributi – {A}).
    Restituisci Radice.

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, assegniamo al nodo la distribuzione di probabilità p tale che p(yes)=2/3 e p(no)=1/3.

Proprietà e limiti

ID3 restituisce un solo albero di decisione, consistente con il dataset passato in input. Non è garantito che tale soluzione sia l'unica né che sia quella ottima, in quanto ID3 può convergere anche a minimi locali: per ovviare a questo problema si può fare uso della tecnica di backtracking, che tuttavia non compare nella formulazione originale dell'algoritmo.

Per prevenire, invece, il problema dell'overfitting, si dovrebbe arrestare l'algoritmo prima che tutti gli attributi siano processati, preferendo come soluzioni alberi di decisione più piccoli. Un approccio alternativo, utilizzato nell'algoritmo C4.5 (il successore di ID3), è la tecnica del post-pruning: l'algoritmo non viene arrestato durante l'esecuzione, permettendo quindi anche l'overfitting, e solo al suo termine vengono applicate le regole di pruning (potatura) per migliorare la capacità di generalizzazione.

Un'altra difficoltà è data dalla gestione degli attributi a valore continuo, come i numeri reali. ID3 non prevede nemmeno la possibilità di assegnare dei pesi agli attributi, né ammette attributi mancanti.

Bibliografia

• (EN) John Ross Quinlan, Semi-autonomous acquisition of pattern-based knowledge, 1980. URL consultato il 12 maggio 2023.

Voci correlate

• Albero di decisione