UNIVERSITÀ DI PISA
FACOLTÀ DI INGEGNERIA
CORSO DI LAUREA SPECIALISTICA IN INGEGNERIA
INFORMATICA PER LA GESTIONE D’AZIENDA
Tesi di laurea:
Progettazione e sviluppo di metodi di selezione di
caratteristiche per analisi di dati ad alta
dimensionalità.
Relatori:
Prof. Francesco Marcelloni
Prof. Beatrice Lazzerini
Candidato:
Baldini Paolo
ANNO ACCADEMICO 2005-2006
Contesto applicativo

Data Clustering

Rappresentazione relazionale dei dati
Algoritmo ARCA


Problemi:

Maggiore occupazione di memoria

Dimensional Curse
Soluzione:


Riduzione del numero di caratteristiche
Da evitare:

Perdita di informazioni necessarie alla corretta
classificazione dei dati
Raggiungere l’obiettivo preposto

Possibile?

Sì perché…


Implicita ridondanza della rappresentazione
relazionale
Come?
Selezione delle caratteristiche salienti (feature
selection)
 Implementazione di apposite tecniche





MYPCA_Fs
NP_Fs
PCA_Fs
CORR_Fs
Sviluppate durante la tesi
Riprese dalla letteratura
NP_Fs: Near Points Feature
Selection

Superfluo considerare più dimensioni relative alla
non somiglianza rispetto a campioni tra loro molto
simili.

Individuazione
dei campioni
meno rappresentativi
Stima di “inutilità”
della caratteristica
j-esima all’interno del data
setdelle
relazionale
(numeroad
deiessi
campioni
tra loro molto simili in
rimozione
dimensioni
corrispondenti
 N-vettore B = [bj]: base alla caratteristica in esame)
b j #{aij : aij  DMED   ( DMED  DMIN )}, i  1,..., N , 0    1
n
 A parità di bj, calcolato vettore S = [sj]: s j   xij
i 1  D
DMED
MIN

DMAX  DMIN
b j  max{
b : b  B}
Stima
della
non
somiglianza
globale
dei dati rispetto
 Caratteristica j-esima eliminata se:
