Algoritmi di classificazione e reti neurali
Seminario su clustering dei dati
A.A. 2013-2014
a cura di Silvia Canale
contatto e-mail: [email protected]
Università Sapienza di Roma
Dipartimento di ingegneria Informatica,
Automatica e Gestionale
Corso di Laurea in “Ingegneria Gestionale”
ARGOMENTI DEL SEMINARIO
 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
 Problema k-means
2
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).
3
DEFINIZIONE DEL PROBLEMA
Un cluster è un gruppo di oggetti simili.
Se gli oggetti sono punti in uno spazio di distanza allora 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.
1
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
1
4
5
4
4
APPRENDIMENTO AUTOMATICO
Apprendimento: Processo di ragionamento induttivo che permette di
passare dalle osservazioni alle regole generali (tipico dell’uomo che
impara dall’esperienza)
REGOLE
Processo
deduttivo
INFORMAZIONE
Processo
induttivo
OSSERVAZIONI
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
5
decisioni
APPRENDIMENTO AUTOMATICO
Processo automatico di estrazione di informazioni su un sistema
fisico S incognito partendo da un insieme finito di n osservazioni.
c1
c2
c3
cn
S
v1
v2
v3
vn
L’insieme { v1, v2, …, vn } prende il nome di training set.
Apprendimento non 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 supervisionato (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.
6
ESTRAZIONE DELLA CONOSCENZA
APPRENDIMENTO
AUTOMATICO
Valutazione
regole
Informazione
Data Mining
Selezione e
trasformazione
dei dati
Regole
Pulizia ed
integrazione
dei dati
Datawarehouse
Database
7
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
- …
8
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
DESCRIZIONE COMPATTA
E SINTETICA DEI CLUSTER
 studio dell’andamento dei cluster
 analisi della validità dei cluster
 confronto esterno
 confronto interno
 controllo relativo
9
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à
10
MATRICE DELLE ISTANZE
Un’osservazione (o istanza) v è rappresentata da un vettore di m
caratteristiche (o attributi).
v =
v1
v2
…
…
vm
L’insieme X = { v1, v2, …, vn } delle osservazioni viene rappresentato
come una matrice n x m detta matrice delle istanze.
X=
v11
v12
....
v1m
v12
v 22
....
v 2m
....
....
....
....
v1n
v 2n
....
v nm
11
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.
12
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=
r11
r12
....
r1n
r21
r22
....
r2n
....
....
....
....
rn1
rn2
....
rnn
Consideriamo relazioni simmetriche ( rij  rji per ogni i, j  V ) e in
particolare:
 relazioni di similarità (più vi e vj sono simili, più rij è grande)
 relazioni di dissimilarità (più vi e vj sono simili, più rij è basso) 13
DISTANZE
Una distanza d definita sull’insieme X è una relazione che gode delle
seguenti proprietà:
a) d è simmetrica d(i, j)  d(j, i) per ogni coppia (i,j) in V.
b) d assume valore nullo d(i, i)  0 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
v2
v2
d(i, j)  d(i, k)  d(k, j)
allora d è una semimetrica sull’insieme X. v1
1
v1
4
1
3
2
v3
4
v3
Si definisce metrica una semimetrica d che soddisfa l’ulteriore
proprietà: d(i, j)  0  i  j
14
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à:
d (v i , v j ) := vi - v j
METRICA
NORMA
Consideriamo lo spazio normato (m, || • ||p) dove || • ||p è la norma lp
m
1
p p
v p  (|v k | )
k 1
15
UNA METRICA NORMA È UNA METRICA
Dim. Sia || • || : X  + una norma definita su X. La funzione
d  (v i , v j )  v i - v j
a)
è simmetrica
||  v || = |  | || v ||
d  (v i , v j )  v i - v j  -1(v j - v i ) | 1 | v j - v i  v j - v i  d  (v j , v i )
b)
d assume valore nullo per ogni coppia (i,i) in V.
|| v || = 0  v = 0
d  (v i , v i )  v i - v i  0  0
c)
d soddisfa la diseguaglianza triangolare per ogni terna (i,j,k)
ini V j
d  (v , v )  v i - v j  v i - v j  v k  v k  (v i  v k )  (v k  v j ) 
|| vi + vj ||  || vi || + || vj ||
 (v i  v k )  (v k  v j )  d  (v i , v k )  d  (v j , v k )
