Titolo accattivante

Analisi non supervisionata su FMRI
tramite tecniche di proiezioni e di
clustering
PROF. TAGLIAFERRI ROBERTO
INTELLIGENZA COMPUTAZIONALE
PERGOLA NICOLO’
UNIVERSITA’ DEGLI STUDI DI SALERNO
Outline
• Introduzione


Obiettivi
Work Flow
• Tecniche utilizzate
• Risultati ottenuti
• Conclusioni
Dataset utilizzato
• Il dataset contiene 9584 voxels per 65 pazienti
• 4 classi suddivise in
•
Pazienti sani
•
•
•
Depressi
Non depressi
Pazienti malati
•
•
Depressi
Non depressi
Obiettivi
• Clustering dei voxels tramite tecniche di proiezione non supervisionate
•
•
Velocizzano le tecniche di clustering grazie alla feature selection
Migliore visualizzazione dei dati
• Individuazione dei prototipi di ogni cluster
• Individuazione del livello di separabilità delle classi dei prototipi selezionati
Work Flow
Clustering
gerarchico
Cat Score
DBSCAN
Cat Score
Clustering
gerarchico
Cat Score
DBSCAN
Cat Score
Sammon
(correlazione/eu
clidea)
Dataset
tSNE
(correlazione/eu
clidea)
Metodi non supervisionati utilizzati
• Sammon
• tSNE
Sammon
•
•
•
E’ una variante pesata dell’MDS classico che vuole risolvere il problema di tenere in
considerazione di più le coppie di distanze grandi rispetto alle coppie di distanze
piccole che sono importanti per la geometria dei dati
La funzione di costo classica viene pesata per ogni coppia (i,j) per l’inverso della
loro distanza nello spazio a grandi dimensioni. In questo modo si assegna un peso
all’incirca uguale a ogni coppia di distanze preservando la struttura dei dati
Matematicamente la funzione di costo è data da:
1
∅ 𝑇 =
𝑖𝑗 𝑑𝑖𝑗
•
•
𝑖≠𝑗
𝑑𝑖𝑗 − | 𝑦𝑖 − 𝑦𝑗 |
𝑑𝑖𝑗
2
𝑑𝑖𝑗 rappresenta la distanza euclidea tra i punti nello spazio a grandi dimensioni
|𝑦𝑖 − 𝑦𝑗 |2 è la distanza euclidea al quadrato tra i punti 𝑦𝑖 e 𝑦𝑗 nello spazio a
dimensione ridotta
tSNE
•
•
•
E’ una tecnica di riduzione non lineare che è particolarmente adatta per
l’incorporamento di dati di elevate dimensioni in uno spazio di dimensioni ridotte
Basata sul vicinato
L’algoritmo è formato da 2 fasi principali
•
La prima fase definisce una distribuzione di probabilità tra gli oggetti nello spazio di grandi
dimensioni con la seguente distribuzione
•
•
La seconda fase definisce una distribuzione di probabilità tra gli oggetti nello spazio ridotto
•
•
Dove 𝑝𝑖𝑗 è la probabilità che gli oggetti 𝑥𝑖 e 𝑥𝑗 siano vicini nello spazio originale
Dove 𝑞𝑖𝑗 è la probabilità che gli oggetti 𝑦𝑖 e 𝑦𝑗 siano vicini nello spazio proiettato
La distanza tra le due distribuzioni viene minimizzata con la Kullback-Leibler
divergence
Stima della dimensione intrinseca dei dati
• La dimensione intrinseca dei dati viene stimata con il metodo degli EigValue
che effettua la PCA sui dati e ne valuta i residui. Le dimensioni vengono
stimate in modo iterativo aumentando di uno il numero delle dimensioni se
l’aggiunta di un autovalore aumenta la variabilità totale di almeno il 2.5%
• I dati vengono proiettati con i metodi non supervisionati Sammon e tSNE e
con la dimensione stimata (nel caso specifico uguale a 7)
Clustering gerarchico con correlazione
• Con l’indice di correlazione di Pearson viene calcolata la matrice di
correlazione
• Viene calcolata la matrice di dissimilarità
• Viene calcolato l’albero dei cluster con il metodo Ward Linkage
• Vengono suddivisi gli indici dei 9584 voxels nei K clusters di appartenenza
• Viene fatto l’MDS in 2 dimensioni per mostrare i risultati ottenuti
Clustering gerarchico con correlazione
Sammon K=30
1.5
1
0.5
0
-0.5
-1
Andamento cluster Sammon
Hierarchical Clustering of Profiles
5
5
5
5
5
0
0
0
0
0
-5
-5
-5
-5
2
4
6
2
4
6
2
4
6
5
5
5
5
0
0
0
0
-5
-5
-5
2
4
6
2
5
5
0
-5
2
4
4
6
-5
2
4
6
4
6
4
6
0
0
0
-5
-5
-5
-5
6
2
4
6
2
4
6
5
5
5
0
0
0
0
0
-5
-5
-5
-5
-5
5
2
4
6
2
4
6
2
4
6
2
4
6
5
5
5
5
0
0
0
0
0
-5
-5
4
6
-5
2
4
6
5
5
4
6
5
2
4
6
0
0
0
0
-5
-5
-5
-5
-5
4
6
2
4
6
2
4
6
4
6
2
4
6
2
4
6
2
4
6
5
5
0
2
2
-5
-5
2
6
5
5
2
4
5
0
4
2
-5
2
5
2
6
0
5
6
4
5
-5
2
2
2
4
6
Clustering gerarchico con correlazione
tSNE K=30
1
0.8
0.6
0.4
0.2
0
-0.2
-0.4
-0.6
-0.8
-1
-1
-0.5
0
0.5
1
1.5
Andamento cluster tSNE
Hierarchical Clustering of Profiles
40
20
0
-20
2
4
6
2
4
6
0
-50
2
4
6
2
4
6
2
4
6
2
4
-50
4
6
2
4
0
-50
2
4
6
40
20
0
-20
-40
2
4
4
6
4
4
6
6
40
40
20
20
0
0
-20
2
6
4
4
6
4
6
4
2
6
4
6
4
6
6
2
4
6
2
4
6
2
4
6
2
4
6
2
4
6
0
-20
-40
-60
-80
2
4
6
40
20
0
-20
-40
20
0
-20
-40
-60
2
4
60
40
20
0
-20
40
20
0
-20
2
2
20
0
-20
-40
-60
2
6
40
20
0
-20
2
4
60
40
20
0
-20
2
6
2
6
20
0
-20
-40
-60
20
0
-20
-40
2
4
20
0
-20
-40
-60
0
-20
-40
-60
2
6
20
0
-20
-40
-60
50
6
40
20
0
-20
-40
0
2
2
6
50
20
0
-20
-40
-60
-80
4
20
0
-20
-40
60
40
20
0
-20
60
40
20
0
-20
2
60
40
20
0
-20
20
0
-20
-40
-60
-80
50
60
40
20
0
-20
-40
40
20
0
-20
-40
40
20
0
-20
2
4
6
1.5
1
0.5
0
-0.5
-1
Clustering gerarchico con correlazione
Sammon K=150
Clustering gerarchico con correlazione
tSNE K=150
1
0.8
0.6
0.4
0.2
0
-0.2
-0.4
-0.6
-0.8
-1
-1
-0.5
0
0.5
1
1.5
1.5
Clustering gerarchico con correlazione
Sammon K=300
1
0.5
0
-0.5
-1
-1
-0.5
0
0.5
1
1.5
1
Clustering gerarchico con correlazione
tSNE K=300
0.8
0.6
0.4
0.2
0
-0.2
-0.4
-0.6
-0.8
-1
-1
-0.5
0
0.5
1
1.5
Clustering gerarchico con correlazione
• Come si evince dalle figure il metodo tSNE separa meglio i cluster rispetto a
Sammon, qualsiasi sia il valore di K.
Clustering gerarchico con distanza euclidea
• Viene calcolata la matrice delle distanze con l’utilizzo della distanza euclidea
• Viene calcolato l’albero dei cluster con il metodo Ward Linkage
• Vengono suddivisi gli indici dei 9584 voxels nei K clusters di appartenenza
• Come per la correlazione viene eseguito lo scaling in 2 dimensioni per la
leggibilità dei dati
8
6
4
2
0
-2
-4
-6
-8
Clustering gerarchico con distanza euclidea
Sammon K=30
Clustering gerarchico con distanza euclidea
tSNE K=30
100
80
60
40
20
0
-20
-40
-60
-80
-80
-60
-40
-20
0
20
40
60
80
100
Clustering gerarchico con distanza euclidea
Sammon K=150
8
6
4
2
0
-2
-4
-6
-8
-8
-6
-4
-2
0
2
4
6
8
10
Clustering gerarchico con distanza euclidea
tSNE K=150
100
80
60
40
20
0
-20
-40
-60
-80
-80
-60
-40
-20
0
20
40
60
80
100
Clustering gerarchico con distanza euclidea
Sammon K=300
8
6
4
2
0
-2
-4
-6
-8
-8
-6
-4
-2
0
2
4
6
8
10
100
Clustering gerarchico con distanza euclidea
tSNE K=300
80
60
40
20
0
-20
-40
-60
-80
-80
-60
-40
-20
0
20
40
60
80
100
Clustering gerarchico con distanza euclidea
• Anche con la distanza euclidea tSNE separa meglio i cluster rispetto a
Sammon
• Si può inoltre notare come la distanza euclidea separi i cluster in maniera più
chiara rispetto alla correlazione
DBSCAN con correlazione
• È basato sulla densità perché connette regioni di punti con densità
sufficientemente alta
• Vengono suddivisi i 9584 voxels nei K clusters calcolando di volta in volta il
valore di eps e il minimo numero di punti per formare un cluster
• Prende in input la matrice di correlazione
DBSCAN con correlazione
Sammon K=30
1.5
1
0.5
0
-0.5
-1
-1
-0.5
0
0.5
1
1.5
DBSCAN con correlazione
tSNE K=30
1
0.8
0.6
0.4
0.2
0
-0.2
-0.4
-0.6
-0.8
-1
DBSCAN con correlazione
Sammon K=150
1.5
1
0.5
0
-0.5
-1
-1
-0.5
0
0.5
1
1.5
DBSCAN con correlazione
tSNE K=150
1
0.8
0.6
0.4
0.2
0
-0.2
-0.4
-0.6
-0.8
-1
-1
-0.5
0
0.5
1
1.5
DBSCAN con correlazione
Sammon K=300
1.5
1
0.5
0
-0.5
-1
-1
-0.5
0
0.5
1
1.5
DBSCAN con correlazione
tSNE K=300
1
0.8
0.6
0.4
0.2
0
-0.2
-0.4
-0.6
-0.8
-1
-1
-0.5
0
0.5
1
1.5
DBSCAN con correlazione
• Le figure sopra elencate mostrano, come nel caso del clustering gerarchico
per correlazione, una delineazione dei cluster più netta con il metodo tSNE
rispetto a Sammon, qualsiasi sia il numero di cluster
DBSCAN con distanza euclidea
• Vengono suddivisi i 9584 voxels nei K clusters calcolando di volta in volta il
valore di eps e il minimo numero di punti per formare un cluster
• Prende in input la matrice delle distanze eculidee
DBSCAN con distanza euclidea
Sammon K=30
8
6
4
2
0
-2
-4
-6
-8
-8
-6
-4
-2
0
2
4
6
8
10
Andamento cluster Sammon
5
5
5
5
0
0
0
0
0
-5
-5
-5
-5
-5
5
2
4
6
2
4
6
2
4
6
2
4
6
5
5
5
5
5
0
0
0
0
0
-5
-5
-5
2
4
6
2
4
6
4
6
2
4
6
5
5
5
5
5
0
0
0
0
0
-5
-5
-5
-5
-5
2
4
6
2
5
5
0
0
4
6
-5
-5
2
4
6
5
0
0
-5
-5
2
4
6
4
2
0
-2
-4
4
4
6
6
4
0
0
0
-5
2
6
4
6
0
0
4
6
5
0
0
4
6
-5
4
6
4
6
2
4
6
2
4
6
2
4
6
2
4
6
4
2
0
-2
-4
0
2
2
-5
2
5
-5
6
4
5
6
6
-5
2
-5
2
5
4
6
5
5
2
4
5
6
4
2
0
-2
-4
2
2
5
6
-5
2
4
-5
2
5
2
4
-5
-5
2
2
2
4
6
DBSCAN con distanza euclidea
tSNE K=30
100
80
60
40
20
0
-20
-40
-60
-80
-80
-60
-40
-20
0
20
40
60
80
100
Andamento cluster tSNE
40
20
0
-20
-40
50
0
-50
2
4
6
40
20
0
-20
-40
2
4
6
4
6
60
40
20
0
-20
-40
2
4
4
6
2
4
2
4
6
6
4
6
4
2
6
4
6
4
6
0
-50
40
20
20
20
0
0
0
4
6
6
4
6
6
4
6
4
6
4
6
2
4
6
2
4
6
20
0
-20
-40
0
-20
2
4
6
2
4
6
20
0
-20
-40
-60
-80
20
0
-20
4
2
40
40
20
2
2
60
40
20
0
-20
-60
2
60
20
0
-20
-40
-60
6
-60
4
-20
2
4
-40
2
40
2
0
-50
40
6
-20
2
6
4
20
0
4
2
-40
4
50
2
6
0
60
50
4
-20
2
6
2
20
40
20
0
-20
-40
60
40
20
0
-20
2
2
40
20
0
-20
-40
2
6
20
0
-20
-40
-60
-80
60
40
20
0
-20
4
0
-20
-40
-60
-80
60
40
20
0
-20
2
-50
2
6
40
20
0
-20
-40
0
20
0
-20
-40
-60
-80
40
20
0
-20
-40
2
50
20
0
-20
-40
-60
2
4
6
40
20
0
-20
2
4
6
DBSCAN con distanza euclidea
Sammon K=150
8
6
4
2
0
-2
-4
-6
-8
-8
-6
-4
-2
0
2
4
6
8
10
DBSCAN con distanza euclidea
tSNE K=150
100
80
60
40
20
0
-20
-40
-60
-80
-80
-60
-40
-20
0
20
40
60
80
100
DBSCAN con distanza euclidea
Sammon K=300
8
6
4
2
0
-2
-4
-6
-8
-8
-6
-4
-2
0
2
4
6
8
10
DBSCAN con distanza euclidea
tSNE K=300
100
80
60
40
20
0
-20
-40
-60
-80
-80
-60
-40
-20
0
20
40
60
80
100
DBSCAN con distanza euclidea
• Anche in questo caso dalle figure si evince che con la distanza euclidea il
metodo tSNE separa meglio i cluster rispetto al metodo Sammon
• Dalle figure si può inoltre osservare come la separazione dei cluster sia più
netta con la distanza euclidea
Riassumendo
• Nei test effettuati risulta che, in generale, il dataset risulta meglio
clusterizzato con il metodo tSNE
• La distanza euclidea risulta migliore rispetto all’indice di correlazione di
Pearson
• Il clustering gerarchico separa meglio le classi rispetto al DBSCAN
Voxel più correlati
• Per entrambi i metodi vengono calcolati i medoidi di ogni cluster come
l’oggetto che è mediamente più correlato con tutti gli altri voxel nel cluster
Voxel più vicini
• Vengono calcolate le distanze medie di ogni cluster, prendendo la distanza
minima così da avere il voxel che minimizza la distanza con gli altri voxel
Separabilità delle classi
• Per calcolare le features più significative tra i prototipi estratti per la
separabilità delle classi è stato utilizzato il Cat Score
• Il CAT-score è una modifica al classico t-test per tenere in considerazione la
dipendenza tra le features.
• Selezione delle features:
•
20%, 30%, 40%, 50%, 60%, 70%, 80%
Accuratezza della Classificazione dei pazienti con prototipi del
Clustering Gerarchico con distanza euclidea tSNE
• E’ stato usato il classificatore LDA
• Il metodo di validazione utilizzato
è la divisione in training e test
•
Il test set è costruito lasciando fuori 5
pazienti per ogni classe
Accuratezza della Classificazione dei pazienti con prototipi del
Clustering Gerarchico con correlazione tSNE
Accuratezza della Classificazione dei pazienti con prototipi del
DBSCAN con distanza euclidea tSNE
Accuratezza della Classificazione dei pazienti con prototipi del
DBSCAN con correlazione tSNE
Accuratezza della Classificazione dei pazienti con prototipi del
Clustering Gerarchico con distanza euclidea Sammon
Accuratezza della Classificazione dei pazienti con prototipi del
Clustering Gerarchico con correlazione Sammon
Accuratezza della Classificazione dei pazienti con prototipi del
DBSCAN con distanza euclidea Sammon
Accuratezza della Classificazione dei pazienti con prototipi del
DBSCAN con correlazione Sammon
Visualizzazione dei cluster
• Nelle immagini seguenti:
•
•
I punti di colore giallo indicano i cluster con Cat Score più alto
I punti di colore rosso indicano i cluster con Cat Score più basso
Visualizzazione dei cluster (Vista sagittale)
Visualizzazione dei cluster (Vista trasversale)
Visualizzazione dei cluster (Vista coronale)