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