Introduzione agli alberi di decisione

Dr. A. Appice
Alberi di Decisione
Caso di studio di Metodi Avanzati di
Programmazione
AA 2012-2013
Dr. A. Appice
Data Mining
Lo scopo del data mining è l’estrazione (semi)
automatica di conoscenza nascosta in voluminose
basi di dati al fine di renderla disponibile e
direttamente utilizzabile
Dr. A. Appice
Aree di Applicazione
1. previsione
utilizzo di valori noti per la previsione di quantità non note (es. stima del
fatturato di un punto vendita sulla base delle sue caratteristiche)
2. classificazione
individuazione delle caratteristiche che indicano a quale gruppo un certo caso
appartiene (es. discriminazione tra comportamenti ordinari e fraudolenti)
3. segmentazione
individuazione di gruppi con elementi omogenei all’interno del gruppo e diversi
da gruppo a gruppo (es. individuazione di gruppi di consumatori con
comportamenti simili)
4. associazione
individuazione di elementi che compaiono spesso assieme in un determinato
evento (es. prodotti che frequentemente entrano nello stesso carrello della
spesa)
5. sequenze
individuazione di una cronologia di associazioni (es. percorsi di visita di un sito
web)
…
Dr. A. Appice
Classificazione
Considerando dati storici relativi a passati clienti e
pagamenti, predire (decidere) se il richiedente un
prestito sarà o meno un buon pagatore
Storico Clienti
Nome
Età
Reddito
Professione
Indirizzo
Tipo cliente
Classificatore
Regole di decisione
reddito > 35.000
prof. = insegnante
Buono
? pagatore
Cattivo
Dati di un nuovo cliente: Paolo Rossi, 35,37.000,architetto,Bari, ?
Dr. A. Appice
Metodi di classificazione
Apprendimento induttivo da esempi per imparare
la definizione di una funzione di
classificazione
Gli esempi usati per l’apprendimento sono
descritti come vettori di coppie attributo-valore
per i quali è nota la classe
Dr. A. Appice
Metodi di classificazione
Alberi di decisione
Le funzioni di classificazione sono apprese in forma di albero dove:
• ogni nodo interno rappresenta una variabile,
• un arco verso un nodo figlio rappresenta un possibile valore per
quella proprietà, e
• una foglia il valore predetto per la classe a partire dai valori delle
altre proprietà, che nell'albero è rappresentato del cammino (path)
dalla nodo radice (root) al nodo foglia.
Un albero di decisione viene costruito utilizzando tecniche di
apprendimento a partire dall'insieme dei dati iniziali (training set)
per i quali è nota la classe
http://it.wikipedia.org/wiki/Albero_di_decisione
Dr. A. Appice
Induzione di Alberi di decisione
Input
Input: una collezione di esempi di apprendimento (training set),
ciascun esempio è una tupla di valori per un prefissato insieme di
attributi (variabili indipendenti)
A = {A1, A2, …, Am}
e un attributo di classe (variabile dipendente). L’attributo Ai è
descritto come continuo o discreto a seconda che i sui valori siano
numerici o nominali.
L’attributo di classe C è discreto e ha valori C1, C2, …, Ck.
Dr. A. Appice
Induzione di Alberi di Decisione
Input
Day
Outlook
Temperature
Humidity
Wind
PlayTennis
D1
D2
D3
D4
D5
D6
D7
D8
D9
D10
Sunny
Sunny
Overcast
Rain
Rain
Rain
Overcast
Sunny
Sunny
Rain
Hot
Hot
Hot
Mild
Cool
Cool
Cool
Mild
Cool
Mild
High
High
High
High
Normal
Normal
Normal
High
Normal
Normal
Weak
Strong
Weak
Weak
Weak
Strong
Strong
Weak
Weak
Weak
No
No
Yes
Yes
Yes
No
Yes
No
Yes
Yes
D11
Sunny
Mild
Normal
Strong
Yes
D12
Overcast
Mild
High
Strong
Yes
D13
Overcast
Hot
Normal
Weak
Yes
D14
Rain
Mild
High
Strong
No
[See: Tom M. Mitchell, Machine Learning, McGraw-Hill, 1997]
Dr. A. Appice
Induzione di Alberi di Decisione
Output
Outlook
Sunny
Humidity
High
No
Overcast
Rain
Yes
Normal
Yes
Wind
Strong
No
Weak
Yes
Dr. A. Appice
Decision Trees
C4.5: Output
Outlook
Sunny
No
Rain
nodi interni sono associati a test su attributi
Humidity
High
Overcast
Normal
Yes
Ciascun ramo e associato a un
valore del test
Ciascuna foglia è associata a un
valore di classe
Dr. A. Appice
Alberi di decisione
Come usare l’albero per classificare?
Outlook Temperature Humidity Wind PlayTennis
Sunny
Hot
High Weak
?
Outlook
Sunny
Humidity
High
No
Overcast
No
Rain
Yes
Normal
Yes
Wind
Strong
No
Weak
Yes
Dr. A. Appice
Alberi di Decisione
Congiunzione di condizioni
Outlook
Sunny
Wind
Strong
No
Overcast
No
Rain
No
Weak
Yes
Outlook=Sunny  Wind=Weak
Dr. A. Appice
Alberi di Decisione
Disgiunzione di congiunzioni
Outlook
Sunny
Humidity
High
No
Overcast
Rain
Yes
Normal
Yes
Wind
Strong
No
(Outlook=Sunny  Humidity=Normal)