16
METRICHE NORME
Una classe molto importante di metriche è quella delle metriche dlp
indotte dalle diverse norme lp:
d  (v i , v j )  v i - v j
p
1
p p
m
p
 (|v ik - v kj | )
k 1
 p = 1 – distanza di Manhattan o metrica “city-block”
m
d  (v , v )  |v ik - v kj |
i
j
1
k 1
 p = 2 – distanza Euclidea
d  (v , v ) 
i
j
2
 p =  – distanza di Lagrange
d  (v i , v j )  v i - v j

m
|v
k 1

i
k
- v kj |2
 max | v ik - v kj |
k 1,...,m
 p = 0 – distanza di Hamming
d  (v i , v j )  v i - v j
0
0
|{ k  1,..., m :|v ik - v kj |  0}|
17
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
k
  Vj  X
j1
 Vi  V j  0
i, j  1,..., k
i j
18
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!
n(n  1)
m
2
19
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 ViP(G) vengono definiti componenti o clique del
clustering P(G).
Dato un grafo G(N,A) si definisce clique un sottoinsieme V  N dei
nodi tali che per ogni coppia di nodi i e j l’arco ij appartiene ad A.
G(N, A)
1
V1  {1,2,3,4}
5
V2  {3,4,5,6}
4
6
2
3
V3  {1,2,4,5}
NON è una clique:
25  A
Se il grafo G(N,A) è completo, ogni
sottoinsieme V  N è una clique. 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).
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
δ(Vh )  ij  A|i  Vh , j  Vh 
j
V
i
Se |Vh| = 1, (Vh) è la stella del nodo in Vh.
δ(V)
21
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
δ(Vh , Vl )  ij  A|i  Vh , j  Vl 
In generale, dati k sottoinsiemi
V1,…, Vk  N, l’insieme
degli archi con estremi in due
sottoinsiemi diversi viene
indicato con
V2
V1
V3
δ(V1, V3 )
V2
V1
V3
δ(V1, V2 , V3 )
δ(V1,...., Vk )  ij  A|i  Vh , j  Vl , h, l  1,..., k, h  l
22
INSIEME DELLE SOLUZIONI – DEFINIZIONI
Ad ogni clustering P(G)= { V1, V2, …, Vk } del grafo G(N,A) è possibile
associare un insieme multi-cut (P(G))
(P(G)) = ( V1, V2, …, Vk ) V2
V3
Definiamo il vettore di incidenza yP
di un insieme multi-cut (P(G))
y P  0,1
m
1 ij  δ(P(G))
y ij  
0 otherwise
V1
V4
δ(V1, V2 , V3 , V4 )
23
INSIEME DELLE SOLUZIONI – DEFINIZIONI
Sia Vi  N. Indichiamo con E(Vi) l’insieme degli archi che connettono
nodi in Vi.
E(Vi )  uv  A|u  Vi , v  Vi 
v
Se |Vi| = 1, E(Vi) è vuoto.
V1
In generale, dati k sottoinsiemi
V1,…, Vk  N, l’insieme degli
archi con estremi nello stesso
sottoinsieme viene indicato con
E(V1,...., Vk )  E(V1 )  ...  E(Vk )
V2
V1
u
E(V1 )
V3
E(V1, V224, V3 )
INSIEME DELLE SOLUZIONI – DEFINIZIONI
Ad ogni clustering P(G)= { V1, V2, …, Vk } del grafo G(N,A) è possibile
associare un insieme partizione E(P(G))
E(P(G)) = E( V1, V2, …, Vk ) V2
V3
Definiamo il vettore di incidenza xP
di un insieme partizione E(P(G))
x P  0,1
m
1 ij  E(P(G))
x ij  
0 otherwise
V1
V4
E(V1, V2 , V3 , V4 )
Gli insiemi multi-cut e partizione
definiscono una partizione di A
x P  y P  1m
25
VETTORE DI INCIDENZA DI UNA PARTIZIONE
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 }
6 E(V2 ) 7
3
8
V1
P(G)   V1, V2 , V3 
E(V3 )
V2
1
4
E(V1 )
2
5
V3
xP 
 x12   1 

  
 x13   0 
 x  0
 14   
 x15   0 
