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 xX
descritta mediante un vettore (coppie attributo-valore) ed emette
in uscita una "decisione”, ad es. binaria ( si o no)
no
SI
Es: Dare o meno un mutuo?
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,15)PagaconCC(r,SI)Mutuo(r)
Dove r rappresenta l’istanza (di richiedente) da valutare.
• O equivalentemente, mediante una espressione
booleana. Se il
i
generico attributo vj assume kj valori val j i=1,..kj, occorrono
N=∑jlog2(kj) variabili booleane.
Alberi di Decisione
• La decisione deve basarsi sull'esame di esempi D: xX, 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
Es.
X1
X2
X3
X4
X5
X6
X7
X8
X9
X10
X11
X12
Crim
SI
SI
NO
SI
SI
NO
NO
NO
NO
SI
NO
SI
Inc
A
A
B
C
A
A
B
B
C
C
A
B
Year
A
B
B
B
B
C
C
C
A
C
B
A
CC
SI
SI
NO
SI
NO
SI
NO
SI
NO
SI
NO
SI
Att?
no
no
si
no
A,B e C corrispondono ai tre ranges degli attributi
Income e years in present job
• 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
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)=CkC)
Function APPRENDIMENTO_ALBERI_DECISIONE (D,V,Def) return
un albero di decisione
If D= then return Def
Else if xi, c(xi)=CkC then return Ck
Else if P= then return VALORE_MAGGIORANZA(D)
Else
miglioreSCEGLI-ATTR IBUTO(V,D) (migliore V)
albero un nuovo albero avent e per radice il te st su migliore
for each val iVALmigl iore di migliore do
Ei : xiD migliore=vali
sottoalbero APPRENDIMENTO_ALBERI_DECISIONE(Ei,
V-migliore, VALORE_MAGGIORANZA(D))
Aggiungi un ramo a albero con etichetta vali e sottoalbero=
sottoalbero
End
Esempio
Studenti: x (media,età,conosce_BP,sesso); c(x) promosso?
Valori attributi: media: >27, 22media27 <22 (A,B,C)
età:  22, >22 (D,E) conosce_BP: si,no sesso: F,M
Set 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>
conosce_BP?
Migliore=conosce_BP
E(si):
D+si:1,2,4
D-si:
si

E(no):
D+no:3
no:5,6
Dmedia?
no
D+C: 
for
If D=
eachAPPRENDIMENTO_ALBERI_DECISIONE
then
valiVAL
returnmigliore
Def di
C:5,6
Function
(D,V,Def) return un albero di
D-decisione
Else
migliore
D+A,B:do
3
A,B:C
IfElse
D=
then
Def kCi then return
Ei
: x
if
D
xreturn
,migliore=val
c(xi)=C
Di
i
k(migliore V)
miglioreSCEGLI-ATTRIBUTO(V,D)
Else
then return
Ck
i, c(xi)=C
kC return
sottoalbero
Elseif x
if V=
APPRENDIMENTO_ALBERI_DECISIONE(E
then
VALORE_MAGGIORANZA(D)
i, 
albero
un
albero avente per radice
il
test
su
migliore
Else if V=
thennuovo
return VALORE_MAGGIORANZA(D)

V-migliore, VALORE_MAGGIORANZA(D))
Else
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 1in
n
n
i 1
i 1
H(X )    p(X  xi )log2 p(X  xi )    pilog2 pi
• Se X assume valori continui in a,b
b
H(X )    p(X  xi )log2 p(X  xi )
a
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, allora
0  H(X)  1
Esempio: lancio del dado
• La stima di una probabilità, o valore atteso, si
indica con E(p(X)), oppure pˆ ( X)
• Se X modella l’evento “lancio di un dado”:
p
ˆ ( X  i) 
1
i  1,2,3,4,5,6
6
6
1
ˆ
H (X )    p
ˆ ( X  i ) log( p
ˆ ( X  i ))  6 log 6  log 6
6
i 1
• Se il dado è “truccato” p(X=6)=1 , p(X6)=0 e si
ha: Hˆ (X)  H(X)  p( X  6)log(p4X  6))  0
• L’entropia di un evento certo è zero!! L’entropia di
N eventi equiprobabili è log2 N (massimo
dell’incertezza)
Definizione di Entropia nell’apprendimento
automatico
• Sia C un concetto da apprendere e V l’insieme dei
valori possibili per C, e V  N
• La variabile aleatoria modella gli eventi C(x)=v,vV
x X (spazio delle istanze)
H(C)    p(C  v)log( p(C  v))
v V
• 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)
Stima dell’entropia di una classificazione
• D è il set di esempi di addestramento
• Posso stimare la probabilità di C(x)=v su D:
Dv
pˆ (C  v)  ˆpv 
D
• La stima di H(C) è data dalla:
ˆH(C)  H(D)    Dv log( Dv )
D
v V D
Esempio
• C : 0,1
• D D+ :(x1,x2,x4,x5) D- : (x3)
ˆH(C)  H(D)   4 log( 4 )  1 log( 1 )  0,72
5
5 5
5
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, aiVALa
• Sia Da ai il sottoinsieme di esempi in D aventi a=ai
• L’entropia del sottoinsieme è data da:
H(Da ai )   
vV
Dav ai
Da ai
log(
Dav  ai
Da  ai
)
Scelta attributo migliore (2)
• La stima su D della p(a=ai) è data dalla:
pˆ (a  ai ) 
Da  ai
D
• L’entropia del campione D dopo aver raggruppato gli
esempi a seconda del valore dell’attributo a è data da:
H(Da ) 
ˆp(a  ai )H(Da ai )  

