Alberi di Decisione

Alberi di decisione (decision trees)

• Tipo di apprendimento: supervisionato, da esempi• Tipo di funzione appresa: come per Find_S e VS, una

funzione simbolica• La funzione di classificazione appresa è un albero di

decisone, alternativamente esprimibile mediante una espressione logica disgiuntiva o un insieme di clausole FOL.

• Vantaggi: Maggiore potere espressivo della funzione obiettivo, tolleranza al rumore e ai dati incompleti

Apprendimento da Alberi di Decisione

• Un albero di decisione prende in ingresso un’istanza xX descritta mediante un vettore (coppie attributo-valore) ed emette in uscita una "decisione”, ad es. binaria ( si o no)

Es: Dare o meno un mutuo?

no SI no si

Obiettivo• Lo scopo è, come in tutti i modelli di apprendimento induttivo da esempi,

imparare la definizione di una funzione obiettivo espressa in termini di albero di decisioni.

• Un albero di decisione può essere espressa come una disgiunzione (OR) di implicazioni, aventi il valore della decisione come conclusione.

• Nell'esempio, la funzione obiettivo (decisione) è ”Mutuo" ed è implicata, fra l'altro, dalla implicazione:

r Reddito(r, 30-70)Impiegato_da(r,1-5)PagaconCC(r,SI)Mutuo(r)Dove r rappresenta l’istanza (di richiedente) da valutare.

• O equivalentemente, mediante una espressione booleana. Se il generico attributo vj assume kj valori i=1,..kj, occorrono N=∑jlog2(kj) variabili booleane.

val ji

Alberi di Decisione• La decisione deve basarsi sull'esame di esempi D: xX, così

descritti:• ogni esempio è rappresentato da un vettore che rappresenta

i valori degli attributi prescelti per descrivere le istanze del dominio x: <v1=vali,v2=valj,..vn=valm>

(utilizzando attributi booleani : <a1,a2,………..aN> ai={0,1} )• gli attributi sono proprietà che descrivono gli esempi del

