Vyhledávání v časových řadách

Martin Chrz

Časové řady a databáze

Časová řada je posloupnost reálných čísel, které reprezentují měření reálné proměnné v určitých časových intervalech Vývoj kurzů akcií Záznam teploty v určitých intervalech Objem prodejů v čase Audio záznam

Databáze časových řad obsahuje obrovské soubory dat Např. vývoj kurzů na New Yorkské burze

Podobnost časových řad

Problém s definicí podobnosti Trend křivky Velikost fluktuací Hustota a frekvence fluktuací Absolutní hodnoty prvků časových řad

U časových řad nás typicky zajímá „tvar křivky“ Např. : Najdi všechny akcie, které se chovají

podobně jako akcie IBM

Jak definovat podobnost časových řad? Formální definice databáze časových řad

DB = {X1, X2, ..., XN}, kde Xi = [x1i, ..., xn

i] je časová řada

Dotaz je nějaký bod v tomto prostoru Q=[q1,q2,...,qn]

Množina výsledků R = {X1, X2, ..., XM}, kde každý prvek R splňuje D(Xj, Q) < d

D je Eukleidovská vzdálenost:

j

jj yxYXD2

),(

Zpracování dotazů – sekvenční algoritmus Jednoduchý algoritmus:

porovnáme dotaz q s každým záznamem v databázi a do výsledku vložíme ty záznamy, které splňují uvedenou nerovnost

Úplně přesné výsledky... ... ale za jakou cenu

Pomalé – pro každý vektor se počítá drahá funkce pro podobnost

Matematické transformace - DFT Převádí signál do frekvenčního oboru Existuje rychlý algoritmus pro výpočet Fourierových

koeficientů v čase O(n log n) Časová řada je Xi = [x1

i, ..., xni] a koeficienty se

spočtou následovně:

1,...,1,0,1 1

0

2

1

nfexn

Xn

t

n

tfiit

if

DFT – indexace

1. Každou posloupnost rozděl na podposloupnosti stejné délky

2. Normalizuj všechny podposloupnosti tak, aby všechny hodnoty spadaly do určitého rozmezí

3. Pomocí DFT spočti Fourierovy koeficienty pro podposloupnosti

4. Pro reprezentaci podposloupností použij pouze prvních k koeficientů

5. Tyto koeficienty zaindexuj – např. do R - stromu

Dotazování

Dotaz Q má stejnou délku jako všechny podposloupnosti v databázi

1. Na dotaz aplikuj kroky 2 a 3 z indexační fáze2. Použij pouze prvních k koeficientů, stejně jako v

kroku 4 v indexační fázi (máme transformovaný dotaz Q´)

3. Prohledej R – strom a do R´ vlož všechny podposloupnosti, které mají od Q´ menší vzdálenost než d

4. Zkontroluj každou podposloupnost v R´, zda její zkutečná vzdálenost od Q je menší než d

Vlastnosti vyhledávání

Počítáním pouze s prvními k koeficienty držíme pouze přibližný tvar časové řady

Z Parcevalovy rovnosti plyne, že vzdálenost mezi dotazem a podposloupností je v indexovaném prostoru vždy menší nebo rovná vzdálenosti skutečné

V bodě 3 vyhodnocování dotazu proto můžeme zanést do výsledků false hits (množina R´ je vždy nadmnožina R)

Rozložení signálu algoritmem DFT

Při návrhu je potřeba rozmyslet, kolik koeficientů ponechat Málo koeficientů → rychlé hledání, ale nepřesné Příliš mnoho koeficientů → pomalé, ale přesnější hledání

Reverzní DFT

Symetrie DFT koeficientů

U reálných řad jsou koeficienty symetrické, t. j. posledních k koeficientů je komplexně sdružených k prvním k koeficientům

Díky tomu lze zvýšit přesnost výpočtů, aniž by se zvýšil počet zaindexovaných koeficientů

Pokud tedy máme prvních k koeficientů, můžeme počítat s 2k koeficienty

Tato technika umožňuje podstatně snížit chyby ve výpočtech a počet false hitů

Symetrie DFT koeficientů

Diskrétní waveletová transformace - DWT Chová se podobně jako

DFT, ale používá rekurzivní funkce místo sinusoid

Každý signál v L2(R) lze rozložit pomocí matice koeficientů aj,k

Množina těchto koeficientů se nazývá DWT

ktt jkj

j

22)( 2,

kjkjkj

kj

jkj

ta

ktatfj

,,,

,,

)(

22)( 2

Rozložení signálu algoritmem DWT

Vlastnosti DWT

Dekompozice původního signálu je podobná jako u DFT

U DFT se jednotlivé složky liší frekvencí, zatímco u DWT se liší jak frekvencí, tak i pozicí (posunem)

Elementární signály tedy u DWT nepřispívají svou hodnotou celému původnímu signálu, ale pouze jeho části

DWT funkcí existuje spousta typů Stejně jako u DFT se pro indexaci používá pouze

prvních k koeficientů

Reverzní DWT

Reverzní DFT x reverzní DWT Počty koeficientů u předchozího obrázku

stejné, na stejné křivce Výsledky DWT jsou jednoznačně lepší Dáno způsobem rozkladu

DWT umožňuje nejen rozklad na vyšší frekvence jako DFT, ale i zakomponování posunu, což značně zvyšuje přesnost

Je tedy DWT lepší?

Porovnání DFT a DWT

Experimentální výsledky ukazují, že DWT je skutečně lepší než DFT

Dosud jsme ovšem neuvažovali symetrii DFT koeficientů! V tomto případě je DFS s využitím symetrie vždy lepší než DWT V následujících experimentech byl použit 360 denní záznam 100

akcií Každý záznam byl rozsekán na podposloupnosti délky 128 Po dosažení konce původního záznamu byl použit začátek

sekvence Tím se pro každou akcii získalo 360 podposloupností, tedy

36000 vzorků pro vyhledávání Stejné dotazy byly zpracovávány algoritmem DFT, DWT a DFT s

využitím symetrie

Míra napodobení původního signálu po reverzních transformacích

Míra napodobení původního signálu po reverzních transformacích - zvětšení

Experimentální výsledky - souhrn Experimentální výsledky hovoří pro použití

DFT algoritmu s využitím symetrie koeficientů Dimenzionalita indexu je v praxi velmi

důležitá, zejména pokud je použit R – strom, protože R – stromy degenerují už při relativně nízké dimenzi (kolem 10)

Efektivita DFT algoritmu s využitím symetrie je mnohem vyšší než efektivita DWT právě v nízkých dimenzích

Matematické transformace

Dosud jsme se zabývali indexací a vlastním vyhodnocením dotazu

Vhodnými transformacemi lze však časové řady předzpracovat tak, že bude vyzdvižen celkový trend křivky bez ohledu na krátkodobé fluktuace

Podobnost křivek je ve značné míře závislá na tazateli (např. dvě akcie jsou podobné, pokud mají stejné fluktuace v čase, i když jedna má třeba dvakrát větší hodnotu než druhá)

Základní transformace

Normalizace Nechť µ je průměrná hodnota řady Xk a σ je její

směrodatná odchylka. Pak xik´=(xj

k- µ)/ σ je normální forma řady Xk

Moment Vzniká vydělením hodnoty řady v čase t + 1

hodnotou řady v čase t (lze obecně brát hodnotu v čase t + n)

Základní transformace 2

Posunutí indexů xi

´ = xi±n

Moving average Moving average za n dní se pro hodnotu xi

´ spočte jako průměr z hodnot xj-n/2, ..., xi, ..., xi+n/2

Význam základních transformací Normalizace vyrovnává rozdíly průměrných hodnot

(například jedna akcie je dvakrát dražší než druhá) Moment vyjadřuje poměr, v jakém se hodnota řady

mění během daného období Posunutí indexů se používá v případě, kdy jedna z

řad kopíruje průběh té druhé s určitým zpožděním (například dvě různé akcie reagují jinak rychle na určitou událost na trhu)

Moving average v podstatě „vyhlazuje“ křivku Na různé typy dotazů se hodí různé typy

transformací

Příklad 1

Příklad 1

První řádek zobrazuje Dow Jones 65 akciový index (COMPV), NYSE akciový index a poté porovnání jejich normálních forem a 9 – ti denních moving average

Druhý řádek zobrazuje Dow Jones 65 akciový index (COMPV), NYSE akciový index a poté porovnání jejich normálních forem a 19 – ti denních moving average

Příklad 2

Příklad 2

Dvě různé akcie a jejich momenty za 128 dní Transformace (vypočítání momentu)

vyrovnala cenové rozdíly „špičky“ v grafech se liší o 5 dní Aplikací posunu indexů o 5 dní se výrazně

sníží vzájemná vzdálenost těchto řad

Transformace – obecně a více formálně Každá lineární transformace lze provést jak na řadu,

tak i na její index spočtený DFT algoritmem (linearita)

Transformaci lze obecně zapsat jako pár reálných vektorů t = (a, b)

Aplikací t na vektor x (dotaz nebo řada v k – rozměrném prostoru) dostaneme nový vektor x´ = a * x + b

Všechny uvedené transfomace (moment, posunutí indexů, normalizace, moving average) jsou lineární

Transformace - skládání

Chceme – li použít více transformací současně, je lepší použít transformaci složenou

Například u akcií chceme provést s – denní posun (posun indexů) a zároveň moving average pro m dní

Máme tedy t1 = (a1, b1) a t2 = (a2, b2), které chceme aplikovat na x

21212

211212

***

**

bbaxaa

bbxaaxtt

Transformace – skládání 2

Často je užitečné definovat množinu všech transformací, které se mají před vyhledáváním aplikovat

Například s – denní posun (posun indexů) a zároveň moving average pro m dní pro s = 0, ..., 10 a m = 1, ..., 40; označme tyto množiny transformací jako T1 a T2

Složení transformací t2(t1) lze zapsat jako t3 = (a3,b3), kde a3 = a2 * a1 a b3 = a2 * b1 + b2

22111233 ,| TtTttttT

Vyhodnocování dotazů

Demonstrační dotaz: Pro každý den máme kurzy akcie q a množinu transformací T. Najdi všechny akcie z DB a transformace z T, pro které je jejich Eukleidovská vzdálenost po transformaci menší než daná mez ε.

Množinu T tvoří moving average pro m dní pro m = 1, ..., 40. Najděte všechny akcie, které mají po transformaci podobný průběh jako akcie IBM.

Algoritmy vyhodnocení

Jednoduchý: Provést transformaci na každou řadu v databázi a

vzniklé řady porovnat Příliš neefektivní

Lepší: Provést na DFT index každé řady v databázi

požadovanou transformaci a na tento index udělat rozsahový dotaz

Výsledkem je sjednocení elementárních řešeních z předchozího kroku pro každou transformaci

Jak vyhodnocení vylepšit?

Provést všechny požadované transformace najednou Transformaci t = (a, b) lze chápat jako bod v 2n dimenzionálním

prostoru Pro všechny transformace zkonstruujeme minimální ohraničující

obdélník (MBR) Protože tento obdélník je v 2n dimenzionálním prostoru, je

potřeba ho rozložit do n dimenzionálního prostoru na dva obdélníky (jeden odpovídá a a druhý b)

Takto upravené transformace lze pak aplikovat na datové obdélníky

Předpokládá se existence DFT indexu uloženého v R – stromu s kořenem N

Transformace datového obdélníku

Algoritmus vyhodnocení – všechny transformace najednou1. Sestroj MBR r pro všecny „body“ v T a rozlož ho na

odpovídající složky

2. Sestroj „vyhledávací“ obdélník qrect kolem dotazu q. Šířka obdélníku je ε.

3. Pokud N není list, aplikuj r na každý prvek (obdélník) N a zkontroluj, zda neprotíná qrect. Pokud ano, opakuj na tento prvek bod 3.

4. Pokud N je list, aplikuj r na každý prvek (bod) N a zkontroluj, zda neprotíná qrect. Pokud ano, tento prvek je kandidát.

5. Pro každého kandidáta použij plný databázový záznam, proveď požadované transformace a spočti, zda vzdálenost je menší než ε.

Slabá místa algoritmu

Požadované transformace mohou být takové, že MBR, který je nad nimi postavený, pokrývá většinu daného prostoru

V takovém případě ztratíme výhodu provedení více transformací zároveň

V nejhorším případě se tento algoritmus chová stejně jako výše uvedený vylepšený algoritmus (procházíme celý prostor)

Řešením je spočítat více MBR, které už pokryjí mnohem méně prostoru – potřeba najít kompromis

Čas, potřebný na 1 dotaz při různém počtu procházených sekvencí

Čas, potřebný na 1 dotaz při různém počtu provedených transformací

Zdroje

Davood Rafiei, On Similarity-Based Queries for Time Series Data, University of Toronto

Yi-Leh Wu, Divyakant Agrawal, Amr El Abbadi, A Comparison of DFT and DWT Based Similarity Search in Time-Series Databases

Dimitrios Gunopulos, Finding Similar Time Series