x   
 16   0 
 x17   0 

  
 x18   0 
 x 23   0 

  
 x 24   0 
 x  0
 25   
 x 26   0 
 x  0
 27   
 x 28   0 

  
 x 34    1 
 x 35   1 

  
 x 36   0 
 x  0
 37   
 x 38   0 
 x  1
 45   
 x 46   0 

  
 x 47   0 
 x 48   0 

  
 x 56   0 
 x 57   0 

  
 x 58   0 
 x  1
 67    26
 x 68   1 
x   
 78   1 
INSIEME DELLE SOLUZIONI
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.

S  x P  {0,1} m : x P vettore di incidenza di E(P(G))

Supponiamo di voler determinare una partizione in k cluster.
n
Sia s =   . Se vogliamo che i cluster contengano un numero uguale
k 
di osservazioni, il problema è equivalente al problema di determinare
una partizione in cluster che abbiano ciascuno un numero di
osservazioni non inferiori a s.
i
δ(i)
Vincolo di dimensione
j
x
k
2
s =3 x ij  x ik  s  1
ijδ(i)
ij
 s  1 i  N
27
PROBLEMA DI PARTIZIONE IN CLIQUE
Consideriamo 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
}
In base al valore di s possiamo avere diversi problemi:
 se s  1, S è l’insieme delle soluzioni del problema di partizione in
clique (CPP) dei nodi di un grafo
 se s  1, S è l’insieme delle soluzioni del problema di partizione in
clique con vincolo di dimensione (CPPMIN)
 se k = 2, S è l’insieme delle soluzioni del problema di equipartizione
 se n è multiplo di s, S è l’insieme delle soluzioni del problema di
N
equipartizione in k sottoinsiemi  x ij  s 1   x ij  s 1 i28
ijδ(i)
ijδ(i)
CRITERIO DI OTTIMALITÀ
Come valutare le soluzioni in S? Qual è la migliore soluzione?
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 }
7
6
7
6
3
4
3
8
4
V6
8
V2
5
1
V1
5
V3
2
1
V5
2
V4
In P1(G) i punti appartenenti allo stesso cluster sono più vicini…
29
CRITERIO DI OTTIMALITÀ
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ù d ij è basso)
Assegniamo ad ogni arco ij di A il peso d ij
6
1
7
6
3
1
1
1
4
1
8
1
V2
1
1
3
2
V1
5
V3
1.5
2
4
3
5
1
1
V6
8
3
1
7
1
V5
3
2
V4
30
CRITERIO DI OTTIMALITÀ
Assegniamo ad ogni arco ij di A il peso d ij
Assegniamo ad ogni cluster V  N
la somma dei pesi degli archi in E(V)
c(V) 
d
ijE(V)
ij
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))   c(Vi )
c(P1(G))
6
1
<
= 1.5 + 3 + 3 = 7.5
c(V2 )  3
7
1
c(V3 )  3
3 1 4
1
8
1
V2
c(P2(G))
= 15
c(V5 )  11
c(V6 )  1
6 1 7
V6
1
1
2
P 1(G) è migliore 3
di P (G)
4
1
8
3
1
Vi P(G)
3
2
5
1
V
1.5
2
c(V1 )  1.5
5
V3
3
1
V5 c(V
4
2
) 3
31
V
CRITERIO DI OTTIMALITÀ
Ad ogni partizione P(G)= { V1, V2, …, Vk } del grafo G(N,A) associamo
il costo
c(P(G)) 
 c(V )
Vi P(G)
i
Ad ogni P(G)= { V1, V2, …, Vk } è associato il vettore di incidenza xP di
un insieme partizione E(P(G))
E(P(G))  E(V1,..., Vk )
x P  0,1
m
V
i
1 ij  E(P(G))
x ij  
0 otherwise
x ij
x ij  1 ij  E(Vh ),
h  1,..., k
j
x ik x jk
E(V) k
c(P(G)) =
∑d
ij
ij∈E(P (G))
= ∑d ijx ij
ij∈A
32
CRITERIO DI OTTIMALITÀ
Ad ogni partizione P(G)= { V1, V2, …, Vk } del grafo G(N,A) associamo
il costo
c(P(G))   d ijx ij
ijA
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 }
6
1
c(V2 )  3
7
c(V3 )  3
3 1 4
1
1
xP 
8
1
V2
1
5
1
V
1.5
2
c(V1 )  1.5
 x12   1 

  
 x13   0 
 x  0
 14   
 x15   0 
