Algoritmi di classificazione e reti neurali Seminario su clustering dei dati – Parte II...

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

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: [email protected]

2

Problema della partizione in clique

algoritmo dei piani di taglio

esempio algoritmo dei piani di taglio

algoritmo euristico

Clustering partizionale – Criteri di ottimalità

ARGOMENTI DEL SEMINARIO

3

FORMULAZIONE DI UN PROBLEMA DI PL01

Sia S l’insieme delle soluzioni di un problema di Programmazione Lineare 0–1

Esempio CPP – Dato un grafo G(N,A)

S è l’insieme di tutte le possibili partizioni in clique di G(V,A)

A)G(N,

1

23

4

5

6

56

46

45

36

35

34

26

25

24

23

16

15

14

13

12

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

211 V,V(G)P 1Px

1

1

1

0

0

0

0

0

0

1

0

0

0

1

1

432 V,V(G)P

653 V,V(G)P

S x

xd minAij

ijij

S x

xc min T

} { P(G)diincidenza di vettorex :{0,1}xS Pm

P

4


Indichiamo con x* la soluzione ottima del problema di PL01

xc minargx* T

S x

In un problema di PL01 S è un insieme finito

La soluzione ottima x* esiste sempre e può essere individuato con una enumerazione completa di S

L’enumerazione completa di tutte le soluzioni in S

richiede tempi moltomolto lunghi

PROCEDURA DI ENUMERAZIONE COMPLETA (ESEMPIO CPP)

1. Genera tutte le partizioni in clique del grafo G(N,A)

2. Per ogni partizione in clique calcola il costo

3. Scegli la partizione in clique che produce la soluzione di costo minimo

Aij

ijijxd

5

SOLUZIONE DI UN PROBLEMA DI PL01

In generale, la soluzione di un problema di PL01 richiede algoritmi sofisticatisofisticati e molto efficientiefficienti.

Quanto è buonabuona la soluzione ammissibile trovata?

Gli algoritmi di soluzione si basano generalmente su:

certificati di qualità della soluzione

metodologie generali di soluzione, sia di tipo esatto che di tipo euristico

Gli algoritmi di soluzione possono essere:

di tipo esatto: determinano sempre la soluzione ottima

approssimati: determinano sempre una soluzione ammissibile

Formulare non implicanon implica risolvere un problema di PL0.

6

SEMISPAZI E POLIEDRI

PP = { x Rm : Ax ≤ b }

Siano

• A Rpxm una matrice reale di p righe e m colonne

• b Rp un vettore reale di p componenti

L’insieme dei vettori xRm che soddisfano le p disequazioni x ≤ bq del sistema

è definito POLIEDROPOLIEDRO e viene indicato con la lettera PP

Ax ≤ b

Tqa

x P P x ≤ bq per per qq = 1, …, p = 1, …, pTqa

7

SEMISPAZI E FORMULAZIONI

PP = { x R2 : }

Geometricamente, ogni disequazione del sistema Ax ≤ b individua unsemispazio

Esempio – m = 2 1xx2

121 Consideriamo la retta

1xx2

121

Quindi un poliedro PP è intersezione di un numero finito q di semispazi.

PPPP = { x Rp : Ax ≤ b }

x1

x2

8


Sia S l’insieme delle soluzioni di un problema di Programmazione Lineare 0–1.

P {0,1}m = S

Il poliedro P è una formulazioneformulazione del problema di Programmazione Lineare 0–1 se e solo se

contiene tutti i vettori di S: S P

non contiene alcun vettore di S’ ={ 0,1}m \ S: P S’ =

Ci sono infiniteinfinite formulazioni dello stesso problema di PL01.

Per ognuna vale l’ovvia proprietà:

min { cTx: x S } = min { cTx: x P {0,1}m }

= cTx*

x1

x2

PP

0

0

0

1

1

1

1

0

9

FORMULAZIONI E LOWER BOUND

Per ogni formulazione P vale inoltre la disuguaglianza

Il valore

LB(P) = min { cTx: x P }viene definito lower bound del problema di PL01.

min { cTx: x P {0,1}m }min { cTx: x P }

Per ogni formulazione di un problema di PL01 con insieme delle soluzioni vale la proprietà

LB(P) cTx*

Il lower bound è il valore ottimo della soluzione di un problema di PL che viene definito rilassamento lineare

min { cTx: x P }

10

FORMULAZIONE OTTIMA

Esiste una formulazione P* migliore di tutte le altre?

P* = conv( S )

Per il problema della partizione in clique dei nodi di un grafo, non

conosciamo tutte le disequazioni che definiscono il poliedro P*

Argomento trattato nel corso di Ottimizzazione Combinatoria (III anno)

x1

x2

P*P*

conosciamo alcune famiglie di disequazioni che definiscono

P*

SI

Inoltre….

Una disequazione aTx b si definisce validavalida per un poliedro P se e solo se è soddisfatta da tutti i punti in P

conosciamo famiglie di disequazioni valide per P*

PP { x Rp : aTx b }

11

DISEQUAZIONI TRIANGOLO

Consideriamo tre nodi i, j, k N di G(N,A)

1 xse ij

Si definisce disequazione triangolodisequazione triangolo relativa ai nodi i, j, k

1xxx jkikij

Una disequazione triangolo rappresenta il vincolo logico:

1 x jk

A)G(N,i

jk

1 xe ik

12

i

j k

0

0

0

x

x

x

jk

ik

ij

(a)

NO

(b)

0

0

1

x

x

x

jk

ik

ij

i

j k

(c)

i

j k

0

1

0

x

x

x

jk

ik

ij

(e)

i

j k

0

1

1

x

x

x

jk

ik

ij

(d)

i

j k

1

0

0

x

x

x

jk

ik

ij

(f)

i

j k

1

0

1

x

x

x

jk

ik

ij

(h)

i

j k

1

1

1

x

x

x

jk

ik

ij

(g)

i

j k

1

1

0

x

x

x

jk

ik

ij

13

FORMULAZIONE DEL PROBLEMA CPP

Consideriamo il poliedro definito dalle disequazioni triangolo relative a tutte le terne di nodi G(N,A)

} mji1per 1x 0

