Sistemi di supporto alle decisioni
4. Clustering
Ing. Leonardo Rigutini, Ph.D.
Dipartimento di Ingegneria dell’Informazione
Università di Siena
[email protected]
http://www.dii.unisi.it/ ~rigutini/
Clustering
Data una base di dati di oggetti, suddividere tali oggetti
in gruppi, in modo che…
...oggetti appartenenti allo stesso gruppo siano molto simili
...oggetti in gruppi diversi siano molto diversi
La suddivisione non può avvalersi di dati supervisionati
(Learning set):
Clustering ==> processo non supervisionato
Sistemi di supporto alle decisioni - Leonado Rigutini
Clustering
Gli algoritmi di clustering possono essere suddivisi in
tre tipologie:
Partitional clustering (k-clustering): viene creato un
partizionamento dello spazio
Clustering gerachico: viene creata una gerarchia di gruppi
(albero) basandosi su particolari criteri.
Sistemi di supporto alle decisioni - Leonado Rigutini
Clustering
Una seconda categorizzazione degli algoritmi di
clustering considera la possibilità che un oggeto
appartenga a più di un cluster:
Hard-clustering: ogni elemento è assegnato ad un solo cluster
e quindi i clusters non si sovrappongono
Soft-luster: dove un elemento può essere assegnato a più di
un gruppo con un grado di appartenenza
Noi consideriamo gli algoritmi di hard-clustering.
Sistemi di supporto alle decisioni - Leonado Rigutini
Esempi di applicazioni
Identificazione di popolazioni omogenee di clienti in basi di dati di marketing
Valutazione dei risultati di esperimenti clinici
Monitoraggio dell’attività di aziende concorrenti
Identificazione di geni con funzionalità simili
Nel WWW…
Classificazione di documenti
Identificazione di gruppi di utenti (in base ai file di log) con caratteristiche
di “navigazione” simili
Sistemi di supporto alle decisioni - Leonado Rigutini
“Classificazione non supervisionata”
Abbiamo già sottolineato come il processo di clustering sia un
task non-supervisionato
Questo fatto implica che:
Non esiste un learning set dal quale apprendere le classi
Si parla di unlabeled-set, cioè l’insieme di esempi non etichettati che sono
oggetto dell’algoritmo
Il numero di gruppi da individuare nell’unlabeled-set (solitamente indicato
con k) è sconosciuto
E’ un processo di classificazione non supervisionato:
come tale si utilizzeranno i modelli di classificatori visti in precedenza
risolvendo però il problema dell’assenza del learning-set
Sistemi di supporto alle decisioni - Leonado Rigutini
Partitioning clustering
Partitioning clustering
Lo scopo di tale approccio è suddividere lo spazio dei
pattern in k gruppi ed assegnare ogni esempio ad un
gruppo in modo da creare clusters omogenei
Normalmente viene minimizzata/massimizzata un funzionale:
Minimizzare le distanze tra gli esempi interni al gruppo
Massimizzare le distanze tra gli esempi in gruppi diversi
Massimizzare le distanze tra due gruppi diversi
…
Sistemi di supporto alle decisioni - Leonado Rigutini
1. k-Means
K-means è l’algoritmo di clustering più popolare nella
letteratura scientifica e deriva dall’algoritmo EM
(Expectation Massimization)
EM è un algoritmo sviluppato nella teoria delle
probabilità per risolvere il problema delle stime nonsupervisionate a massima verosomiglianza (maximum
likelihood)
Sistemi di supporto alle decisioni - Leonado Rigutini
Maximum likelihood
Supponiamo di avere un insieme di dati D non
etichettati, lo scopo è approssimare la loro distribuzione
nello spazio con k distribuzioni di probabilità
caratterizzate quindi da k parametri Teta
La likelihood degli elementi dato il modello Teta è
quindi:
Sistemi di supporto alle decisioni - Leonado Rigutini
Maximum likelihood
Normalmente viene utilizzata la log-likelihood
la funzione logaritmica è un funzione monotona crescente
Lo scopo delle stima a maximum likelihood è quindi trovare Teta
che massimizza la log-likelihood:
Sistemi di supporto alle decisioni - Leonado Rigutini
EM
EM assume l’esistenza di parametri nascosti nel sistema che
semplificano il problema:
Sostituendo nella formula ML e massimizzando rispetto a Teta:
Sistemi di supporto alle decisioni - Leonado Rigutini
EM
Sviluppando:
Dopo alcuni passaggi si ottiene:
Sistemi di supporto alle decisioni - Leonado Rigutini
EM
La formula precedente ci da un modo per stimare il Teta ottimo.
Esso può essere stimato utilizzando un’algoritmo ad ascesa del
gradiente
E step: il valore al passo t+1 della likelihood è stimato utilizzando la
configurazione dei parametri stimata al tempo t
M step: i parametri del modello sono aggiornati utilizzando i dati
etichettati al passo E
Sistemi di supporto alle decisioni - Leonado Rigutini
k-Means
Ma come utilizzare questi risultati per il clustering?
Se guardiamo P(Ck|d,), questa indica una classificazione:
Assegna la classe Ck dato il pattern d ed i parametri 
Se inseriamo un classificatore centroids-based invece che un
classificator probabilistico otteniamo l’algoritmo k-Means
Sistemi di supporto alle decisioni - Leonado Rigutini
k-Means
1. Scegli i k centri iniziali
2. Repeat
E-step: assegna ciascun oggetto al cluster più vicino, il cui centroide
risulta il più vicino (simile) all’oggetto dato
2. M-step: ri-calcola i centroidi (punti medi) dei cluster
1.
until gli assegnamenti non cambiano (o cambiano poco)
Viene minimizzato l’errore
quadratico medio
E K   xk  mc ( xk )
k
Sistemi di supporto alle decisioni - Leonado Rigutini
2
k-Means
Limiti di Kmeans:
Può essere applicato solo se il tipo di dato permette di definire
la media
Occorre specificare in anticipo il numero k di cluster
Sebbene sia possibile dimostrare che il procedimento termina
sempre, non è detto che venga raggiunto il minimo globale (il
risultato è influenzato dalla scelta dei centri iniziali)
Non garantisce la connessione dei cluster trovati e l’assenza di
punti isolati
Può produrre risultati scadenti quando…
…i cluster hanno differenti dimensioni, densità, forma non
sferica/ellissoidale
…i dati contengono outlier
Sistemi di supporto alle decisioni - Leonado Rigutini
k-Means con nubi di punti non di forma sferica
Sistemi di supporto alle decisioni - Leonado Rigutini
k-Means
Soluzione:
usare molti cluster
In questo caso…
…i cluster calcolati sono partizioni dei cluster effettivamente
presenti
…è necessario fondere i cluster calcolati
Sistemi di supporto alle decisioni - Leonado Rigutini
Clustering Gerarchico
Clustering gerarchico
Questi algoritmi non producono una rappresentazione “flat”
(piatta) dei gruppi estratti dai dati, ma un albero T (Tree) i cui
nodi rappresentano un subset dello spazio
La radice di T rappresenta l’intero spazio D non partizionato
Due tipi di algoritmi di clustering gerachico esistono:
Agglomerativo: partendo dalle foglie vengono via via fusi i cluster più
simili fino a raggiungere la radice
Divisivo: partendo dalla root (l’intero spazio non partizionato), vengono
via via divisi i gruppi in sottogruppi più piccoli fino a raggiungere un
dimensione minima.
Sistemi di supporto alle decisioni - Leonado Rigutini
Clustering gerachico
Tali algoritmi richiedono delle misure per decidere ad ogni step
quali clusters fondere (agglomerativo) o quali dividere (divisivo)
Funzioni di prossimità, utilizzate dal clustering agglomerativo
per scegliere i due clustes da unire
Single-link - calcola la prossimità tra due cluster utilizzando la
distanza dei due punti più vicini appartenenti ai due diversi
clusters
Average-link - usa la distanza media tra i punti appartenenti ai
due diversi clusters
Sistemi di supporto alle decisioni - Leonado Rigutini
Clustering gerachico
Complete-link - usa la distanza tra i due punti più distanti
appartenenti ai due clusters
Centroids-distance - usa la distanza tra i centroidi dei due cluster
Sistemi di supporto alle decisioni - Leonado Rigutini
Clustering gerachico
Funzioni di densità, utilizzate dal clustering divisivo per
scegliere i clusters da dividere in due sottogruppi
Intra-cluster distance - calcola la distanza media tra gli elementi
in un cluster
I(C j ) 
1
Cj
2
d
r
 di
