Sequence Matching
Traduzione e Integrazione
delle Lezioni a cura di Sandro Gallo
Home Antipole Clustering HMM
Le sequenze sono liste di valori S = (x1, x2, ..., xk), ma
spesso ci riferiremo ad esse come a funzioni continue definite in
[0,1].
Quindi una sequenza S può essere pensata come un campione
di valori da una funzione continua S(t), con xi = S(i/k).
Nel caso più semplice, data una collezione di sequenze
{S1, S2, ..., Sn} e una sequenza query Q, tutte della stessa
lunghezza, il nostro problema è trovare quelle sequenze Si
la cui distanza da Q sia minima(minore di un certa soglia
), dove
per distanza intendiamo l'energia della differenza tra le
sequenze, cioè
Noi tratteremo le sequenze di lunghezza k come punti di uno
spazio k-dimensionale, ma fare così non è
probabilmente molto utile. Infatti, di solito k sarà
così grande che le tecniche di indicizzazione spaziale
come k-d-tree o gli R-tree non saranno utili.
Il trucchetto adottato da Faloustos e dai suoi colleghi è
di associare ogni sequenza con i primi termini della sua
trasformata di Fourier. Formalmente, il j-esimo termine
dell'espansione di Fourier della funzione S(t) è
Ricordando che il termine
Così le parti reale e immaginaria di Xj ci dicono quanto
la funzione S(t) si avvicina alle funzioni seno e coseno che
hanno nell'intervallo [0,1] j periodi, cioè
.
Il punto chiave della nostra discussione sta nel teorema di
Parsival che dice che l'energia in un segnale S(t) è la
stessa dell'energia nella sua trasformata di Fourier,
cioè
.
Nota che
è il modulo del numero complesso X. Un' altra nota
importante è che se S(t) è la differenza di due
sequenze, allora la distanza tra quelle due sequenze, che
è
,
è la stessa della somma dei quadrati dei moduli delle
differenze tra i coefficienti di Fourier di due sequenze,
cioè
dove S(t) e T(t) sono due sequenze. Poiché il quadrato del
modulo è sempre positivo, noi possiamo cercare tutte le
sequenze la cui distanza da una data query Q non sia più
grande di 
,
trovando tutte le sequenze di S la cui somma dei moduli delle
differenze dei primi m coefficienti di Fourier non è
più grande di .
Ovviamente otterremo anche quelle sequenze, dette falsi positivi,
vicine a Q nei loro primi m coefficienti ma molto differenti in
quelli più grandi. Questo in effetti non è un
grande problema perchè esiste una regola che dice che
tutta l'energia è conservata nei coefficienti di Fourier
di basso ordine, così lo schema proposto per la ricerca di
sequenze simili si può considerare abbastanza accurato in
termini pratici.
Quando la collezione di sequenze S e la sequenza query Q hanno la
stessa lunghezza, sistemeremo le sequenze in una semplice
struttura dati a bassa dimensione, come segue:
- Computa i primi m coefficienti di Fourier di ogni sequenza
Si, per qualche piccolo m fissato. Spesso è sufficente
usare m = 2 o 3. poiché i coefficienti di Fourier sono
complessi, il nostro spazio avrà dimensione 2m,
cioè per i valori usati di m uno spazio 4-dimensionale o
6-dimensionale.
- Posiziona ogni sequenza Si nello spazio in accordo con i
valori dei primi m coefficienti di Fourier. Gli stessi punti
saranno memorizzati in qualche struttura dati multidimensionale,
come gli R-tree o i k-d-tree).
- Per cercare tutte le sequenze la cui distanza da Q sia
inferiore a , computa i primi m coefficienti di Fourier
della query Q, e cerca nello spazio quei punti la cui distanza
dai punti di Q non sia maggiore di .
- Poiché ci sono falsi positivi, compara ogni sequenza
trovata con Q per verificare se effettivamente la distanza non
è superiore a.
Assumiamo che ogni query Q abbia lunghezza >= w. E siano le
sequenze di S di lunghezza maggiore di Q. Allora il metodo di
scanning sequentiale per trovare quelle sequenze la cui distanza
da Q è inferiore a è:
- Memorizza nella struttura dati 2m-dimensionale i primi m
coefficienti di ogni sottosequenza di lunghezza w, per ogni
sequenze Si di S. Come risultato, se le sequenze di S hanno
lunghezza k memorizzeremo k-w+1 punti per ogni sequenza Si.
- Data una query Q, prendi i primi w valori di Q e computa la
trasformata di Fourier di quella sequenza di lunghezza w. Prendi
quei punti delle sequenze di S la cui distanza dai rispettivi
punti di Q sia inferiore ae le rispettive posizioni.
- Per ogni sequenza Si con la rispettiva posizione p, compara
l'intera query Q con la sequenza Si partendo dalla posizione p.
Se la distanza non superaaccetta il match.
C'è un problema con la scansione sequenziale del numero di
punti che devono essere memorizzati, perchè il loro numero
è il prodotto del numero di sequenze per la lunghezza
delle sequenze. Faloustos, Ranganathan, Manoulopoulos
(FRM) sfruttano per risolvere questo problema l'idea che
prendendo in considerazione una finestra di lunghezza w di
sequenze di S (quindi sequenze adiacenti), i coefficienti di
Fourier di basso ordine non varieranno troppo rapidamente.
Noi quindi terremo una traccia se plotteremo i punti
corrispondenti a finestre consecutive di lunghezza w. Invece di
memorizzare punti, noi memorizzeremo rettangoli, nell'appropriato
numero di dimensioni, che limitano i punti in un segmento della
traccia. Un rettangolo può essere memorizzato usando i
vertici opposti. Quindi se i rettangoli tendono a rappresentare
molti punti, allora lo spazio usato per memorizzare i rettangoli
è molti inferiore rispetto allo spazio necessario per
memorizzare i singoli punti.
Per recuperare i punti la cui distanza a una query Q di lunghezza
w non è maggiore di , trova i rettangoli a distanza inferiore a
. Confronta
Q solo con quelle sequenze che corrispondono ad almeno un
rettangolo recuperato, e solo dalle posizione iniziali
rappresentate da quei rettangoli.
Partizionare la traccia in rettangoli è un problema di
ottimizzazione. FRM usa come dell'operazione di
memorizzazione dei rettangoli, la cui dimensione nella dimensione
i è Li, la quantità:
.
Se la query Q ha lunghezza w, si procede come sopra cercando i
rettangoli a distanza inferiore a . Se Q ha lunghezza >= w, diciamo kw per
qualche k > 1, ci sono molte cose che possiamo fare:
- Recuperare le sequenze matchate e le loro posizioni, e quindi
comparare l'intera Q con la sequenza partendo dalla posizione p.
Questo metodo è come la scanning sequentiale solo che
sfrutta l'efficenza delle tracce.
- Cercare i rettangoli a distanza <= da Q nei primi w
valori, nei successivi w, e così via.
Solo la sequenza che ha almeno un rettangolo con distanza
inferiore a da ogni sottosequenza Q è una
candidata. Controlla solo i candidati.
- Come 2, ma controlla una sequenza S se ha un rettangolo con
distanza
da almeno una delle p sottosequenze di Q. Nota che la distanza
delle sequenze deve essere al più e se tutte le p
sottosequenze di Q sono da ogni punto sulla traccia di S, allora
che è un lower bound della distanza tra Q e ogni
sottosequenza di S.
Home Antipole Clustering HMM