Post on 02-May-2015
transcript
Sistemi Informativi Per Le Decisioni LS, Prof. Marco Patella
Presentazione di Alessandro Mariucci, Massimiliano Bertocchi, Michele Federici
Usiamo la struttura di IB per definire una misura
di distanza per le tuple categoriche
LIMBO può essere usato per clusterizzare sia le
tuple sia i valori di attributi categorici
Algoritmo di clustering categorico gerarchico e scalabile che costruisce un framework per quantificare le informazioni rilevanti conservate quando si effettua clustering
Director Actor Genret1 (Godfather II) M. Scorsese R. De Niro Crime
t2 (Good Fellas) F. F. Coppola R. De Niro Crime
t3 (Vertigo) A. Hitchcock J. Stewart Thriller
t4 (N by NW) A. Hitchcock C. Grant Thriller
t5 (The Bishop’s Wife) K. Koster C. Grant Comedy
t6 (Harvey) K. Koster J. Stewart Comedy
Director Actor Genret1 (Godfather II) M. Scorsese R. De Niro Crime
t2 (Good Fellas) F. F. Coppola R. De Niro Crime
t3 (Vertigo) A. Hitchcock J. Stewart Thriller
t4 (N by NW) A. Hitchcock C. Grant Thriller
t5 (The Bishop’s Wife) K. Koster C. Grant Comedy
t6 (Harvey) K. Koster J. Stewart Comedy
C1
C2
D1
D2
Siano T e A due variabile discrete random che possono variare rispettivamente all’interno dell’insieme T e A
( ; ) ( ) ( | ) ( ) ( | )I T A H T H T A H A H A T
È l’entropia di una varabile privata della conoscenza che l’altra variabile
fornisce sulla prima.
Misura la quantità di informazione che le due variabili forniscono l’una per l’altra
Dalla teoria dell’informazione:
Sia Sia AA = = A1 A1 …… AmAm il set di tutti i possibili valori degli attributi il set di tutti i possibili valori degli attributi SiaSia d = k1+…+km la dimensione di d = k1+…+km la dimensione di AA..
Director Actor Genre
t1 (Godfather II) M. Scorsese R. De Niro Crime
t2 (Good Fellas) F. F. Coppola R. De Niro Crime
t3 (Vertigo) A. Hitchcock J. Stewart Thriller
t4 (N by NW) A. Hitchcock C. Grant Thriller
t5 (The Bishop’s Wife) K. Koster C. Grant Comedy
t6 (Harvey) K. Koster J. Stewart Comedy
A1 = {d.S, d.C, d.H, d.K}
A2 = {a.S, a.DN, a.S, a.G}
A3 = {g.Cr, g.T, g.C}
A = {d.S, d.C, d.H, d.K, a.S, a.DN, a.S, a.G, g.Cr, g.T, g.C}
d = 11
La rappresentazione di La rappresentazione di TT sarà una matrice M n sarà una matrice M n×d, e ×d, e
l’elemento M[i][j] sarà 1 se la tupla i contiene il valore j, 0 l’elemento M[i][j] sarà 1 se la tupla i contiene il valore j, 0
altrimenti. Per quanto detto prima, ogni vettore che altrimenti. Per quanto detto prima, ogni vettore che
rappresenta una tupla avrà esattamente m valori 1.rappresenta una tupla avrà esattamente m valori 1.
d.S d.C d.H d.K a.DN a.S a.G g.Cr g.T g.C
t1 1 0 0 0 1 0 0 1 0 0
t2 0 1 0 0 1 0 0 1 0 0
t3 0 0 1 0 0 1 0 0 1 0
t4 0 0 1 0 0 0 1 0 1 0
t5 0 0 0 1 0 0 1 0 0 1
t6 0 0 0 1 0 1 0 0 0 1
3
Si procede alla normalizzazione della matrice MSi procede alla normalizzazione della matrice M
d.S d.C d.H d.K a.DN a.S a.G g.Cr g.T g.C p(t)
t1 1/3 0 0 0 1/3 0 0 1/3 0 0 1/6
t2 0 1/3 0 0 1/3 0 0 1/3 0 0 1/6
t3 0 0 1/3 0 0 1/3 0 0 1/3 0 1/6
t4 0 0 1/3 0 0 0 1/3 0 1/3 0 1/6
t5 0 0 0 1/3 0 0 1/3 0 0 1/3 1/6
t6 0 0 0 1/3 0 1/3 0 0 0 1/3 1/6
p(a|t) = 1/m
probabilità condizionata degli attributi nota la
tupla
p(A|t)
distribuzione di probabilità condizionata dei valori
dell’attributo data la tupla t
p(t) = 1/n
probabilità della tupla t
| |( ) ( )
t c
cp c p t
n
1
( | ) ( ) ( | )( ) t c
p a c p t p a tp c
Il criterio utilizzato da LIMBO per definire la bontà della fusione tra due
cluster c1 e c2 è quello della information loss
I(ci , cj) = I(A ; C) – I(A ; C’)
dove C e C’ indica il clustering prima e dopo la fusione di c1 e c2 Information loss è indipendente dal clustering: dipende solo da ci e cj Si dimostra che la distanza d(ci , cj) è data dalla seguente formula:
Divergenza di Jensen-Shannon.
Indica il degrado che si ottiene assumendo come distribuzione valida la seconda quando invece la prima è giusta e viceversa
( , ) [ ( ) ( )]* [ ( | ), ( | )]i j i j JS i jI c c p c p c D p A c p A c
DCF relativo al cluster c DCF(c) = ( p(c), p(A|c) )
DCF relativo alla tupla t DCF(t) = ( p(t), p(A|t) )
Per cluster più grandi, il DCF è calcolato ricorsivamente utilizzando il meccanismo della fusione:
• sia c* il cluster che otteniamo fondendo due cluster c i e cj
( *) ( ) ( )
( )( )( | *) * ( | ) * ( | )
( *) ( *)
i j
jii j
p c p c p c
p cp cp A c p A c p A c
p c p c
LIMBO non utilizza l’intero dataset per calcolare i clusters ma alcune statistiche
rilevanti sulle tuple
Per fare questo summary del dataset si usa una struttura particolare,
Distributional Cluster Features (DCF)
L’algoritmo LIMBO consta di tre fasi:
Costruzione DCF tree
Clusterizzazione
Assegnazione tuple ai cluster
DCF1 DCF2 DCF3 --- DCF6
child1 child2 child3 --- child6
prev DCF1 DCF2 --- DCF6 next
DCF1 DCF2 --- DCF5
child1 child2 --- child5
Root Node
prev DCF1 DCF2 --- DCF4 next
Non leaf node
Leaf node Leaf node
Ogni nodo foglia mantiene un clustering delle tupleOgni nodo intermedio mantiene un DCF che è dato dalla fuzione di DCFs
dei suoi figliIl LIMBO costruisce alberi space bounded dove l’upper bound è definito
dal parametro SIl parametro B descrive il branching factor
Le tuple del dataset vengono processate una per volta. La tupla t viene convertita in DCF(t ). Si parte dalla radice fino ad un nodo foglia:
Quando ci si trova in un nodo intermedio si trova il DCF(c) più vicino a DCF(t) e si segue il cammino verso il suo figlio.
Quando ci si trova in un nodo foglia, si trova il DCF(c) più vicino a DCF(t). A questo punto si decide se fondere t nel cluster c in base alla distanza d(c,t), che misura l’information loss dovuta alla fusione.
Se è minore del valore di soglia allora si procede alla fusione. Altrimenti, t formerà un cluster a parte. In questo caso ci si trova
davanti a due possibilità: Se c’è ancora spazio nel nodo, allora viene inserito DCF(t ). Altrimenti, si “splitta” il nodo scegliendo come semi per i due nodi i
due DCF che hanno distanza massima nel nodo. In questo caso vengono aggiornati i DCF del nodo padre inserendo un nuovo DCF per descrivere il nuovo nodo inserito; anche per i nodi intermedi può avvenire lo split se la nuova informazione non può essere contenuta dal nodo.
O ( n h d B + d U B2 )
La complessità della fase 1 è:
fase inserimento
fase split
n = n° totale tuple
h = altezza dell’albero
B = branching factor
U = n° nodi non-foglia
d = n° totale di valori di attributo
DCFc4DCFc1 DCFc3DCFc2
DCFc1 DCFc2
DCFc10 DCFc11 DCFc12DCFc7 DCFc8 DCFc9DCFc4 DCFc5 DCFc6
DCFc3
DCFc5 DCFc6
DCFt2 DCFc2 DCFc3DCFc1
c1 c2 c3 c4
• Applica un algoritmo di clustering qualsiasi per
produrre k cluster• Calcola i k DCF(c)
O ( L2 d2 logL )
La complessità della fase 2 è
(in caso si utilizzi l’algoritmo AIB):
L = numero totale delle entrate DCF delle foglie dell’albero
TUPLA t1
TUPLA tn
.
.
..
.
c1
c2
ck
D(t1, c1)
D(t1, c2)
D(t1, ck)
TUPLA t1
TUPLA tn
.
.
c1
c2
ck
D(t1, c2)
O ( k d n )
La complessità della fase 3 è:
k = numero totale dei cluster
d = numero totale dei valori dell’attributo
n = numero totale tuple
Versione accuracy-limited non spazio limitata
controlla la perdita di informazione
si usa una soglia sulla distanza d(c,t) per decidere se fondere o meno la tupla t con il cluster c
( ; )( ) *
I A T
n
A
d.S
d.H
d.K
d.C
a.DN
a.Sa.Gg.Cr
g.C
g.T
A’A’’
director a.DN a.S a.G g.Cr g.T g.C p(d)
Scorsese 1/2 0 0 1/2 0 0 1/6
Coppola 1/2 0 0 1/2 0 0 1/6
Hitchcock 0 1/3 1/3 0 2/3 0 2/6
Koster 0 1/3 1/3 0 0 2/3 2/6
Director Actor Genre
t1 (Godfather II) M. Scorsese R. De Niro Crime
t2 (Good Fellas) F. F. Coppola R. De Niro Crime
t3 (Vertigo) A. Hitchcock J. Stewart Thriller
t4 (N by NW) A. Hitchcock C. Grant Thriller
t5 (The Bishop’s Wife) K. Koster C. Grant Comedy
t6 (Harvey) K. Koster J. Stewart Comedy
p(a|v)
con aЄA’’ e vЄA’
( 1) ( 2)( | 1 2) ( | 1) ( | 2)
( 1 2) ( 1 2)
p v p vp a v v p a v p a v
p v v p v v
INFORMATION LOSS (IL):
è la % delle informazioni mutuali iniziali perse dopo aver prodotto un numero desiderato di cluster
CATEGORY UTILITY (CU):
( ; ) ( ; )IL I A T I A C
2 2| |[ ( | ) ( ) ]i ij i ij
c C i j
cCU P A v c P A v
n
è la differenza fra un numero previsto di valori di attributo che possono essere correttamente indovinati dati un cluster ed il numero di corrette previsioni senza tale conoscenza
MIN CLASSIFICATION ERROR (Emin):
Date T tuple classificate in k classi G={g1,…,gk} e sia C una possibile classificazione delle tuple T in k cluster {c1,..,ck}:
misura il numero di tuple appartenenti alla classe g_i che ricevono un’etichetta sbagliata, per i={1,…,k}.
1
| ( ) |k
i ii
E g f g
PRECISION (P) e RECALL (R):
| |
| |i i
ii
c gP
c
| |
| |i i
ii
c gR
g
1
| |ki
ii
gP P
T
1
| |
| |
ki
ii
gR R
T
Pi misura l’ACCURATEZZA con la quale ogni cluster ci riproduce la classe gi
Ri misura la COMPLETEZZA con la quale ogni cluster ci riproduce la classe gi
LIMBOS LIMBOØ
Fase 2: O ( L2 d2 logL )
LIMBOS LIMBOØ
Fase 1: O ( nhdB + dUB2 )
LIMBOS LIMBOØ
Fase 3: O ( kdn )
LIMBOØ LIMBOS
RISULTATI DEL CLUSTERING SU TUPLE:
RISULTATI DEL CLUSTERING SU ATTRIBUTI:
a causa del # ridotto di split e della ridotta dimensione dell’albero
N° valori di attributoN° di attributi
LIMBO applica il concetto di Mutua Informazione al clustering
Rispetto agli altri algoritmi di “Information Theoretic Clustering” ha vantaggi in termini di:
Scalabilità
Qualità di clustering
Stabilità dei parametri
E’ l’unico algoritmo scalabile categorico che è gerarchico
La qualità della clusterizzazione realizzata da LIMBO dipende fortemente da: Fase 3: assegnazione le tuple ai cluster rappresentativi
nasconde molta della perdita di informazione incorsa nelle fasi precedenti.
DCFc4DCFc1DCFc3DCFc2
DCFc1 DCFc2
DCFc10 DCFc11 DCFc12DCFc7 DCFc8 DCFc9DCFc4 DCFc5 DCFc6
DCFc3
DCFc5 DCFc6
DCFt2DCFc2 DCFc3DCFc1
c1 c2 c3 c4
L’algoritmo di clustering utilizzato nella Fase 2 deve scoprire i K rappresentanti ben separati
Il paper indica i valori di Φ compresi tra 1.0 e 1.5 come valori per cui si ha: un albero DCF con una dimensione accettabile un tempo di esecuzione basso nelle fasi 1 e 2
La qualità del Custering degrada
notevolmente
Problema intuitivo: sensibilità di LIMBO all’ordinamento dei dati in ingresso nella costruzione del DCF Tree
100 ESECUZIONI ALGORITMO Non particolarmente
sensibile all’ordinamento
delle tuple