Algoritmi di classificazione e reti neuraliSeminario su clustering dei dati – Parte I

Università di Roma“La Sapienza”

Dipartimento di Informatica e Sistemistica

Corso di Laurea in “Ingegneria Gestionale”

A.A. 2011-2012

a cura di Silvia Canale

contatto e-mail: canale@dis.uniroma1.it

2

Definizione del problema di clustering di dati

Apprendimento automatico e data mining

Schema generale di una procedura di clustering

Applicazioni del clustering di dati

Definizioni preliminari e rappresentazione dei dati

Misure di similarità e di dissimilarità – distanze

Problema della partizione in clique

definizione e formulazione

algoritmo dei piani di taglio

ARGOMENTI DEL SEMINARIO

3

DEFINIZIONE DEL PROBLEMA

CLUSTERING: classificazione di oggetti sulla base delle similarità percepite

Gli oggetti sono descritti:

- dagli attributi che lo definiscono (misure oggettive o soggettive)

- dalle relazioni con gli altri oggetti

Lo scopo è quello di determinare un’organizzazione degli oggetti che sia:

- valida

- facile da determinare

Un cluster è un gruppo di oggetti simili (criterio di omogeneità). Oggetti che appartengono a cluster diversi non sono simili (criterio di separazione).

4

DEFINIZIONE DEL PROBLEMA

Un cluster è un gruppo di oggetti simili.

SeSe gli oggetti sono puntipunti in uno spazio di distanza spazio di distanza alloraallora possiamo dare la seguente definizione:

Un cluster è un sottoinsieme di punti tali che la distanza tra due punti qualsiasi del cluster è minore della distanza tra un qualsiasi punto del cluster ed un punto esterno al cluster.

Sia X uno spazio di oggetti e d una distanza definita su X.

Indicheremo con (X,d) lo spazio di distanza definito da d su X.

Un sottoinsieme V X è un cluster se e solo se

d(i,j) d(k,l) per ogni i,j,k V, l V

1

11

4

4

5

5

APPRENDIMENTO AUTOMATICO

Apprendimento: Processo di ragionamento induttivoragionamento induttivo che permette di passare dalle osservazioni alle regole generali (tipico dell’uomo che impara dall’esperienza)

Automatico: Definizione automatica, distinta da quella naturale, delle regole generali a partire dalle osservazioni (dati sperimentali)

Scopo: Estrazione di informazione interessante dai dati nuova (non è qualcosa di già noto, analisi esplorativa) oppure

attesa (ipotesi a priori da convalidare, analisi confermativa) implicita: presente nei dati analizzati ma non immediatamente

accessibile potenzialmente utile: può essere utilizzata per prendere delle

decisioni

REGOLE

OSSERVAZIONI

Processo deduttivo

Processo induttivo

INFORMAZIONE

6

APPRENDIMENTO AUTOMATICO

Processo automatico di estrazione di informazioni su un sistema fisico S incognito partendo da un insieme finito di n osservazioni.

L’insieme { v1, v2, …, vn } prende il nome di training set.

Apprendimento non supervisionatonon supervisionato (clustering): Il sistema S non ha ingressi e lo scopo è determinare una regola che metta in relazione le osservazioni del training set sulla base di una misura di similarità definita.

Apprendimento supervisionatosupervisionato (analisi discriminante): Il sistema S riceve gli ingressi { c1, c2, …, cn

} e lo scopo è determinare una regola che metta in relazione le osservazioni del training set con gli ingressi.

S

v1

v2

v3

vn

c1

c2

c3

cn

7

ESTRAZIONE DELLA CONOSCENZA

Pulizia ed integrazione

dei dati

Data Mining

Valutazioneregole

Database

Selezione e trasformazione

dei dati

Informazione

Datawarehouse

Regole

APPRENDIMENTO AUTOMATICO

8

APPLICAZIONI

Segmentazione di immagini – partizione di un’immagine in regioni che siano omogenee rispetto ad una proprietà di interesse (es. intensità, colore, struttura, …)

Riconoscimento di oggetti e caratteri – Analisi di immagini allo scopo di riconoscere particolari strutture

Information retrieval – Processo di raccolta e recupero automatico di informazioni (es. libri e riviste di una biblioteca)

Segmentazione di grandi database in gruppi omogenei di dati

Classificazioni di documenti web

Analisi predittiva in Customer Relationship Management- Customer profiling- Customer retention- Market segmentation- … ….E MOLTE ALTRE

9

