Document

Classification
Salvatore Orlando
Data Mining - S. Orlando
1
Classificazione
 Dati una collezione di dati (training set )
– Ciascun record contiene un insieme di attributi, uno dei quali è
la classe di appartenenza.
 Trova un modello per l’attributo classe che diventa
funzione degli altri attributi
 Obiettivo: trovare una funzione che assegni in modo
accurato l’attributo classe a nuovi records non
classificati.
– Un test set è usato per determinare l’accuratezza del modello.
– Di solito il dataset iniziale è suddiviso in training e test sets:
costruiamo il modello con il training set, e usiamo il test set per
validarlo.
Data Mining - S. Orlando
2
Esempio di classificazione
Tid Refund Marital
Status
Taxable
Income Cheat
Refund Marital
Status
Taxable
Income Cheat
1
Yes
Single
125K
No
No
Single
75K
?
2
No
Married
100K
No
Yes
Married
50K
?
3
No
Single
70K
No
No
Married
150K
?
4
Yes
Married
120K
No
Yes
Divorced 90K
?
5
No
Divorced 95K
Yes
No
Single
40K
?
6
No
Married
No
No
Married
80K
?
60K
10
7
Yes
Divorced 220K
No
8
No
Single
85K
Yes
9
No
Married
75K
No
10
No
Single
90K
Yes
10
Training
Set
Learn
Classifier
Test
Set
Model
Cheat = truffatore,imbroglione
Data Mining - S. Orlando
3
Classificazione vs. Clustering
 Supervised learning (classification)
– Supervisione: I dati del training set (osservazioni, misure, etc.)
sono stati preventivamente associati a etichette che indicano la
classe di appartenenza
• conoscenza supervisionata
– I nuovi record di dati sono classificati usando il modello
costruito sulla base del training set
 Unsupervised learning (clustering)
– L’etichetta della classe è sconosciuta
– Dati un insieme di misure, osservazioni, ecc. lo scopo del
clustering è quello di stabilire l’esistenza di gruppi/classi nei dati
• Imparare l’esistenza di un qualche modello presente nei dati, che dà
luogo ad una suddivisione dei dati, senza conoscenza precedente
Data Mining - S. Orlando
4
Tecniche di classificazione







Metodi basati sugli Alberi di Decisione (Decision Tree)
Metodi Rule-based
Memory-based reasoning
Neural Networks
Genetic Algorithms
Naïve Bayes
Support Vector Machines
Data Mining - S. Orlando
5
Classificazione basata su Decision Tree
 I modelli di classificazione basati su Decision Tree sono
considerati tra i migliori
–
–
–
–
Non costosi da costruire
Facili da interpretare
Facili da integrare con le basi di dati
Buona accuratezza in molte applicazioni, anche in confronto ad
altri metodi di classificazione
Data Mining - S. Orlando
6
Decision tree
 Decision Tree
– Un struttura ad albero che somiglia ad un flow-chart
– Ogni nodo interno denota un test su un attributo
• Gli archi uscenti rappresentano i risultati del test
– Ogni nodo foglia rappresenta un’etichetta di classe o la
distribuzione delle varie classi
 Uso di un Decision Tree
– Per classificare un nuovo dato campione sulla base degli
attributi
• ovvero per assegnare un’etichetta di classe al nuovo dato
– Effettua i test sui valori degli attributi del campione rispetto ai
test presenti nel decision tree
• A partire dalla radice, e sulla base degli attributi del campione da
classificare, segue un cammino fino ad una foglia
• L’etichetta della foglia definisce la classe di appartenenza del
campione
Data Mining - S. Orlando
7
Esempio di albero di classificazione
Tid Refund Marital
Status
Taxable
Income Cheat
1
Yes
Single
125K
No
2
No
Married
100K
No
3
No
Single
70K
No
4
Yes
Married
120K
No
5
No
Divorced 95K
Yes
6
No
Married
No
7
Yes
Divorced 220K
No
8
No
Single
85K
Yes
9
No
Married
75K
No
10
No
Single
90K
Yes
60K
Splitting Attributes
Refund
Yes
No
NO
MarSt
Single, Divorced
Married
TaxInc
< 80K
NO
NO
> 80K
YES
10
Data Mining - S. Orlando
8
Un altro albero di classificazione
MarSt?
Tid Refund Marital
Status
Taxable
Income Cheat
1
Yes
Single
125K
No
2
No
Married
100K
No
3
No
Single
70K
No
4
Yes
Married
120K
No
5
No
Divorced 95K
Yes
6
No
Married
No
7
Yes
Divorced 220K
No
8
No
Single
85K
Yes
9
No
Married
75K
No
10
No
Single
90K
Yes
60K
Married
NO
Single,
Divorced
Refund?
No
Yes
NO
TaxInc?
< 80K
NO
> 80K
YES
Si possono derivare più alberi dagli
stessi dati!
10
Data Mining - S. Orlando
9
Un altro esempio
age
<=30
<=30
31…40
>40
>40
>40
31…40
<=30
<=30
>40
<=30
31…40
31…40
>40
income student
high
no
high
no
high
no
medium no
low
yes
low
yes
low
yes
medium no
low
yes
medium yes
medium yes
medium no
high
yes
medium no
credit_rating buys_computer
fair
no
excellent
no
fair
yes
fair
yes
fair
yes
excellent
no
excellent
yes
fair
no
fair
yes
fair
yes
excellent
yes
excellent
yes
fair
yes
excellent
no
age?
<=30
>40
31..40
student?
YES
credit rating?
no
yes
excellent
NO
YES
NO
fair
YES
Data Mining - S. Orlando
10
Algoritmo per Decision Tree Induction
 Algoritmo di base (metodo greedy)
