succ prec indice

ID3

Sviluppato da Quinlan nel 1986 e da lui successivamente migliorato nella versione denominata C4.5 (1993), viene oggi largamente usato per compiti di classificazione in contesti applicativi diversi, come la diagnostica medica o la valutazione del rischio sul credito.

Lo scopo del programma e' di approssimare una funzione a valori discreti o un predicato mediante un albero di decisione (il nome e' un acrononimo per "inductive decision three").

Un albero di decisione e' un struttura dati in cui i nodi interni corrispondono gli attributi di classificazione, gli archi ne rappresentano i possibili valori, e le foglie indicano il risultato della funzione approssimata (valore booleano nel caso di predicati).

Un albero di decisione puo' anche essere visto come un insieme di regole

...
if attributo₁=valore_a then funzione_approx = f₁
if attributo₁=valore_b and attributo₂ =valore_c then funzione_approx = f₂
...

Ad esempio:

<tempo>
      |-(piovoso)----------------------------------[spiaggia_affollata=no]
      |-(assolato)-<mese>
                                         |--(luglio)--<giorno>
                                         |                                |-----(festivo)---[spiaggia_affollata=si]
                                         |                                |-----(feriale)---[spiaggia_ affollata=no]
                                         |--(agosto)--------------------[spiaggia_affollata=si]

regole corrispondenti:

           if tempo=piovoso then spiaggia_affollata=no
(or)    if tempo=assolato and mese=luglio and giorno=festivo then spiaggia_affollata=si
(or)    if tempo=assolato and mese=luglio and giorno=feriale then spiaggia_affollata=no
(or)    if tempo=assolato and mese=agosto then spiaggia_affollata=si

L'albero di decisione viene costruito applicando ricorsivamente una procedura di scelta dell'attributo piu' significativo, ai fini della classificazione, tra quelli non ancora utilizzati.

Per ogni arco, viene considerato il sottoinsieme S degli esempi E, compatibili con i vincoli specificati dai nodi precedenti.

Per la valutazione della "impurita'" della classificazione degli esempi, si utilizza l'entropia dell'insieme S, misurata rispetto al valore di classificazione

H (S) = - p⁺ log₂p⁺ - p^- log₂p^-

dove, con p⁺ e p^-, sono state indicate rispettivamente le proporzioni di esempi positivi e negativi dell'insieme S.

In base a questa, si introduce una misura del guadagno di informazione Gain(S,A), che la scelta di un determinato attributo A, puo' indurre sull'insieme S

Gain(S,A) = H(S) - Sum ( |S_v|/|S| H(S_v) )
v in Values(A)

dove, Values(A) indica l'insieme dei possibili valori dell'attributo A , e S_vindica il sottoinsieme di S per cui l'attributo A valga v.

Dato un insieme di esempio, esistono diversi alberi di decisione compatibili. ID3 esegue una ricerca di tipo "hill climbing" di un albero di decisione di lunghezza minima, in grado di rappresentare gli esempi con un'ipotesi "semplice".

Il fatto che non vengano riconsiderate le scelte gia' effettuate, non assicura la minimalita' del risultato, che richiederebbe invece una scansione esaustiva di tutti gli alberi compatibili.

In applicazioni reali, gli esempi presentano errori o casi insoliti, che possono provocare un eccessiva complessita' dell'albero di decisione, determinata dalla consistenza del risultato con l'intero insieme di esempio. Questo puo' comportare una scarsa capacita' di generalizzazione rispetto alla distribuzione reale dei casi da classificare.

Per ovviare al problema, sono stati utilizzati con successo metodi di "potatura" (post pruning), che, rispetto a misure statistiche di accuratezza delle regole prodotte, riducono il numero di regole considerate.

succ prec indice