d r ,d i C j

Sistemi di supporto alle decisioni - Leonado Rigutini
Self Organizing Maps (SOM)
dette anche
reti di Kohonen
SOM - 1
Il clustering può essere interpretato come una forma di
classificazione non supervisionata
Come tale, può essere realizzato mediante un particolare tipo di
architettura neurale, chiamata SelfOrganizing Map (SOM), che
viene addestrata in modalità non supervisionata, cioè non
conoscendo l’output atteso per ciascun dato in input
Sistemi di supporto alle decisioni - Leonado Rigutini
SOM - 2
Al termine della fase di apprendimento, la SOM sarà comunque
in grado di raggruppare i dati in cluster, ovvero di produrre output
simili per input “vicini”, secondo una qualche metrica nello
spazio degli ingressi
Sistemi di supporto alle decisioni - Leonado Rigutini
Self Organizing Map  1
Motivazione biologica
La rete di Kohonen viene modellata sulla base di un comportamento caratteristico
dei neuroni che compongono un tessuto nervoso laminare: tali neuroni si attivano,
sotto l’azione di uno stimolo, in gruppi caratterizzati dalla presenza o assenza di
attività, definendo come attività l’emissione di un numero di impulsi nell’unità di
tempo superiore ad una certa soglia
La demarcazione spaziale tra i due gruppi è netta, per cui si parla di formazione di
“bolle di attivazione”, a partire da una situazione indifferenziata di bassa attività di
tutti i neuroni presenti nella rete
Sistemi di supporto alle decisioni - Leonado Rigutini
Self Organizing Map  2
Nel caso biologico, i neuroni che sono fisicamente vicini a neuroni attivi hanno
legami forti ed eccitatori mentre quelli periferici hanno legami inibitori
Nella corteccia cerebrale esistono proiezioni di stimoli sensoriali su specifiche reti di
neuroni corticali
I neuroni sensomotori costituiscono una mappa distorta (l’estensione di ciascuna
regione è proporzionale alla sensibilità della corrispondente area corporea, non alle
dimensioni) della superficie corporea
Tuttavia, parti adiacenti della corteccia corrispondono a parti adiacenti della
superficie corporea
Sistemi di supporto alle decisioni - Leonado Rigutini
Self Organizing Map  3
Questa caratteristica è stata modellata da Kohonen restringendo la variazione
dei pesi ai neuroni vicini ad un neurone scelto
SOM (Kohonen, 1981): mappe “sensoriali”, costituite da un singolo strato di
neuroni in cui le unità si specializzano a rispondere a stimoli diversi in modo
tale che:
ingressi di tipo diverso attivino unità diverse (lontane)
unità topologicamente vicine vengano attivate da ingressi simili
Sistemi di supporto alle decisioni - Leonado Rigutini
Self Organizing Map  4
Architettura della rete
Formata da un singolo strato di neuroni ni, i=1,…,wh:
w=larghezza, h= altezza della mappa
L’ingresso X Rn è collegato a tutti i neuroni
Ogni neurone i ha un set di parametri Wi di dimensione
pari a quella dell’ingresso
La funzione di attivazione è inversamente proporzionale
alla distanza tra il vettore dei parametri e l’input:
fi = 1/d(Wi,X), d una qualsiasi funzione distanza
Collegamenti laterali tra i neuroni
Sistemi di supporto alle decisioni - Leonado Rigutini
Architettura
Sistemi di supporto alle decisioni - Leonado Rigutini
Self Organizing Map  7
Interazione laterale
Ogni neurone è connesso con un “vicinato” di neuroni
per una mappa in R1 (la retta) abbiamo solamente PREC e
SUCC
per una mappa in R2 (piano) sono i neuroni
N,NE,E,SE,S,SO,O,NO
…e così in Rm con m>2
I pesi dei collegamenti tra neuroni non sono soggetti ad
apprendimento ma sono fissi e positivi e variano con il
valore della epoca ep e della distanza tra i neuroni nella
mesh dist ==> a(dist,ep) - funzione di decay
Sistemi di supporto alle decisioni - Leonado Rigutini
Collegamenti laterali
Sistemi di supporto alle decisioni - Leonado Rigutini
Aggiornamento dei pesi
Per ogni pattern fornito alla rete, un neurone soltanto risulta
“vincente”:
il neurone che presenta il massimo valore in uscita, chiamato anche
best-matching unit (BMU)
I pesi dei neuroni vengono aggiornati secondo la regola
W(t+1)=W(t)+a(dist,ep)(W(t)-Xi)
a(dist,ep) è una funzione che pesa l’aggiornamento dei
neuroni in base alla distanza dalla BMU e in base alla
epoche di addestramento
Sistemi di supporto alle decisioni - Leonado Rigutini
Aggiornamento dei pesi
Quindi:
Aggiornamento dei pesi della BMU ==> a(dist,ep) diventa a(0,ep),
poiché la distanza tra la BMU e la BMU è 0 (ovviamente!)
Aggiornamento dei pesi dei neuroni non BMU ==> a(dist,ep) con
dist≠0 decresce all’aumentare della distanza tra il neurone in esame
e la BMU
Inoltre, a(dist,ep), normalmente decresce all’aumentare
dell’epoca di stima dei parametri, in modo da convergere
per ep sufficientemente grande
Ossia dopo un certo numero di epoche
Sistemi di supporto alle decisioni - Leonado Rigutini
Funzioni di decay
Alcune funzioni di decay utilizzate nella pratica sono:
Decadimento lineare:
Decadimento nello spazio - a(dist,ep)=g  a(dist-1,ep)
Decadiemento nel tempo - a(dist,ep)=g  a(dist,ep-1)
con g<1
Decadimento logaritmo (o gaussiano):
a(dist,ep)  e
 dist 2


 (ep ) 