x   
 16   0 
 x17   0 

  
 x18   0 
 x 23   0 

  
 x 24   0 
 x  0
 25   
 x 26   0 
 x  0
 27   
 x 28   0 

  
 x 34    1 
 x 35   1 

  
 x 36   0 
 x  0
 37   
 x 38   0 
 x  1
 45   
 x 46   0 

  
 x 47   0 
 x 48   0 

  
 x 56   0 
 x 57   0 

  
 x 58   0 
 x  1
 67   
 x 68   1 
x   
1
V3
c(P(G))   d ijx ij 
ijA
d12  d 34  d 35  d 45
 d 67  d 68  d 78  7.5
33
FORMULAZIONE MATEMATICA DEL CPP
Risolvere il problema di partizione in clique dei nodi di un grafo
significa determinare la soluzione del seguente problema
min  d ijx ij
ijA
x S
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
34
}
FORMULAZIONE DI UN PROBLEMA DI PL01
Sia S l’insieme delle soluzioni di un problema di Programmazione
Lineare 0–1
min c T x
x 
 1


 
x 
 1


 0
x
x S


 
12
13
14
Esempio CPP – Dato un grafo G(N,A)
G(N, A)
1
P1 (G)   V1 , V2 
5
x P1 
4
6
2
3
P2 (G)   V3 , V4 
 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
0 
0

0
0

0
0

1
1

1 
P3 (G)   V5 , V6 
S è l’insieme di tutte le possibili partizioni in clique di G(V,A)
S  { x P  {0,1} : x P vettore di incidenza di P(G) }
m
min  d ijx ij
ijA
x S
35
FORMULAZIONE DI UN PROBLEMA DI PL01
Indichiamo con x* la soluzione ottima del problema di PL01
x*  arg min c T x
x S
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
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.
d x
ijA
ij
ij
Scegli la partizione in clique che produce la soluzione di costo minimo
L’enumerazione completa di tutte le soluzioni in S
richiede tempi molto lunghi
36
SOLUZIONE DI UN PROBLEMA DI PL01
Formulare non implica risolvere un problema di PL0.
In generale, la soluzione di un problema di PL01 richiede algoritmi
sofisticati e molto efficienti.
Gli algoritmi di soluzione possono essere:
 di tipo esatto: determinano sempre la soluzione ottima
 approssimati: determinano sempre una soluzione ammissibile
Quanto è buona 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
37
SEMISPAZI E POLIEDRI
Siano
• A  Rpxm una matrice reale di p righe e m colonne
• b  Rp un vettore reale di p componenti
L’insieme dei vettori xRm che soddisfano le p disequazioni
del sistema
a Tqx ≤ bq
Ax ≤ b
è definito POLIEDRO e viene indicato con la lettera P
P = { x  Rm : Ax ≤ b }
xP

a Tqx ≤ bq per q = 1, …, p
38
SEMISPAZI E FORMULAZIONI
Geometricamente, ogni disequazione del sistema Ax ≤ b individua un
semispazio
Esempio – m = 2 Consideriamo la retta
x2
P=
1
 x1  x 2  1
2
{xR
2
:
1
 x1  x 2  1 }
2
x1
Quindi un poliedro P è intersezione di un numero finito q di semispazi.
P
P = { x  Rp : Ax ≤ b }
39
FORMULAZIONE DI UN PROBLEMA DI PL01
Sia S l’insieme delle soluzioni di un problema di Programmazione
Lineare 0–1.
Il poliedro P è una formulazione del problema di Programmazione
 0
1
 
 
Lineare 0–1 se e solo se
1 
1
 
 
x2
P  {0,1}m = S
 contiene tutti i vettori di S:
P
SP
 non contiene alcun vettore di S’ ={ 0,1}m \ S:
 0
 
 0
 
x1
1 
 
 0
 
