Algoritmi di classificazione e reti neurali
Seminario su clustering dei dati – Parte II
a cura di Silvia Canale
contatto e-mail: [email protected]
Università di Roma“La Sapienza”
Dipartimento di Informatica e Sistemistica
Corso di Laurea in “Ingegneria Gestionale”
ARGOMENTI DEL SEMINARIO
 Problema della partizione in clique
 esempio algoritmo dei piani di taglio
 algoritmo euristico
 Clustering partizionale – Criteri di ottimalità
 Problema k-means
 formulazione
 algoritmo euristico
2
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 }.
G(N, A)
2
3
10
0 20 20 10 10 0.5
20
1
Sia D la matrice delle distanze
20
10
0.5
10
0.3
0.5
0.5
6
10
0.2
10
0.5
10
D=
10
4
20
20
10
10
0
10
10
0.5
10
0
10
0.3
10
10
0
0.5
0.5
0.3
0.5
0
0.5
0.2
10
10
0.5 0.5 0.2 10 10 0
5
Risolviamo il problema di partizione in clique con vincolo di
3
dimensione con s = 2.
APPLICAZIONE ALGORITMO
Definiamo il poliedro P0  P’ definito da un
sottoinsieme di disequazioni triangolo e h = 0
P0 = {
x [0,1]15:
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
15
x12 - x16 + x26 <= 1 } { x [0,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
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
4
APPLICAZIONE ALGORITMO
risolviamo il problema di PL
min
d
ijA
ij
x ij
x  P0
sia x0 la soluzione ottima del problema di PL di costo 1.8
G(N, A)
2
3
1
1
1
1
x0 
4
1
6
5
 x12   0 

  
 x13   0 
 x   0
 14   
 x15   0 
x   1 
 16   
 x 23   0 

  
 x 24   0 
 x 25    1 

  
 x 26   0 
 x   0
 34   
 x 35   1 
 x   0
 36   
 x 45   1 

  0
x
46

  
 x   0 
 56 
5
APPLICAZIONE ALGORITMO
esiste una disequazione triangolo violata da x0 ?
2
3
- x23 + x25 + x35 = 2 > 1
1
- x34 + x35 + x45 = 2 > 1
1
1
1
4
1
6
5
per enumerazione
o ispezione visiva
SI
x0  P’ : aggiungi la disequazione a P0 e definisci il nuovo
poliedro
+ x25 + x35 <= 1
P1 = P0{ x [0,1]15: -- x23
}
x34 + x35 + x45 <= 1
6
APPLICAZIONE ALGORITMO
risolviamo il problema di PL
min
d
ijA
ij
x ij
x  P1
sia x1 la soluzione ottima del problema di PL di costo 6.25
2
1
1
1
1
3
2
1
2
2
x1 
2
1
2
1
4
2
1
6
5
2
 x12  

 
x
 13  
x  
 14  
 x15  
 x  
 16  
 x 23  

 
x
24

 
 x 25   

 
x
 26  
x  
 34  
 x 35  
 x  
 36  
 x 45  

 
 x 46  
x  
 56  





2

0 
1 
2
0 

0 
1 
2

1 
2

0 
1 
2
1 
2
1 
2

0 7
0 
0
0
1
APPLICAZIONE ALGORITMO
esiste una disequazione triangolo violata da x1 ?
2
1
1
1
1
3
2
1
2
2
2
1
2
1
4
2
1
6
2
5
NO
x1  P’
x1  {0,1}m ?
NO
x1  S : esistono due insiemi S e
T tali che la disequazione a 2
applico l’euristica
partizioni (S,T) sia violata da x1?
8
APPLICAZIONE ALGORITMO
esiste una disequazione a 2 partizioni violata da x1 ?
2
1
1
1
1
3
2
1
Iterazione 1
2
Sia i = 1 e poniamo S = { 1 }
2
2
1
Definiamo W = { 4, 6 }
2
1
4
2
1
6
2
5
Poniamo T = { 4 } e verifichiamo:
T = { 4, 6 }
T = T  { 6 } se x46 = 0
x’(S,T)= 1  1
Nessuna disequazione a 2 partizioni trovata
con S = { 1 }
9
APPLICAZIONE ALGORITMO
2
1
1
1
1
3
2
1
Iterazione 2
2
Sia i = 2 e poniamo S = { 2 }
2
2
1
Definiamo W = { 5, 6 }
2
1
4
2
1
6
2
5
Poniamo T = { 5 } e verifichiamo:
T = { 5, 6 }
T = T  { 6 } se x56 = 0
x’(S,T)= 1  1
Nessuna disequazione a 2 partizioni trovata
con S = { 2 }
10
APPLICAZIONE ALGORITMO
2
1
1
1
1
3
2
1
Iterazione 3
2
Sia i = 3 e poniamo S = { 3 }
2
2
1
Definiamo W = { 5, 6 }
2
1
4
2
1
6
2
5
Poniamo T = { 5 } e verifichiamo:
T = { 5, 6 }
T = T  { 6 } se x56 = 0
x’(S,T)= 1  1
Nessuna disequazione a 2 partizioni trovata
con S = { 3 }
11
APPLICAZIONE ALGORITMO
2
1
1
1
1
3
2
1
Iterazione 4
2
Sia i = 4 e poniamo S = { 4 }
2
2
1
Definiamo W = { 1, 5 }
2
1
4
2
1
6
2
5
Poniamo T = { 1 } e verifichiamo:
T = { 1, 5 }
T = T  { 5 } se x15 = 0
x’(S,T)= 1  1
Nessuna disequazione a 2 partizioni trovata
con S = { 4 }
12
APPLICAZIONE ALGORITMO
T
2
1
1
1
1
3
2
1
Iterazione 5
2
Sia i = 5 e poniamo S = { 5 }
2
2
1
6
Definiamo W = { 2, 3, 4 }
2
1
4
2
1
S
2
5
Poniamo T = { 2 } e verifichiamo:
T = { 2, 3 }
T = T  { 3 } se x23 = 0
T = T  { 4 } se x43 = 0 e x42 = 0
T = { 2, 3, 4 }
x’(S,T)= 3 / 2 >1
x(δ(S, T)) x(E(S))  x(E(T))  1
x(δ(S, T))  x(E(S))  x(E(T))  1
13
APPLICAZIONE ALGORITMO
T
2
1
1
1
1
3
2
1
Iterazione 6
2
Sia i = 6 e poniamo S = { 6 }
2
2
1
S
Definiamo W = { 1, 2, 3 }
2
1
4
2
1
6
2
5
Poniamo T = { 1 } e verifichiamo:
T = { 1, 2 }
T = T  { 2 } se x12 = 0
T = T  { 3 } se x13 = 0 e x23 = 0
T = { 1, 2, 3 }
x’(S,T)= 3 / 2 >1
x(δ(S, T)) x(E(S))  x(E(T))  1
x(δ(S, T))  x(E(S))  x(E(T))  1
14
APPLICAZIONE ALGORITMO
esiste una disequazione a 2 partizioni violata da x1 ?
2
1
1
1
3
2
1
2
x25 + x35 + x45 - x23 - x24 - x34 <= 1
2
x16 + x26 + x36 - x12 - x13 - x23 <= 1
1
2
1
2
1
4
2
1
6
SI
2
5
x1  P’’ : aggiungi le disequazioni a P1 e definisci il
nuovo poliedro P2
P2 = P1{
x [0,1]15:
x25 + x35 + x45 - x23 - x24 - x34 <= 1
x16 + x26 + x36 - x12 - x13 - x23 <= 1
}
15
APPLICAZIONE ALGORITMO
risolviamo il problema di PL
min
d
ijA
ij
x ij
x  P2
sia x2 la soluzione ottima del problema di PL di costo 7.833
2
1
1
1
8
3
3
9
9
6
9
9
1
9
x2 
9
1
9
4
4
9
4
6
5
9
 x12  

 
x
 13  
x  
 14  
 x15  
x  
 16  
 x 23  

 
 x 24  
 x 25   

 
 x 26  
x  
 34  
 x 35  
x  
 36  
 x 45  

 
 x 46  
x  
 56  
0 
0 

1 
9
0 

8 
9

1 
9
3 
9
4 
9
1 
9
1 
9
6 
9

1 
9

4 
9
0 
0 
16
APPLICAZIONE ALGORITMO
esiste una disequazione triangolo violata da x2 ?
2
1
1
1
8
3
3
9
9
6
9
9
9
1
1
9
4
9
4
9
4
6
9
5
NO
x2  P’
x2  {0,1}m ?
NO
x2  S : esistono due insiemi S e
T tali che la disequazione a 2
applico l’euristica
partizioni (S,T) sia violata da x1?
17
APPLICAZIONE ALGORITMO
esiste una disequazione a 2 partizioni violata da x2 ?
2
1
1
1
8
3
3
9
9
6
Iterazione 1
Sia i = 1 e poniamo S = { 1 }
9
9
1
9
Definiamo W = { 4, 6 }
9
1
9
4
4
9
4
6
9
5
Poniamo T = { 4 } e verifichiamo:
T = { 4, 6 }
T = T  { 6 } se x46 = 0
x’(S,T)= 1  1
Nessuna disequazione a 2 partizioni trovata
con S = { 1 }
18
APPLICAZIONE ALGORITMO
2
1
1
1
8
3
3
9
9
Iterazione 2
6
9
9
9
1
1
9
4
9
Sia i = 2 e poniamo S = { 2 }
Definiamo W = { 3, 5, 6 }
4
9
4
6
9
5
Poniamo T = { 3 } e verifichiamo:
NO
T = T  { 5 } se x35 = 0
NO
T = T  { 6 } se x36 = 0
|T|= 1
Nessuna disequazione a 2 partizioni trovata
con S = { 2 }
19
APPLICAZIONE ALGORITMO
2
1
1
1
8
3
3
9
9
Iterazione 3
6
9
9
9
1
1
9
4
9
Sia i = 3 e poniamo S = { 3 }
Definiamo W = { 2, 4, 5, 6 }
4
9
4
6
9
5
Poniamo T = { 2 } e verifichiamo:
T = { 2, 4 }
T = T  { 4 } se x24 = 0
NO
T = T  { 5 } se x25 = 0 e x45 = 0
NO
T = T  { 6 } se x26 = 0 e x46 = 0
x’(S,T)= 1  1
Nessuna disequazione a 2 partizioni trovata
20
con S = { 3 }
APPLICAZIONE ALGORITMO
2
1
1
1
8
3
3
9
9
Iterazione 4
6
9
9
9
1
1
9
4
9
Sia i = 4 e poniamo S = { 4 }
Definiamo W = { 1, 3, 5 }
4
9
4
6
9
5
Poniamo T = { 1 } e verifichiamo:
T = { 1, 3 }
T = T  { 3 } se x13 = 0
T = T  { 5 } se x15 = 0 e x35 = 0
NO
x(S,T)= 1  1
Nessuna disequazione a 2 partizioni trovata
con S = { 4 }
21
APPLICAZIONE ALGORITMO
2
1
1
1
8
3
3
9
9
Iterazione 5
6
9
9
9
1
1
9
4
9
Sia i = 5 e poniamo S = { 5 }
Definiamo W = { 2, 3, 4 }
4
9
4
6
9
5
Poniamo T = { 2 } e verifichiamo:
NO
T = T  { 3 } se x23 = 0
T = T  { 4 } se x24 = 0
T = { 2, 4 }
x(S,T)= 1  1
Nessuna disequazione a 2 partizioni trovata
con S = { 5 }
22
APPLICAZIONE ALGORITMO
2
1
1
1
8
3
3
9
9
Iterazione 6
6
9
9
9
1
1
9
4
9
Sia i = 6 e poniamo S = { 6 }
Definiamo W = { 1, 2, 3 }
4
9
4
6
9
5
Poniamo T = { 1 } e verifichiamo:
T = { 1, 2 }
T = T  { 2 } se x12 = 0
T = T  { 3 } se x13 = 0 e x23 = 0
x(S,T)= 1  1
NO
Nessuna disequazione a 2 partizioni trovata
con S = { 6 }
23
APPLICAZIONE ALGORITMO
esiste una disequazione a 2 partizioni (S,T) violata da x2 ?
2
1
1
1
8
NO
3
3
9
9
6
9
9
9
1
1
6
x2  P’’
9
4
9
4
9
4
5
x2  {0,1}m ? NO
9
x2  S : applica il metodo del
branch and bound per risolvere il
problema di PL01
min
d
ijA
ij
x ij
x  P 2  {0,1} m
STOP
24
APPLICAZIONE ALGORITMO
applichiamo il metodo del branch and bound per risolvere il
problema di PL01 e ricaviamo la soluzione x3 di costo 10.7
2
1
3
1
x3 
1
1
6
4
5
la soluzione x3 è una soluzione 0-1
 x12   0 
  

 x13   0 
x   1 
 14   
 x15   0 
x   
 16   0 
 x 23   0 
  

 x 24   0 
 x 25    1 
  

 x 26   0 
 x   0
 34   
 x 35   0 
x   1 
 36   
 x 45   0 
  

 x 46   0 
 x   0
 56   
la soluzione x3 rispetta le disequazioni triangolo x3  P’
la soluzione x3 è la soluzione ottima del problema
STOP
25
CONSIDERAZIONI
Il costo della soluzione ottima è dTx3 =10.7
Per ogni poliedro Ph indichiamo
LB(Ph) = min { dTx: x  Ph }
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
bound
E se P2 {0,1}m avesse avuto dimensioni troppo grandi?
Algoritmo euristico di soluzione
26
per determinare un upper bound
ALGORITMO EURISTICO
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
27
cluster cui appartiene il nodo più vicino
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 }.
G(N, A)
2
3
10
0 20 20 10 10 0.5
20
1
Sia D la matrice delle distanze
20
10
0.5
10
0.3
0.5
0.5
6
10
0.2
10
0.5
10
D=
10
4
20
20
10
10
0
10
10
0.5
10
0
10
0.3
10
10
0
0.5
0.5
0.3
0.5
0
0.5
0.2
10
10
0.5 0.5 0.2 10 10 0
5
Applichiamo l’algoritmo euristico di soluzione del problema di
28
partizione in clique con vincolo di dimensione con s = 2.
ESEMPIO ALGORITMO EURISTICO
1. Poniamo U := { 1, 2, 3, 4, 5, 6 }, i := 1
2. Determiniamo i nodi più lontani in U
2
0 20 20 10 10 0.5
20
1
3
10
20
10
0.5
10
0.3
0.5
0.5
6
10
0.2
10
0.5
10
D=
10
4
20
20
10
10
0
10
10
0.5
10
0
10
0.3
10
10
0
0.5
0.5
0.3
0.5
0
0.5
0.2
10
10
0.5 0.5 0.2 10 10 0
5
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 }
29
ESEMPIO ALGORITMO EURISTICO
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
C2
10. 2 ≤ |U| < 4
C3 = { 3, 4 }
2
La soluzione euristica è
P = { C 1, C 2 , C 3 }
Il valore della soluzione è
c(P) = 0.5 + 0.5 +10 = 11
C3
3
1
10
0.5
0.5
4
C1
6
5
30
PROBLEMA DI PARTIZIONE DI CLIQUE
Risolvere il problema di partizione in clique dei nodi di un grafo
significa determinare la soluzione del seguente problema
min  d ijx ij
V2
1
1
1
1
ijA
x S
1
V3
1
V1
1
dove l’insieme delle soluzioni è
S  { x P  {0,1} m : x P vettore di incidenza di P(G),
x
ijδ(i)
ij
 s 1 i  N
somma delle distanze tra nodi appartenenti allo stesso cluster
È l’unico criterio di ottimalità?
31
}
CRITERI DI OTTIMALITÀ
I criteri di ottimalità sono funzioni che associano un valore
numerico ad un cluster
s:V  R
V  N
I criteri di ottimalità si dividono in due classi:
 criteri di separazione (da massimizzare)
 criteri di omogeneità (da minimizzare)