dominio (es: precedenti-penali=si,no reddito = $,$$,$$$ • Gli alberi di decisione hanno il potere espressivo dei

linguaggi proposizionali, ovvero - qualsiasi funzione booleana può essere scritta come un

albero di decisione (e viceversa).

Quando è appropriato usare AD?

• Quando è appropriato usare alberi di decisione?- Gli esempi (istanze) sono rappresentabili in termini di coppie

attributo-valore- La funzione obiettivo assume valori nel discreto. Un albero di

decisioni assegna classificazioni booleane ma può essere esteso al caso di funzioni a più valori. Non è comune, ma possibile, l'utilizzo di questa tecnica per apprendere funzioni nel continuo (discretizzando i valori di f(x)).

- E’appropriato rappresentare il concetto da apprendere mediante una forma normale disgiuntiva

- I dati di apprendimento possono contenere errori, oppure attributi di cui il valore è mancante

Come utilizzare gli esempi D?• L'insieme di addestramento D è l'insieme completo degli esempi sottoposti al sistema di

apprendimento

• Una soluzione semplice sarebbe creare una espressione congiuntiva per ogni esempio e costruire una disgiunzione: ma il sistema non avrebbe alcun potere predittivo su esempi non visti! Il problema è estrarre uno schema dagli esempi, che sia in grado di estrapolare al caso di esempi non visti

Es. Crim Inc Year CC Att? X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11 X12

SI SI NO SI SI NO NO NO NO SI NO SI

A A B C A A B B C C A B

A B B B B C C C A C B A

SI SI NO SI NO SI NO SI NO SI NO SI

no no si no

A,B e C corrispondono ai tre ranges degli attributi Income e years in present job

Algoritmo di apprendimento di alberi di decisione

• L'obiettivo è (come sempre) di estrarre uno schema coinciso.

• Rasoio di Occam: l'ipotesi più probabile è la più semplice che sia consistente con tutte le osservazioni (entia non est moltiplicanda praeter necessitatem)

• Il problema di identificare l'albero più piccolo è intrattabile. Tuttavia esistono euristiche che consentono di trovare alberi "abbastanza" piccoli.

• L'idea consiste nell’analizzare dapprima gli attributi più importanti, ovvero quelli che discriminano di più.

• Più avanti vedremo come la teoria dell'informazione può aiutare nella scelta dell'attributo migliore.

• Supponendo per ora di poter fare questa scelta ad ogni passo i, l'algoritmo di creazione di un albero delle decisioni da un set di esempi D è il seguente:

Algoritmo ID3

• Sia D un insieme di esempi, xi il generico esempio,Vuna lista di attributi, vj un generico attributo, Vi il dominio di vi, valij il valore di vj in xi, C l'insieme delle classificazioni , c(xi) la classificazione di xi, Def un valore di default per la decisione. (Notate che stiamo considerando una classificazione NON necessariamente binaria: c(xi)=CkC)

Function APPRENDIMENTO_ALBERI_DECISIONE (D,V,Def) returnun albero di decisioneIf D= then return DefElse if xi, c(xi)=CkC then return Ck

Else if P= then return VALORE_MAGGIORANZA(D)Else

migliore SCEGLI-ATTRIBUTO(V,D) (migliore V)albero un nuovo albero avente per radice il test su migliorefor each valiVALmigliore di migliore do

Ei : xiD migliore=vali

sottoalbero APPRENDIMENTO_ALBERI_DECISIONE(Ei,V-migliore, VALORE_MAGGIORANZA(D))Aggiungi un ramo a albero con etichetta vali e sottoalbero=sottoalbero

End

EsempioStudenti: x (media,età,conosce_BP,sesso); c(x) promosso?Valori attributi: media: >27, 22media27 <22 (A,B,C)età: 22, >22 (D,E) conosce_BP: si,no sesso: F,MSet di apprendimento D:D+: (1.<A,D,si,F> 2.<B,D,si,M> 3.<A,E,no,F> 4.<C,E,si,M>)

D- : (5.<C,E,no,M> 6.<C,E,no,F>

Migliore=conosce_BP conosce_BP?

E(si):D+si:1,2,4D-si:

si no E(no): D+no:3 D-no:5,6 media?

D+A,B: 3D-A,B:

D+C: D-C:5,6

Function APPRENDIMENTO_ALBERI_DECISIONE (D,V,Def) return un albero di decisioneIf D= then return DefElse if xi, c(xi)=CkC then return Ck

Else if V= then return VALORE_MAGGIORANZA(D)

Else

ElsemiglioreSCEGLI-ATTRIBUTO(V,D) (migliore V)albero un nuovo albero avente per radice il test su migliore

for each valiVALmigliore di migliore do

Ei : xiD migliore=vali

sottoalbero APPRENDIMENTO_ALBERI_DECISIONE(Ei,

V-migliore, VALORE_MAGGIORANZA(D))

If D= then return DefElse if xi, c(xi)=CkC then return Ck

Else if V= then return VALORE_MAGGIORANZA(D)

Algoritmo ID3

• ID3 è un algoritmo greedy che accresce l’albero secondo un’ordine top-down, selezionando ad ogni nodo l’attributo che classifica meglio gli esempi correntemente disponibili

• L’algoritmo procede finchè tutti gli esempi sono classificati perfettamente, o sono stati esaminati tutti gli attributi

• Il passo “cruciale” è la scelta dell’attributo migliore, basata sul concetto di entropia

Entropia• Interpretazione “fisica”: misura del disordine

• Teoria dell’Informazione: è la misura dell’ incertezza sul risultato di un esperimento modellabile mediante una variabile aleatoria X

• X variabile aleatoria p(X) è la distribuzione di probabilità di X

• Se X assume valori discreti xi 1in

• Se X assume valori continui in a,bH(X ) p(X xi )log2p(X xi )

i1

n pilog2pi

i1

n

H(X ) p(X xia

b )log2p(X xi )

Esempio di Entropia per variabili booleane

•H(X) per X booleana

•Asse delle x: p(X=1), asse y: H(X)

•Osservate che, se X può assumere solo due valori, P(X=x1)=1-P(X=x2)

•Se X booleana, allora0 H(X ) 1

Esempio: lancio del dado• La stima di una probabilità, o valore atteso, si indica con

E(p(X)), oppure• Se X modella l’evento “lancio di un dado”:

• Se il dado è “truccato” p(X=6)=1 , p(X6)=0 e si ha: • L’entropia di un evento certo è zero!! L’entropia di N

eventi equiprobabili è (massimo dell’incertezza)

ˆ p ( X)

ˆ H (X ) H(X) p( X 6)log(p4X 6)) 0

log2N

6log6log66

1))(ˆlog()(ˆ)(ˆ

6,5,4,3,2,16

1)(ˆ

6

1

iiXpiXpXH

iiXp

Definizione di Entropia nell’apprendimento automatico

• Sia C un concetto da apprendere e V l’insieme dei valori possibili per C, e

• La variabile aleatoria modella gli eventi C(x)=v,vV x X (spazio delle istanze)

• H(C) viene definito come il bisogno informativo, o numero di bit necessari per codificare la classificazione di un arbitrario elemento x di X (ecco perché log2)

V N

H(C) p(C v)log(vV p(C v))

Stima dell’entropia di una classificazione

• D è il set di esempi di addestramento

• Posso stimare la probabilità di C(x)=v su D:

• La stima di H(C) è data dalla:

ˆ p (C v) ˆ p v Dv

D

ˆ H (C) H(D) Dv

DvV log(

Dv

D)

Esempio

• C : 0,1

• D D+ :(x1,x2,x4,x5) D- : (x3)

ˆ H (C) H(D) 4

5log(

4

5)

1

5log(

1

5) 0,72

Algoritmo Scelta attributo migliore (1)

• Siano V i valori di una classificazione C• Sia H(D) l’entropia associata ad un certo insieme di

esempi D, e sia a un attributo della lista A di attributi da esaminare

• Siano N i valori dell’attributo a, aiVALa

• Sia il sottoinsieme di esempi in D aventi a=ai

• L’entropia del sottoinsieme è data da:

Daai

H(Daai)

Daaiv

DaaivV log(

Daaiv

Daai

)

Scelta attributo migliore (2)

• La stima su D della p(a=ai) è data dalla:

• L’entropia del campione D dopo aver raggruppato gli esempi a seconda del valore dell’attributo a è data da:

ˆ p (a ai ) Daai

D

H(Da) ˆ p (a ai )H(DaaiaiVALa

) Daai

DaiVAL a (

Daaiv

DaaivV log(

Daaiv

Daai

)

Scelta attributo migliore (3)

• Il guadagno informativo G(a) misura la riduzione di entropia ottenuta ripartendo gli esempi D secondo i valori di a, cioè la riduzione del “bisogno informativo” che si otterrebbe conoscendo i valori di a:

• L’attributo migliore, dato un insieme D di esempi classificati e una lista A di attributi, è quello che massimizza il guadagno informativo

G(a) H(D) H(Da)

Esempio

H(D)=-4/6log(4/6)-2/6log(2/6)=0,92

D sesso=F=1+,3+,6- D sesso=M=2+,4+,5-H(D sesso=F)=-2/3log2/3-1/3log1/3=0,92H(D sesso=M)=- 2/3log2/3-1/3log1/3=0,92p(sesso=F)=0,5 p(sesso=M)=0,5G(sesso)=0,92 - 0,50,92-0,5 0,92=0 !!!

D c_BP=si=1+,2+,4+ D c_BP=no=3+,5-,6-H(D c_BP=si)=-3/3log3/3=0 H(D c_BP=no)=-1/3log1/3-2/3log2/3=0,92p(c_BP=si)=3/6 Pr(c_BP=no)=3/6G(c_BP)=0,92-0,5 0- 0,5 0,92=0,46

Studenti: x (media,età,conosce_BP,sesso) c(x) promosso?D+: (1.<A,D,si,F> 2.<B,D,si,M> 3.<A,E,no,F> 4.<C,E,si,M>)D- : (5.<C,E,no,M> 6.<C,E,no,F>

Esempio 2• D: 14 esempi così ripartiti [9+,5-] => H=0,940

• Due attributi: humidity: {high,normal} wind: {weak,strong}

• Quale preferire?

humidity

high normal

Dhigh :[3+,4-] Dnorm :[6+,1-]

Hhigh=0,985 Hnorm=0,592Gain(humidity)=0,940-(7/14)0,958

-(7/14)0,592=0,151

wind

weak strong

Dweak :[6+,2-] Dstrog :[3+,3-]

Hhigh=0,811 Hnorm=1,00Gain(humidity)=0,940-(8/14)0,811

-(6/14)1,0=0,048

Problemi nell’apprendimento da esempi

• Dati rumorosi

• Sovradattamento

• Attributi irrilevanti

Come si comporta ID3???

Problema del rumore negli AD• Problema: se i dati sono rumorosi, posso esaurire tutti gli attributi senza

ottenere delle ripartizioni perfette dei Di in D+ (SI) o D- (NO). Quindi non posso emettere delle decisioni “perfette”

• Soluzioni:

• associare a ciascuna foglia la classificazione della maggioranza degli esempi (vedi terza condizione dell’algoritmo ID3: if V=0 then C=classificazione di maggioranza)

• b) associare a ciascuna foglia la probabilità stimata di correttezza, in base alle frequenze relative (agente probabilistico basato sulla teoria delle decisioni)

test su ultimo attributoD: 3+, 2-

p(+)=3/5 p(-)=2/5

a=ai

Sovradattamento• Ricodate il problema: che succede se l’algoritmo viene

“sovra-addestrato” ?

• Per aderire al meglio agli esempi, tende a generare un apprendista con ridotte capacità di generalizzazione, ovvero, un algoritmo che si comporta bene sugli esempi di D, ma peggio su esempi non visti durante l’apprendimento

• Come si misura il “comportamento” di un apprendista rispetto a questo problema?

Misura della prestazione di un apprendista • Sia T un insieme di N esempi di cui è nota la classificazione

• Sia L un apprendista (ad es, un albero di decisione)

• Sia ntp il numero di esempi positivi che L classifica come positivi, ntn il numero di esempi negativi che L classifica come negativi, nfp il numero di esempi negativi che L classifica come positivi, nfn il numero di esempi positivi che L classifica come negativi

• Nota che in generale, TD (altrimenti in si ha una sovrastima!!)accuracy(L)

n tp n tn

ntp ntn n fp n fn ntp n tn

N

Curve di apprendimento

Accuracy

Training Data

soglia

D

T

Metodi per ridurre il sovradattamento (1).

1. Reduced error pruning• Si considera ogni nodo ni di un albero di decisione.• Si rimuove il sottoalbero avente per radice il nodo , rendendolo

in tal modo una "foglia" dell'albero più generale• Si assegna ad ni la classificazione più probabile del sottoinsieme

di esempi affiliati al nodo.• Si misura l'accuratezza su T dell'albero non potato e dell'albero

potato.• Si effettua la potatura solo se la potatura sotto ni non produce un

peggioramento.• Si procede iterativamente considerando tutti i nodi finché non si

misurano ulteriori miglioramenti.

Reduced error pruning

• Questa potatura ha l'effetto di ridurre il problema delle "coincidenze" visto che difficilmente le coincidenze si verificano anche sul set T.

• Questo procedimento è applicabile quando i dati a disposizione sono molti. Sarà dunque possibile considerarne una parte per generare l'albero, ed una parte per potarlo.

Esempio

attributok

attibuto nSi

Si No

vero falso

D+:5D+:2D-:2

vero falsoD+:2 D-:2

SI Confidenza:7/9

Metodi per ridurre il sovradattamento (2).2. Rule post-pruning• Deriva un albero di decisione dai dati D, eventualmente

consentendo un sovradattamento• Converti l'albero in un insieme di regole. Ogni regola

rappresenta un percorso dalla radice ad una foglia.• Generalizza ogni regola, provando a rimuovere

incrementalmente ogni precondizione della regola che generi un miglioramento dell'accuratezza

• Ordina le regole così ottenute per accuratezza, e utilizzale in questa sequenza quando si classificano istanze nuove.

Es: IF (tempo=assolato)&(umidità=alta) THEN playtennis=noProva a rimuovere (tempo=assolato) e poi (umidità=alta)

Metodi per ridurre il sovradattamento (3).

• E' possibile valutare l'effetto della potatura anche sul set di apprendimento, usando una stima pessimistica per tener conto che la stima su D è comunque favorevole.

• Si stima l'accuratezza a(D) su D.• Si assume che la probabilità di errore abbia una distribuzione

binomiale (studieremo in seguito questa distribuzione).• Sotto questa ipotesi, si calcola la deviazione standard s.• Per un certo grado di confidenza d, l'errore reale a cade il d % delle

volte nell'intervallo aD zds• (per una binomiale, zd e d sono correlati)• Si sceglie come stima pessimistica dell'errore il massimo valore

dell'intervallo (es. per d=0,95 a= aD -1,96s)

Attributi irrilevanti: Metodo della potatura

dell'albero di decisione(1)

• La potatura dell'albero di decisione è un metodo di identificazione di attributi irrilevanti.

• Nella teoria delle probabilità questo corrisponde a misurare la significatività statistica; un test di significatività misura lo scostamento della distribuzione dei dati rispetto alla cosidetta ipotesi nulla, che prevede l'assenza di uno schema sottostante.

• Nel nostro caso l'ipotesi nulla corrisponde ad un guadagno di informazione nullo per un campione infinitamente grande.

Metodo della potatura dell'albero di decisione(2)Potatura 2• Supponiamo di avere un campione D di N esempi , dove N è

proprio il numero di valori che può assumere l'attributo vj (VALj=N) di cui vogliamo verificare la rilevanza.

• Siano p ed n il numero di campioni negativi e positivi in D (p+n=N) e siano pi e ni il numero di esempi positivi e negativi per vj =vali.

• Nel caso di ipotesi nulla, i numeri attesi e per pi ed ni sono

• (la probabilità a posteriori è uguale alla probabilità a priori di p ed n)

Esempi con vj=valiˆ p i p

p n(pi ni )

ˆ n i np n

(pi ni )

Probabilità positivi

Potatura Chi-quadro

• Una misura della deviazione totale, per ogni vali, della distribuzione degli esempi sull'attributo x rispetto all'ipotesi nulla è:

• Nel caso di ipotesi nulla, è distribuito secondo la distribuzione chi-quadro (2 ) con N-1 gradi di libertà.

i

iiN

i i

ii

n

nn

p

pp

ˆ

)ˆ(

ˆ

)ˆ( 2

1

2

Applicazioni di alberi di decisioni:• Progetto di sistemi di separazione del petrolio dal gas : il sistema di separazione ha una

struttura che dipende da numerosi attributi quali: proporzione fra gas, petrolio e acqua, intensità del flusso, viscosità…

– La GASOIL ha costruito un sistema esperto con 2500 regole, generate da un albero di decisione• Addestratore di volo

– Esempi generati monitorando piloti esperti e generando esempi ogni volta che un pilota fissava una variabile di controllo (es manetta o flap).

– 90.000 esempi estratti da 30x3 piani di volo eseguiti da 3 piloti esperti. 20 variabili di stato.– Utilizza il programma C4.5 (Quinlan)

• Fraud Detection– Sulla base di un campione di verifiche tributarie ciascuna registrata con un esito (positivo,

negativo, ammontare dell’imposta se incassata) costruisce un albero di decisioni per decidere, sulla base della denuncia dei redditi, se effettuare o meno un controllo (KDD group all’Università di Pisa).

• Consultate SW DataMining basato su Decision Tree: http://www.kdnuggets.com/software/classification.html#Decision

Per esercitarsi• C4.5 programma freeware per apprendere alberi di decisioni

(Quinlan)• Scaricare C4.5 da: . http://www.cse.unsw.edu.au/~quinlan/c4.5r8.tar.gz

• spiegazioni ulteriori su C4.5 le trovate sul tutorial : www.cs.uregina.ca/~dbd/cs831/notes/ml/dtrees/c4.5/tutorial.html

• Anche sul sito WEKA (J4)• Dati scaricabili dal repository: http://www.ics.uci.edu/~mlearn/

MLSummary.html

• http://www.mlnet.org/cgi-bin/mlnetois.pl/?File=datasets.html• Varie decine di applicazioni, medicina, economia, classificazione di specie,

architettura, scacchi…