AA14 Clustering copia File - e

UNIVERSITA’ DI MILANO-BICOCCA
LAUREA MAGISTRALE IN INFORMATICA
Corso di
APPRENDIMENTO AUTOMATICO
Prof. Giancarlo Mauri
Lezione
Clustering
Cosa si intende per clustering
 Il clustering è un procedimento che si pone come
obiettivo la suddivisione di un insieme di elementi in
sottoinsiemi
 Gli elementi di ogni sottoinsieme sono accomunati da
caratteristiche simili
2
Clustering: settori di applicazione
 Machine learning
 Data mining
 Pattern recongnition
 Image analysis
 Bioinformatica
 Ricerche di mercato
 Pianificazione urbana
 Sismologia
 Astronomia
Dati necessari per il clustering
 Insieme di elementi da classificare
 Ogni elemento è specificato da un vettore caratteristico
 Misura di similarità (o dissimilarità) tra gli elementi
 Criteri da rispettare:
 OMOGENEITA’: elementi dello stesso cluster hanno alto
livello di similarità
 SEPARAZIONE: elementi di cluster diversi hanno basso
livello di similarità
4
Cenni matematici (1)
 Sia N = {e1, …, en} un insieme di n elementi, e sia
C = {C1, …, Ck} una partizione di N in sottoinsiemi. Ogni
sottoinsieme è chiamato cluster e C è detto clustering
di N
 Due elementi e1 e e2 sono chiamati mates rispetto a C
se sono membri dello stesso cluster in C
 Un elemento può essere rappresentato da un vettore
di numeri reali, ciascuno dei quali misura una specifica
caratteristica (feature)
5
Cenni matematici (2)
 Misura di similarità  distanza tra vettori
 Distanza euclidea
é
2ù
d ( x, y ) = êå ( xi - yi ) ú
ë i
û
 Distanza di Manhattan
d ( x, y ) = å xi - yi
1
2
i
 Distanza di Minkowski
é
kù
d ( x, y ) = êå xi - yi ú
ë i
û
1
k
6
Distanza euclidea
 Invariante rispetto a traslazioni e rotazioni degli assi
Distanza di Manhattan
 Non è invariante rispetto a traslazioni o rotazioni degli
assi e pone meno enfasi sulle variabili con distanze
maggiori, non elevando al quadrato le differenze
Distanza di Minkowski
 Dove q è un intero positivo:
 q = 1 ➪ Distanza di Manhattan
 q = 2 ➪ Distanza euclidea
 q = ∞ ➪ Distanza di Lagrange-Tchebychev
Esempio - Espressione genica
 Uno dei principali meccanismi di
regolazione cellulare è il controllo
dell’espressione genica che permette alla
cellula di coordinare operazioni complesse
adattando la concentrazione di proteine
alle variazioni dell’ambiente
 E’ possibile identificare gruppi di geni
coinvolti in un particolare evento (es.
shock termico) sperimentalmente (es.
riscaldando la colonia cellulare).
 Vengono misurati i livelli di mRNA di ogni
gene nelle ore successive. Confrontando i
dati con i livelli di mRNA tipici di ogni
gene, è possibile individuare geni sovra o
sottoespressi.
10
Microarray cDNA
11
Algoritmi di clustering - Classificazione
 Organizzazione dei cluster
 GERARCHICI
 NON GERARCHICI
 Uso di informazioni note, per guidare l’algoritmo
 SUPERVISIONATI
 NON SUPERVISIONATI
 Costruzione della soluzione di clustering
 AGGLOMERATIVI (si parte dal singolo gene)
 DIVISIVI (si parte dalla totalità dei geni)
12
Clustering gerarchico
 Si collocano gli elementi in input in una struttura gerarchica ad
albero, in cui le distanze tra nodi riflettono le similarità degli
elementi. Gli elementi sono localizzati sulle foglie dell’albero
 Vantaggi:
 Una struttura singola, coerente e globale
 Intuitivo
 Svantaggi:
 Non ci sono esplicite partizioni nel cluster
13
Clustering gerarchico
Viene impiegata una struttura ad albero
Non
radicato
Radicato
Una particolare
rappresentazione è il
dendrogramma
14
Clustering gerarchico
 Il clustering gerarchico può essere sia di tipo
agglomerativo che divisivo e per entrambi è necessaria
una funzione di selezione dei cluster
 Agglomerativi: bisogna scegliere la coppia di cluster da
fondere
 Divisivi: si deve valutare il cluster da dividere
Agglomerativi e Divisivi
 Bottom-up
 Inizialmente ogni elemento è un cluster a se stante
 Iterazioni cicliche: unione dei cluster
 Termina quando si ottiene un numero prefissato di