I criteri di separazione si basano sull’ottimizzazione delle
relazioni (similarità e dissimilarità) tra punti in cluster diversi
 critero SPLIT: minima distanza tra cluster
s(V)  min d ij  min d ij
iV, jV
ijδ(V)
32
CRITERI DI SEPARAZIONE
Assegniamo ad ogni arco ij di A il peso d ij
Assegniamo ad ogni cluster V  N
il minimo dei pesi degli archi in (V)
c(V)  min d ij
ijδ(V)
Assegniamo ad ogni partizione P(G)= { V1, V2, …, Vk } del grafo G(N,A)
la somma dei costi degli elementi della partizione
c(P(G)) = 2 + 2 + 2 = 6
6
2
1
1
8
V2 3 2
3
3
3
 c(V )
i
Vi P(G)
c(V2 )  2
7
1
c(P(G)) 
c(V3 )  2
3 1 4
5
1
5
1
V1
1.5
2
4
c(V1 )  2
V3
33
CRITERI DI SEPARAZIONE
 critero CUT: somma delle distanze tra cluster
C(V) 
d
iV, jV
ij

d
ijδ(V)
ij
 critero CUT normalizzato:
C(V)
C N (V) 
| V | (n- | V |)
34
CRITERI DI OMOGENEITÀ
I criteri di omogeneità si basano sull’ottimizzazione delle relazioni
(similarità e dissimilarità) tra punti nello stesso cluster
 critero DIAMETRO: massima distanza nel cluster
