Sistemi Informativi Per Le Decisioni LS, Prof. Marco Patella
Presentazione di Alessandro Mariucci, Massimiliano Bertocchi, Michele Federici
 Algoritmo di clustering categorico gerarchico e
scalabile che costruisce un framework per quantificare
le informazioni rilevanti conservate quando si effettua
clustering
 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
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
C1
C2
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
D1
D2
Dalla teoria dell’informazione:
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
 Sia A = A1 … Am il set di tutti i possibili valori degli attributi
 Sia d = k1+…+km la dimensione di A.
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
A3 = {g.Cr, g.T, g.C}
A2 = {a.S, a.DN, a.S, a.G}
A1 = {d.S, d.C, d.H, d.K}
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 T sarà una matrice M n×d, e
l’elemento M[i][j] sarà 1 se la tupla i contiene il valore j, 0
altrimenti. Per quanto detto prima, ogni vettore che
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 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
|c|
p (c)   p (t ) 
n
tc
p(A|t)
distribuzione di probabilità
condizionata dei valori
dell’attributo data la tupla t
p(t) = 1/n
probabilità della tupla t
1
p (a | c) 
p(t ) p(a | t )

p(c) t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:
 I (ci , c j )  [ p(ci )  p(c j )]* DJS [ p( A | ci ), p( A | c j )]
Divergenza di Jensen-Shannon.
Indica il degrado che si ottiene assumendo come distribuzione
valida la seconda quando invece la prima è giusta e viceversa
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)
DCF relativo alla tupla t
DCF(t) = ( p(t), p(A|t) )
DCF relativo al cluster c
DCF(c) = ( p(c), p(A|c) )
Per cluster più grandi, il DCF è calcolato ricorsivamente utilizzando il meccanismo
della fusione:
• sia c* il cluster che otteniamo fondendo due cluster ci e cj
p(c*)  p(ci )  p(c j )
p (c j )
p(ci )
p( A | c*) 
* p( A | ci ) 
* p( A | c j )
p(c*)
p(c*)
L’algoritmo LIMBO consta di tre fasi:
 Costruzione DCF tree
 Clusterizzazione
 Assegnazione tuple ai cluster
Ogni nodo foglia mantiene un clustering delle tuple
Ogni nodo intermedio mantiene un DCF che è dato dalla fuzione di DCFs
dei suoi figli
Il LIMBO costruisce alberi space bounded dove l’upper bound è definito
dal parametro S
Il parametro B descrive il branching factor
Root Node
DCF1 DCF2 DCF3
---
DCF6
child1 child2 child3
---
child6
Non leaf node
DCF1
DCF2
---
DCF5
child1 child2
---
child5
Leaf node
prev
DCF1
DCF2
---
Leaf node
DCF6
next
prev
DCF1
DCF2
---
DCF4
next
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.
La complessità della fase 1 è:
fase split
O ( n h d B + d U B2 )
fase inserimento
n = n° totale tuple
U = n° nodi non-foglia
h = altezza dell’albero
d = n° totale di valori di attributo
B = branching factor
DCFc1 DCFc2 DCFc3
DCFc4 DCF
• Applica
un algoritmo
c5 DCFc6di
clustering qualsiasi per
produrre k cluster
• Calcola i k DCF(c)
DCFc1 DCFc2 DCFc3
DCF
DCFc1
t2 DCFc2 DCFc3
c1
DCFc4 DCFc5
DCFc6
c2
DCFc7 DCFc8 DCFc9
c3
DCFc10 DCFc11 DCFc12
c4
La complessità della fase 2 è
(in caso si utilizzi l’algoritmo AIB):
O ( L2 d2 logL )
L = numero totale delle entrate DCF delle foglie dell’albero
c1
TUPLA t1
c2
.
.
.
.
.
TUPLA tn
ck
c1
TUPLA t1
c2
.
.
TUPLA tn
ck
La complessità della fase 3 è:
O(kdn)
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
A’
d.S
A’’
d.C
d.H
g.Cr
a.S
a.G
g.C
d.K
g.T
a.DN
Director
Actor
Genre
t1 (Godfather II)
M. Scorsese
R. De Niro
Crime
t2 (Good Fellas)
F. F. Coppola
R. De Niro
Crime
t3 (Vertigo)
J. Stewart
Thriller
p(v1) A. Hitchcock
p(v 2)
p(a | v1t4v 2)
NW)
(a | v1)  C. Grant p(Thriller
a | v2)
(N by
A. p
Hitchcock
pWife)
(v1v 2) K. Koster
pC.(vGrant
1v 2) Comedy
t5 (The Bishop’s
t6 (Harvey)
K. Koster
J. Stewart
Comedy
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
p(a|v)
Coppola
1/2
0
0
1/2
0
0
1/6
con aЄA’’ e vЄA’
Hitchcock
0
1/3
1/3
0
2/3
0
2/6
Koster
0
1/3
1/3
0
0
2/3
2/6
 INFORMATION LOSS (IL):
IL  I ( A; T )  I ( A; C )
è la % delle informazioni mutuali iniziali perse dopo aver prodotto un
numero desiderato di cluster
 CATEGORY UTILITY (CU):
|c|
CU    [ P( Ai  vij | c) 2  P( Ai  vij ) 2 ]
cC n i
j
è 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}:
k
E   | gi  f ( gi ) |
i 1
misura il numero di tuple appartenenti alla classe g_i che ricevono
un’etichetta sbagliata, per i={1,…,k}.
 PRECISION (P) e RECALL (R):
| ci  gi |
Pi 
| ci |
k
| gi |
P
Pi
i 1 T
Pi misura l’ACCURATEZZA con la quale ogni cluster ci riproduce la classe gi
| ci  g i |
Ri 
| gi |
k
| gi |
R
Ri
i 1 | T |
Ri misura la COMPLETEZZA con la quale ogni cluster ci riproduce la classe gi
LIMBOS
Fase 2: O ( L2 d2 logL )
LIMBOØ
LIMBOS
Fase 1: O ( nhdB + dUB2 )
LIMBOØ
LIMBOS
Fase 3: O ( kdn )
LIMBOØ
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°N°divalori
attributi
di attributo
 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.
L’algoritmo di clustering
utilizzato nella Fase 2 deve
scoprire i K rappresentanti
ben separati
DCFc1 DCFc2 DCFc3
DCFc1
DCF DCF
DCF
t2
c1
c2
DCFc3
c1
DCFc2
DCFc4
DCFc3
DCFc4 DCFc5 DCFc6
c2
DCFc5
DCFc6
DCFc7 DCFc8 DCFc9
c3
DCFc10 DCFc11 DCFc12
c4
Il paper indica i valori di Φ compresi tra 1.0 e 1.5 come
valori per cui si ha:
La qualità del
 un albero DCF conCustering
una dimensione accettabile
degrada
 un tempo di esecuzione
basso nelle fasi 1 e 2
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