m,kji1per

1xxx

1xx x

1xx x

:R x {P'

ij

jkikij

jkikij

jkikijm

È facile verificare che P’ è una formulazione del problema CPP

A)G(N,1

23

4

5

6

56

46

45

36

35

34

26

25

24

23

16

15

14

13

12

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

211 V,V(G)P 1Px

1

1

1

0

0

0

0

0

0

1

0

0

0

1

1

P {0,1}m = S

14

i

j k

0

0

0

x

x

x

jk

ik

ij

(a) (b)

0

0

1

x

x

x

jk

ik

ij

i

j k

(c)

i

j k

0

1

0

x

x

x

jk

ik

ij

(e)

i

j k

0

1

1

x

x

x

jk

ik

ij

(d)

i

j k

1

0

0

x

x

x

jk

ik

ij

(f)

i

j k

1

0

1

x

x

x

jk

ik

ij

(h)

i

j k

1

1

1

x

x

x

jk

ik

ij

(g)

i

j k

1

1

0

x

x

x

jk

ik

ij

NO

NO

NO

15

FORMULAZIONE DEL PROBLEMA CPP

Le disequazioni triangolo sono tante.

3

n 33 disequazioni per ogni terna ordinata di nodi

Consideriamo il rilassamento lineare del problema

S x

xd minAij

ijij

P' x

xd minAij

ijij

x {0,1}m

Ora sono ammissibili soluzioni non interenon intere

1

23

4

5

6

56

46

45

36

35

34

26

25

24

23

16

15

14

13

12

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

.....(G)P1

1Px

21

41

41

0

0

41

0

0

0

21

0

0

0

21

21

S P’

?21

21

21

41

41

21

41

16

DISEQUAZIONI A 2 PARTIZIONI

Possiamo trovare disequazioni migliori delle disequazioni triangolo?

Siano S,T N due sottoinsiemi disgiunti e non vuoti di N.

La disequazione a 2 partizioni2 partizioni (S,T) associata ai sottoinsiemi S e T è

|}T||,S| min{x(E(T))x(E(S)) ) x( T)δ(S,S

T

2

3

1

4

1xxxxxx 342423141312

x(E(T)) E(S)

min{1,3}

Una disequazione a 2 partizioni2 partizioni (S,T) associata ai sottoinsiemi S e

T definisce è validavalida per il poliedro P*.

Definisce una faccia di P* se e solo se |T||S|

) x( T)δ(S,

17


Sia P’’ il poliedro costituito da tuttetutte le disequazioni a 2 partizioni2 partizioni (S,T) con |S| |T|

S

T

2

3

1

4

1xxxxxx 342423141312

OsservazioneOsservazione Le disequazioni triangolo sono disequazione a 2 2 partizionipartizioni (S,T) con |S|= 1 e |T| = 2

P’’ P’

0

0

02

12

12

1

x

x

x

x

x

x

x

23

24

23

14

13

12

ˆ

21

21

21

0

00

EsempioEsempio Consideriamo il grafo G(N,A) e la soluzione

soddisfa tutte le 12

disequazioni triangolo

x̂

non soddisfa la

disequazione a 2 part.

S = { 1 } e T = { 2, 3, 4 }

x̂'P'xˆ

1000111 222

P’’ P’

P'xˆ

18


Quindi…

Data una soluzione x’ appartenente a P’ è possibile determinare S

e T tali che la disequazione a 2 partizioni2 partizioni (S,T) sia violata da x’ ?

P* P’’ P’ P*

P’

P’’

PROBLEMA DI SEPARAZIONE delle disequazioni a 2 partizioni

(S,T)

x’

S

T

2

3

1

4

21

21

21

0

00

come individuare S e T tale che

|}T||,S| min{x(E(T))x(E(S)) ) x( T)δ(S,

19

EURISTICA DI SEPARAZIONE

Sia x’ una soluzione appartenente a P’.

Vogliamo determinare, se esiste, una disequazione a 2 partizioni (S,T) con |S|=1

Per ogni i N

poni S = { i } e determina l’insieme W = { j N \{i} : 0 < xij’ < 1 }scegli un ordinamento nell’insieme W: W = { j1, …, jl }

poni T = { j1}

per ogni k = 2, …, l poni T = T { jk } se xjkjk’’ = 0 per ogni jk’

Tse |T|>1 e x’((S,T))>1, la disequazione a 2 partizioni (S,T) è violata

ALGORITMO EURISTICO

complessità O(n3) La soluzione dipende dall’ordinamento!

20


ESEMPIO Consideriamo la soluzione x’ in figura e applichiamo l’algoritmo euristico di separazione

S

T

2

3

1

4

21

21

21

0

00

Sia i = 1 e poniamo S = { 1 }

Definiamo W = { 2, 3, 4 } e scegliamo come ordinamento dato dalla permutazione naturale

Poniamo T = { 2 } e verifichiamo:

T = T { 3 } se x32’ = 0

Iterazione 1

T = { 2, 3 }T = T { 4 } se x43’ = 0 e x42’ = 0 T = { 2, 3, 4

}x’(S,T)= 3 / 2 >1 1x(E(T))x(E(S)) ) x( T)δ(S,

1x(E(T))x(E(S)) ) x( T)δ(S,

21


S

T

2

3

1

4

21

21

21

0

00

Sia i = 2 e poniamo S = { 2 }

Definiamo W = { 1 }

Poniamo T = { 1 }

Iterazione 2

|T| = 1 non è possibile determinare una disequazione violata

Per simmetria, è facile verificare che le iterazione 3 e 4 danno lo stesso risultato dell’iterazione 2.

L’unica disequazione violata da x’ trovata dall’algoritmo è

1xxxxxx 342423141312

22

FORMULAZIONE OTTIMA

Per il problema della partizione in clique dei nodi di un grafo, non

conosciamo tutte le disequazioni che definiscono il poliedro P*conosciamo alcune famiglie di disequazioni che definiscono

P*conosciamo famiglie di disequazioni valide per P*

In particolare,

le disequazioni triangolodisequazioni triangolo relative ai nodi i, j, k

1xxx jkikij

le disequazioni a 2 partizioni2 partizioni (S,T) associate ai sottoinsiemi S e T

|}T||,S| min{x(E(T))x(E(S)) ) x( T)δ(S,

P’

P’’

23

ALGORITMO DEI “PIANI DI TAGLIO”

Definisci il poliedro P0 P’ definito da un

sottoinsieme di disequazioni triangolo

Poni h = 0

risolvi il problema di PL

sia xh la soluzione ottima del problema di PL

esiste una disequazione triangolo violata da xh ?

P*

P’

h

Aijijij

P x

xd min

ALGORITMO DI SOLUZIONE

P’x0

P0

P0

P1

SI xh P’ : aggiungi la disequazione a Ph

e definisci il nuovo poliedro Ph+1

P*

24

esiste una disequazione triangolo violata da xh ?


NO xh P’


xh {0,1}m ?

P’’

P’

P*

P’

P0

P*x0

NO xh S : esistono due insiemi S e T tali che la disequazione a 2 2

partizionipartizioni (S,T) sia violata da xh?

STOP

SI xh P’’ : aggiungi la disequazione a Ph e definisci il nuovo poliedro Ph+1

SI xh S : xh è la soluzione ottimax0

P0

25

esistono due insiemi S e T tali che la

disequazione a 2 partizioni2 partizioni (S,T) sia violata da xh?


NO xh P’’


xh {0,1}m ?

P’

P0

P*

P’

P0

P*x0

NO xh S : applica il metodo del branch and bound per risolvere il problema di PL01

P’’

x0

mh

Aijijij

{0,1}P x

xd min

STOPSI xh S : xh è la soluzione ottima

P’’

STOP

VERO se l’algoritmo di separazione è esatto

26

ESEMPIO

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 } e A = { ij | 1 i j 6 }.