CLUSTERING – SCHEMA GENERALE

1. Rappresentazione dei dati

• Definizione del numero, del tipo e della scala delle caratteristiche (o attributi)

• Definizione del numero di cluster (o classi)

• Selezione delle caratteristiche (opzionale)

• Estrazione delle caratteristiche (opzionale)

2. Definizione di una misura di similarità sull’insieme dei dati

3. Applicazione di un algoritmo di clustering

4. Astrazione sui dati

5. Valutazione dei risultati

studio dell’andamento dei cluster

analisi della validità dei cluster confronto esterno confronto interno controllo relativo

DESCRIZIONE COMPATTA DESCRIZIONE COMPATTA E SINTETICA DEI CLUSTERE SINTETICA DEI CLUSTER

10

DEFINIZIONI PRELIMINARI

Un algoritmo di clustering partizionale raggruppa le osservazioni del training set in cluster sulla base di una misura di similarità definita sull’insieme delle coppie di osservazioni.

Due tipi di algoritmi di clustering partizionale:

- clustering di tipo “hard”: un’osservazione è assegnata ad un solo cluster;

- clustering di tipo “fuzzy”: un’osservazione ha un grado di appartenenza per ciascuno dei cluster individuati.

Le osservazioni possono essere rappresentate in due formati standard:

matrice delle istanze di dato

matrice delle similarità

11

MATRICE DELLE ISTANZE

Un’osservazione (o istanza) v è rappresentata da un vettore di m caratteristiche (o attributi).

v1

v2

v = ……vm

L’insieme X = { v1, v2, …, vn } delle osservazioni viene

rappresentato come una matrice n x m detta matrice delle istanze.

X =

nm

n2

n1

2m

22

21

1m

12

11

v .... v v

.... .... .... ....

v .... v v

v .... v v

12

TIPI DI DATO

Un’istanza può rappresentare un oggetto fisico oppure un concetto astratto.

Un attributo può essere di diversi tipi:

quantitativo

• continuo (es. peso, larghezza, temperatura)

• discreto (es. età di un individuo)

• intervallo (es. durata di un evento)

qualitativo

• nominale (es. colori)

• ordinato (es. intensità di un suono, valutazione di una sensazione)

Sono inoltre possibili altre rappresentazioni delle istanze.

13

MATRICE DELLE RELAZIONI

Sia X = { v1, v2, …, vn } un insieme di n istanze.

Indichiamo con V = { 1, 2, …, n } l’insieme degli indici da 1 a n.

Una relazione r definita sullo spazio X x X delle coppie di istanze può essere rappresentata come una matrice n x n detta matrice delle relazioni.

R =

Consideriamo relazioni simmetriche ( per ogni i, j V ) e in particolare: relazioni di similarità (più vi e vj sono simili, più è grande) relazioni di dissimilarità (più vi e vj sono simili, più è basso)

nnn2n1

2n2221

1n1211

r .... r r

.... .... .... ....

r .... r r

r .... r r

jiij r r

ijr

ijr

14

DISTANZE

i)d(j,j)d(i,

0i)d(i,

Una distanzadistanza d definita sull’insieme X è una relazione che gode delle seguenti proprietà:

a) d è simmetrica per ogni coppia (i,j) in V.

b) d assume valore nullo per ogni coppia (i,i) in V.

Indicheremo con (X,d) lo spazio di distanza definito da d su X.

Se inoltre d soddista la proprietà:

c) d soddisfa la diseguaglianza triangolare per ogni terna (i,j,k) in V

allora d è una semimetricasemimetrica sull’insieme X.

Si definisce metricametrica una semimetrica d che soddisfa l’ulteriore proprietà:

j)d(k,k)d(i,j)d(i,

ji 0j)d(i,

v1

13

4

v2

v3v1

12

4

v2

v3

15

NORME

Se X è uno spazio vettoriale definito sul campo dei reali , una

funzione || • || : X + si definisce norma se:

i. || v || = 0 v = 0 per ogni v in X.

ii. || v || = | | || v || per ogni in , v in X.

iii. || vi + vj || || vi || + || vj || per ogni vi ,vj in X.

Si definisce spazio normato la coppia (X, || • ||).

Ad uno spazio normato (X, || • ||) può essere associata la topologia metrica indotta dalla norma || • || tramite l’identità:

Consideriamo lo spazio normato (m, || • ||p) dove || • ||p è la norma lp

jiji v-v )v,(vd METRICA METRICA NORMANORMA

p1m

1k

pkp

)|v|(v

16

UNA METRICA NORMA È UNA METRICA

Dim. Sia || • || : X + una norma definita su X. La funzione

a) è simmetrica