d(V)  max d ij  max d ij
iV, jV
2
20
1
ijE(V)
3
10
V  {1, 2, 3, 4, 5, 6}
20
10
0.5
10
0.2
10
0.3
0.5
0.5
6
d(V)  20
10
10
4
d(V)  10
0.5
10
5
 critero RAGGIO: minima tra le distanze massime nel cluster
r(V)  min max d ij
iV
jV
35
CRITERI DI OMOGENEITÀ
 critero STELLA: minima somma delle distanze nel cluster
st(V)  min  d ij
iV
2
20
1
jV
0 20 20 10 10 0.5
3
10
20
10
D=
0.5
10
0.3
0.5
0.5
6
10
0.2
10
0
10
10
0.5
10
0
10
0.3
10
10
0
0.5
0.5
0.3
0.5
0
0.5
0.2
10
10
0.5 0.5 0.2 10 10 0
4
st(V)  21.3
0.5
10
V  {1, 2, 3, 4, 5, 6}
10
20
20
10
10
5
cl(V)  112.5
 critero CLIQUE: somma delle distanze nel cluster
cl(V) 
d
ijE(V)
ij
36
CENTRO DI UN CLUSTER
Si definisce centro di un cluster la media aritmetica dei punti del
cluster
1
i
v
v

|V|v i V
2
1 1
X=
5 2
6 0
1 12   4 
v