A)G(N,

1

65

2 3

4

20

10

10

10

10

10

1010

20

0.5

0.50.2

0.3

0.5

0.5

0 10 10 0.2 0.5 0.5

10 0 0.5 0.3 0.5 10

10 0.5 0 10 10 10

0.2 0.3 10 0 10 20

0.5 0.5 10 10 0 20

0.5 10 10 20 20 0

D =

Sia D la matrice delle distanze

Risolviamo il problema di partizione in clique con vincolo di dimensione con s = 2.

27

APPLICAZIONE ALGORITMO

Definiamo il poliedro P0 P’ definito da un

sottoinsieme di disequazioni triangolo e h = 0 x12 + x13 - x23 <= 1 x12 - x13 + x23 <= 1 - x12 + x13 + x23 <= 1 x12 + x14 - x24 <= 1 x12 - x14 + x24 <= 1 - x12 + x14 + x24 <= 1 x12 + x15 - x25 <= 1 x12 - x15 + x25 <= 1 - x12 + x15 + x25 <= 1 x12 + x16 - x26 <= 1 x12 - x16 + x26 <= 1 - x12 + x16 + x26 <= 1 x13 + x14 - x34 <= 1 x13 - x14 + x34 <= 1 - x13 + x14 + x34 <= 1 x13 + x15 - x35 <= 1 x13 - x15 + x35 <= 1 - x13 + x15 + x35 <= 1 x13 + x16 - x36 <= 1 x13 - x16 + x36 <= 1 - x13 + x16 + x36 <= 1

P0 = { x [0,1]15: } { x [0,1]15 : }

x12 + x13 + x14 + x15 + x16 >= 1

x12 + x23 + x24 + x25 + x26 >= 1

x13 + x23 + x34 + x35 + x36 >= 1

x14 + x24 + x34 + x45 + x46 >= 1

x15 + x25 + x35 + x45 + x56 >= 1

x16 + x26 + x36 + x46 + x56 >= 1

28

risolviamo il problema di PL

sia x0 la soluzione ottima del problema di PL di costo 1.8

0

Aijijij

P x

xdmin

A)G(N,

1

65

2 3

41

1

1

1

56

46

45

36

35

34

26

25

24

23

16

15

14

13

12

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

0x

0

0

1

0

1

0

0

1

0

0

1

0

0

0

0

11

1

111

1

1


29

esiste una disequazione triangolo violata da x0 ?

SI x0 P’ : aggiungi la disequazione a P0 e definisci il nuovo poliedro

per enumerazione o ispezione visiva

1

65

2 3

41

1

1

111

1

111

1

1

- x23 + x25 + x35 <= 1- x34 + x35 + x45 <= 1

P1 = P0{ x [0,1]15: }

- x34 + x35 + x45 = 2 > 1

- x23 + x25 + x35 = 2 > 1


30



1

Aijijij

P x

xdmin

1x

0

0 2

1

21

21

0 2

1

21

0

0 2

1

0 2

1

0

0

56

46

45

36

35

34

26

25

24

23

16

15

14

13

12

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

1

65

2 3

42

1

21

21

21

21

21

21


31


NO x1 P’

1

65

2 3

42

1

21

21

21

21

21

21

x1 {0,1}m ?

NO x1 S : esistono due insiemi S e T tali che la disequazione a 2 2

partizionipartizioni (S,T) sia violata da x1?applico l’euristica


32

esiste una disequazione a 2 partizioni violata da x1 ?

1

6

2 3

42

1

21

21

21

21

21

21


Sia i = 1 e poniamo S = { 1 }Definiamo W = { 4, 6 }


T = T { 6 } se x46 = 0

Iterazione 1

T = { 4, 6 }

x’(S,T)= 1 1 Nessuna disequazione a 2 partizioni trovata con S = { 1 }

5

33

1

6

2 3

42

1

21

21

21

21

21

21




T = T { 6 } se x56 = 0

Iterazione 2

T = { 5, 6 }


5

34

1

6

2 3

42

1

21

21

21

21

21

21




T = T { 6 } se x56 = 0

Iterazione 3

T = { 5, 6 }


5

35

1

6

2 3

42

1

21

21

21

21

21

21




T = T { 5 } se x15 = 0

Iterazione 4

T = { 1, 5 }


5

36

1

6

2 3

42

1

21

21

21

21

21

21


Sia i = 5 e poniamo S = { 5 }Definiamo W = { 2, 3, 4 }


T = T { 3 } se x23 = 0

Iterazione 5

T = { 2, 3 }

5

T = T { 4 } se x43 = 0 e x42 = 0 T = { 2, 3, 4 }

x’(S,T)= 3 / 2 >1 1x(E(T))x(E(S)) ) x( T)δ(S,

1x(E(T))x(E(S)) ) x( T)δ(S,

S

T

37

1

6

2 3

42

1

21

21

21

21

21

21




T = T { 2 } se x12 = 0

Iterazione 6

T = { 1, 2 }

5

T = T { 3 } se x13 = 0 e x23 = 0 T = { 1, 2, 3 }

x’(S,T)= 3 / 2 >1 1x(E(T))x(E(S)) ) x( T)δ(S,

1x(E(T))x(E(S)) ) x( T)δ(S,

S

T

38


1

6

2 3

42

1

21

21

21

21

21

21


5

SI x1 P’’ : aggiungi le disequazioni a P1 e definisci il nuovo poliedro P2

x25 + x35 + x45 - x23 - x24 - x34 <= 1

x16 + x26 + x36 - x12 - x13 - x23 <= 1

P2 = P1{ x [0,1]15: } x25 + x35 + x45 - x23 - x24 - x34 <= 1

x16 + x26 + x36 - x12 - x13 - x23 <= 1

39



2

Aijijij

P x

xdmin

2x

0

0 9

4

91

96

91

91

94

93

91

98

0 9

1

0

0

56

46

45

36

35

34

26

25

24

23

16

15

14

13

12

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

1

65

2 3

49

8

91

91

96

94

91

94


91

93

40


NO x2 P’

x2 {0,1}m ?

NO x2 S : esistono due insiemi S e T tali che la disequazione a 2 2

partizionipartizioni (S,T) sia violata da x1?applico l’euristica


1

65

2 3

49

8

91

91

96

94

91

94

91

93

41





T = T { 6 } se x46 = 0

Iterazione 1

T = { 4, 6 }


1

65

2 3

49

8

91

91

96

94

91

94

91

93

42




T = T { 5 } se x35 = 0

Iterazione 2

NO

|T|= 1 Nessuna disequazione a 2 partizioni trovata con S = { 2 }

1

65

2 3

49

8

91

91

96

94

91

94

91

93

T = T { 6 } se x36 = 0 NO

43


Sia i = 3 e poniamo S = { 3 }Definiamo W = { 2, 4, 5, 6 }


T = T { 4 } se x24 = 0

Iterazione 3

T = { 2, 4 }


1

65

2 3

49

8

91

91

96

94

91

94

91

93

T = T { 5 } se x25 = 0 e x45 = 0 NO

T = T { 6 } se x26 = 0 e x46 = 0 NO

44




T = T { 3 } se x13 = 0

Iterazione 4

T = { 1, 3 }

x(S,T)= 1 1 Nessuna disequazione a 2 partizioni trovata con S = { 4 }

1

65

2 3

49

8

91

91

96

94

91

94

91

93

T = T { 5 } se x15 = 0 e x35 = 0 NO

45




T = T { 3 } se x23 = 0

Iterazione 5

NO


1

65

2 3

49

8

91

91

96

94

91

94

91

93

T = T { 4 } se x24 = 0 T = { 2, 4 }

46




T = T { 2 } se x12 = 0

Iterazione 6

T = { 1, 2 }


1

65

2 3

49

8

91

91

96

94

91

94

91

93

T = T { 3 } se x13 = 0 e x23 = 0 NO

47

esiste una disequazione a 2 partizioni (S,T) violata da x2 ?

NO non possiamo dire che x2 P’’ e andiamo avanti

x2 {0,1}m ?


1

6 5

2 3

49

8

91

91

96

94

91

94

91

93

NO x2 S : applica il metodo del branch and bound per risolvere

il problema di PL01

m2

Aijijij

{0,1}P x

xdmin

48

applichiamo il metodo del branch and bound per risolvere il problema di PL01 e ricaviamo la soluzione x3 di costo 10.7


1

6 5

2 3

4

1

11

STOP

56

46

45

36

35

34

26

25

24

23

16

15

14

13

12

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

3x

0

0

0

1

0

0

0

1

0

0

0

0

1

0

0

la soluzione x3 è una soluzione 0-1

la soluzione x3 rispetta le disequazioni triangolo x3 P’

la soluzione x3 è la soluzione ottima del problema

49

Il costo della soluzione ottima è dTx3 =10.7

CONSIDERAZIONI

LB(Ph) = min { dTx: x Ph }

Per ogni poliedro Ph indichiamo

Abbiamo visto che

LB(P0) < LB(P1) < LB(P2) < dTx3

1.8 < 6.25 < 7.833 < 10.7

Più vincoli violati aggiungiamo e maggiore è il valore del lower lower boundbound

E se P2 {0,1}m avesse avuto dimensioni troppo grandi?

Algoritmo euristico di soluzione per determinare un upper upper

boundbound

50

1. Poni U := N, i := 1

2. Trova i nodi u e v più lontani in U

3. Ordina le distanze dei nodi in U\{u} da u

Sia Ou il vettore dei nodi ordinati

4. Forma un cluster Ci con i primi s-1 elementi in Ou

5. U = U \ Ci

6. Ordina le distanze dei nodi in U \{v} da v

Sia Ov il vettore dei nodi ordinati

7. Forma un cluster Ci+1 con i primi s-1 elementi in Ov

8. U = U \ Ci+1

9. i = i + 2

10. SE |U| ≥ 2s ALLORA torna al passo 2.

ALTRIMENTI SE s ≤ |U| < 2s ALLORA Ci = U

ALTRIMENTI assegna ogni nodo in U al cluster cui appartiene il nodo più vicino

ALGORITMO EURISTICO

51

ESEMPIO ALGORITMO EURISTICO

ESEMPIO Consideriamo nuovamente il grafo G(N,A) associato all’insieme X = { v1, v2, v3, v4, v5, v6, v7, v8

}, dove

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

A)G(N,

1

65

2 3

4

20

10

10

10

10

10

1010

20

0.5

0.50.2

0.3

0.5

0.5

0 10 10 0.2 0.5 0.5

10 0 0.5 0.3 0.5 10

10 0.5 0 10 10 10

0.2 0.3 10 0 10 20

0.5 0.5 10 10 0 20

0.5 10 10 20 20 0

D =

Sia D la matrice delle distanze

Applichiamo l’algoritmo euristico di soluzione del problema di partizione in clique con vincolo di dimensione con s = 2.

52

1. Poniamo U := { 1, 2, 3, 4, 5, 6 }, i := 1

2. Determiniamo i nodi più lontani in U

e poniamo u := 1 e v := 2

3. Ordiniamo le distanze dei nodi in U\{1} da 1

e poniamo O1 = { 6, 5, 4, 3, 2 }

4. Formiamo un cluster C1 con i primi s-1 = 1 elementi in O1

C1:= { 1, 6 }

1

65

2 3

4

20

10

10

10

10

10

1010

20

0.5

0.50.2

0.3

0.5

0.5

0 10 10 0.2 0.5 0.5

10 0 0.5 0.3 0.5 10

10 0.5 0 10 10 10

0.2 0.3 10 0 10 20

0.5 0.5 10 10 0 20

0.5 10 10 20 20 0

D =


53

5. U = { 2, 3, 4, 5 }

6. Ordiniamo le distanze dei nodi in U\{2} da 2

e poniamo O2 = { 5, 4, 3 }

7. Formiamo un cluster C2 con il primo elemento in O2

C2 = { 2, 5 }

8. U = { 3, 4 }

9. i = 3

10. 2 ≤ |U| < 4 C3 = { 3, 4 }

1

65

2 3

4

10

0.5 0.5

C2

C1

C3

La soluzione euristica èP = { C1, C2 , C3 }

Il valore della soluzione èc(P) = 0.5 + 0.5 +10 = 11


54

PROBLEMA DI PARTIZIONE DI CLIQUE

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 è

1V

2V3V

1

1

11

11

1

somma delle distanze tra nodi appartenenti allo stesso

clusterÈ l’unico criterio di ottimalitàcriterio di ottimalità?

55

I criteri di ottimalità si dividono in due classi: criteri di separazione (da massimizzare) criteri di omogeneità (da minimizzare)

CRITERI DI OTTIMALITÀ

I criteri di separazionecriteri di separazione si basano sull’ottimizzazione delle relazioni (similarità e dissimilarità) tra punti in cluster diversi

critero SPLIT: minima distanza tra cluster

ijδ(V)ij

ijVjV,i

dmindmins(V)

I criteri di ottimalitàcriteri di ottimalità sono funzioni che associano un valore numerico ad un cluster

NV RV :s

56

CRITERI DI SEPARAZIONE

1V

2V

3V1

8

6

5

43

2

Assegniamo ad ogni cluster V N il minimo dei pesi degli archi in (V)

1

1 1

5.1

1

15

Assegniamo ad ogni arco ij di A il peso ijd

ijδ(V)ij

dminc(V)

7 2)c(V2

2)c(V3

2)c(V1

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(P(G)) = 2 + 2 + 2 = 6

3 24 3

3

4

23

4

5

73

57

critero CUT: somma delle distanze tra cluster

δ(V)ij

ijVjV,i

ij ddC(V)

CRITERI DI SEPARAZIONE

critero CUT normalizzato:

|)V|(n-|V|

C(V)(V)CN

58

CRITERI DI OMOGENEITÀ

I criteri di omogeneitàcriteri di omogeneità si basano sull’ottimizzazione delle relazioni (similarità e dissimilarità) tra punti nello stesso cluster

critero DIAMETRO: massima distanza nel cluster

ijE(V)ij

ijVjV,i

dmaxdmaxd(V)

1

65

2 3

4

20

10

10

10

10

10

1010

20

0.5

0.50.2

0.3

0.5

0.5

}6 ,5 ,4 ,3 ,2 ,1{V

20d(V)

critero RAGGIO: minima tra le distanze massime nel cluster

ijVjVi

dmaxminr(V)

10=r(V)

59

critero STELLA: minima somma delle distanze nel cluster

VjijVi

dminst(V)

1

65

2 3

4

20

10

10

10

10

10

1010

20

0.5

0.50.2

0.3

0.5

0.5

}6 ,5 ,4 ,3 ,2 ,1{V

3.21st(V)

critero CLIQUE: somma delle distanze nel cluster

E(V)ij

ijdcl(V)

5.112cl(V)


0 10 10 0.2 0.5 0.5

10 0 0.5 0.3 0.5 10

10 0.5 0 10 10 10

0.2 0.3 10 0 10 20

0.5 0.5 10 10 0 20

0.5 10 10 20 20 0

D =

60

CENTRO DI UN CLUSTER

I criteri di omogeneitàcriteri di omogeneità basati sui “centricentri” si riferiscono sull’ottimizzazione delle relazioni (similarità e dissimilarità) tra i punti di un cluster ed il centro del cluster

Si definisce centro di un cluster la media aritmetica dei punti del cluster

Vv

i

i

v|V|

1v

1

3

2

0 6

2 5

1 1

X =

1

4

3

12

31

v

61


critero SOMMA DEI QUADRATI: somma delle distanze euclidee al quadrato tra i punti di cluster ed il centro

Vv

2i

i2

)]v,(v[dsq(V)

critero VARIANZA: somma dei quadrati normalizzata

sq(V)|V|

1vr(V)

0 6

2 5

1 1

X = 1

3

2

1

4v

92

516sq(V)

316

vr(V)

62

PROBLEMI DI CLUSTERING PARTIZIONALE

In base al criterio di ottimalità, abbiamo diversi problemi di clustering partizionale

critero CLIQUE: problema di partizione in clique

CLIQUE PARTITIONING PROBLEM

critero STELLA: problema p-median

p-MEDIAN PROBLEM

critero SOMMA DEI QUADRATI: problema k-means

k-MEANS PROBLEM

63

MATERIALE DEL SEMINARIO

Le slide di questo seminario sono reperibili al seguente link:

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

Algoritmi di classificazione e reti neurali Seminario su clustering dei dati – Parte II...

Documents

Transcript of Algoritmi di classificazione e reti neurali Seminario su clustering dei dati – Parte II...