P  S’ = 
Ci sono infinite formulazioni dello stesso problema di PL01.
Per ognuna vale l’ovvia proprietà:
min { cTx: x  S } = min { cTx: x  P {0,1}m } = cTx*
40
FORMULAZIONI E LOWER BOUND
Per ogni formulazione P vale inoltre la disuguaglianza
min { cTx: x  P {0,1}m }  min { cTx: x  P }
Il valore
LB(P) = min { cTx: x  P }
viene definito lower bound del problema di PL01.
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 }
41
FORMULAZIONE OTTIMA
Esiste una formulazione P* migliore di tutte le altre?
SI
Argomento trattato nel corso di
Ottimizzazione Combinatoria (III anno)
x2
P* = conv( S )
P*
x1
Inoltre….
Una disequazione aTx  b si definisce valida per un poliedro P se e
solo se è soddisfatta da tutti i punti in P
P  { x  Rp : aTx  b }
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*
42
DISEQUAZIONI TRIANGOLO
Consideriamo tre nodi i, j, k N di G(N,A)
Si definisce disequazione triangolo relativa ai nodi i, j, k
x ij  x ik  x jk  1
Una disequazione triangolo rappresenta il vincolo logico:
G(N, A)
i
se x ij  1 e x ik  1 
x jk  1
j
k
43
i
 x ij   0 

  
 x ik    0 
 x  0
 jk   
k
j
 x ij   1 

  
 x ik    0 
 x  0
 jk   
(a)
k
j
i
NO
k
j
i
 x ij   1 

  
 x ik    0 
 x  1
 jk   
k
j
(f)
i
j
(g)
k
j
(d)
(e)
 x ij   0 

  
 x ik    1 
 x  1
 jk   
i
 x ij   0 

  
 x ik    0 
 x  1
 jk   
(c)
 x ij   1 

  
 x ik    1 
 x  0
 jk   
k
j
(b)
i
 x ij   0 

  
 x ik    1 
 x  0
 jk   
i
k
i
 x ij  1

  
 x ik   1
 x   1
 jk   
j
(h)
k
44
FORMULAZIONE DEL PROBLEMA CPP
Consideriamo il poliedro definito dalle disequazioni triangolo relative
a tutte le terne di nodi G(N,A)
 x ij  x ik  x jk

m
P'  { x  R :  x ij  x ik  x jk
 x  x  x
ij
ik
jk

0  x ij
1
 1 per 1  i  j  k  m,
1
 1 per 1  i  j  m }
È facile verificare che P’ è una formulazione del problema CPP
G(N, A)
1
5
4
6
2
3
P1 (G)   V1 , V2 
P  {0,1}m = S
x P1 
 x12 


 x13 
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 



















45 


1

1
0

0
0

1
0 
0

0
0

0
0

1
1

1 
i
 x ij   0 

  
 x ik    0 
 x  0
 jk   
k
j
 x ij   1 

  
 x ik    0 
 x  0
 jk   
(a)
k
j
i
NO
k
j
i
 x ij   1 

  
 x ik    0 
 x  1
 jk   
NO
k
j
(f)
i
j
(g)
k
j
(d)
(e)
 x ij   0 

  
 x ik    1 
 x  1
 jk   
i
 x ij   0 

  
 x ik    0 
 x  1
 jk   
(c)
 x ij   1 

  
 x ik    1 
 x  0
 jk   
k
j
(b)
i
 x ij   0 

  
 x ik    1 
 x  0
 jk   
i
NO
k
i
 x ij  1

  
 x ik   1
 x   1
 jk   
j
(h)
k
46
FORMULAZIONE DEL PROBLEMA CPP
Le disequazioni triangolo sono tante.
3 disequazioni per ogni terna ordinata di nodi
Consideriamo il rilassamento lineare del problema
x  {0,1}m
min  d ijx ij
ijA
min  d ijx ij
S  P’
ijA
x S
 n
3 
3 
 
x  P'
Ora sono ammissibili soluzioni non intere
1
1
1
4
2
1
2
5
1
2
1
2
1
4
4
1
4
3
2
6
P1(G)  ..... 
?
x P1 
 x12 


 x13 
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 
 1 
 2


 1 
 2


 0 


 0 


 0 


 1 
 2


 0 


 0 


 0 


1 
 4 


 0 


 0 


 1 
 4


 14 


 1 
 2