con (ep) una funzione monotona decrescente in ep

Sistemi di supporto alle decisioni - Leonado Rigutini
Algoritmo di apprendimento non supervisionato
Ripeti
1. Per ogni esempio xi nel training set:
1.
determina l’unità vincente nj
2.
modifica i pesi dell’unità vincente e di quelle che si
trovano in un suo intorno nel modo seguente: wj(t1) =
wj (t)  a(ep,l)(xi  wj (t))
2.
Nuova epoca: ep=ep+1
finché la rete non raggiunge una configurazione stabile
Sistemi di supporto alle decisioni - Leonado Rigutini
Self Organizing Map
Sistemi di supporto alle decisioni - Leonado Rigutini
Self Organizing Map
L’algoritmo di apprendimento delle SOM è molto semplice (non è
necessario il calcolo di derivate):
Viene selezionato il neurone j* con vettore dei pesi più vicino al
pattern di input; tale neurone “richiama” il vettore di input e
modifica il suo vettore dei pesi in modo da allinearlo a quello di
input
Vengono inoltre modificati i vettori dei pesi dei neuroni vicini a j*
la rete cerca di creare regioni costituite da un ampio set di valori
attorno all’input con cui apprende (cioè non fa corrispondere un
solo valore all’input, ma un set di valori)
i vettori che sono spazialmente vicini ai valori di training
(apprendimento) saranno comunque classificati correttamente anche
se la rete non li ha mai visti (capacità di generalizzazione)
Sistemi di supporto alle decisioni - Leonado Rigutini
Self Organizing Map
Lo scopo di una SOM è quello di avere, per input simili, neuroni
vincenti vicini, così che ogni bolla di attivazione rappresenti una classe
di input con caratteristiche somiglianti
La regione dei vicini può essere scelta come un quadrato, un cerchio o
un esagono attorno al neurone vincente
Il numero di vicini del neurone selezionato deve essere scelto grande
all’inizio e fatto decrescere lentamente all’aumentare dei cicli di
apprendimento
Sistemi di supporto alle decisioni - Leonado Rigutini
Self Organizing Map
Riassumendo…
Le SOM realizzano il clustering dei dati, cioè una identificazione,
nello spazio degli ingressi, di partizioni indotte dalle
similitudini/differenze fra i dati
Ogni partizione è rappresentata da un prototipo (centroide) definito
dal valore dei pesi del neurone corrispondente
Il clustering è di tipo non supervisionato: non si ha alcuna
informazione a priori sulle classi di appartenenza dei dati
A posteriori è possibile etichettare (classificare) dati in base alla
partizione dello spazio degli ingressi cui appartengono
Sistemi di supporto alle decisioni - Leonado Rigutini
Soft-clustering
Tuttavia... il mondo reale non è “crisp”
Effettuando il clustering non è sempre possibile definire in
maniera precisa se un punto appartiene ad un cluster oppure ad un
altro
Sistemi di supporto alle decisioni - Leonado Rigutini