clusters oppure non appena viene raggiunta una distanza
massima di osservazione
Agglomerativi e Divisivi
 Top-down
 Inizialmente tutti gli elementi appartengono ad un unico
cluster
 Iterazioni cicliche: scissione dei cluster
 Termina quando si ottiene un numero prefissato di
cluster
Supervised vs unsupervised
 Supervisionata
 Classi etichettate
 Struttura classificatoria conosciuta
 Non supervisionata
 Estrazione automatica delle classi
 Scarsa conoscenza dei dati da analizzare
18
Esclusivi e non esclusivi
 Esclusivi - Hard clustering
 I gruppi non possono avere elementi in comune.
 Non esclusivi - Soft clustering
 Un elemento può appartenere a più cluster (fuzzy
cluster)
Algoritmi presentati
 Clustering gerarchico
 Neighbor joining
 Metodo del centroide
 Clustering non gerarchico
 K-means
 Basati sulla teoria dei grafi:
 Highly Connected Subgraph (HCS)
 CLustering Identification via Connectivity Kernels (CLICK)
 Euristica per un algoritmo polinomiale:
 Clustering Affinity Search Technique (CAST)
 Self-Organizing Maps (SOM)
20
Neighbor Joining Algorithm
1. Input: la matrice delle distanze Dij
2. Trovare gli elementi r, s tali che: Drs = minij(Dij)
3. Fondere i cluster r, s
4. Eliminare gli elementi r, s, e aggiungere un nuovo
elemento t con:
Dit = Dti =
Dir + Dis - Drs
2
5. Ripetere, finché non rimane un solo elemento
21
Neighbor Joining Algorithm
 Quindi
 inizialmente ogni individuo rappresenta un cluster
contenente solo se stesso
 Si cercano i 2 cluster r e s con la minima distanza tra
loro
 r ed s vengono fusi insieme e rimpiazzati con un nuovo
cluster t
 Si ricalcolano le distanze tra il cluster t e ognuno dei
rimanenti cluster i, ad esempio con la formula mostrata
 Si ripetono le fasi 2, 3 e 4 finché il numero totale dei
cluster non diviene 1, cioè finché non sono stati presi in
considerazione tutti gli individui
22
Neighbor Joining Algorithm
 Vediamo ora un semplicissimo esempio di esecuzione
dell’algoritmo, partendo dalla seguente matrice delle
distanze:
23
Neighbor Joining Algorithm
 Alla 1° iterazione la distanza minima è D1,2 = 2 per cui
si fondono i cluster 1 e 2 (avremmo potuto scegliere 3
e 4).
 Si calcola poi D(1,2),3 = (D1,3+D2,3-D1,2)/2 = (6+6-2)/2 = 5
e analogamente D(1,2),4 = 5
24
Neighbor Joining Algorithm
 Alla 2° iterazione il minimo è D3,4 = 2 per cui si
fondono 3 e 4 e si ricalcolano le distanze
 Alla 3° iterazione fondiamo i due cluster così
ottenuti e otteniamo una matrice con un unico
elemento. L’esecuzione quindi termina.
25
Neighbor Joining Algorithm
Vediamo come avviene la generazione dell’albero (ricordando che i pesi
degli archi sono determinati tramite Drs 2 ):
26
Neighbor Joining Algorithm
 Varianti: si basano sul differente Linkage Method usato per
calcolare le distanze tra due cluster
 Single Linkage: le distanze sono misurate da ogni membro di un
cluster ad ogni membro dell’altro cluster. Si considera come distanza
tra i cluster quella minima
 Average Linkage: la misura della distanza tra due cluster è
calcolata come media della distanza di ogni membro del
cluster da ogni membro dell’altro
 Complete Linkage: le distanze sono misurate da ogni membro
di un cluster ad ogni membro dell’altro cluster. Si considera
come distanza tra i cluster quella massima
27
Single linkage
 La distanza di due cluster è uguale alla distanza fra gli
elementi più vicini dell'uno e dell'altro cluster
Average linkage
 La distanza fra i due cluster viene calcolata come la
media delle distanze fra i singoli elementi
Average Linkage
 La distanza tra un cluster i e il nuovo cluster t, unione
di r ed s, si può anche calcolare come
ns
nr
Dit = Dti =
× Dir +
× Dis
nr + ns
nr + ns
30
Complete linkage
 La distanza di due cluster è uguale alla distanza fra gli
elementi più lontani dell'uno e dell'altro cluster
Average Linkage
Data la seguente matrice delle distanze vediamo un esempio pratico
di tutti e tre i metodi sopra citati:
32
Single Linkage
Il seguente è il
dendrogramma relativo al
Single Linkage dell’esempio
riportato sopra. Gli altri due
sono differenti ma si
ricavano esattamente nello
stesso modo.
33
Metodo del Centroide
 Si tratta di un metodo gerarchico aggregativo nel