– L’albero è costruito in modo:
• top-down - ricorsivo - divide-and-conquer
– All’inizio tutti gli esempi di training sono in corrispondenza della
radice
– Gli esempi di training sono partizionati ricorsivamente sulla
base degli attributi selezionati
– Gli attributi di test sono selezionati in base ad un’euristica o a
misure statistiche (es., gini index, information gain)
• Scopo: suddividere gli esempi creando partizioni omogenee
• Esistono metodi che funzionano su attributi di test categorici e/o su
attributi numerici
 Condizioni per stoppare il partizionamento
– Tutti gli esempi di una partizione in una stessa classe
– Non abbiamo più attributi sulla cui base partizionare
ulteriormente – usiamo una tecnica di majority voting per
classificare la foglia
Data Mining - S. Orlando
11
Come effettuare lo splitting: attributi nominali
 Ciascuna partizione è caratterizzato da un sottoinsieme di valori.
 Multi-way split: Usa tanti ramificazioni dello split quanti sono i
valori distinti.
CarType
Family
Luxury
Sports
 Binary split: Divisi i valori in due sottoinsiemi.
Bisogna individuare un partizionamento ottimale.
{Sports,
Luxury}
CarType
{Family}
oppure
{Family,
Luxury}
CarType
{Sports}
Data Mining - S. Orlando
12
Come effettuare lo splitting: attributi ordinali
 Ciascuna partizione è caratterizzato da un sottoinsieme di valori.
 Multi-way split: Usa tanti ramificazioni dello split quanti sono i
valori distinti.
Size
Small
Large
Medium
 Binary split: Divisi i valori in due sottoinsiemi.
Bisogna individuare un partizionamento ottimale.
{Small,
Medium}
Size
{Large}
oppure
{Medium,
Large}
Size
{Small}

Questo partizionamento
potrebbe essere possibile?
{Small,
Large}
Size
{Medium}
Data Mining - S. Orlando
13
Come effettuare lo splitting: attributi numerici
 Metodi differenti
– Binary Decision: (A < v) or (A  v)
• considera tutti i possibili split e individua il miglior taglio
• Può risultare molto costo computazionalmente, anche se
esistono dei metodi basati sull’ordinamento
– Discretizzazione per formare un attributo categorico
(ordinale)
• Statico – discretizzato una volta per tutte all’inizio
• Dinamico – le suddivisioni possono essere trovati tramite
equal interval partitioning, equal frequency partitioning, o
distance-based clustering.
Data Mining - S. Orlando
14
Discretizzazione
 Equal-width (distance) partitioning:
– Dividi la scala di variazione dell’attributo in N intervalli identici
– Se A e B sono il più piccolo e il più grande valore di un attributo, la
larghezza degli intervalli sarà: W = (B-A)/N.
– E’ il metodo più semplice, ma gli outlier (o dati non ben distribuiti)
possono dare problemi al metodo di discretizzazione
 Equal-depth (frequency) partitioning:
– Dividi la scala di variazione dell’attributo in N intervalli identici,
ciascuno contenente approssimativamente lo stesso numero di
campioni
– Buon metodo
 Cluster analysis partitioning:
– Può risultare costoso
Data Mining - S. Orlando
15
Discretizzazione
Data
Equal frequency
Equal interval width
K-means (clustering)
Data Mining - S. Orlando
16
Criterio di splitting
 Come scegliere l’attributo e il relativo splitting?
– uso di particolari indici di dispersione dei valori dell’attributo
categorico di classe
 Gini index (algoritmo di IBM IntelligentMiner, CART, SLIQ, SPRINT)
 Information gain (algoritmi ID3/C4.5)
Data Mining - S. Orlando
17
Gini index
 In corrispondenza di un certo nodo t dell’albero in costruzione, e
rispetto alla corrispondente partizione del dataset di training,
possiamo definire il Gini Index:
GINI (t )  1   [ p( j | t )]2
j
(NOTA: p( j | t) è la frequenza relativa della classe j al nodo t).
– Misura l’impurità/disordine del dataset corrispondente a t.
• Massimo valore (1 - 1/nc) quando i record sono equamente
distribuiti tra tutte le classi  informazione meno interessante
• Minimo valore (0.0) quando tutti i record appartengono ad una sola
classe  informazione più interessante
C1
C2
0
6
Gini=0.000
C1
C2
1
5
Gini=0.278
C1
C2
2
4
Gini=0.444
C1
C2
3
3
Gini=0.500
Data Mining - S. Orlando
18
Gini
 Una sola classe:
– 1 - 12 = 0
 nc classi equiprobabili:
– 1 - \sum ((n / nc) / n)2 = 1 - \sum (1 / nc)2 = 1 – nc (1 / nc)2 = 1 – 1 / nc
Data Mining - S. Orlando
19
Esempi relativi a Gini Index
GINI (t )  1   [ p( j | t )]2
j
C1
C2
0
6
P(C1) = 0/6 = 0
C1
C2
1
5
P(C1) = 1/6
C1
C2
2
4
P(C1) = 2/6
P(C2) = 6/6 = 1
Gini = 1 – P(C1)2 – P(C2)2 = 1 – 0 – 1 = 0
P(C2) = 5/6
Gini = 1 – (1/6)2 – (5/6)2 = 0.278
P(C2) = 4/6
Gini = 1 – (2/6)2 – (4/6)2 = 0.444
Data Mining - S. Orlando
20
Uso del GINI Index
 Criterio di Splitting: Minimizza il Gini Index della suddivisione.
 Quando un nodo t è suddiviso in k partizioni (figli), la qualità della