3  3  1 
1
3
I criteri di omogeneità basati sui “centri” si riferiscono
sull’ottimizzazione delle relazioni (similarità e dissimilarità) tra i
punti di un cluster ed il centro del cluster
37
CRITERI DI OMOGENEITÀ
 critero SOMMA DEI QUADRATI: somma delle distanze euclidee
al quadrato tra i punti di cluster ed il centro
sq(V) 
i
2
[d
(v
,
v
)]
 2
v i V
 4
v 
1 
 
2
1 1
X=
5 2
6 0
1
9
2
5
sq(V)  16
16
3 vr(V) 
3
 critero VARIANZA: somma dei quadrati normalizzata
1
vr(V) 
sq(V)
|V |
38
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
39
K-MEANS
critero SOMMA DEI QUADRATI: problema k-means
Teorema di Huyhen La somma delle distanze al quadrato tra i punti
di un cluster ed il centro è pari al rapporto tra la somma delle
distanze al quadrato tra i punti del cluster ed il numero di punti
1
2
i
j
d
(v
,
v
)

d
(v
,
v
)



2
|V|v i Vv jV
v i V
2
2
i
Formulazione del
problema del K-means
40
K-MEANS – ALGORITMO EURISTICO
INPUT il numero k di cluster
1. seleziona in maniera del tutto casuale k punti
2. assegna ogni punto al cluster il cui centro sia più vicino
3. calcola nuovamente i centri dei cluster
4. Se non è verificato il criterio di convergenza, torna al passo 2
Criterio di convergenza
 non ci sia alcun assegnamento nuovo possibile di alcun punto