quale la misura di vicinanza tra due cluster viene
valutata sulla base della distanza dei relativi centroidi
 Il centroide di un cluster è il vettore la cui j-esima
coordinata è la media aritmetica delle j-esime variabili
di tutti gli elementi del cluster in questione
34
Distanza fra i centroidi
 La distanza fra i due cluster corrisponde a quella che
intercorre fra i due centroidi (o medoidi)
Esempio
Si supponga di avere la matrice X di 5 elementi di
dimensione 3:
0
2
X = 1
0
5
2
4
1
0
11
5
0
4
2
0
x1
x2
x3
x4
x5
Presi i cluster A = {x1, x2} e B = {x3, x4, x5}, i loro
centroidi sono rispettivamente c(A) = (1, 3, 2.5) e c(B)
= (2, 4, 2) e la loro distanza (Manhattan) è
d(A,B) =
|1-2|+|3-4|+|2.5-2| = 2.5
36
Una struttura generale
 Riportiamo la struttura generale del clustering gerarchico:
Dit = Dti = a r Dir + a s Dis + g Dir - Dis
 Nell’algoritmo dell’Average Linkage avremo che i
parametri assumeranno i seguenti valori:
g =0
nr
ar =
nr + ns
ns
as =
nr + ns
37
Metodi non gerarchici
 I metodi non gerarchici mirano a ripartire le n unità
della popolazione in k gruppi, fornendo una sola
partizione anziché una successione di partizioni tipica
dei metodi gerarchici
 Es.: metodo di Forgy o delle K-Medie o delle
aggregazioni dinamiche
38
K-means (1)
 È divisivo e generalmente non supervisionato
 La soluzione non è visualizzabile attraverso
dendrogrammi
 L’algoritmo K-means assume che il numero k di clusters
sia noto
 Si propone di minimizzare le distanze tra elementi e i
centroidi dei clusters loro assegnati
39
K-means (2)
 Algoritmo
1. Si inizia fissando k centroidi iniziali di altrettanti
cluster
2. Per ogni individuo calcola la distanza da ciascun
centroide e lo si assegna al più vicino
3. Per la partizione provvisoria così ottenuta si ricalcolano
i centroidi di ogni cluster (media aritmetica)
4. Per ogni gene si ricalcola la distanza dai centroidi e si
effettuano gli eventuali spostamenti tra cluster
5. Si ripetono le operazioni 3 e 4 finché si raggiunge il
numero massimo di iterazioni impostate o non si
verificano altri spostamenti
40
K-means (3)
HCS e CLICK
 I dati di input vengono rappresentati come un grafo di similarità
 OBIETTIVO: costruzione dei kernel
 L’algoritmo partiziona ricorsivamente l’insieme corrente di
elementi in due sottoinsiemi
 Prima di una partizione, si considera il sottografo indotto dal
corrente sottoinsieme di elementi
 Se il sottografo soddisfa un criterio di arresto allora viene
dichiarato un kernel
 Altrimenti viene eseguito un taglio minimo pesato su quel
sottografo e l’insieme viene diviso in due sottoinsiemi separati dal
taglio, su cui verrà ripetuta la procedura di costruzione dei
kernel
 L’output è una lista di kernel che serve come base per gli
eventuali cluster
42
HCS (1)
 Costruisce un grafo di similarità non pesato (gli archi in realtà
hanno peso 1 o 0) in cui esiste un arco tra due vertici sse la
similarità tra i loro corrispondenti elementi supera una soglia
predefinita
 Un HCS è un sottografo indotto H di G il cui valore di taglio
minimo eccede |V(H)|/2
 L’algoritmo identifica gli HCS come kernel
 Possiede due buone proprietà per il clustering:
 il diametro di ogni cluster che produce è al massimo due
 ogni cluster è denso almeno la metà di una cricca
43
HCS (2)
 Varianti
 Iterated-HCS: quando il minimo valore di taglio viene ottenuto
da diversi tagli distinti, l’algoritmo HCS ne sceglie uno
arbitrariamente. Questo processo potrebbe suddividere
piccoli cluster in singoletti. Per superare questo
inconveniente, è possibile eseguire diverse (1-5) iterazioni di
HCS fino a che nessun nuovo cluster viene trovato
 Singletons Adoption: i singoletti possono essere “adottati” dai
cluster. Per ogni elemento singolo x si calcola il numero dei
vicini presenti in ogni cluster e nell’insieme dei singoletti S. Se
il massimo numero di vicini è sufficientemente grande ed è
ottenuto da uno dei cluster (piuttosto che da S) allora x viene
aggiunto a quel cluster. Questo processo viene ripetuto
diverse volte
44
HCS (3)
 Removing Low Degree Vertices: quando il grafo di
