CAPITOLO 14
CLASSIFICAZIONE
La Clusterizzazione e
La Classificazione non supervisionata
A. Dermanis, L. Biagi
Clusterizzazione
Clusterizzazione = divisione di N pixel in K classi ω1, ω2, …, ωK
media della classe ωi :
1
mi = n
i
x
xi
matrice di dispersione della classe ωi :
Si =
 (x – m )(x – m )
i
i
T
xi
matrice di covarianza della classe ωi :
1
C i = n Si
i
matrice di dispersione totale:
media globale
ST =
m=
1
N
 x
i
xi
  (x – m)(x – m)
i
T
xi
matrice di covarianza totale:
1
C T = ST
N
A. Dermanis, L. Biagi
Criteri di clusterizzazione
indice di coerenza delle classi  matrice di dispersione interna
Sin =
 S =   (x – m )(x – m )
i
i
i
i
i
T
xi
indice di distanza fra le classi  matrice di dispersione esterna
Sex =
n
i
(mi – m)(mi – m)T
ST = Sin + Sex = costante
i
Algoritmo ottimale: Sin = min e Sex = max contemporaneamente
Problema: Quanti cluster ? (K = ?)
Scelta estrema:
mk = xk,
K=N
Sk = 0,
(una classe per ogni pixel)
Sin =
 S = 0 = min,
k
k = {xk}
Sex = ST =max
k
Scelta estrema:
K=1
(un’unica classe)
Sin = ST, Sex = 0
A. Dermanis, L. Biagi
Clusterizzazione gerarchica
1
2
3
4
5
6
B
C
D
DIVISIVE
AGGLOMERATIVE
A
Agglomerativa:
Ad ogni passo
vengono uniti
i due cluster più vicini
Divisiva:
Ad ogni passo
il cluster più disperso viene
diviso in due nuovi cluster
E
Sono necesssari:
F
Criteri di unione.
Criteri di divisione.
A. Dermanis, L. Biagi
Clusterizzazione gerarchica
6
1
2
3
4
5
6
B
C
DIVISIVE
AGGLOMERATIVE
A
5
4
D
3
E
F
1
2
ABCDEF
A. Dermanis, L. Biagi
Distanza fra due cluster (alternative):
distanza media:
1
d 
ni n k
  || x  x ||
x
i
x
k
|| x  x ||  (x  x) T (x  x)
distanza minima:
d min 
distanza massima:
d max 
min
x i , x k
|| x   x ||
max || x   x ||
x i , x k
Utilizzate nella clusterizzazione gerarchica
A. Dermanis, L. Biagi
L’algoritmo K-means (o delle medie mobili)
9
16
14
8
15
13
12
7
6
11
5
4
10
4
6
3
5
2
2
3
1
8
1
1
9
7
2
3
4
5
6
7
8
9
A. Dermanis, L. Biagi
L’algoritmo K-means (o delle medie mobili)
Passo 0:
9
16
14
8
15
13
12
7
6
Selezione di K = 3 pixel
come posizioni iniziali delle medie
11
5
4
10
4
6
3
5
2
2
3
1
8
1
1
9
7
2
3
4
5
6
7
8
9
A. Dermanis, L. Biagi
L’algoritmo K-means (o delle medie mobili)
Passo 1:
9
16
14
8
15
13
12
7
6
Assegnazione di ogni altro pixel al cluster
con la media più vicina.
11
5
4
10
4
Ricalcolo delle nuove medie
per ogni cluster.
6
3
5
2
2
3
1
8
1
1
9
7
2
3
4
5
6
7
8
9
A. Dermanis, L. Biagi
L’algoritmo K-means (o delle medie mobili)
Passo 2:
9
16
14
8
15
13
12
7
6
Riassegnazione di ogni pixel al cluster
con la media più vicina.
11
5
4
10
4
Ricalcolo delle nuove medie
per ogni cluster.
6
3
5
2
2
3
1
8
1
1
9
7
2
3
4
5
6
7
8
9
A. Dermanis, L. Biagi
L’algoritmo K-means (o delle medie mobili)
Passo 3:
9
16
14
8
15
13
12
7
6
Riassegnazione di ogni pixel al cluster
con la media più vicina.
11
5
4
10
4
Ricalcolo delle nuove medie
per ogni cluster.
6
3
5
2
2
3
1
8
1
1
9
7
2
3
4
5
6
7
8
9
A. Dermanis, L. Biagi
L’algoritmo K-means (o delle medie mobili)
Passo 4:
9
16
14
8
15
13
12
7
6
Riassegnazione di ogni pixel al cluster
con la media più vicina.
11
5
4
10
4
Tutti i pixel rimangono
nella classe in cui erano.
Le medie non cambiano.
6
3
5
2
2
3
1
8
1
1
9
7
2
3
4
5
6
7
Fine della clusterizzazione !
8
9
A. Dermanis, L. Biagi
L’algoritmo Isodata
Una variante di quello K means.
Ad ogni passo una delle 3 seguenti procedure:
1. ELIMINAZIONE
Elimina cluster
con pochi pixel
2. UNIONE
Unisci coppie di cluster
reciprocamente vicini
3. DIVISIONE
Dividi cluster
dispersi in due nuovi
cluster
A. Dermanis, L. Biagi
L’algoritmo Isodata
1. ELIMINAZIONE
Elimina cluster
con pochi pixel
A. Dermanis, L. Biagi
L’algoritmo Isodata
2. UNIONE
Unisci coppie di cluster
reciprocamente vicini
A. Dermanis, L. Biagi
L’algoritmo Isodata
3. DIVISIONE
Dividi cluster
dispersi in due nuovi
cluster
A. Dermanis, L. Biagi
L’algoritmo Isodata
Il processo di unione
Il processo di divisione
m2+kσ2
m2
m2–kσ2
m1
A. Dermanis, L. Biagi
Esempi di
classificazione:
l’algoritmo K-means
K-means: 3 classi
K-means: 5 classi
K-means: 7 classi
K-means: 9 classi
A. Dermanis, L. Biagi
Esempi di
classificazione:
l’algoritmo ISODATA
ISODATA : 3 classi
ISODATA : 7 classi
ISODATA : 5 classi
ISODATA : 9 classi
A. Dermanis, L. Biagi