ai VALa
ai VAL a
Da  ai
D
( 
vV
Dav ai
Da a
i
log(
Dav  ai
Da  a
i
)
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:
G(a)  H(D)  H(Da )
• L’attributo migliore, dato un insieme D di esempi
classificati e una lista A di attributi, è quello che
massimizza il guadagno informativo
Esempio
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>
H(D)=-4/6log(4/6)-2/6log(2/6)=0,92
D sesso=F=1+,3+,6- D sesso=M=2+,4+,5H(D sesso=F)=-2/3log2/3-1/3log1/3=0,92
H(D sesso=M)=- 2/3log2/3-1/3log1/3=0,92
p(sesso=F)=0,5 p(sesso=M)=0,5
G(sesso)=0,92 - 0,50,92-0,5 0,92=0 !!!
D c_BP=si=1+,2+,4+ D c_BP=no=3+,5-,6H(D c_BP=si)=-3/3log3/3=0
H(D c_BP=no)=-1/3log1/3-2/3log2/3=0,92
p(c_BP=si)=3/6 Pr(c_BP=no)=3/6
G(c_BP)=0,92-0,5 0- 0,5 0,92=0,46
Esempio 2
• D: 14 esempi così ripartiti [9+,5-] => H=0,940
• Due attributi: humidity: {high,normal} wind: {weak,strong}
• Quale preferire?
humidity
high
Dhigh :[3+,4-]
wind
normal
Dnorm :[6+,1-]
Hhigh=0,985
Hnorm=0,592
Gain(humidity)=0,940-(7/14)0,958
-(7/14)0,592=0,151
weak
strong
Dweak :[6+,2-]
Dstrog :[3+,3-]
Hhigh=0,811
Hnorm=1,00
Gain(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 attributo
D: 3+, 2- a=ai
p(+)=3/5 p(-)=2/5
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
n tp  n tn
ntp  n tn
accuracy(L)  tp
fp
fn 
tn
N
n n n n
• Nota che in generale, TD (altrimenti in si ha una
sovrastima!!)
Curve di apprendimento
D
Accuracy
soglia
Training Data
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
D+:5
falso
vero
Si
SI
D+:2
D+:2
D-:2
7/9
attibuto
Confidenza:
n
falso
vero
Si
No
D-:2
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=no
Prova 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 zds
• (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,96s)
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
p
Esempi con vj=vali
pˆ i 
( pi  ni )
Probabilità positivi
pn
n
nˆi 
( pi  ni )
pn
• (la probabilità a posteriori è uguale alla probabilità a priori di
p ed n)
Potatura Chi-quadro
• Una misura della deviazione totale, per ogni
vali, della distribuzione degli esempi
sull'attributo x rispetto all'ipotesi nulla è:
( pi  pˆ i )2 (ni  nˆi ) 2


i 1
pˆ i
nˆi
N
• Nel caso di ipotesi nulla,  è distribuito secondo
la distribuzione chi-quadro (2 ) con N-1 gradi
di libertà.
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#Decisio
n
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.h
tml
• Anche sul sito WEKA (J4)
• Dati scaricabili dal repository:
http://www.ics.uci.edu/~mlearn/MLSummary.html
• http://www.mlnet.org/cgibin/mlnetois.pl/?File=datasets.html
• Varie decine di applicazioni, medicina, economia,
classificazione di specie, architettura, scacchi…