Progetto Reti Neurali e Knowledge Discovery - NeuRoNe Lab

Progetto Reti Neurali e Knowledge Discovery
Antonio Della Pietra
Francesco Muto
Università degli Studi di Salerno
22 Luglio 2014
Della Pietra - Muto (UNISA)
Progetto RNKD
22 Luglio 2014
1 / 53
Outline
1
Introduzione
Obiettivi
Workflow
2
Tecniche Utilizzate
Classificatori
Feature Ranking
Dimensionality Reduction
Feature Selection
3
Mappe
4
Conclusioni
Della Pietra - Muto (UNISA)
Progetto RNKD
22 Luglio 2014
2 / 53
Outline
1
Introduzione
Obiettivi
Workflow
2
Tecniche Utilizzate
3
Mappe
4
Conclusioni
Della Pietra - Muto (UNISA)
Progetto RNKD
22 Luglio 2014
3 / 53
Outline
1
Introduzione
Obiettivi
Workflow
2
Tecniche Utilizzate
3
Mappe
4
Conclusioni
Della Pietra - Muto (UNISA)
Progetto RNKD
22 Luglio 2014
4 / 53
Goal
Realizzare un sistema di classificazione
Pattern da classificare: stimoli alla corteccia uditiva bilaterale
6 soggetti
2 dataset per ogni soggetto per un totale di 12 dataset
SUBJECT_FREQbig: cambio di tonalità molto percepito
SUBJECT_FREQsmall: cambio di tonalità poco percepito
49 stimoli per dataset
2 classi:
prima classe: passaggio da 500 Hz a 1000 Hz
seconda classe: passaggio da 1000 Hz a 500 Hz
Della Pietra - Muto (UNISA)
Progetto RNKD
22 Luglio 2014
5 / 53
Outline
1
Introduzione
Obiettivi
Workflow
2
Tecniche Utilizzate
3
Mappe
4
Conclusioni
Della Pietra - Muto (UNISA)
Progetto RNKD
22 Luglio 2014
6 / 53
Workflow
Della Pietra - Muto (UNISA)
Progetto RNKD
22 Luglio 2014
7 / 53
Outline
1
Introduzione
2
Tecniche Utilizzate
Classificatori
Feature Ranking
Dimensionality Reduction
Feature Selection
3
Mappe
4
Conclusioni
Della Pietra - Muto (UNISA)
Progetto RNKD
22 Luglio 2014
8 / 53
Outline
1
Introduzione
2
Tecniche Utilizzate
Classificatori
Feature Ranking
Dimensionality Reduction
Feature Selection
3
Mappe
4
Conclusioni
Della Pietra - Muto (UNISA)
Progetto RNKD
22 Luglio 2014
9 / 53
Classificatori
SVM lineare
SVM non lineare
k-Nearest Neighbors
Tecnica di validazione dei modelli: Leave One Out
Della Pietra - Muto (UNISA)
Progetto RNKD
22 Luglio 2014
10 / 53
Support Vector Machine
SVM
Una SVM è un classificatore binario che apprende il confine fra dati
appartenenti a due diverse classi.
SVM ha come obiettivo quello di cercare di massimizzare il margine di
separazione tra le classi.
Funziona proiettando i dati in uno spazio a dimensione maggiore e
cercando un iperpiano di separazione lineare ottimale in questo spazio.
Della Pietra - Muto (UNISA)
Progetto RNKD
22 Luglio 2014
11 / 53
SVM Lineare
SVM lineare presuppone che i dati siano linearmente separabili nello spazio
originario e, quindi, cerca direttamente l’iperpiano di separazione ottimo
che divide i dati delle due classi nello stesso spazio.
Della Pietra - Muto (UNISA)
Progetto RNKD
22 Luglio 2014
12 / 53
SVM Non Lineare
SVM non lineare, invece, presuppone che i dati siano non linearmente
separabili nello spazio orignario e sfrutta delle funzioni particolari, dette
kernel, per mappare i dati in uno spazio a più grandi dimensioni e cercare
un iperpiano lineare di separazione in questo spazio più grande.
Radial Basis Function as Kernel
2
K (x , y ) = e (−γkx −y k )
Della Pietra - Muto (UNISA)
Progetto RNKD
22 Luglio 2014
13 / 53
SVM Non Lineare
Della Pietra - Muto (UNISA)
Progetto RNKD
22 Luglio 2014
14 / 53
K-Nearest Neighbours
Un pattern è classificato in base alla maggioranza dei voti dei suoi k vicini.
k è un intero positivo tipicamente non molto grande.
Nel nostro caso, k = 3.
Della Pietra - Muto (UNISA)
Progetto RNKD
22 Luglio 2014
15 / 53
Outline
1
Introduzione
2
Tecniche Utilizzate
Classificatori
Feature Ranking
Dimensionality Reduction
Feature Selection
3
Mappe
4
Conclusioni
Della Pietra - Muto (UNISA)
Progetto RNKD
22 Luglio 2014
16 / 53
Correlation Adjusted T-score
Il CAT-score è una modifica al classico t-test per tenere in considerazione
la dipendenza tra le feature.
τkadj = P − /2
1
1
1
+
V
nk
n
−1/2
(µk − µpool )
= P − /2 · τk
1
dove
k è il numero delle classi;
µpool =
nj
j=1 n µj
PK
è la media pesata globale;
P è la matrice di correlazione;
V è la matrice diagonale delle varianze;
τk è il vettore dei t-score di tutte le feature per la classe k;
Della Pietra - Muto (UNISA)
Progetto RNKD
22 Luglio 2014
17 / 53
τkadj
=P
−1/2
1
1
+
V
nk
n
−1/2
(µk − µpool )
= P − /2 · τk
1
CAT-score come differenza tra le medie standardizzata e decorrelata
CAT-score come media pesata dei t-score di tutte le feature.
Lo score finale Si della feature i
adj
Si = τi,1
Della Pietra - Muto (UNISA)
2
adj
+ τi,2
Progetto RNKD
2
22 Luglio 2014
18 / 53
Top 20 Feature
Della Pietra - Muto (UNISA)
Progetto RNKD
22 Luglio 2014
19 / 53
Scelta del taglio
Dato che CAT-score è un t-score modificato, ad ogni feature è associato
anche un p-value, che indica se una feature è significativa o meno rispetto
ad un livello di significatività α scelto (di solito, α = 0.05 o α = 0.01). La
selezione delle feature con un p − value ≤ α non è una scelta accurata.
Problema dei confronti multipli
Pr (falso positivo) = 1 − (1 − α)N . N ' 1000, Pr (falso positivo) →1
Probabilità alta di etichettare feature come significative, quando in realtà
non lo sono.
Della Pietra - Muto (UNISA)
Progetto RNKD
22 Luglio 2014
20 / 53
Scelta del taglio
Dato che CAT-score è un t-score modificato, ad ogni feature è associato
anche un p-value, che indica se una feature è significativa o meno rispetto
ad un livello di significatività α scelto (di solito, α = 0.05 o α = 0.01). La
selezione delle feature con un p − value ≤ α non è una scelta accurata.
Problema dei confronti multipli
Pr (falso positivo) = 1 − (1 − α)N . N ' 1000, Pr (falso positivo) →1
Probabilità alta di etichettare feature come significative, quando in realtà
non lo sono.
Della Pietra - Muto (UNISA)
Progetto RNKD
22 Luglio 2014
20 / 53
Scelta del taglio
Dato che CAT-score è un t-score modificato, ad ogni feature è associato
anche un p-value, che indica se una feature è significativa o meno rispetto
ad un livello di significatività α scelto (di solito, α = 0.05 o α = 0.01). La
selezione delle feature con un p − value ≤ α non è una scelta accurata.
Problema dei confronti multipli
Pr (falso positivo) = 1 − (1 − α)N . N ' 1000, Pr (falso positivo) →1
Probabilità alta di etichettare feature come significative, quando in realtà
non lo sono.
Della Pietra - Muto (UNISA)
Progetto RNKD
22 Luglio 2014
20 / 53
False Discovery Rate
FDR è una correzione al p-value, che cerca di mitigare tale problema.
p-value corretti
Siano p(1) ≤ . . . ≤ p(N) i p-value ordinati in maniera
non-decrescente
∀j ∈ {1, . . . , N}
pjfdr = min
j≤i≤N
p(i) ·
N
i
Un fdr basso (di solito, fdr < 0.2) permette di selezionare le feature
“significative”.
Della Pietra - Muto (UNISA)
Progetto RNKD
22 Luglio 2014
21 / 53
False Discovery Rate
FDR è una correzione al p-value, che cerca di mitigare tale problema.
p-value corretti
Siano p(1) ≤ . . . ≤ p(N) i p-value ordinati in maniera
non-decrescente
∀j ∈ {1, . . . , N}
pjfdr = min
j≤i≤N
p(i) ·
N
i
Un fdr basso (di solito, fdr < 0.2) permette di selezionare le feature
“significative”.
Della Pietra - Muto (UNISA)
Progetto RNKD
22 Luglio 2014
21 / 53
False nondiscovery rate per la selezione delle feature
Quando addestriamo un classificatore, però, il nostro scopo è
identificare l’insieme di feature che non sono informative per la
separazione tra le classi, in modo da eliminarle dal classificatore.
Questo è controllato dal false non-discovery rate (FNDR).
fndr (Si ) = 1 − fdr (Si )
Selezionare le feature non informative da scartare con fndr (Si ) ≤ 0.2,
corrisponde a scartare le feature con fdr (Si ) ≥ 0.8
Della Pietra - Muto (UNISA)
Progetto RNKD
22 Luglio 2014
22 / 53
Numero di feature selezionate con CAT-score e FNDR
Feature
Ranking ottenuto con fdr < 0.8
Della Pietra - Muto (UNISA)
Progetto RNKD
22 Luglio 2014
23 / 53
CAT-score + Fndr
Problema
Come procedere?
Dataset con #feature ≤ 20:
Basso rischio di overfitting → Classificazione
Dataset con #feature > 20: alto rischio di overfitting
MDS → Classificazione
PCA → Classificazione
Forward Selection:
Scatter Matrix → Classificazione
Wrapper → Classificazione
Dataset con #feature = 0: considerato il dataset originale
Della Pietra - Muto (UNISA)
Progetto RNKD
22 Luglio 2014
24 / 53
CAT-score + Fndr
Feature
Dataset con #feature < 20 nessun processo ulteriore
Della Pietra - Muto (UNISA)
Progetto RNKD
22 Luglio 2014
25 / 53
CAT-score + Fndr
Feature
MISH500small: nessuna feature ottenuta col ranking
Della Pietra - Muto (UNISA)
Progetto RNKD
22 Luglio 2014
26 / 53
Outline
1
Introduzione
2
Tecniche Utilizzate
Classificatori
Feature Ranking
Dimensionality Reduction
Feature Selection
3
Mappe
4
Conclusioni
Della Pietra - Muto (UNISA)
Progetto RNKD
22 Luglio 2014
27 / 53
Principal Component Analysis
La PCA è una trasformazione lineare che può essere usata per ridurre la
dimensionalità di un data set. Proietta i dati in un nuovo sistema di assi
ortogonali, per cui le proiezioni dei punti lungo gli assi del nuovo sistema
risultano caratterizzate dalla massima variabilità possibile.
Della Pietra - Muto (UNISA)
Progetto RNKD
22 Luglio 2014
28 / 53
PCA
Della Pietra - Muto (UNISA)
Progetto RNKD
22 Luglio 2014
29 / 53
PCA - Riduzione Dimensionalità
Numero PCs
Il 95% della varianza espressa fino a un massimo di 20.
Della Pietra - Muto (UNISA)
Progetto RNKD
22 Luglio 2014
30 / 53
PCA - Classificazione
Della Pietra - Muto (UNISA)
Progetto RNKD
22 Luglio 2014
31 / 53
Multidimensional Scaling
Anche MDS è una tecnica di riduzione della dimensionalità.
Permette di rappresentare i dati in una dimensione più piccola, cercando di
lasciare inalterata la dissimilarità degli oggetti di partenza.
È un metodo iterativo, ossia i punti vengono di volta in volta rilocati nello
spazio:
1
Inizialmente, i punti sono dislocati casualmente sulla mappa
2
Calcolo della funzione di stress
P
2
Stress =
i<j
(dij − f (δij ))2
P
i<j
f (δij )2
dove δij è la distanza tra i e j nella dimensione originaria e dij è la
distanza tra i punti nella dimensione ridotta.
3
I punti vengono rilocati in una nuova posizione in modo tale da avere
livelli di stress inferiori
Della Pietra - Muto (UNISA)
Progetto RNKD
22 Luglio 2014
32 / 53
MDS
Della Pietra - Muto (UNISA)
Progetto RNKD
22 Luglio 2014
33 / 53
MDS - Riduzione Dimensionalità
Della Pietra - Muto (UNISA)
Progetto RNKD
22 Luglio 2014
34 / 53
MDS - Classificazione
Della Pietra - Muto (UNISA)
Progetto RNKD
22 Luglio 2014
35 / 53
PCA vs MDS
PCA
SVM Lineare
SVM Rbf
3-NN
Della Pietra - Muto (UNISA)
MDS
90.25%
89.79%
82.53%
SVM Lineare
SVM Rbf
3-NN
Progetto RNKD
87.76%
90.02%
84.13%
22 Luglio 2014
36 / 53
Outline
1
Introduzione
2
Tecniche Utilizzate
Classificatori
Feature Ranking
Dimensionality Reduction
Feature Selection
3
Mappe
4
Conclusioni
Della Pietra - Muto (UNISA)
Progetto RNKD
22 Luglio 2014
37 / 53
Sequential Forward Selction
Scelta sottoinsieme di feature
Si parte con nessuna feature selezionata, e ad ogni passo si aggiunge la
feature che dà il maggiore incremento secondo un criterio di selezione
Criterio di selezione
Scatter Matrices
Classificatori
Della Pietra - Muto (UNISA)
Progetto RNKD
22 Luglio 2014
38 / 53
Sequential Forward Selction
Scelta sottoinsieme di feature
Si parte con nessuna feature selezionata, e ad ogni passo si aggiunge la
feature che dà il maggiore incremento secondo un criterio di selezione
Criterio di selezione
Scatter Matrices
Classificatori
Della Pietra - Muto (UNISA)
Progetto RNKD
22 Luglio 2014
38 / 53
Sequential Forward Selction
Scelta sottoinsieme di feature
Si parte con nessuna feature selezionata, e ad ogni passo si aggiunge la
feature che dà il maggiore incremento secondo un criterio di selezione
Criterio di selezione
Scatter Matrices
Classificatori
Della Pietra - Muto (UNISA)
Progetto RNKD
22 Luglio 2014
38 / 53
SBS con Scatter Matrices
J=
Trace{Sm }
Trace{Sw }
Offre una misura della seperazione tra le classi.
In particolare:
Sm = Sw + Sb
Sw è la matrice di scatter within-class e Trace{Sw } è una misura della
varianza media delle feature.
Sb è la matrice di scatte between-class e Trace{Sb } è una misura della
distanza media della media di ogni classe dalla media globale
J assume valori grandi nei seguenti casi
La varianza all’interno di ogni classe è piccola
Le medie delle classi sono distanti
Della Pietra - Muto (UNISA)
Progetto RNKD
22 Luglio 2014
39 / 53
SBS con classificatori
Addestrati direttamente:
SVM Lineare
SVM Radiab basis
K-NN
Della Pietra - Muto (UNISA)
Progetto RNKD
22 Luglio 2014
40 / 53
Forward Selection - Scatter Matrix
Della Pietra - Muto (UNISA)
Progetto RNKD
22 Luglio 2014
41 / 53
Forward Selection - Classification
Della Pietra - Muto (UNISA)
Progetto RNKD
22 Luglio 2014
42 / 53
Forward Selection - Metodi Wrapper
Della Pietra - Muto (UNISA)
Progetto RNKD
22 Luglio 2014
43 / 53
Forward Selection - Classificazione
Della Pietra - Muto (UNISA)
Progetto RNKD
22 Luglio 2014
44 / 53
Separabilità SOHE500small
Della Pietra - Muto (UNISA)
Progetto RNKD
22 Luglio 2014
45 / 53
Scatter Matrices vs Metodi Wrapper
Scatter Matrix
SVM Lineare
SVM Rbf
3-NN
Della Pietra - Muto (UNISA)
Wrapper
84.81%
87.53%
80.50%
SVM Lineare
SVM Rbf
3-NN
Progetto RNKD
96.82%
96.14%
90.70%
22 Luglio 2014
46 / 53
Outline
1
Introduzione
2
Tecniche Utilizzate
3
Mappe
4
Conclusioni
Della Pietra - Muto (UNISA)
Progetto RNKD
22 Luglio 2014
47 / 53
MISH_500big - CAT-score
Della Pietra - Muto (UNISA)
Progetto RNKD
22 Luglio 2014
48 / 53
MISH_500big - Forward Scatter
Della Pietra - Muto (UNISA)
Progetto RNKD
22 Luglio 2014
49 / 53
SOHE_500big - CAT-score
Della Pietra - Muto (UNISA)
Progetto RNKD
22 Luglio 2014
50 / 53
SOHE_500big - Forward Scatter
Della Pietra - Muto (UNISA)
Progetto RNKD
22 Luglio 2014
51 / 53
Outline
1
Introduzione
2
Tecniche Utilizzate
3
Mappe
4
Conclusioni
Della Pietra - Muto (UNISA)
Progetto RNKD
22 Luglio 2014
52 / 53
Conclusioni
CAT-score si è rivelato molto potente come metodo di filtraggio.
Le metodologie utilizzate hanno mostrato più o meno tutte lo stesso
potere di classificazione (solo 3-nn di poco inferiore rispetto agli altri
classificatori).
Differenze praticamente nulla tra MDS e PCA.
Forward Selection significativamente superiore addestrando
direttamente i classificatori.
Della Pietra - Muto (UNISA)
Progetto RNKD
22 Luglio 2014
53 / 53