b) d assume valore nullo per ogni coppia (i,i) in V.

c) d soddisfa la diseguaglianza triangolare per ogni terna (i,j,k) in V

jiji v-v )v,(vd

)v,(vdv-vv-v v--1(vv-v )v,(vd ijijijijjiji |1|)

|| v || = | | || v ||

00 iiii v-v )v,(vd

|| v || = 0 v = 0

)v,(vd)v,(vdvvv(v

vvv(vvvv-vv-v )v,(vd

kjkijkki

jkkikkjijiji

)()

)()|| vi + vj || || vi || + || vj ||

17

METRICHE NORME

Una classe molto importante di metriche è quella delle metriche dlp

indotte dalle diverse norme lp:

p = 1 – distanza di Manhattan o metrica “city-block”

p = 2 – distanza Euclidea

p = – distanza di Lagrange

p = 0 – distanza di Hamming

p1

pm

1k

jk

ikp

jiji )|v-v|(v-v )v,(vdp

|v-v| )v,(vdm

1k

jk

ik

ji

1

2m

1k

jk

ik

ji |v-v| )v,(vd2

|| jk

ik

m1,...,k

jiji v-vmaxv-v )v,(vd

0}| |v-v| :m1,...,k |{v-v )v,(vd jk

ik0

jiji

0

18

PROBLEMA DI PARTIZIONE

Un algoritmo di clustering partizionale di tipo “hard” determina una partizione delle osservazioni del training set sulla base di una misura di similarità definita sull’insieme delle coppie di osservazioni.

Si definisce partizione P di un insieme X = { v1, v2, …, vn } è una

famiglia finita di k insiemi V1, V2, …, Vk

P = { V1, V2, …, Vk }

tali che

ogni insieme Vj in P è un sottoinsieme non vuoto di X: Vj X

XVk

1jj

jik 1,..., ji, 0VV ji

19

RAPPRESENTAZIONE DEI DATI

Dato un insieme di osservazioni X = { v1, v2, …, vn } e la matrice

delle similarità relative all’insieme X, si definisce grafo associato a

X il grafo G(N,A) tale che:

N rappresenta l’insieme dei nodi { 1, 2, …, n } tale che ciascun

nodo i N sia associato ad un’osservazione vi X

A sia l’insieme degli archi che connettono ogni coppia non

ordinata (vi, vj) di osservazioni in X con vi vj.

L’arco in A che connette due nodi i e j viene indicato con (i,j) o con

ij.

Siano n e m il numero di nodi e di archi, rispettivamente, in N e A.

Il grafo associato a X è completo! 21)n(n

m

20

INSIEME DELLE SOLUZIONI – DEFINIZIONI

Si definisce clustering del grafo G(N,A) una partizione

P(G) = { V1, V2, …, Vk }

dei nodi del grafo G(N,A).

Gli elementi ViP(G) vengono definiti componenti o cliqueclique del

clustering P(G).

Dato un grafo G(N,A) si definisce cliqueclique un sottoinsieme V N dei nodi tali che per ogni coppia di nodi i e j l’arco ij appartiene ad A.

A)G(N,

1

23

4

5

6

Se il grafo G(N,A) è completo, ogni sottoinsieme V N è una cliqueclique.

}4,3,2,1{1V

}6,5,4,3{2V

}5,4,2,1{3VNON è una clique:

25 A

21

INSIEME DELLE SOLUZIONI – DEFINIZIONI

Si definisce clustering del grafo G(N,A) una partizione

P(G) = { V1, V2, …, Vk }

dei nodi del grafo G(N,A).

Come sono fatte le soluzioni di un problema di clustering?

Sia Vh N. Indichiamo con (Vh)

l’insieme degli archi che connettono

nodi in Vh e nodi fuori da Vh

Se |Vh| = 1, (Vh) è la stella del nodo in Vh.

hhh Vj,VA|iij)δ(V Vδ(V)

i

j

22

INSIEME DELLE SOLUZIONI – DEFINIZIONI

Siano Vh, Vl N. Indichiamo con

(Vh ,Vl) l’insieme degli archi che

connettono nodi in Vh e nodi in Vl

In generale, dati k sottoinsiemi

V1,…, Vk N, l’insieme

degli archi con estremi in due

sottoinsiemi diversi viene

indicato con

lhlh Vj,VA|iij)V,δ(V

lh k,1,...,lh,Vj,VA|iij)V,....,δ(V lhk1 ,

1V

2V3V

)V,δ(V 31

1V

2V3V

)V,V,δ(V 321

23

INSIEME DELLE SOLUZIONI – DEFINIZIONI

Ad ogni clustering P(G)= { V1, V2, …, Vk } del grafo G(N,A) è

possibile associare un insieme multi-cutmulti-cut (P(G))

(P(G)) = ( V1, V2, …, Vk )

Definiamo il vettore di incidenza yP

di un insieme multi-cutmulti-cut (P(G)) 1V

2V3V

)V,V,V,δ(V 4321

4V

otherwise 0

δ(P(G))ij 1y 0,1y ij

mP

24

INSIEME DELLE SOLUZIONI – DEFINIZIONI

1V)E(V1u

v

Sia Vi N. Indichiamo con E(Vi) l’insieme degli archi che

connettono

nodi in Vi.

Se |Vi| = 1, E(Vi) è vuoto.

In generale, dati k sottoinsiemi

V1,…, Vk N, l’insieme degli

archi con estremi nello stesso

sottoinsieme viene indicato con

iii Vv,VA|uuv)E(V

)E(V ... )E(V)V,....,E(V k1k1 1V

2V3V

)V,V,E(V 321

25

INSIEME DELLE SOLUZIONI – DEFINIZIONI

Ad ogni clustering P(G)= { V1, V2, …, Vk } del grafo G(N,A) è

possibile associare un insieme partizionepartizione E(P(G))

E(P(G)) = E( V1, V2, …, Vk )

Definiamo il vettore di incidenza xP

di un insieme partizione E(P(G))partizione E(P(G)) 1V

2V3V

)V,V,V,E(V 4321

4V

otherwise 0

E(P(G))ij 1 x0,1x ij

mP

mPP 1yx Gli insiemi multi-cutmulti-cut e partizionepartizione definiscono una partizione di A

26

VETTORE DI INCIDENZA DI UNA PARTIZIONE

1V

2V

3V

)E(V3

)E(V1

)E(V2

1

8

76

5

43

2

1

1

1

0

0

0

0

0

0

1

0

0

0

1

1

0

0

0

0

0

0

0

0

0

0

0

0

1

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

78

68

67

58

57

56

48

47

46

45

38

37

36

35

34

28

27

26

25

24

23

18

17

16

15

14

13

12

321 V,V,VP(G)

Esempio –– Sia X = { v1, v2, v3, v4, v5, v6, v7, v8 }.

Definiamo il grafo G(N,A) associato all’insieme X, dove

N = { 1, 2, 3, 4, 5, 6, 7, 8 } e A = { ij | 1 i j 8 }.

Consideriamo il clustering

P(G)= { V1, V2, V3 }

Px

27

INSIEME DELLE SOLUZIONI

Supponiamo di voler determinare una partizione in k cluster.

Sia s = . Se vogliamo che i cluster contengano un numero numero

ugualeuguale di osservazioni, il problema è equivalente al problema di

determinare una partizione in cluster che abbiano ciascuno un

numero di osservazioni non inferiori a s.

kn

k

ji

δ(i)1sxx ikij

2

L’insieme S delle soluzioni del problema di clustering di X è

l’insieme dei vettori di incidenza di tutte le possibili insiemi

partizione E(P(G)) del grafo G(N,A) associato a X.

E(P(G)) di incidenza di vettore x :{0,1}xS Pm

P

δ(i)ij

ijx 1 s Ni

Vincolo di

dimensione

s =3

28

PROBLEMA DI PARTIZIONE IN CLIQUE

In base al valore di s possiamo avere diversi problemi:

}