alla caratteristica j-esima
s j  min{ s : s  S}
{
MyPCA_Fs

Principal Component Analysis
Matrice di covarianza dei dati

Autovettori
Autovalori
1.
2.

3.
Matrice A
(ogni riga un
autovettore)
Vettore B
Autovettori pesati per i relativi autovalori
Somma delle componenti relative a ciascuna caratteristica
N-vettore B’ = B x A

b’j = misura dell’importanza della corrispondente dimensione
dello spazio iniziale in termini di varianza sul data set
considerato.
Selezione delle M caratteristiche con massimo valore di b’j
corrispondente
PCA_Fs

Principal Component Analysis

Matrice di covarianza dei dati
Autovettori
Autovalori
Matrice A
(ogni colonna
un
autovettore)
Vettore B
1. Eliminazione delle N - q colonne di A con autovalori associati
di valore minimo
 1≤q≤N
Preferibilmente 1 ≤ q ≤ M
 Nuova matrice A’
2.
3.
4.
Clustering delle righe di A’ con numero di prototipi i pari a M
Individuazione della riga più vicina a ciascuno degli M
prototipi
Selezione delle M caratteristiche corrispondenti alle righe
individuate
CORR_Fs

Matrice R di correlazione dei dati
Scelta delle M caratteristiche meno correlate fra
loro come più rappresentative

1. Individuata coppia di caratteristiche massimamente
correlate tra loro
2. Eliminata delle due quella per cui la somma dei
coefficienti di correlazione rispetto a tutte le altre sia
massima

Valore di soglia minima di correlazione

Procedimento interrotto se non vi sono elementi di R
maggiori di tale soglia
Criterio di STOP adottato

Eliminazione di un numero prefissato di
caratteristiche
Eventuale verifica a posteriori
del miglior compromesso tra
dimensione dei dati e quantità di
informazione residua
Valutazione dei risultati sperimentali

Validità della partizione

Ripreso dalla letteratura
Coefficiente di partizione
1 N C 2
P    uik 
N  k 1 i 1 

1/C ≤ P ≤ 1

Misura del livello di fuzzyness
Valutazione dei risultati sperimentali (II)

Sviluppato durante
la tesi
Differenza dalla partizione
di riferimento
Indice Ivx

Misura della distanza tra due generiche partizioni Pi e Pj
Indipendente
dall’ordinedei
deicampioni
prototipi in
e dal
numerospazio N Trasposizione
un fittizio
di dimensioni
dello spazio dei campioni
dimensionale

Nuova immagine dei dati dipendente dalla partizione
Distanza normalizzata tra immagini ottenute da
partizioni diverse
vij 
u x
k 1
N
m
ik kj
m
u
 ik
k 1
C
C
N
xkj 
u v
i 1
C
m
ik ij
m
u
 ik
i 1
xkn 
u
i 1
C
u
m
u
 ik
i 1
N
m
ik in
Ivx 

k 1
xki  xkj
N N
Quantizzazione di Ivx
Fase Sperimentale

Fase 1:
 5 dataset di dimensioni relativamente
 Dati reali dal
contenute
database UCI
 Numero delle
di
 Dimostrazione della validità
tesi
dimensioni variabile
ipotizzate
da 150 (Iris) a 1473
 Impiego di tutti e 4 gli(CMC)
algoritmi di feature
conservazione dell’informazione necessaria
selection
per una corretta classificazione dei
campioni
anche a seguito
dell’eliminazione
 Test dell’effettiva
efficacia
degli algoritmi
in
 CORR_Fs
di un
elevato numero di caratteristiche
esame
MYPCA_F
s
 NP_Fs
Fase sperimentale (II)

Fase 2:
 2 dataset ad altissima dimensionalità
(dell’ordine delle migliaia di dimensioni)
Raggiungere le condizioni necessarie a far
 Ulteriore riprova dei risultati ottenuti nella
convergere ARCA anche laddove
Fase 1 Phonemes
precedentemente essa lo impediva
 dati reali dal database
 Verifica dell’eliminazione
delladel progetto
maledizioneELENA
dimensionale
5404 caratteristiche
 Impiego del solo NP_Fs
DS8
 dati sintetici generati per l’occasione
15000 caratteristiche
Struttura dei test
1. Partizione di riferimento eseguita sul dataset
completo
2. Eliminazione successiva di un numero crescente
di caratteristiche

Confronto ogni volta con la partizione di riferimento
 Grafico degli andamenti di Ivx rispetto al numero di
dimensioni eliminate
3. Più cicli considerando numeri diversi di cluster

Controllo del coefficiente di partizione
Esempio di grafico dei test
Risultati Fase 1

Nella quasi totalità dei casi è stato possibile
identificare almeno una configurazione in cui,
nonostante l’eliminazione di un sostanzioso
numero di dimensioni, la classificazione restasse
sostanzialmente simile all’originale
Valore medio globale di Ivx: 0.0681
Risultati Fase 1 (II)

In alcuni casi la feature selection ha
permesso addirittura una classificazione
dei campioni più aderente all’originale
ripartizione dei dati


Variazione di andamento della pendenza della
curva di Ivx: da crescente a decrescente
Variazione inversa del numero di campioni
classificati diversamente rispetto al dataset
overfitting
Risultati Fase 1 (III)

Sostanziale equivalenza dei metodi di
feature selection




Impossibile individuarne uno universalmente
migliore
Dipendenza delle prestazioni dai diversi
scenari
Algoritmi tra loro più simili:
MYPCA_Fs e PCA_Fs
NP_Fs = via di mezzo tra essi e CORR_Fs
Risultati Fase 2


Conferma dei risultati ottenuti durante la
Fase 1 anche quando il numero dimensioni
Dataset
dei dati supera il migliaio
Phonemes
Conferma dell’efficacia della feature
selection per eliminare la maledizione
dimensionale
Dataset

Maggiore chiarezza deiDS8
dati
Convergenza dell’algoritmo di clustering (ARCA)
Valori più alti del coefficiente di partizione P
Conclusioni

Gli obiettivi preposti sono stati raggiunti



Riduzione del numero di caratteristiche dei dati
preservando le informazioni essenziali alla classificazione
Eliminazione della maledizione dimensionale
Sono stati sviluppati due nuovi algoritmi di feature
selection e se ne è verificata l’efficacia


NP_Fs
MYPCA_Fs