(Outlook=Overcast)

(Outlook=Rain  Wind=Weak)
Weak
Yes
Dr. A. Appice
Alberi di Decisione
Regole
Outlook
Sunny
Humidity
High
No
R1:
R2:
R3:
R4:
R5:
If
If
If
If
If
Overcast
Rain
Yes
Normal
Yes
Wind
Strong
No
Weak
Yes
(Outlook=Sunny)  (Humidity=High) Then PlayTennis=No
(Outlook=Sunny)  (Humidity=Normal) Then PlayTennis=Yes
(Outlook=Overcast) Then PlayTennis=Yes
(Outlook=Rain)  (Wind=Strong) Then PlayTennis=No
(Outlook=Rain)  (Wind=Weak) Then PlayTennis=Yes
Dr. A. Appice
Alberi di Decisione
Tipo di test
Ciascun nodo interno è associato ad un test che coinvolge
un attributo Ai.
Se Ai è discreto:
• un test con z alternative, una per ciascun valore
assunto da Ai
Outlook
Sunny
Overcast
Rain
Dr. A. Appice
Alberi di Decisione
Tipo di test
Ciascun nodo interno è associato ad un test che coinvolge
un attributo Ai.
Se Ai è continuo:
• un test con 2 alternative sulla base di una soglia :
Ai  vs. Ai >.
Tenure
Tenure<=2.5
Tenure>2.
Services
Stay
Services<=3
Leave
Services>3
Stay
Dr. A. Appice
Alberi di decisione
Selezionare i test
Domanda: Come determinare quale attributo
classifica meglio dati?
Risposta: Entropia!!!
Sia:
– S la porzione di esempi di training correntemente analizzati.
– Cj una classe in C1, C2, …, Ck.
– RF(Ci,S), i=1,..k sono le frequenze relative delle etichette Ci
in S (numero di casi di S che appartengono alla classe Ci.
L’entropia di E in S è calcolata come:
E(S)    RF(Ci , S) log 2 (RF(Ci , S))
i 1..k
Dr. A. Appice
Alberi di decisione
Selezionare i test
E(S) è una misura dell’incertezza contenuta in S.
– Assume valore massimo se gli eventi sono
equiprobabili
RF(C1,S)=…= RF(Ck,S)=1/k.
– Assume valore minimo se solo uno degli eventi ha
probabilità diversa da zero.
RF(Ci,S)=1 RF(Cj,S)=0 ji
Dr. A. Appice
Alberi di decisione
Selezionare i test
In problemi di classificazione binaria (due classi C1=+, C2 = -)
con:
– p il numero di esempi di S in classe +
– n il numero di esempi di S in classe La entropia E(S) è calcolata come segue:
E(S) = -plog2p - nlog2n
Dr. A. Appice
Alberi di decisione
Selezionare i test
• Lo Information Gain G(S, t) rappresenta la riduzione
attesa di entropia conseguente al partizionamento
degli esempi di S in accordo al test t.
• Sia S1, …, St il partizionamento di S per il test t
sull’attributo Ai,:
| Si |
G( S , t )  E ( S ) 
E (Si )
|S|
i

Il criterio basato sull’Information Gain sceglie il test t
che massimizza G(S,t)
Dr. A. Appice
Alberi di decisione
Selezionare i test
Esempio
Day
D1
D2
D3
D4
D5
D6
D7
D8
D9
D10
D11
D12
D13
D14
Outlook
Sunny
Sunny
Overcast
Rain
Rain
Rain
Overcast
Sunny
Sunny
Rain
Sunny
Overcast
Overcast
Rain
Temp.
Hot
Hot
Hot
Mild
Cool
Cool
Cool
Mild
Cold
Mild
Mild
Mild
Hot
Mild
Humidity
High
High
High
High
Normal
Normal
Normal
High
Normal
Normal
Normal
High
Normal
High
Wind
Weak
Strong
Weak
Weak
Weak
Strong
Weak
Weak
Weak
Strong
Strong
Strong
Weak
Strong
Play Tennis
No
No
Yes
Yes
Yes
No
Yes
No
Yes
Yes
Yes
Yes
Yes
No
Dr. A. Appice
Alberi di decisione
Selezionare i test
14 esempi di apprendimento: 9 - Yes, 5 - No
E(S) = -9/14log2(9/14) - 5/14log2 (5/14) = .940
Information Gain per Outlook
Outlook: sunny (5), overcast (4), rain (5)
Il test su Outlook partiziona S come segue:
outlook = sunny (5 esempi)  RF(Yes)=2/5 RF(No)=3/5
outlook = overcast (4 esempi)  RF(Yes)=4/4 RF(No)=0/4
outlook = rain
(5 esempi)  RF(Yes) = 3/5 RF(No) =2/5
Dr. A. Appice
Alberi di decisione
Selezionare i test
[Yes, No]=[9,5]
E=0.940
Outlook
Sunny
[Yes, No]=[2,3]
E=0.971
Overcast
[Yes, No]=[4,0]
E=0
Rain
[Yes, No]=[3,2]
E=0.971
Dr. A. Appice
Alberi di decisione
Selezionare i test
E(sunny) = -2/5log2 (2/5)-3/5log2 (3/5)=.971
E(overcast) = 0
E(rain) = .971
L’entropia di Outlook è:
E(Outlook)=5/14 0.971+4/14  0+5/14
0.971=0.694
L’Information Gain di un test su Outlook è:
G(Outlook)=E(S)-E(Outlook)=0.940-0.694=0.246
Dr. A. Appice
Alberi di decisione
Selezionare i test
Similmente possiamo clacolare:
–
–
–
–
G(Temperature)=0.029
G(humidity)=0.151
G(windy)=0.048
G(Outlook)=0.246  MAX
Il test che massimizza lo Information Gain è il
test eseguito su Outlook
Dr. A. Appice
Alberi di decisione
Definire le soglie per test continui
•
Come identificare le possibili soglie  per
l’attributo continuo A?
1. ordinare gli esempi sulla base dei valori
dell’attributo A (quicksort)
2. per ciascuna coppia (Xi, Xi+1) nella lista
ordinata, se le classi di Xi e Xi+1sono diverse
allora usare la media dei due valori come
soglia candidata.
Dr. A. Appice
Alberi di decisione
Definire le soglie per test continui
Esempio
A:
10
15
21
28
32
40
50
Class:
No
Yes
Yes
No
Yes
Yes
No
Threshold:
12.5
24.5
30
45
Dr. A. Appice
Alberi di Decisione
Algoritmo
learnTree(Table S, int begin, int end){
if( isLeaf(S begin, end)
root=new LeafNode(S,begin,end);
else //split node
{
root=determineBestSplitNode(S, begin, end);
childTree=new DecisionTree[root.getNumberOfChildren()];
for(int i=0;i<root.getNumberOfChildren();i++){
childTree[i]=new DecisionTree();
childTree[i].learnTree(trainingSet,root.begin,root.end);
}
}
}
Dr. A. Appice
Alberi di Decisione
Esercizio
Spiegare come costruire un albero di decisione per Assicurazione
carta di credito sul seguente insieme di addestramento:
Attributi: Range Reddito, Promozione assicurazione vita,
Assicurazione carta di credito, Genere, Età
Range
Promozione Assicurazione
Dati:
Genere
Età
Reddito
assic. vita
carta di cred.
40-50K
30-40K
40-50K
30-40K
50-60K
20-30K
30-40K
20-30K
30-40K
30-40K
40-50K
20-30K
50-60K
40-50K
20-30K
No
Si
No
Si
Si
No
Si
No
No
Si
Si
Si
Si
No
Si
No
No
No
Si
No
No
Si
No
No
No
No
No
No
No
Si
Maschio
Femmina
Maschio
Maschio
Femmina
Femmina
Maschio
Maschio
Maschio
Femmina
Femmina
Maschio
Femmina
Maschio
Femmina
45
40
42
43
38
55
35
27
43
41
43
29
39
55
19
Dr. A. Appice
Alberi di Decisione
Ross Quinlan, author of C4.5
http://www.cse.unsw.edu.au/~quinlan/
Ross Quinlan’s personal website at the University of New South Wales. c4.5 is available to
download, as are several of Quinlan’s academic papers.
Dr. A. Appice
Caso di studio
Progettare e realizzare un sistema client-server
denomianto “Decision Tree Classifier”.
Il server include funzionalità di data mining per
l’apprendimento di alberi di decisione e uso degli
stessi come strumento di previsione.
Il client è un applet Java che consente di effettuare
previsioni usufruendo del servizio di predizione
remoto
Dr. A. Appice
Istruzioni
1. Il progetto dell'a.a. 2012/13 riguarda il “Decision Tree Classifier"
ed è valido solo per coloro che superano la prova scritta entro il
corrente a.a.
2. Ogni progetto può essere svolto da gruppi di al più TRE (3)
studenti.
3. Coloro i quali superano la prova scritta devono consegnare il
progetto ENTRO la data prevista per la corrispondente prova
orale.
4. La discussione del progetto avverrà alla sua consegna, ad
personam per ciascun componente del gruppo. Il voto massimo
della prova scritta è 33. Un voto superiore a 30 equivale a 30 e
lode.
5. Il voto finale sarà stabilito sulla base del voto attribuito allo
scritto e al progetto.
Dr. A. Appice
Istruzioni
Non si riterrà sufficiente un progetto non
sviluppato in tutte le su parti (client-server,
applet, accesso al db, serializzazione,…