{

Ni 1sx

,P(G) di incidenza di vettore x :{0,1}xS

δ(i)ijij

Pm

P

se s 1, S è l’insieme delle soluzioni del problema di partizione partizione

in in cliqueclique (CPP) dei nodi di un grafo

Consideriamo l’insieme delle soluzioni

se s 1, S è l’insieme delle soluzioni del problema di partizione partizione

in in clique con vincolo di dimensioneclique con vincolo di dimensione (CPPMIN)

se k = 2, S è l’insieme delle soluzioni del problema di

equipartizioneequipartizione se n è multiplo di s, S è l’insieme delle soluzioni del problema di

equipartizione in k sottoinsiemiequipartizione in k sottoinsiemi Ni 1sx 1sxδ(i)ij

ijδ(i)ij

ij

29

CRITERIO DI OTTIMALITÀ

Esempio –– Sia X = { v1, v2, v3, v4, v5, v6, v7, v8 } e s = 2

Definiamo il grafo G(N,A) associato all’insieme X, dove

N = { 1, 2, 3, 4, 5, 6, 7, 8 } con n = 8, e A = { ij | 1 i j 8 }.

Consideriamo i due clustering P1(G)= { V1, V2, V3 } e P2(G)= { V4, V5,

V6 }

Come valutare le soluzioni in S? Qual è la migliore soluzione?

1V

2V

3V1

8

76

5

43

24V

5V

6V

1

8

76

5

43

2

In P1(G) i punti appartenenti allo stesso cluster sono più vicini…

30

CRITERIO DI OTTIMALITÀ

1V

2V

3V1

8

76

5

43

24V

5V

6V

1

8

76

5

43

2

In P1(G) i punti appartenenti allo stesso cluster sono più vicini…

La matrice delle relazioni contiene le informazioni relative alla similarità o alla dissimilarità tra i punti

Sia D la matrice n x n delle relazioni di dissimilarità (più i e j sono simili, più è basso)ijd

1

1 1

5.1

1

11

1

1 1

32 3

1

3

Assegniamo ad ogni arco ij di A il peso ijd

31

CRITERIO DI OTTIMALITÀ

1V

2V

3V1

8

6

5

43

24V5V

6V

1

8

6

5

43

2

Assegniamo ad ogni cluster V N la somma dei pesi degli archi in E(V)

1

1 1

5.1

1

11

1

1 1

32 3

1

3

Assegniamo ad ogni arco ij di A il peso ijd

E(V)ij

ijdc(V)

7 73)c(V2

3)c(V3

5.1)c(V1

11)c(V5

1)c(V6

3)c(V4

Assegniamo ad ogni partizione P(G)= { V1, V2, …, Vk } del grafo G(N,A) la somma dei costi degli elementi della partizione

P(G)V

i

i

)c(Vc(P(G))

c(P1(G)) = 1.5 + 3 + 3 =

7.5

c(P2(G)) = 15<

P1(G) è migliore di P2(G)

32

CRITERIO DI OTTIMALITÀ

Ad ogni partizione P(G)= { V1, V2, …, Vk } del grafo G(N,A) associamo il costo

P(G)V

i

i

)c(Vc(P(G))

Ad ogni P(G)= { V1, V2, …, Vk } è associato il vettore di incidenzavettore di incidenza

xP di un insieme partizione E(P(G))partizione E(P(G))

k

ji

E(V)

otherwise 0

E(P(G))ij 1 x0,1x ij

mP

k1,..., h

),E(Vij x hij

1

V

)V,...,E(VE(P(G)) k1

∑∑A∈ij

ijijE(P(G))∈ij

ij xddc(P(G)) ==

ijx

jkxikx

33

CRITERIO DI OTTIMALITÀ

Ad ogni partizione P(G)= { V1, V2, …, Vk } del grafo G(N,A) associamo il costo

Aij

ijijxdc(P(G))

1

1

1

0

0

0

0

0

0

1

0

0

0

1

1

0

0

0

0

0

0

0

0

0

0

0

0

1

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

78

68

67

58

57

56

48

47

46

45

38

37

36

35

34

28

27

26

25

24

23

18

17

16

15

14

13

12

Px

Esempio –– Sia X = { v1, v2, v3, v4, v5, v6, v7, v8 } e s = 2

Consideriamo la soluzione xP associata al

clustering P(G)= { V1, V2, V3 }

1V

2V

3V1

8

6

5

43

2

1

1 1

5.1

1

11

7 3)c(V2

3)c(V3

5.1)c(V1

Aij

ijijxdc(P(G))

5.7

786867

45353412

ddd

dddd

34

FORMULAZIONE MATEMATICA DEL CPP

S x

xd minAij

ijij

} { Ni 1sx,P(G) di incidenza di vettore x :{0,1}xSδ(i)ij

ijPm

P

Risolvere il problema di partizione in cliquepartizione in clique dei nodi di un grafo

significa determinare la soluzione del seguente problema

dove l’insieme delle soluzioni è

35

MATERIALE DEL SEMINARIO

Le slide di questo seminario sono reperibili al seguente link:

http://www.dis.uniroma1.it/~canale/didattica/ACRN1.ppt