• Non ci sono risultati.

Progettazione e sviluppo di metodi di selezione di caratteristiche per analisi di dati ad alta dimensionalità.

N/A
N/A
Protected

Academic year: 2021

Condividi "Progettazione e sviluppo di metodi di selezione di caratteristiche per analisi di dati ad alta dimensionalità."

Copied!
20
0
0

Testo completo

(1)

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

(2)

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

(3)

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

(4)

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 rimozione

delle 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 DD 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    

(5)

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 dello

spazio 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

(6)

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.

(7)

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

(8)

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

(9)

Valutazione dei risultati sperimentali

Valutazione dei risultati sperimentali

Validità della partizione

Validità della partizione

Coefficiente di partizione

Coefficiente di partizione



  N k C i ik

u

N

P

1 1 2

1

 1/C ≤ P ≤ 11/C ≤ P ≤ 1

Misura del livello di fuzzynessMisura del livello di fuzzyness

Ripreso dalla letteratura

(10)

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 1

Indipendente 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

(11)

Quantizzazione di Ivx

Quantizzazione di Ivx

(12)

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

(13)

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

(14)

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

(15)

Esempio di grafico dei test

Esempio di grafico dei test

(16)

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

(17)

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

(18)

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

(19)

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

(20)

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

Riferimenti

Documenti correlati

Concetto di Paziente Ciascun paziente è caratterizzato da numero della tessera sanitaria, nome, cognome, indirizzo, data di nascita, luogo di nascita e età... DB M

Ciascun paziente è caratterizzato da numero della tessera sanitaria, nome, cognome, indirizzo, data di nascita, luogo di nascita e età.. Gli ospedali della ASL sono caratterizzati

Professore(Matricola, Nome, Cognome) Università(NomeUniversità, Città, Matricola, DataElezione ).

accorpamento delle entità figlie nell’entità padre accorpamento dell’entità padre nelle entità figlie sostituzione della gerarchia con relazioni... DB M G 12 Accorpamento

Ridondanza e Anomalie In tutte le righe in cui compare uno studente è ripetuta la sua

Una decomposizione conserva le dipendenze se ciascuna delle dipendenze funzionali dello. schema originario è presente in una delle

Le brillanti ed originali formule risolutive delle equazioni algebriche di terzo e di quarto grado presentavano qualche inconveniente quando , di fronte alla certezza di radici

Gli obiettivi posti sono stati ampiamente raggiunti realizzando un servizio web come estensione di Geoserver, per gli oggetti in formato CityGML in analogia con il servizio Web