similarità contiene vertici con grado basso, un’iterazione
dell’algoritmo di taglio minimo potrebbe semplicemente
separare i vertici di grado basso dal resto del grafo.
Eliminare i vertici di grado basso da G elimina queste
iterazioni e riduce in modo significativo il tempo di
esecuzione. Il processo è ripetuto con diverse soglie sul
grado
45
CLICK
 L’informazione iniziale è rappresentata dalla matrice nxp dell’Espressione
Genica M.
 Ogni riga i di M rappresenta l’impronta digitale del gene i-esimo.
L’obiettivo dell’algoritmo è quello di determinare cluster di geni tali che i
geni in ogni cluster siano altamente simili nell’espressione mentre geni in
cluster diversi siano dissimili nell’espressione.
 Sulla base di M si costruisce un grafo i cui vertici sono i geni mentre gli
archi rappresentano la probabilità che i due vertici dell’arco stiano in uno
stesso cluster. Ad essa si assegna il valore:
wij = log
Sij
p × f (Sij i, j stanno nello stesso cluster )
(1 - p )× f (Sij i, j stanno in cluster diversi)
Variabile casuale che rappresenta la similarità tra il gene i e il gene j
(
f (Sij i, j stanno nello stesso cluster )» N mT , s T2
(
f (Sij i, j stanno in cluster diversi)» N m F , s F2
)
)
mT > m F
p = P{due geni stiano nello stesso cluster}
46
CLICK: l’algoritmo
L’idea dell’algoritmo è la seguente: dato un grafo G si vorrebbe decidere se i suoi vertici
rappresentano geni appartenenti ad un solo cluster oppure no. Nel primo caso di dice che
G è puro. Per decidere questo si determinano tutti i tagli del grafo G e si valutano le seguenti
ipotesi per ogni taglio C del grafo:
4 H0C: il taglio contiene solo geni di uno stesso cluster
4 H1C: il taglio contiene almeno due geni di cluster diversi
Se P[H0C]>P[H1C] per ogni taglio C di G allora si dice che G è un kernel
Basic-CLICK(G(V,E))
if (V(G)={v}) then
sposta v nell’insieme di singoletti R
elseif (G è un kernel) then
return V(G)
else
(H,Q,taglio) = Taglio_A_Peso_Minimo(G)
Basic-CLICK(H)
Basic-CLICK(Q)
end if
end
Lemma G é un kernel se e solo se il taglio a peso minimo di G
é positivo
dim :
Utilizzando la regola di Bayes si vede che
W (C ) = log
{ }
P{H C}
P H1C C
C
0
{
} {
}
Ovviamente W (C ) > 0 sse P H1C C > P H 0C C . Se il taglio minimo
é positivo a maggir ragione lo saranno gli altri tagli. Viceversa se
il taglio minimo é non positivo allora per quel taglio
{
} {
}
P H1C C £ P H 0C C e dunque G non può essere un kernel
Le performance di CLICK raffrontate con altri algoritmi di clustering risultano superiori
sia in qualità che velocità
47
Analisi Componenti Principali (PCA)
La PCA è una tecnica per la riduzione del numero di variabili casuali che
descrivono un fenomeno. L’obiettivo e’ quello di identificare un sottoinsieme
di variabili casuali dalle quali dipende la maggiore varianza (‘variabilità’) del
fenomeno
y descrive meglio di x la variabilità del
fenomeno
48
PCA: i dati
input
x
Matrice di Covarianza
{ }
R = E x xT
Il sottospazio generato da r(1), …, r(M),
(M<d), è chiamato sottospazio PCA
Componente principale i
xT r (i)
r (i) ® l (i)
r(i) è l’autovettore
corrispondente all’i-esimo
autovalore (i)
49
Trasformazione di Karhunen-Loéve
Obiettivo: mappare vettori x = (x1,…, xd) in vettori z = (z1,…, zM) con
M<d.
Errore
u iT u j = d ij
M
d
x = å x iu i
i=1
zi = u iT x
~
x = å zi u i +
i =1
d
å bi u i
x -~
xn =
n
d
å ( zin - bi )u i
i = M +1
i = M +1
ui sono d vettori ortonormali
Somma dei quadrati degli errori
1 d T
EM = å u i å u i
2 i =M +1
å u i = li u i
1 N n
bi = å zi = u iT x
N n=1
1 d
EM = å li
2 i =M +1
2
1 N n ~n
1 N d n
EM = å x - x = å å ( zi - bi ) 2
2 n=1
2 n=1 i=M +1
L’errore minimo è ottenuto scegliendo
i più piccoli d-M autovalori; ogni
autovettore ui è chiamato componente
principale
50