suddivisione è calcolata come:
k
ni
GINI split   GINI (i )
i 1 n
dove,
ni = numero di record della partizione (figlio) i,
n = numero di record del dataset al nodo t.
ni /n costituisce il peso dei vari GINI(i)
 Dato il dataset associato al nodo t, si sceglie l’attributo che fornisce
il più piccolo GINIsplit(t) per partizionare il dataset
– È necessario enumerare tutti i possibili punti di splitting per
ciascun attributo
Data Mining - S. Orlando
21
Calcolare il GINI Index per attributi binari
 Suddivisione in due partizioni
 Si cercano partizioni più grandi e più pure possibili.
Parent
B?
Yes
No
Node N1
C1
C2
N1
0
6
N2
6
0
Gini=0.000
C1
C2
N1
5
1
Gini=0.278
C1
C2
N1
4
3
6
C2
6
Gini = 0.500
Node N2
N2
1
5
C1
N2
2
3
Gini=0.486
C1
C2
N1
3
3
N2
3
3
Gini=0.500
Data Mining - S. Orlando
22
Calcolare il GINI Index per attributi categorici
 Per ciascuna classe nel dataset, conta il numero dei valori differenti
per ogni attributo
– computa le singole righe delle matrici di conteggio
 Usa la matrice dei conteggi per prendere le decisioni
Two-way split
(bisogna trovare il migliore
partizionamento dei valori)
Multi-way split
CarType
Family Sports Luxury
C1
C2
Gini
1
4
2
1
0.393
1
1
C1
C2
Gini
CarType
{Sports,
{Family}
Luxury}
3
1
2
4
0.400
C1
C2
Gini
CarType
{Family,
{Sports}
Luxury}
2
2
1
5
0.419
Data Mining - S. Orlando
23
Calcolare il GINI Index per attributi continui
 Solitamente si usa Binary Decision, basato su un singolo valore di
splitting
– Non abbiamo bisogno di discretizzare
 Sono possibili scelte diverse per il valore di splitting
– Es.: Numero di possibili valori di splitting = Numero di valori distinti
assunti dall’attributo
 Ciascun valore di splitting ha una matrice di conteggi associata
– Conteggio delle varie classi per ciascuna partizione, (A < v) e (A  v)
 Metodo naive per scegliere il miglior v
– Per ciascun v, scandisci il database per raccogliere la matrice dei
conteggi e computare il corrispondente Gini Index (GINIsplit)
– Questo metodo è computazionalmente inefficiente! Lavoro ridondante.
Data Mining - S. Orlando
24
Calcolare il GINI Index per attributi continui (2)
 Metodo per migliorare l’efficienza
 Per ciascun attributo
– Ordina rispetto ai valori degli attributi
– Scandisci linearmente questi valori, aggiornando ogni volta la matrice dei
conteggi necessario per calcolare il GINI index
• considera che, quando spostiamo il pivot, abbiamo un singolo elemento
(appartenente ad una certa classe) che passa da una partizione all’altra
• +/- 1 in una particolare riga
– Scegli le posizioni di split che hanno il GINI index minore
Cheat
No
No
No
Yes
Yes
Yes
No
No
No
No
100
120
125
220
Taxable Income
Sorted Values
60
Split Positions
70
55
75
65
85
72
90
80
95
87
92
97
110
122
172
230
<=
>
<=
>
<=
>
<=
>
<=
>
<=
>
<=
>
<=
>
<=
>
<=
>
<=
>
Yes
0
3
0
3
0
3
0
3
1
2
2
1
3
0
3
0
3
0
3
0
3
0
No
0
7
1
6
2
5
3
4
3
4
3
4
3
4
4
3
5
2
6
1
7
0
Gini
0.420
0.400
0.375
0.343
0.417
0.400
0.300
0.343
0.375
0.400
0.420
Data Mining - S. Orlando
25
Criterio di splitting alternativo: Information Gain
 In corrispondenza di un certo nodo t dell’albero in costruzione, e
rispetto alla corrispondente partizione del dataset di training,
possiamo definire l’Information Gain:
Entropy(t )   p( j | t ) log p( j | t )
j
(NOTA: p( j | t) è la frequenza relativa della classe j al nodo t).
– Misura l’omogeneità/ordine di un nodo.
• Massimo (log nc) quando i record sono equamente distribuiti tra
tutte le classi  implica meno informazione
• Minimo valore (0.0) quando tutti i record appartengono ad una sola
classe  implica più informazione
– I calcoli basati sulla misura dell’Entropia sono simili a quelle
basate sul GINI index
Data Mining - S. Orlando
26
Entropy
 Una sola classe:
– - (1 * log 1) = 0
 nc classi equiprobabili:
– - (\sum ( (n / nc) / n) * log ((n / nc) / n) ) =
– - ( \sum ( (1 / nc) * log (1 / nc) ) =
– - nc * (1 / nc) * log (1 / nc) = - log (1 / nc) = - (log 1 - log nc) = log nc
Data Mining - S. Orlando
27
Esempi relativi all’Information Gain (Entropia)
Entropy(t )   p( j | t ) log p( j | t )
j
C1
C2
0
6
C1
C2
1
5
P(C1) = 1/6
C1
C2
2
4
P(C1) = 2/6
P(C1) = 0/6 = 0
2
P(C2) = 6/6 = 1
Entropy = – 0 log 0 – 1 log 1 = – 0 – 0 = 0
P(C2) = 5/6
Entropy = – (1/6) log2 (1/6) – (5/6) log2 (1/6) = 0.65
P(C2) = 4/6
Entropy = – (2/6) log2 (2/6) – (4/6) log2 (4/6) = 0.92
Data Mining - S. Orlando
28
Uso dell’Entropia come criterio di splitting
 Quando un nodo t è suddiviso in k partizioni (figli), la qualità della
suddivisione è calcolata come IG (Information Gain):
 k ni

GAIN split  Entropy(t )    Entropy(i) 
 i 1 n

dove, ni = numero di record della partizione (figlio) i,
n = numero di record del dataset al nodo t.
ni /n costituisce il peso dei vari Entropy(i)
 Misura la riduzione nell’Entropia in conseguenza dello split. Scegli
lo split che raggiunge la riduzione maggiore (massimizza il GAIN)
 Usato in ID3 e C4.5
Data Mining - S. Orlando
29
Problemi legati all’Information Gain
 Svantaggio:
– l’IG tende a preferire suddivisioni che producono molte partizioni,
piccole ma pure (ovvero che comprendono elementi appartenenti ad
una singola classe). Si rischia di costruire un albero overfitted rispetto
al training set
 Gain Ratio:
GAIN
n
n
GainRATIO 
SplitINFO    log
SplitINFO
n
n
Split
split
k
i
i
i 1
Il nodo padre, è suddiviso in k partizioni
ni è il numero di record della partizione i
– Corregge l’Information Gain dello split usando l’entropia del
partizionamento (SplitINFO).
– Valori alti di SplitINFO si ottengono all’aumento del numero di piccole
partizioni!
 l’aumento di SplitINFO penalizza Gain Ratio
– Usato in C4.5
Data Mining - S. Orlando
30
Algoritmo C4.5 - like
Data Mining - S. Orlando
31
Overfitting
 L’albero può overfit-are i dati di training
– Troppi rami, alcuni dei quali possono riflettere anomalie dovuti a rumori
o outlier
– Poca accuratezza (troppi errori) per campioni non visti (test dataset)
Overfitting
Data Mining - S. Orlando
32
Overfitting: Pre-Pruning
 Pre-Pruning (Early Stopping Rule)
– Stop dell’algoritmo prima che esso produca un albero fullygrown
– Le tipiche condizioni di stopping:
• Stop se tutte le istanze appartengono alla stessa classe
• Stop se tutti i valori degli attributi hanno lo stesso valore
– Condizioni più restrittive per il pruning:
• Stop se il numero di istanze è minore di uno user-specified
threshold
– Evita la creazione di piccole partizioni
– Difficile trovare il threshold
• Stop se espandendo il nodo corrente non miglioriamo la misura di
impurità
(es.., Gini o Information Gain).
Data Mining - S. Orlando
33
Overfitting: Post-Pruning
 Post-Pruning
– Rimuovi nodi/rami da un albero completo (“fully grown” tree)
• Elimina i nodi in modo bottom-up
– Usa un insieme di dati differenti dal training data (testing data)
per decidere qual è il “best pruned tree”
– Se l’errore sui dati di testing migliora dopo la sostituzione del
sotto-albero con un nodo foglia
• Sostituisci in maniera permanente, generando un albero pruned
– L’etichetta di classe da assegnare al nuovo nodo foglia è
determinato dalla classe maggioritaria nel sotto albero
Data Mining - S. Orlando
34
Presentation: decisiontree
Data Mining - S. Orlando
35
Presentation: decisiontree
Data Mining - S. Orlando
36
Estrarre regole di classificazione da alberi
 Rappresenta la conoscenza nella forma di regole IFTHEN
– Una regola per ogni cammino dalla radice ad una foglia
– Ciascuna coppia attributo-valore lungo un cammino forma una
congiunzione
– Il nodo foglia restituisce la predizione della classe per la regola
estratta
 Le regole sono più facili da capire
 Esempi
IF age = “<=30” AND student = “no” THEN buys_computer = “no”
IF age = “<=30” AND student = “yes” THEN buys_computer = “yes”
IF age = “31…40”
THEN buys_computer = “yes”
IF age = “>40” AND credit_rating = “excellent” THEN buys_computer =
“yes”
IF age = “>40” AND credit_rating = “fair” THEN buys_computer = “no”
Data Mining - S. Orlando
37
Classificatori Bayesiano


Metodo probabilistico (Bayesian) per risolvere
il problema della classificazione
Probabilità condizionali:
P( A  C )
P(C | A) 
P( A)
P( A  C )
P( A | C ) 
P(C )
C
A
 Teorema di Bayes :
P( A | C ) P(C )
P(C | A) 
P( A)
Data Mining - S. Orlando
38
Esempio di applicazione del teorema di Bayes
 Conoscenza pregressa:
– Un dottore sa che la meningite causa rigidità del collo per il 50% dei
casi
• P(rigidità del collo | meningite) = 1/2
– La probabilità incondizionata che un paziente possa avere la
meningite è
• P(meningite) = 1/50000 = 0,00002
– La probabilità incondizionata che un paziente possa avere rigidità del
collo è
• P(rigidità del collo) = 1/20 = 0,05
 Se un paziente ha rigidità del collo, qual è la
probabilità che egli abbia la meningite?
P( R | M ) P( M ) 0.5 1 / 50000
P( M | R) 

 0.0002
P( R)
1 / 20
Data Mining - S. Orlando
39
Classificatori Bayesiano
 Considera i vari attributi e l’etichetta della classe come variabili
casuali
 Dato un record R contenente gli attributi (A1, A2,…,An)
– Lo scopo è predire la classe C di R
– Più specificatamente, vogliamo trovare il valore di C che massimizza:
P(C| A1, A2,…,An )
 Possiamo stimare P(C| A1, A2,…,An ) direttamente dai dati?
Data Mining - S. Orlando
40
Classificatori Bayesiano
 Approccio:
– Calcoliamo la probabilità a posteriori P(C | A1, A2, …, An) per tutti i valori
dell’etichetta C di classe
– Scegli il valore di C che massimizza
P(C | A1, A2, …, An)
P( A A  A | C ) P(C )
P(C | A A  A ) 
P( A A  A )
1
1
2
2
n
n
1
2
n
 Sulla base del teorema di Bayes, possiamo equivalentemente
scegliere il valore di C che massimizza
P(A1, A2, …, An | C) P(C)
 Come stimiamo P(A1, A2, …, An | C) ?
Data Mining - S. Orlando
41
Classificatore Naïve Bayes
 Assunzione Naïve : Assumiamo l’indipendenza tra gli attributi Ai
quando sia data una certa classe C
– P(A1, A2, …, An |Cj) = P(A1| Cj) P(A2| Cj)… P(An| Cj)
– Possiamo facilmente calcolare P(Ai| Cj) per tutte le coppie Ai e Cj nel
training set, oltre ai vari P(Cj)
– Un nuovo record (B1, B2, …, Bn) è classificato come Cj se risulta
massima la produttoria:
P(Cj)
 P(Ai| Cj) =
P(Cj) P(A1, A2, …, An |Cj)
Data Mining - S. Orlando
42
Come stimiamo
la probabilità
dai dati?
s
al
al
c
Tid
e
at
Refund
g
ic
r
o
c
e
at
g
ic
r
o
c
t
n
o
in
u
o
u
s
s
a
cl
Marital
Status
Taxable
Income
Evade
1
Yes
Single
125K
No
2
No
Married
100K
No
3
No
Single
70K
No
4
Yes
Married
120K
No
5
No
Divorced
95K
Yes
6
No
Married
60K
No
7
Yes
Divorced
220K
No
8
No
Single
85K
Yes
9
No
Married
75K
No
10
No
Single
90K
Yes
 Probabilità delle Classi:
– P(C) = Nc/N
– dove Nc è il numero di istanze
che appartengono alla classe C
– Es., P(No) = 7/10, P(Yes) = 3/10
 Per attributi discreti:
– P(Ai | Ck) = |Aik| / Nck
– dove |Aik| è il numero di istanze
che hanno l’attributo Ai e
appartengono alla classe Ck
– dove Nck è il numero di istanze
che appartengono alla classe Ck
10
– Esempi:
P(Married | No) = 4/7
P(Refund=Yes | Yes)=0
Data Mining - S. Orlando
43
Come stimiamo la probabilità dai dati?
 Per attributi continui:
– Abbiamo bisogno di conoscere la probabilità condizionale
P(Ai|C)
• nota che il particolare valore dell’attributo continuo Ai potrebbe
non essere presente nel dataset di training
– Assumiamo che gli attributi obbediscono a certe
distribuzioni di probabilità
• Tipicamente, si assume la distribuzione normale
• Si usano i dati per stimare i parametri della distribuzione di
probabilità
(ovvero, media e deviazione standard)
• Una volta che la distribuzione di probabilità è nota, possiamo
usarla per stimare la probabilità condizionale P(Ai|C)
Data Mining - S. Orlando
44
l
a
c
i
r
a
c
i
r
l
s
u
Come stimiamo
le
probabilità
dai dati?
o
u
o
o
c
Tid
e
at
Refund
g
c
e
at
Marital
Status
g
c
t
n
o
Taxable
Income
in
as
l
c
Evade
1
Yes
Single
125K
No
2
No
Married
100K
No
3
No
Single
70K
No
4
Yes
Married
120K
No
5
No
Divorced
95K
Yes
6
No
Married
60K
No
7
Yes
Divorced
220K
No
8
No
Single
85K
Yes
9
No
Married
75K
No
10
No
Single
90K
Yes
s
 Distribuzione normale:
1
P( A | c ) 
e
2
i
j

( Ai   ij ) 2
2  ij2
2
ij
– Una per ciascuna coppia (Ai,ci)
 Per (Income, Class=No):
– Se Class=No
• ij (media nel campione)
= 110
• 2ij (varianza nel campione) =
2975
10
1
P( Income  120 | No) 
e
2 (54.54)

( 120110) 2
2 ( 2975)
 0.0072
Data Mining - S. Orlando
45
Esempio di classificatore Naïve Bayes
Dato il seguente test:
X  (Refund  No, Married, Income  120K)
P(Refund=Yes|No) = 3/7
P(Refund=No|No) = 4/7
P(Refund=Yes|Yes) = 0
P(Refund=No|Yes) = 1
P(Marital Status=Single|No) = 2/7
P(Marital Status=Divorced|No) = 1/7
P(Marital Status=Married|No) = 4/7
P(Marital Status=Single|Yes) = 2/3
P(Marital Status=Divorced|Yes) = 1/3
P(Marital Status=Married|Yes) = 0
Per Income:
Se No:
Se Yes:
media = 110
varianza = 2975
media = 90
varianza = 25

P(X|Class=No) = P(Refund=No| Class=No)
 P(Married| Class=No)
 P(Income=120K| Class=No)
= 4/7  4/7  0.0072 = 0.0024
P(X|Class=No)  P(No) = 0.0024  0.7 = 0.00168

P(X|Class=Yes) = P(Refund=No| Class=Yes)
 P(Married| Class=Yes)
 P(Income=120K| Class=Yes)
= 1  0  1.2  10-9 = 0
P(X|Class=Yes)  P(Yes) = 0.0  0.3 = 0.0
Poiché P(X|No)P(No) > P(X|Yes)P(Yes)
abbiamo che: P(No|X) > P(Yes|X)
=> Class = No
Data Mining - S. Orlando
46
Esempio di classificatore Naïve Bayes
Test sugli attributi:
Give Birth
yes
Can Fly
no
Live in Water Have Legs
yes
no
A: attributes
Class
M: mammals
?
Non-M: non-mammals
Name
human
python
salmon
whale
frog
komodo
bat
pigeon
cat
leopard shark
turtle
penguin
porcupine
eel
salamander
gila monster
platypus
owl
dolphin
eagle
Give Birth
yes
no
no
yes
no
no
yes
no
yes
yes
no
no
yes
no
no
no
no
no
yes
no
Can Fly
no
no
no
no
no
no
yes
yes
no
no
no
no
no
no
no
no
no
yes
no
yes
Live in Water
no
no
yes
yes
sometimes
no
no
no
no
yes
sometimes
sometimes
no
yes
sometimes
no
no
no
yes
no
Have Legs
yes
no
no
no
yes
yes
yes
yes
yes
no
yes
yes
yes
no
yes
yes
yes
yes
no
yes
Class
M
non-M
non-M
M
non-M
non-M
M
non-M
M
non-M
non-M
non-M
M
non-M
non-M
non-M
M
non-M
M
non-M
6 6 2 2
P( A | M )      0.06
7 7 7 7
1 10 3 4
P( A | N )      0.0042
13 13 13 13
7
P( A | M ) P( M )  0.06 
 0.021
20
13
P( A | N ) P( N )  0.004 
 0.0027
20
P(A|M)P(M) > P(A|N)P(N)
=> Mammals
Data Mining - S. Orlando
47
Classificatore Naïve Bayes: sommario
 Robusto rispetto al rumore
 Gestisce i valori mancanti ignorando le istanze durante il calcolo
della stima di probabilità
 Purtroppo l’assunzione di indipendenza può non essere valida per
qualche attributo
 Per superare queste limitazioni:
– Bayesian networks, che combinano ragionamenti Bayesiani con
relazioni di causalità tra gli attributi
– Alberi di decisione, che ragionano su un attributo alla volta,
considerando gli attributi più importanti per primi
Data Mining - S. Orlando
48
Classificatori Instance-Based
• Memorizza le istanze di training
=> “Ritarda” nella costruzione del modello (lazy learner)
• Usa le istanze di training per predire l’etichetta di classe di
nuovi casi non visti
• Approcci Tipici
Set of Stored Cases
• k-nearest neighbor
• Locally weighted regression
Atr1
……...
AtrN
Class
A
• Case-based reasoning
B
B
C
A
Unseen Case
Atr1
……...
AtrN
C
B
Data Mining - S. Orlando
49
K-nearest neighbor
Unseen Instance
 Istanze come punti nel piano
euclideo
– attributi continui
 Richiede tre cose:
– L’insieme di istanze
memorizzate
– Metrica di Distanza
– Il valore di k, il numero di
vicini “nearest” da estrarre
 Per la classificazione:
– Estrai i k nearest neighbors
– Usa le etichette di classe dei
nearest neighbors per
determinare l’etichetta di
classe dell’istanza non vista
(es., attraverso il voto di
maggioranza)
Data Mining - S. Orlando
50
K-nearest neighbor
X
(a) 1-nearest neighbor
X
X
(b) 2-nearest neighbor
(c) 3-nearest neighbor
I K-nearest neighbors di un’istanza x sono i punti che
hanno le K più piccole distanze da x
Data Mining - S. Orlando
51
1 nearest-neighbor
Voronoi Diagram

A causa del costo della classificazione, è necessario indicizzare/precomputare
informazioni per velocizzare il calcolo dei K vicini più prossimi
Data Mining - S. Orlando
52
Classificatore K-nearest neighbor
 Calcola la distanza tra due punti:
– Distanza Euclidea
d ( p, q ) 
 ( pi
i
q )
2
i
 Distanza per pesare i voti
– fattore di peso, w = 1/d2
– pesa il voto in accordo alla distanza
Data Mining - S. Orlando
53
Classificatore K-nearest neighbor ………
 Scegliere il valore di k:
– Se k è troppo piccolo, il classificatore è sensibile al rumore
– Se k è troppo grande,
• costoso dal punto di vista computazionale
• la cerchia dei vicini può includere punti appartenenti ad altre classi
X
Data Mining - S. Orlando
54
Case-Based Reasoning
 Anche questo metodo usa: lazy evaluation + analisi delle istanze
più simili
 Differenza: Le istanze non sono “punti nello spazio Euclideo”
 Metodologia
– Le istanze/casi sono rappresentate da una ricca descrizione simbolica
(es., grafi, funzioni)
– Un case-based reasoner prima cerca di capire se esiste un caso di
training identico al nuovo caso da classificare => classificazione OK
– Se questo caso uguale non esiste, si cercano casi di training “vicini”,
ovvero con componenti simili a quelli del nuovo caso
• Es.: se i casi sono rappresentati come grafi, si cercano sottografi comuni
 Problemi
– Trovare una buona misura di similarità (es. per il matching tra grafi)
– Metodi di indicizzazione per velocizzare la ricerca di casi simili
Data Mining - S. Orlando
55
Lazy (pigro) vs. eager (impaziente) evaluation
 Instance-based learning: lazy evaluation
 Decision-tree and Bayesian classification: eager evaluation
 Differenze chiavi
– I metodi lazy considerano l’istanza di query q contemporaneamente
alla decisione su come generalizzare a partire dal dataset D di training
– I metodi eager non possono farlo, poiché hanno già scelto
approssimazioni globali per costruire il modello nel momento in cui
vedono la query
 Efficienza: i metodi lazy impiegano meno tempo per il training, ma
più tempo per predire la classe
 Accuratezza
– I metodi lazy: usano efficientemente uno spazio di ipotesi più ricco
ritagliato sulla query q
– I metodi eager: devono convergere da subito ad una ipotesi singola che
copre l’intero spazio delle istanze di training
Data Mining - S. Orlando
56
Metriche per valutare i classificatori
 Siamo interessati alle prestazioni dei classificatori
– rispetto alla capacità predittiva del modello
– possibile tradeoff rispetto alla velocità dell’algoritmo
 Confusion Matrix:
PREDICTED CLASS
Class=Yes
Class=No
a: TP (true positive)
ACTUAL
CLASS
Class=Yes
a
b
b: FN (false negative)
c: FP (false positive)
Class=No
c
d
d: TN (true negative)
Conteggi: a, b, c, e d anche esprimibili in percentuale
Data Mining - S. Orlando
57
Metriche per valutare i classificatori
PREDICTED CLASS
Class=Yes
ACTUAL
CLASS
Class=No
Class=Yes
a
(TP)
b
(FN)
Class=No
c
(FP)
d
(TN)
 Metrica più usata:
ad
TP  TN
Accuracy 

a  b  c  d TP  TN  FP  FN
Error Rate = 1 - Accuracy
Data Mining - S. Orlando
58
Problemi con lo sbilanciamento delle classi
 Se il problema non è bilanciato
P(Class=Y) molto diverso da P(Class=N)
Accuracy non è una misura adeguata o obiettiva
 Esempio:
– solo l’1% delle transazioni di carte di credito sono fraudolente
– il 99% sono quindi lecite !
– un modello che classifica tutte le transazioni come legittime, ha
un’accuratezza dello 0.99 !!!
– ma il modello è cattivo  ha un rate di FP dell’1%, ma questo 1%
include TUTTE le transazioni fraudolente a cui siamo interessati
Data Mining - S. Orlando
59
Altre misure
 Misure che considerano le classi rare più interessanti
 Nella classificazione binaria, di solito la classe rara = positiva
 True positive rate (TPR) o sensibilità
– TPR = TP / (TP + FN)
– frazione di veri positivi individuati, rispetto a tutti i positivi
 True negative rate (TNR) o specificità
– TPR = TN / (TN + FP)
– frazione di veri negativi individuati, rispetto a tutti i negativi
 Recall e Precision
– misure tipiche dell’Information Retrieval
– usate quando è signicativo individuare correttamente una delle due
classi
Recall:
Precision:
r = TP / (TP + FN)
p = TP / (TP + FP)
Data Mining - S. Orlando
60
Metodi di valutazione

Holdout
– Usa 2/3 del dataset classificato per il training, e 1/3 per il testing
– Problemi dovuti alla riduzione degli esempi per il training, e al fatto che training
e test sono sottoinsiemi dello stesso dataset

Random subsampling
– Holdout ripetuto
– acci : accuratezza del modello all’iterazione i-esima

– accsub = i=1,k acci/k
Cross validation
– Partiziona il dataset in k sottoinsiemi disgiunti
– Stesso record usato lo stesso numero di volte per il training, e una sola volta
per il testing
– k-fold: allena su k-1 partizioni, e testa sulla partizione rimanente
– Leave-one-out: Cross-validation con k=N

Bootstrap
– Training: Sampling con rimpiazzamento
– Lo stesso record può apparire più volte nel training dataset
– Dati N record, un training costituito da N record contiene circa il 63.2% dei
record originali
– Test set = record non selezionati
– Ripetuto b volte
Data Mining - S. Orlando
61
Prediction (vs. Classification)
 I metodi predittivi sono simili a quelli per la classificazione
– Prima costruisci il modello
– Poi usa il modello per predire i valori sconosciuti
• Il metodo di predizione più importante è la regressione
– Regressione Lineare e Multipla
– Regressione non-lineare
 La predizione è differente dalla classificazione
– La classificazione predice etichette di classe categoriche
– I metodi predittivi si occupano di predire valori continui non conosciuti
Data Mining - S. Orlando
62
Metodi predittivi
 Regressione lineare: Y =  +  X
– Modelliamo una variabile Y (variabile che vogliamo predire) come una
funzione lineare di un’altra variabile X (che di solito è nota, e sulla quale
basiamo la predizione di Y)
– I coefficienti del modello (, ) determinati sulla base dei dati conosciuti
(di training del modello)
• Metodi dei minimi quadrati applicati ai valori conosciuti del training dataset Y1,
Y2, …, X1, X2, ….
Y = 21.7 + 3.7 X
Data Mining - S. Orlando
63
Metodi predittivi
 Regressione lineare multipla: Y = b0 + b1 X1 + b2 X2 ….
– Abbiamo variabili multiple di predizione X1, X2, ecc. su cui basare il
valore di Y
– Ancora minimi quadrati
 Regressione non lineare
– I dati non mostrano l’esistenza di una dipendenza lineare
– La variabile di predizione X ha una relazione con la variabile da predire
Y modellabile con una funzione polinomiale
Y =  + 1 X + 2 X2 + 3 X3
– Possiamo introdurre nuove variabili (X1 = X, X2 = X2, X3 = X3) per
trasformare l’equazione polinomiale in una lineare, su cui applicare il
metodo dei minimi quadrati
Data Mining - S. Orlando
64
Reti neurali
Neurone artificiale
- k
x0
w0
x1
w1
xn

f
output y
wn
Input
weight
vector x vector w
weighted
sum
Activation
function
 Il vettore x di input a n-dimensioni è mappato in una variabile y
attraverso un prodotto scalare e una funzione nonlineare
Data Mining - S. Orlando
65
Rete neurale multilivello
Output vector
Output nodes
Hidden nodes
wij
Input nodes
Input vector: xi
Data Mining - S. Orlando
66
Allenamento della rete
 L’obiettivo dell’allenamento
– Ottenere un insieme di pesi/bias che permette di classificare
correttamente la quasi totalità dei dati di training
 Passi del metodo di backpropagation
– Inizializza i pesi con valori random
– Poni sugli input le ennuple di allenamento una alla volta
– Per ogni ennupla in input
• Calcola i valori di output
• Calcola l’errore
• Aggiorna i pesi e il bias
Data Mining - S. Orlando
67
Reti neurali
 Vantaggi dei classificatori neurali
– Accuratezza nella predizione
– Robustezza, funziona anche con esempi di training che contengono
errori
– Valutazione veloce
 Critiche
– Tempo di training lungo
– Difficile da interpretare la funzione di classificazione modellata dalla
fase di training, ed applicata nella classificazione
• interpretazione dei pesi degli archi della rete
Data Mining - S. Orlando
68
Conclusioni
 La Classificazione è stato un problema studiatissimo (soprattutto
in statistica, machine learning & neural networks)
 La Classificazione è probabilmente una delle tecniche di data
mining più usate, e rispetto alle quali sono state introdotte
moltissime estensioni
 Direzioni di ricerca: classificazione di dati non-relazionali, es.: testi,
dati spaziali, multimedia, etc..
Data Mining - S. Orlando
69
Classificatori basati su regole associative
 Dati su cui costruire il classificatore
– Insieme di record in D classificati, ovvero contenenti un attributo
categorico yY, che determina la classe di appartenenza
 Trasformiamo il dataset per poter applicare un algoritmo Apriori-like
– Ogni record deve diventare una transazione che contiene un insieme di
item  I
– Gli attributi categorici vengono mappati su insiemi di interi consecutivi
– Gli attributi continui sono discretizzati e trasformati come quelli
categorici
– Ogni record diventa una ennupla di item distinti appartenenti a I, dove
ogni item è una coppia (Attribute, Integer-value)
 Le regole estratte (CAR=Class Association Rule) con
supporto/confidenza minimi hanno quindi forma
– condset  y
– Dove condset è un insieme di item (Attribute, Integer-value)
Data Mining - S. Orlando
70
Classificatori basati su regole associative
 Una CAR ha confidenza c
– se il c% dei campioni in D che contengono condset contengono
anche y (ovvero appartengono alla classe y)
 Una CAR ha supporto s
– se l’ s% dei campioni in D contengono sia condset e sia y (ovvero
contengono condset ed appartengono anche alla classe y )
Data Mining - S. Orlando
71
Classificatori basati su CAR in dettaglio
 1° passo (generazione delle CAR)
– Algoritmo iterativo (come Apriori) che ricerca k-ruleitems frequenti
(CAR frequenti il cui condset contiene K item)
– Scansione multipla del database
– Cerca ad ogni iterazione k = 1, 2, 3, … i k-ruleitems frequenti
– La conoscenza dei k-ruleitems frequenti viene usata per generare i
(k+1)-ruleitems candidati
Data Mining - S. Orlando
72
Classificatori basati su CAR in dettaglio
 2 ° passo (generazione del Classificatore)
– Ricerca delle CAR più accurate
– Metodo euristico, basato su un ordinamento tra CAR
– Una regola ri precede una regola rj (ri < rj) se
• La confidenza di ri è più grande di rj
• La confidenza è la stessa, ma ri ha un supporto più grande
• La confidenza e il supporto delle due regole sono uguali, ma ri è
stata generata prima di rj
– Al termine l’algoritmo seleziona un insieme di CAR ordinate che
coprono tutti i campioni in D
 Uso del classificatore
– Nel classificare un nuovo campione, si usa l’ordine tra le CAR
• Si sceglie la prima regola il cui condset soddisfa il campione.
– E’ necessaria una regola di default, a precedenza minima, che specifica
una classe di default
• Serve per classificare nel caso in cui nessuna regola soddisfa il nuovo
campione da classificare
 Buoni risultati sia in velocità e sia in accuratezza rispetto a C4.5
Data Mining - S. Orlando
73