da un cluster ad un altro (passo 2 non cambia nulla)
 la
funzione
di
errore
quadratico
cessi
di
ridursi
significativamente dopo un certo numero di iterazioni (passo 3
non cambia nulla)
41
K-MEANS – ALGORITMO EURISTICO
Passo I seleziona in maniera del tutto
casuale k punti all’interno dell’insieme di dati
K=3
Passo II assegna ogni punto al cluster
il cui centro sia più vicino al punto in esame
42
K-MEANS – ALGORITMO EURISTICO
Passo III calcola nuovamente i centri
dei cluster secondo la configurazione attuale
Passo IV assegna ogni punto al cluster
il cui centro sia più vicino al punto in esame
K=3
43
K-MEANS – ALGORITMO EURISTICO
Passo V calcola nuovamente i centri
dei cluster secondo la configurazione attuale
Passo VI assegna ogni punto al cluster
il cui centro sia più vicino al punto in esame
K=3
44
K-MEANS – ALGORITMO EURISTICO
Passo VII calcola nuovamente i centri
dei cluster secondo la configurazione attuale
Passo VIII assegna ogni punto al cluster
il cui centro sia più vicino al punto in esame
K=3
45
K-MEANS – ALGORITMO EURISTICO
Passo IX calcola nuovamente i centri
dei cluster secondo la configurazione attuale
Passo X assegna ogni punto al cluster
il cui centro sia più vicino al punto in esame
K=3
46
K-MEANS – ALGORITMO EURISTICO
Passo XI calcola nuovamente i centri
dei cluster secondo la configurazione attuale
Passo XII assegna ogni punto al cluster
il cui centro sia più vicino al punto in esame
K=3
STOP
Nessuna nuova
47
assegnazione possibile
MATERIALE DEL SEMINARIO
Le slide di questo seminario sono reperibili
 nella pagina del corso di Algoritmi di Classificazione e Reti Neurali
 nella pagina del corso di Ottimizzazione Combinatoria, nella
sezione “clustering dei dati” (prime 4 lezioni)
http://www.dis.uniroma1.it/~or/gestionale/OC/
48