Sistemi di supporto alle decisioni
2. Features space
Ing. Leonardo Rigutini, Ph.D.
Dipartimento di Ingegneria dell’Informazione
Università di Siena
[email protected]
http://www.dii.unisi.it/ ~rigutini/
Feature extraction
I dati memorizzati nel data warehouse provengono da sources differenti:
Databases,pagine html, blog, bollettini interni, news, newsgroups, etc…
Normalmente tali dati sono memorizzati in forma non-strutturata,
rappresentazione non particolarmente adatta per essere processata da uno
strumento elettronico
deve essere derivata una nuova rappresentazione dei dati estraendo caratteristiche
ritenute utili all’analisi che deve essere fatta
Rappresentazione che sia memorizzata in una forma strutturata in modo da poter
essere analizzata da un software
Dati (Rappresentazione non-strutturata) ==> Feature Space
Es. bag-of-words nell’Automatic Text Processing, DAG nell’ananlisi delle immagini
ecc…
Sistemi di supporto alle decisioni - Leonardo Rigutini
Feature extraction
Varie sono le possibili rappresentazioni nello spazio delle features:
i dati sono rappresentati da vettori in uno spazion n-dimensionale
i dati sono rappresentati da sequenze
i dati sono rappresentati da strutture più complesse (alberi,grafi ecc…)
…
la rappresentazione vettoriale è la più semplice ma anche la più semplice e
povera di informazioni:
più si complica la struttura utilizzata nella rappresentazione dei dati, più essa
contiene informazione
Sistemi di supporto alle decisioni - Leonardo Rigutini
Feature extraction
Es.1: consideriamo ad esempio una rappresentazione dei dati con un grafo
(Image Processing):
i nodi sono caratterizzati da features rappresentati in vettori n-dimensionali
gli archi contengono informazioni riguardo alle relazioni presenti tra i nodi
anche gli archi comunque sono caratterizzati da features rappresentate da
vettori m-dimensionali
Es.2: le sequenze temporali contengono una informazione aggiuntiva rispetto ad
un vettore in Rn:
la dipendenza temporale tra le features
Individuare le features dalle quali estrarre informazioni dai dati è compito del
progettista del sistema di data mining:
Nel proseguo assumeremo che i pattern sono rappresentati da vettori in Rn
Sistemi di supporto alle decisioni - Leonardo Rigutini
Feature selection
Non tutte le features scelte per la rappresentazione dei pattern sono realmente
significative, al contrario alcune potrebbero anche disturbare il processo di
analisi:
Ad esempio, gli articoli, gli avverbi e le congiunzioni non sono utili alla
determinazione del topic di un documento di testo
Normalmente dopo la fase di feature extraction, segue una fase di filtraggio
automatico delle feature:
feature selection o feature filtering
Sistemi di supporto alle decisioni - Leonardo Rigutini
1. La legge di Zipf
 Si basa su un’analisi sulla distribuzione delle features nella base di
dati
 Zipf,s law
 La probabilità che un item occorra q volte nella collezione è inversamente
proporzionale al numero delle sue occorrenze:
1
Pq  a
q
con a  1
 La legge di Zipf può essere espressa anche come:

f  pos  k
Sistemi di supporto alle decisioni - Leonardo Rigutini
1. La legge di Zipf
 L’idea è che solamente le features comprese in un intervallo
t1ft2 sono significative
f
t2
t1
pos
Sistemi di supporto alle decisioni - Leonardo Rigutini
2. Misure di informatività
 La legge di Zipf, taglia le features in base alla loro frequenza nel
training set.
 Ma la frequenza di una features misura abbastanza l’informatività
(informativeness) della feature stessa?
 è possibile definire una funzione di pesatura fw(x) più idonea a misurare
l’informatività delle features
 2 possibili approcci:
 fissare una soglia sulla informativeness in modo da rimuovere le features con
valore inferiore
 definire un naturale k e selezionare le prime k features con informativenes
maggiore
Sistemi di supporto alle decisioni - Leonardo Rigutini
2. Misure di informatività
 Alcune funzioni di pesatura
 Document frequency
 misura il numero di esempi in cui la feature appare. E’ necessario rimuovere
quelle features presenti in troppi esempi (troppo diffuse) e quelle che appaiono
in pochi esempi (non significative)
 Information gain
 Misura il guadagno di informazione dovuto alla presenza o assenza di una
feature wi data la classe Ck
 Se il valore di IG è alto, la feature è importante per la classe, altrimenti può
essere rimossa (soglia o k)
Sistemi di supporto alle decisioni - Leonardo Rigutini
2. Misure di informatività
 Gain Ratio
 è una versione normalizzata dell’IG.
 Chi-quadro
 deriva dalla statistica e misura l’indipendenza tra due variabili. Il risultato è zero
se le due variabili sono indipendenti
Sistemi di supporto alle decisioni - Leonardo Rigutini
2. Misure di informatività
 Le misure viste assegnano pesi alle features fissata la classe. Per
ottenere una misura globale e indipendente dalal categoria viene
applicata una funzione finale che combina le misure classdependent:
Sistemi di supporto alle decisioni - Leonardo Rigutini
3. Latent Semantic Analysis
 Un approccio differente per ridurre la dimensionalità dello spazio
ed individuare features più significative deriva dalla teoria di
decomposizione matriciale
 Sia X una matrice di dimensioni w x D, dove w è la dimensione
dello spazio originario e D è il numero di esempi nella base di dati:
D vettori colonna, ognuno è il features vector di un esempio.
Sistemi di supporto alle decisioni - Leonardo Rigutini
3. Latent Semantic Analysis
 Utilizzando la decomposizione a valori singolari (SVD) si può
scrivere:
U  R wr => matrice degli autovettori sinistri

dove   R rr =>matrice diagonale degli autovalori
V  R rd => matrice degli autovettori destri

 Poiché r < w, si ha che U è la matrice che mappa il vecchio spazio
(dimensione w) nel nuovo spazio (dimensione r) mentre
con
è la
rappresentazione di X in questo nuovo spazio.
 Nota che
dove
mappa il vecchio spazio nel nuovo
 Dato un vettore y, la sua rappresentazione nel nuovo spazio è semplicemente
Ry
Sistemi di supporto alle decisioni - Leonardo Rigutini
3. Latent Semantic Analysis
 Ogni nuova feature generata da R è una combinazione lineare degli
elementi dello spazio originale:
 Concetto, significato di un set di features
 Normalmente viene scelto un
k autovalori di Sigma:
con
e vengono selezionati i primi
e
Sistemi di supporto alle decisioni - Leonardo Rigutini
4. Random projection
 In questo approccio, lo spazio originale n-dimensionale è proiettato
in uno spazio molto più piccolo utilizzando una matrice random R
stocastica (le colonne sommano ad 1).
 Come nel caso precedente, sia
la matrice [features x
esempi], l’insieme dei features vector nel nuovo spazio sara:
 Il teorema di Jonson-Linderstrauss assicura che è possibile
proiettare k in uno spazio di dimensione
senza distorcere
lo spazio di un fattore superiore a
,
con
Sistemi di supporto alle decisioni - Leonardo Rigutini
4. Random projection
 Questo vuol dire che se due pattern sono vicini (simili) nello spazio
originario, lo saranno anche nel nuovo spazio di rappresentazione,
a meno di un errore di
 R deve essere una matrice ortogonale, quindi una volta creata
random, deve essere effettuato uno step per renderla ortogonale:
 Passo computazionalmente molto costoso
Sistemi di supporto alle decisioni - Leonardo Rigutini