47
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 partizioni (S,T) associata ai sottoinsiemi S e T è
x( δ(S, T) )  x(E(S))  x(E(T))  min{ |S|,| T|}
S
min{1,3}
1
x12  x13  x14  x 23  x 24  x 34  1
T
2
4
3
x( δ(S, T) ) x(E(T))
E(S)  
Una disequazione a 2 partizioni (S,T) associata ai sottoinsiemi S e T
definisce è valida per il poliedro P*.
Definisce una faccia di P* se e solo se
|S|| T|
48
DISEQUAZIONI A 2 PARTIZIONI
Sia P’’ il poliedro costituito da tutte le disequazioni a 2 partizioni
(S,T) con |S|  |T|
Osservazione Le disequazioni triangolo sono disequazione a 2
partizioni (S,T) con |S|= 1 e |T| = 2
 x12   12 


P’’  P’
 x13   12 
x  1 
Esempio Consideriamo il grafo G(N,A) e la soluzione xˆ   14    2 
 x 23   0 

x  
S
1
x̂ soddisfa tutte le 12
xˆ  P'
 24   0 

 x  
disequazioni triangolo
1
1
23

  0 
2
2
T
x̂ non soddisfa la
0
2
1
2
0
4
0
3
disequazione a 2 part.
S = { 1 } e T = { 2, 3, 4 }
x12  x13  x14  x 23  x 24  x 34  1
xˆ  P' '
P’’  P’
49
1  1  1 000
1
2
2
2
DISEQUAZIONI A 2 PARTIZIONI
x’ P’
Quindi…
P*  P’’  P’
P*
P’’
Data una soluzione x’ appartenente a P’ è possibile determinare S e
T tali che la disequazione a 2 partizioni (S,T) sia violata da x’ ?
PROBLEMA DI SEPARAZIONE
delle disequazioni a 2 partizioni (S,T)
S
1
T
1
1
2
0
2
1
x(δ(S, T))  x(E(S))  x(E(T))  min{ |S|,| T|}
2
0
4
2
come individuare S e T tale che
0
3
50
EURISTICA DI SEPARAZIONE
Sia x’ una soluzione appartenente a P’.
Vogliamo determinare, se esiste, una
disequazione a 2 partizioni (S,T) con |S|=1
ALGORITMO EURISTICO
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’ T
se |T|>1 e x’((S,T))>1, la disequazione a 2 partizioni (S,T) è violata
La soluzione dipende dall’ordinamento!
51
complessità O(n3)
EURISTICA DI SEPARAZIONE
ESEMPIO Consideriamo la soluzione x’ in figura e applichiamo
l’algoritmo euristico di separazione
S
1
T
1
1
2
0
2
1
Sia i = 1 e poniamo S = { 1 }
2
0
4
2
Iterazione 1
0
3
Definiamo W = { 2, 3, 4 } e scegliamo come
ordinamento dato dalla permutazione naturale
Poniamo T = { 2 } e verifichiamo:
T = { 2, 3 }
T = T  { 3 } se x32’ = 0
T = T  { 4 } se x43’ = 0 e x42’ = 0
x’(S,T)= 3 / 2 >1
T = { 2, 3, 4 }
x(δ(S, T)) x(E(S))  x(E(T))  1
x(δ(S, T))  x(E(S))  x(E(T))  1
52
EURISTICA DI SEPARAZIONE
S
1
T
1
1
2
0
2
1
Sia i = 2 e poniamo S = { 2 }
2
0
4
2
Iterazione 2
0
3
Definiamo W = { 1 }
Poniamo T = { 1 }
|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 è
x12  x13  x14  x 23  x 24  x 34  1
53
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 triangolo relative ai nodi i, j, k
x ij  x ik  x jk  1
P’
 le disequazioni a 2 partizioni (S,T) associate ai sottoinsiemi S e T
