Pattern Recognition
Lez.13: Unsupervised
classification: clustering
gerarchico
Clustering per “dicotomie successive”
• Quando una popolazione va divisa in
sottogruppi? Quando al suo interno non
c’è sufficiente omogeneità.
• Questa idea è alla base di un altro
approccio al clustering, detto clustering
gerarchico.
• L’idea si concretizza in un paio di algoritmi
abbastanza facili da descrivere e
implementare.
La popolazione e la matrice delle
distanze
• Possiamo didatticamente presentare il clustering
gerarchico assumendo che siano date una
popolazione di N record da ripartire e una
matrice D, di N x N elementi in cui ciascun
elemento Dij riporta la “distanza” tra il record iesimo e il record j-esimo.
• Attenzione non sempre nelle reali
implementazioni tale matrice è calcolata per
intero (per ragioni di efficienza o di limiti di
memoria).
Un esempio “saccheggiato” da
Internet
BA
FI
MI
NA
RM
TO
BA
0
662
877
255
412
996
FI
662
0
295
468
268
400
MI
877
295
0
754
564
138
NA
255
468
754
0
219
869
RM
412
268
564
219
0
669
TO
996
400
138
869
669
0
Distanze in chilometri tra città italiane
Struttura di ogni algoritmo di
clustering gerarchico
Passo 0: ogni record è l’unico rappresentante di
una classe che lo contiene. Ci sono quinid
all’inizio N classi ciascuna con un solo elemento.
Passo 1: fondere assieme le due classi che sono
le più vicine possibili secondo la tabella delle
distanze.
Passo 2: ri-calcolare le distanze tra la nuova
classe, nata dalla fusione, e le altre classi.
I passi 1 e 2 vanno ripetuti alternativamente
fino a che tutti i record non sono stati fusi in
una unica mega classe onnicomprensiva.
Un unico “punto sottile”: passo 2
• Se le distanze iniziali tra record sono ben
definite cosa sono le distanze tra “classi”?
• Non esiste un unico approccio alla
distanza tra “cluster” e nel contesto del
clustering gerarchico si parla di due
approcci:
– Single-linkage;
– Complete-linkage;
– Average-linkage;
Single-linkage
(metodo della connessione o della minima distanza)
• La distanza tra due gruppi di record è
definita come la minima distanza
osservata tra tutte le coppie formate da un
elemento del primo gruppo e un elemento
del secondo gruppo.
La distanza è
posta eguale alla
distanza tra la
coppia di record
più vicini
Complete-linkage
(metodo del diametro o della massima distanza)
• La distanza tra due gruppi di record è
definita come la massima distanza
osservata tra tutte le coppie formate da un
elemento del primo gruppo e un elemento
del secondo gruppo.
La distanza è
posta eguale alla
distanza tra la
coppia di record
più lontani
Average-linkage
(metodo della distanza media)
• La distanza tra due gruppi di record è
definita come la distanza media osservata
tra tutte le coppie formate da un elemento
del primo gruppo e un elemento del
secondo gruppo.
Variante:
considerare la
mediana invece
della media.
Simuliamo il single-linkage sulle
città italiane
BA
FI
MI/T
O
NA
RM
BA
0
662
877
255
412
FI
662
0
295
468
268
MI/T
O
877
295
0
754
564
NA
255
468
754
0
219
RM
412
268
564
219
0
Prima fusione
Simuliamo il single-linkage sulle
città italiane
BA
FI
MI/
TO
NA/
RM
BA
0
662
877
255
FI
662
0
295
268
MI/
TO
877
295
0
564
NA/
RM
255
268
564
0
Seconda fusione
Simuliamo il single-linkage sulle
città italiane
BA/N
A/RM
FI
MI/T
O
BA/N
A/RM
0
268
564
FI
268
0
295
MI/T
O
564
295
0
Terza fusione
Simuliamo il single-linkage sulle
città italiane
BA/N
A/RM
FI
MI/T
O
BA/N
A/RM
0
268
564
FI
268
0
295
MI/T
O
564
295
0
Quarta fusione
Simuliamo il single-linkage sulle
città italiane
BA/FI/N
A/RM
MI/TO
BA/FI/N
A/RM
0
295
MI/TO
295
0
Quinta fusione
La sesta fusione
ovviamente forma un
unico blocco
La sequenza
L’”albero” delle fusioni è una
guida alla “partizione” in
classi.
Tagliando l’albero a vari
livelli si possono ottenere
classi più fini o più generali.
• PRO
Pro e Contro
– Algoritmo facile e non richiede analisi matematica
complessa per la convergenza e per la ottimizzazione;
– L’albero “spiega” le relazioni tra cluster ed è facile per
un esperto (in generale) interpretare i risultati
dell’algoritmo;
• CONTRO
–
–
–
–
Quale livello di “taglio” scegliere per formare le classi?
Forte dipendenza dalla misura di similarità.
Impossibile gestire le similarità “fuzzy”.
Complessità elevata (la matrice iniziale e le successive
matrici richiedono O(N2) passi per il loro
aggiornamento.
– (Antipole?)