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