x( δ(S, T) )  x(E(S))  x(E(T))  min{|S|,|T|}
P’’
54
ALGORITMO DEI “PIANI DI TAGLIO”
ALGORITMO DI SOLUZIONE
P0
Definisci il poliedro P0  P’ definito da un
sottoinsieme di disequazioni triangolo
Poni h = 0
P’
P*
risolvi il problema di PL
min
d
ijA
ij
x ij
x  Ph
sia xh la soluzione ottima del problema di PL
x0
esiste una disequazione triangolo violata da xh ?
SI
h
x  P’ : aggiungi la disequazione a P
e definisci il nuovo poliedro Ph+1
P0
P1
P’
h
P*
55
ALGORITMO DEI “PIANI DI TAGLIO”
ALGORITMO DI SOLUZIONE
P0
esiste una disequazione triangolo violata da xh ?
NO
P’
h
x  P’
P*
xh  {0,1}m ?
SI
xh  S : xh è la soluzione ottima
STOP
NO
x0
xh  S : esistono due insiemi S e
T tali che la disequazione a 2
P0
partizioni (S,T) sia violata da xh?
SI
xh  P’’ : aggiungi la
disequazione a Ph e
definisci il nuovo
poliedro Ph+1
P’’ P’
P*
x0
56
ALGORITMO DEI “PIANI DI TAGLIO”
ALGORITMO DI SOLUZIONE
P0
esistono due insiemi S e T tali che la disequazione
P’’ P’
a 2 partizioni (S,T) sia violata da xh?
NO
xh  P’’
VERO se l’algoritmo
di separazione è esatto
P*
x0
xh  {0,1}m ?
SI
xh  S : xh è la soluzione ottima
STOP
NO
P0
h
x  S : applica il metodo del
branch and bound per risolvere il
problema di PL01
min  d ijx ij
P*
ijA
x  P h  {0,1} m
P’’ P’
x0
STOP
57
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
58
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
59
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 
60
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
61
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 62

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?
63
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 }
64
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 }
65
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 }
66
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 }
67
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
68
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
69
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
}
70
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 
71
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?
72
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 }
73
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 }
74
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
75
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 }
76
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 }
77
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 }
78
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
9
4
4
9
6
9
4
9
5 che x2  P’’ e andiamo avanti
non possiamo dire
x2  {0,1}m ? NO
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
79
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
80
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
81
per determinare un upper bound
PROBLEMA CPP – 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
82
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
83
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 }
84
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
85
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à?
86
}
CRITERI DI OTTIMALITÀ
I criteri di ottimalità sono funzioni che associano un valore
numerico a 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)
87
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
1
1
8
V2 3 2
1
V1
4
7
3
4 3
2
3
3
1.5
2
 c(V )
i
Vi P(G)
c(V2 )  2
7
1
c(P(G)) 
c(V3 )  2
3 1 4
5
5
4
c(V1 )  2
1
5
V3
88
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 |)
89
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
r(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
90
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
91
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
92
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 |
93
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
94
ALGORITMO K-MEANS
Passo 1 Noto il numero k di cluster da individuare nella
partizione, seleziona in maniera del tutto casuale k punti
all’interno dell’insieme di dati.
Passo 2 Assegna ogni pattern al cluster il cui CENTRO sia più
vicino al pattern in esame
v j ↔Vi* : i* = arg min [d  2 (v j , vi )]2
i=1,.., k
Passo 3 Calcola nuovamente i CENTRI dei cluster secondo la
configurazione attuale
1
vi =
vj
∑
| Vi | v j∈Vi
i = 1,...k
Passo 4 Se non è verificato il criterio di convergenza, torna al
Passo 2.
95
ALGORITMO K-MEANS
Passo 1 Noto il numero k di cluster da individuare nella
partizione, seleziona in maniera del tutto casuale k punti
all’interno dell’insieme di dati.
 Buone configurazioni di partenza
e.g. Neat trick: Posiziona il primo centro casualmente
all’interno dell’insieme di dati in input. Per ogni successivo
centro j, scegli scegli all’interno dell’insieme di dati in input il
punto che sia il più lontano possibile dai primi j-1 centri.
 Running multipli a partire da diverse configurazioni di
partenza
96
ALGORITMO K-MEANS
Passo 4 Se non è verificato il criterio di convergenza, torna al
Passo 2.
 non ci sia alcun assegnamento nuovo possibile di alcun
pattern da un cluster ad un altro (al Passo 2 non cambia nulla)
 la funzione di errore quadratico cessi di ridursi
significativamente dopo un certo numero di iterazioni (al Passo
3 non cambia nulla)
 Buone configurazioni di partenza
 Neat trick: Place first center on top of randomly chosen
datapoint. Place j’th center on datapoint that’s as far away
as possible from the closest of Centers 1 through j-1
 Running multipli a partire da diverse configurazioni di
partenza
97
MATERIALE DEL SEMINARIO
Le slide di questo seminario sono reperibili al seguente link:
http://www.dis.uniroma1.it/~canale/didattica/ACRN_2013.ppt
98