Dömötör Csilla - Idősorok analízise, diplomamunka

Datasheet

Year, pagecount:2008, 52 page(s)

Language:Hungarian

Downloads:86

Uploaded:February 27, 2011

Size:2 MB

Institution:
-

Comments:

Attachment:-

Download in PDF:Please log in!

Comments

No comments yet. You can be the first!

What did others read after this?

Content extract

http://www.doksihu Idősorok analı́zise Diplomamunka Dömötör Csilla Alkalmazott matematikus szak Témavezető: Lukács András, tudományos főmunkatárs Számı́tógéptudományi Tanszék Eötvös Loránd Tudományegyetem, Természettudományi Kar Eötvös Loránd Tudományegyetem Természettudományi Kar 2008 http://www.doksihu Tartalomjegyzék 1. Bevezetés 4 1.1 Adatbányászat 4 1.11 Az adatbányászat szakaszai 4 1.12 Adatbányászati feladatok 5 1.2 Az idősorokról általában 6 1.21 Példák idősorokra 6 1.3 Elnevezések, definı́ciók 7 1.4 Feladatok idősorokon 10 1.41 Klaszterezés 11 1.42 Osztályozás

11 1.43 A legmeglepőbb részsorozat 11 1.44 Motı́vumkeresés . 12 1.5 A dolgozat felépı́tése 12 2. Szimbolikus reprezentáció 13 2.1 Reprezentációról általában 13 2.11 SAX - Symbolic Aggregate approXimation 14 2.12 PAA - Piecewise Aggregate Approximation 14 2.13 Más távolságfüggvények 15 2.14 Szimbólumok 16 2.15 Sűrűségfüggvények 17 2.2 A SAX alkalmazásai 18 2.21 Klaszterezés 18 2.22 Osztályozás 19 2.23 Anomália detektálás 19 2.24 Motı́vumkeresés 22 . 3.

Fourier-sorok és waveletek 24 3.1 Fourier-sorok 24 3.2 FFT - Gyors Fourier-transzformáció 25 3.3 A waveletek 25 3.31 Waveletek előállı́tása 25 3.32 Multirezolúció . 27 3.33 FWT - Gyors Wavelet Transzformáció 28 3.4 A waveletek alkalmazása 29 3.41 Alkalmazási területek 29 2 http://www.doksihu 3.42 Tulajdonságok 29 3.43 Zajtalanı́tás 30 3.44 Dimenzió csökkentés 31 3.45 Klaszterezés 32 3.46 Klasszifikáció 32 3.47 Hasonlóság keresés, indexelés 33 4. Mérési

eredmények 34 4.1 WEKA 34 4.11 Klaszterezők 34 4.12 Osztályozók 35 4.2 Energia adatok 35 4.21 Klaszterezés 36 4.22 Osztályozás 37 4.3 A kisbabás adatok 42 4.4 SAX 44 4.41 Függés l-től 44 4.42 Sűrűségfüggvények 45 4.5 Wavelet-transzformáció 46 4.51 Wavelet függvény 46 4.52 Együtthatók száma 46 4.53 Legjobb k együttható 47 4.6 Összefoglalás 48 4.7

Köszönetnyilvánı́tás 48 5. Függelék 50 3 http://www.doksihu 1. fejezet Bevezetés 1.1 Adatbányászat Mai világunkban az élet az információ körül forog, birtoklása és értelmezése központi szerepet tölt be. A technika fejlődésével az elérhető, megszerezhető adatok mennyisége rohamosan növekszik, a különböző mérésekből egyre több és egyre pontosabb információkat szerezhetünk Az internet fejlődésével ezek az eredmények széles körben hozzáférhetőek, a tárolókapacitás növekedése pedig lehetővé tette, hogy ezeket az adatokat tárolni tudjuk. Az adatok mennyisége azonban megakadályoz minket abban, hogy átlássuk az egészet, gyakran a hasznos összefüggések, az adatokban rejlő tudás az emberi szem előtt rejtve marad. A nagy mennyiségű adat értelmezésére különböző statisztikai módszereket dolgoztak

ki, a tárolásához adattárházakat, adatbázisokat hoztak létre, ezek kezelésére pedig lekérdező nyelveket fejlesztettek ki. A lekérdező nyelvekkel azonban nem tudunk minden kérdést leı́rni Gondoljunk például egy telefonszolgáltató által gyűjtött adathalmazra, amely tartalmazza az ügyfelek hı́vásainak adatait! A statisztikai módszerekkel meg tudjuk határozni például a beszélgetések átlagos hosszúságát, vagy megkereshetjük a legrövidebb és a leghosszabb beszélgetést. Egy lekérdezés segı́tségével könnyen választ kaphatunk a következő a kérdésre: Melyik ügyfél mennyit telefonált az elmúlt héten? Viszont lekérdező nyelvekkel nem megfogalmazható például a következő kérdés: Várhatóan melyik ügyfelet fogja érdekelni a legújabb akciónk? Tovább rontja az adatbázisokból kinyerhető információ minőségét az emberi szubjektivitás, hiszen

hibás feltételezésekből kiindulva könnyen tehetünk fel rossz kérdést. Ezeket a hiányosságokat igyekszünk pótolni az adatbányászat eszközeivel. 1.11 Az adatbányászat szakaszai Az adatbányászatot a következő módon definiálhatjuk: ”Nagy mennyiségű adatból érvényes, újszerű, feltehetően érdekes, értelmezhető információ automatikus kinyerése.” Vizsgáljuk meg közelebbről ezt a definı́ciót! Újszerűnek nevezzünk egy eredményt, ha az eddigi tudásunkat valami újjal egészı́ti ki, meglepőnek vagy érdekesnek tekintjük, ha az eddigi tudásunknak vagy feltételezéseinknek ellentmond. Hogy valóban érdekes és hasznos-e, arról végső 4 http://www.doksihu sorban az adott téma szakértője tud véleményt mondani. A kapott eredményeknek érthetőnek, áttekinthetőnek kell lenniük, hiszen csak ı́gy tudjuk őket felhasználni. Mivel eredményeinket sok

esetben üzletembereknek, felsővezetőknek kell átadnunk, ezért rendkı́vül fontos a megjelenı́tés, ez a téma szinte külön tudományágnak tekinthető. Automatikus tudáskinyerés alatt azt értjük, hogy a módszereink algoritmikusak, törekszünk arra, hogy minél kevésbé legyen szükség az emberi beavatkozásra (pl. paraméterek beállı́tása), ezek ugyanis növelik a téves előı́téletekből származó hibák valószı́nűségét. Az adatbányászat folyamatát a következő szakaszokra bonthatjuk ([1]): 1. Megértés A vizsgált terület megismerése, megértése, előzetes információ gyűjtése, konzultáció a terület szakemberével. 2. Adatbázis létrehozása Ki kell választanunk azt az adatbázist, amiből aztán a tudást ki szeretnénk nyerni. 3. Adattisztı́tás Az előfeldolgozás részeként a lehető legjobban el kell távolı́tanunk a hibákat az

adatbázisunkból. Ilyenek például a hibás bejegyzések, hiányos adatok, üres mezők és a véletlen zaj. 4. Adatintegráció Az esetlegesen különböző forrásból származó adatokat azonos formátumúra kell alakı́tanunk. 5. Adattér csökkentése Az adatbázisból ki kell választanunk azokat az attribútumokat, amelyek a feladat megoldása szempontjából fontosak, hasznosak. Célszerű itt is bevonni a vizsgált terület szakértőjét 6. Az adatbányászati algoritmus tı́pusának kiválasztása 7. A konkrét adatbányász algoritmus kiválasztása Előnyök, hátrányok vizsgálata, futásidő és memóriaigény elemzése, paraméterek beállı́tása. 8. Az adatbányász algoritmus futtatása 9. Értelmezés A kinyert információt értelmezzük, értékeljük, szükség esetén visszatérünk az egyik korábbi ponthoz és javı́tjuk, finomı́tjuk az eredményt. 10. A megszerzett

tudás megerősı́tése Az eredményt összevetjük az előzetes tudásunkkal és várakozásainkkal. A tapasztalatainkat dokumentáljuk és amennyiben rendelkezésünkre áll referencia adat, az eredményeket ellenőrizzük, végül átadjuk a felhasználónak 1.12 Adatbányászati feladatok Az alábbiakban a legfontosabb adatbányászati feladatokat tekintjük át. A lista messze nem teljes, de jól mutatja a feladatok bonyolultságát és sokszı́nűségét. - Gyakori minta kinyerése Adott objektumok egy sorozata. Célunk a gyakori objektumok vagy részobjektumok megtalálása Ilyen objektumok lehetnek például elemhalmazok, részsorozatok vagy részgráfok 5 http://www.doksihu - Attribútumok közötti kapcsolatok Az objektumaink tulajdonságai között keresünk összefüggéseket, szabályosságokat. Ilyenek például az asszociációs szabályok vagy a funkcionális függőségek. - Osztályozás Az

előző feladat egy speciális esete: egy kiemelt attribútum értékét szeretnénk megjósolni a többi segı́tségével. - Klaszterezés Az objektumokat előre meg nem határozott csoportokba kell beosztani úgy, hogy a hasonló elemek azonos, a különböző elemek különböző csoportokba kerüljenek. - Sorozatelemzés Több feladat is ide tartozik: kereshetünk gyakori vagy éppen ritka, meglepő részsorozatot, vagy egy előre meghatározott mintához leginkább hasonlı́tó szakaszt. Másrészt lehet a célunk a sorozat általános viselkedésének feltárása, amelynek segı́tségével megjósolhatjuk, hogy várhatóan hogyan fog folytatódni. - Webes adatbányászat Az interneten található óriási mennyiségű adatból történő tudáskinyerés. Például ilyen feladat a kereső oldalak rangsorolási algoritmusának kialakı́tása vagy hasonló tartalmú oldalak keresése. A dolgozatban az

idősorok kapcsán elsősorban a klaszterezésről, az osztályozásról és a sorozatelemzési feladatokról lesz szó. 1.2 Az idősorokról általában Az utóbbi években nagyon sok cikk jelent meg az idősorokkal kapcsolatban. Az érdeklődés érthető, hiszen a heurisztikus definı́ciót használva (”valós számok rendezett sorozata”) gyakorlatilag bármit leı́rhatunk idősorral, amit mérések eredményeként kapunk, ı́gy a fizikában, a biológiában, a kémiában, a pénzügyek világában, az orvostudományban, mindenhol idősorokkal kapcsolatos feladatokra bukkanunk. A mérési eredmények kiértékelésénél olyan információkat szeretnénk megtudni, mint például hogy melyik a legjellemzőbb vagy éppen a legritkábban előforduló, legmeglepőbb részsorozat, a részsorozatok csoportosı́tása vagy annak eldöntése, hogy egy adott részsorozatot milyen folyamat generált Az idősorok

általában hosszúak, valós értékkészletűek, ı́gy elemzésük során nagy dimenziójú adatokkal kell dolgoznunk. A legtöbb adatbányász algoritmus viszont pont a dimenziószámra érzékeny, ezért törekszünk az adatok tömörı́tésére, reprezentálására, modellezésére. A dolgozatban két reprezentálási módszert hasonlı́tok össze: a szimbolikus reprezentációt és a wavelet reprezentációt 1.21 Példák idősorokra Szinte bármilyen rendezett adatsor idősornak tekinthető. Nézzünk néhány példát: 6 http://www.doksihu 1.1 ábra a) véletlen bolyongás b) tőzsde 1.2 ábra Villamosenergia-kérelem a) Hollandia b) Olaszország 1.3 ábra EEG 1.4 ábra a) Space Shuttle Marotta Valve - energia b) földrengés 1.3 Elnevezések, definı́ciók Szinte tetszőleges rendezett számhalmazt idősornak nevezhetünk. A dolgozatban a következő defibı́ciót fogjuk használni: 7

http://www.doksihu 1.5 ábra Kisbaba légzés 1.31 Definı́ció A T = t1 , t2 , , tm valós számokból álló szám m-est idősornak nevezzük 1.32 Definı́ció Ha C = tp , tp+1 , , tp+w−1 valamilyen 1 ≤ p ≤ m − w + 1 esetén, akkor a C-t a T idősor részsorozatának nevezzük. Ha hangsúlyozni szeretnénk, hogy a részsorozat a p-edik karaktertől indul, akkor a Cp jelölést fogjuk használni. Elemzéseink során gyakran fogunk hivatkozni a csúszóablakos módszerre, ezért nézzük meg az ehhez kapcsolódó fogalmakat: 1.33 Definı́ció Adott egy m hosszú T idősor és egy részsorozat, amelynek n hosszát a felhasználó ı́rja elő. A csúszóablakos módszerrel a T idősor összes n hosszúságú részsorozatát megvizsgáljuk úgy, hogy egy n hosszúságú ablakot görgetünk végig az idősoron. 1.34 Definı́ció Azt mondjuk, hogy a Cp és a Cq részsorozatok egyezése triviális, ha

valamilyen előre definiált ǫ konstansra |p − q| ≤ ǫ A kitűzött összes feladatban szükségünk van egy mértékre, amellyel két idősort vagy részsorozatot össze tudunk hasonlı́tani. Ennek a mértéknek a megválasztása egyáltalán nem egyértelmű feladat. Néhány példa: 8 http://www.doksihu 1.35 Definı́ció Adott két idősor, C és Q, mindkettő hossza n Az euklideszi távolságukat a következő módon definiálhatjuk: v u n uX Deucl (C, Q) = t (qi − ci )2 i=1 Ez a távolság bizonyos esetekben túlságosan merev, hiszen a mérések során azonos forrásból származó adatok tartalmazhatnak lokális torzı́tásokat, vagy lehetnek egymás kis mértékű nyújtott változatai. Ezeket mégis hasonlónak szeretnénk tekinteni Az idővetemı́tés módszere (Dynamic Time Warping, DTW) olyan mértéket ad, ami tolerálja ezeket a kis mértékű hibákat ([6]). Intuitı́van a DTW egy olyan

mérték, amely megengedi, hogy az összehasonlı́tandó idősorokat a távolság kiszámı́tása előtt lokálisan megnyújtsuk vagy összehúzzuk. A pontos definı́ció: 1.36 Definı́ció Legyenek adottak C = C1 , C2 , , Cn és Q = Q1 , Q2 , , Qm idősorok Ezek DTW távolsága: DT W (0, 0) = 0 DT W (C, 0) = DT W (0, Q) = inf   DT W (C, Rest(Q))   DT W (C, Q) = D(C1 , Q1 ) + min DT W (Rest(C), Q)    DT W (Rest(C), Rest(Q)) ahol Rest(C) = C2 , C3 , . , Cn és Rest(Q) = Q2 , Q3 , , Qm A későbbiekben találkozni fogunk olyan sorozatokkal, amelyeket véges, kis számú szimbólum alkot. Ezeken a legismertebb távolság a Hamming-távolság: megszámoljuk, hogy hány pozı́ción találunk eltérő karakterket. Ez azonban megint túl merev, gakorlati alkalmazásokban egy olyan távolságmértéket szeretnénk definiálni, ami azt mondja meg, hogy egy karakter beszúrásával, törlésével vagy

cseréjével milyen könnyen alakı́thatjuk át az egyik kifejezést a másikba. 1.37 Definı́ció Legyenek A és B szimbólumsorozatok, az i-edik szimbólimot ai -vel illetve bi -vel fogjuk jelölni, ED(i,j) pedig az a1 , a2 , . , ai és a b1 , b2 , , j részsorozatok szerkesztési távolságát ¯ jelöli. Ekkor A és B szerkesztési távolságát (edit distance) a következő dinamikus programozási algoritmus határozza meg: ED(0, 0) = 0 ED(0, i) = ED(i, 0) = i     ED(i − 1, j − 1) + Ham(ai , bj ) ED(i, j) = min ED(i − 1, j) + 1    ED(i, j − 1) + 1 ahol Ham(ai , bj ) a két szimbólum Hamming-távolsága, azaz 0, ha a két szimbólum megegyezik, 1, ha különbözőek. Több alkalmazásban az energia megőrzése a célunk. 9 http://www.doksihu 1.38 Definı́ció A c1 , c2 , , cn jelsorozat energiája: E= n X c2i i=1 A döntési fák felépı́tésénél azt az attribútumot

választjuk, amellyel a legjobban tudjuk csökkenteni az entrópiát. 1.39 Definı́ció Legyen A egy olyan attribútum (valószı́nűségi változó), ami k különböző értéket vesz fel p1 , . , pk valószı́nűséggel Ekkor A Shannon-entrópiája: H(A) = H(p1 , . , pk ) = − k X pi log2 pi i=1 Kölcsönös entrópiáról akkor beszélünk, ha lehetőségünk van egy B változót megfigyelni, majd ennek a megfigyelésnek a függvényében szeretnénk a bizonytalanságról mondani valamit. 1.310 Definı́ció Ha egy B attribútumot (valószı́nűségi változót) megfigyelünk és azt kapjuk, hogy B = bj , akkor az A-val kapcsolatos bizonytalanságunk: H(A|B = bj ) = − k X i=0 P (A = ai |B = bi )log2 P (A = ai |B = bi ) 1.311 Definı́ció A B attribútum (valószı́nűségi változó) megfigyelésével a bizonytalanság csökkenése: I(A, B) = H(A) − H(A|B) ahol H(A|B) = k X P (B = bi )H(A|B = bi

) i=1 Egy másik index amelyet döntési fák épı́tésénél használhatunk a Gini-index. 1.312 Definı́ció Az előző definı́ciókban használt jelölésekkel Gini(A) = 1 − 1.4 k X p2i i=1 Feladatok idősorokon Az idősorok sokszı́nűsége miatt a rajtuk végrehajtandó feladatok is nagyon változatosak. Egy értékpapı́r árának változásában kereshetünk szabályosságokat, tendenciákat, periodikusságot, de előfordulhat az ellenkező eset is, hogy éppen a szabálytalan, meglepő részsorozatok érdekelnek minket. A kinyert adatokat valószı́nűleg előrejelzésre szeretnénk majd használni Egy hipnogramban kı́váncsiak lehetünk az egyes alvásszakaszokat reprezentáló légzésmintázatra Szintén törekedhetünk előrejelzésre, például a hirtelen csecsemőhalál szempontjából veszélyeztett gyermekek kiszűrése egy nagy eredmény lenne. Egy kardiogramon meg kell tudnunk

különböztetni az egészséges, szabályos szı́vverést az abnormálistól. Mérési eredmények kiértékelése során több probléma is adódik. Először is a mért értékek pontatlanok, zajosak lehetnek Másrészt az adathalmaz mérete nagyon nagy lehet és előfordulhat, hogy az adatok dimenziója túl nagy. Ezen kı́vül nem egyértelmű, hogy milyen mértéket használjunk idősorok összehasonlı́tására, ez általában feladatfüggő. Az alábbiakban áttekintjünk azt a négy konkrét feladatot, amelyeket a dolgozatban részletesen vizsgálunk ([2]). 10 http://www.doksihu 1.41 Klaszterezés Adott egy idősorokat tartalmazó adatbázis. Feladatunk, hogy találjunk egy természetes csoportosı́tást valamilyen hasonlósági vagy különbözőségi mértékre nézve Célunk, hogy a mérték szerint hasonló idősorok azonos, a mérték szerint különböző idősorok különböző

csoportba kerüljenek. A feladat nehézségét az adja, hogy nem tudjuk, mik a csoportok, amelyekbe be akarjuk sorolni az idősorainkat, sőt, gyakran a csoportok számáról sincsenek előzetes ismereteink. További probléma a mérték kiválasztása, néhány lehetőség: euklideszi (négyzetes) távolság vektorok, szerkesztési távolság szimbólumsorozatok, idővetemı́tés (dynamic time warping) pedig olyan idősorok esetén, amelyeknél megengedhetők kisebb helyi torzulások. A klaszterező algoritmusok két nagy csoportja a hierarchikus és a particionáló klaszterezők. A hierarchikus klaszterezők vagy alulról felfele épı́tkeznek (kezdetben minden pont külön klaszter, majd minden lépésben összevonjuk a két legközelebbi klasztert), vagy fentről lefelé haladnak (kezdetben egy klaszterünk van, minden lépésben kettévágunk egy klasztert úgy, hogy a változás valamilyen mérték szerint a

lehető legnagyobb legyen). A partı́cionáló algoritmusok egy előre megadott k számú csoportot hoznak létre és ebbe sorolják be az elemeket A legismertebb partı́cionáló algoritmusok a k-közép és a k-medoid. 1.42 Osztályozás Adott egy idősorokat tartalmazó adatbázis, amelyben az idősorok csoportokba vannak osztva és adott egy új idősor, ami még nincs besorolva. Feladatunk, hogy megtaláljuk azt a csoportot, amelyhez a besorolandó idősor a legjobban hasonlı́t. A legismertebbek a k-legközebbi szomszéd módszere és a döntési fák. A k-legközelebbi szomszéd módszer esetén megkeressük az adatbázisban azt a k idősort, amely valamilyen (előre meghatározott) mérték szerint a legközelebb van a besorolandó idősorhoz. Feltételezzük, hogy a hasonlósági mértékünk ”jó”, vagyis az egymáshoz közeli idősorok hasonló tulajdonságokkal rendelkeznek A besorolandó idősor

csoportját a k legközelebbi szomszéd csoportja határozza meg többségi szavazással. A döntési fák módszere esetén igyekszünk egy modellt felállı́tani a csoportjainkra, amely különböző egyszerű döntési lépések során végül leı́rja, hogy milyen tulajdonságok jellemzőek az egyes csoportokra. A fa csúcsaiban a tulajdonságokra vonatkozó kérdések, a levelekben pedig a csoportok találhatók. 1.43 A legmeglepőbb részsorozat Idősorok elemzésénél szükségünk lehet a legmeglepőbb részsorozat megtalálására. Meglepő például egy szabálytalan szı́vverés egy kardiogramban, egy apnoé egy légzés-diagramban. Fontos lehet meglepő részek felderı́tése tőzsdei folyamatok idősorában is. A meglepetést tehát többféle módon definiálhatjuk: - Meglepő az a részsorozat az adatbázisra nézve, ami jelentősen többször vagy kevesebbszer fordul elő az

idősorban, mint amennyi az előfordulásának a várható értéke. - Meglepő az a részsorozat, ami jelentősen különbözik az idősor többi részsorozatától. Az első definı́ciót akkor használhatjuk, ha meg tudjuk határozni az egyes részfolyamatok előfordulásainak várható értékét. Ez csak akkor lehetséges, ha az idősorunk egy nem túl nagy diszkrét 11 http://www.doksihu halmazból veszi fel az értékeit. Folytonos adatsor esetén ugyanis minden érték és ı́gy minden konkrét részsorozat valószı́nűsége 0 és nagy értékkészlet esetén is túlságosan kicsi számokkal kellene dolgoznunk, illetve egy nem elég nagy minta könnyen torz becsléshez vezethet. A légzéses adatok ugyan diszkrétnek és véges értékkészletűnek tekinthetők, a valószı́nűségek becslése mégis reménytelen feladat. Ezért a második módon definiáljuk a legmeglepőbb részsorozatot:

1.41 Definı́ció A T idősorban azt az n hosszú részsorozatot nevezzük a legmeglepőbbnek, amelynek (euklideszi) távolsága a hozzá euklideszi távolságban legközelebbi nem triviális illeszkedésű részsorozattól a legnagyobb. 1.44 Motı́vumkeresés Adott egy idősorokat tartalmazó adatbázis és egy minta idősor. Feladatunk, hogy megtaláljuk az adatbázisban azt az idősort vagy részsorozatot, amely megegyezik a minta motı́vumunkkal vagy valamilyen előre adott érték szerint a legjobban hasonlı́t rá. A legegyszerűbb megoldás a csúszóablak módszere, amellyel megvizsgáljuk az összes olyan részsorozatot, ami azonos hosszúságú a mintánkkal, megállapı́tjuk, hogy azonosak-e vagy kiszámoljuk a távolságukat. A módszerrel biztosan jó eredményt kapunk, viszont a futási ideje négyzetes, ami a legtöbb valós életből vett probléma esetén nem megengedhető. Nem kell minden

részsorozatot átvizsgálnunk, ha létre tudunk hozni a mintaadatbázison egy jó indexelést, azaz egy olyan tömör leı́rást, amely alapján kevés részsorozat átvizsgálásával megtalálhatjuk a keresett motı́vumot. Az indexelési problémát kétféleképpen közelı́thetjük meg: bizonyos alkalmazásokban elég egy nagyon hasonló részsorozatot találni, máshol viszont szükség van arra, hogy megtaláljuk az adatbázisban a motı́vumhoz legközelebbi részsorozatot. Egy indexelőtől a következőket várjuk el: - Gyorsı́tsa fel lényegesen a motı́vum keresését - Az indexek terén nem lehet távoli olyan részsorozatot, ami az eredeti adatok terén közel van (false dismissal) - Az indexek terén közeli részsorozatok nagy része legyen közeli az eredeti adatok terén is (false alarm) - Az indexet ne kelljen újra előállı́tani, ha az adatbázisból törlünk vagy új elemet szúrunk be. A

index előállı́tásának gyorsı́tására az adatainkat különböző módokon reprezentálhatjuk, ám ekkor figyelni kell, hogy a reprezentáció során ne veszı́tsünk el helyes találatokat. Ez a feltétel biztosan teljesül, ha a reprezentált idősorokon bevezetett mérték alulról becsüli az eredeti idősorokon használt mértéket. 1.5 A dolgozat felépı́tése Dolgozatomban az idősorok két lehetséges modelljét szeretném összehasonlı́tani. A második fejezetben a szimbolikus reprezentációról, a harmadikban pedig a Fourier- és wavelet-reprezentációkról lesz szó. Ezekben a fejezetekben először a módszer elméletét ı́rom le, majd a fejezet második felében bemutatom, hogy az adott modell hogyan használható a bevezetésben kitűzött feladatok megoldására. Végül a negyedik fejezetben a mérési eredményeken keresztül összehasonlı́tom a két módszer hatékonyságát

az egyes feladatokon. 12 http://www.doksihu 2. fejezet Szimbolikus reprezentáció Ebben a fejezetben a szimbolikus reprezentációt mutatom be. Először megindokolom, hogy miért szükséges az adatokat tömörı́teni, majd leı́rom a konkrét SAX illetve PAA módszert és megvizsgálom, hogy milyen hatása lehet a paraméterek változtatásának. A fejezet második részében a módszer gyakorlati hasznáról lesz szó, az anomália detektálás esetén részletesen ismertetek egy algoritmust, a motı́vumkeresésnél pedig a SAX egy lehetséges továbbfejlesztését mutatom be. 2.1 Reprezentációról általában A valós életből vett adatsorok általában hosszúak és valós értékkészletűek, ezért ha az eredeti formájukban próbáljuk feldolgozni őket, akkor az adataink nagyon nagy dimenziósok lesznek. Mivel a legtöbb adatbányász algoritmus érzékeny a dimenziószámra, ezért

törekszünk az adatokat tömörı́teni, kis dimenziós objektumokkal reprezentálni. Az idősorok esetén a tömörı́tés mellett szól az is, hogy az adatpontok között nagy a korreláció, a reprezentációval a felesleges redundanciát is csökkentjük. Felmerül a kérdés, hogy mennyit veszı́tünk a tömörı́téssel. A vizsgált feladatoknál a kulcs mindig a távolságfüggvény, hiszen minden algortimus során valahol közeli részsorozatokat kell keresnünk. Így a reprezentált adatokon végzett elemzés során kétféle hibát követhetünk el: - Téves riasztás (false alarm) Téves risztásról akkor beszélünk, ha a reprezentált részsorozatokat a keresés során közelinek találtuk, viszont a valóságban távoliak. Ezt a hibát gyorsan tudjuk ellenőrizni és javı́tani - Téves elhagyás (false dismissal) Komolyabb problémát jelent, ha közeli adatok egymástól messze kerülnek a

reprezentáció során, ı́gy a kisebb téren kereső algoritmus ezeket nem találja meg. Ez a hiba csak négyzetes időben, az összes részsorozat átvizsgálásával derı́thető fel, ı́gy a gyakorlatban nem megengedhető. A téves elhagyás elkerülésének érdekében olyan mértéket kell választanunk a reprezentált objektumok terén, ami alulról becsüli az eredeti mértéket az eredeti adatok terén, azaz bármely két C és Q részsorozatra teljesülnie kell: Drepr ter (C, Q) ≤ Deredeti (C, Q) 13 http://www.doksihu ahol C és Q a C ill. a Q reprezentáltjait jelölik Ha ez a feltétel teljesül, akkor biztosak lehetünk benne, hogy ha két részsorozat az eredeti mérték szerint közel volt egymáshoz, akkor a reprezentáltjaik legalább ugyanannyira közel lesznek egymáshoz, ı́gy az algoritmusunk során téves elhagyás nem történhet. Másrészt a téves riasztások számának

csökkentése érdekében törekednünk kell arra, hogy a reprezentációnk minél pontosabban közelı́tse a vizsgálandó idősort. A reprezentáció jóságát a reprezentáció szorosságával jellemezzük: 2.11 Definı́ció A reprezentáció szorossága alatt a Drepr ter (C,Q) Deredeti (C,Q) hányadost értjük. Minél közelebb van ez a hányados az egyhez, annál pontosabb eredményeket várhatunk. 2.11 SAX - Symbolic Aggregate approXimation Az idősorok gyakran valós értékeket vesznek fel, ı́gy az értékkészletük gyakorlatilag végtelen elemszámú. Az adatbányász algoritmusok hatékony futtatása érdekében elengedhetetlen az értékek diszkretizálása és a tömör leı́rás, ezért igyekszünk az idősorunkat egy minél kisebb diszkrét térbe leképezni. Az ötlet, hogy ez a tér néhány, például az ABC betűivel reprezentált osztályt tartalmazzon, természetesen jön a

biológia területéről, ahol az egyik fontos kutatási terület a DNS láncok elemzése. A DNS négyféle épı́tőkőből épül fel: adenin, cytosin, guanin és timin [1] Az ilyen, négyféle szimbólumból álló sorozatok elemzésére, összehasonlı́tására, csoportosı́tására már sok módszert kifejlesztettek, amiket négytől különböző számú szimbólumra általánosı́tva más tı́pusú adatok elemzésére is felhasználhatunk. A SAX reprezentációt két lépésben hajtjuk végre: 1. Először az idősor l hosszú darabjait közelı́tjük egy konstanssal (Piecewise Aggregate Approximation) 2. Ezután az értékkészlet részekre bontásával a konstans függvénydara-bokhoz rendelünk egyegy cı́mkét Ezt a két lépést úgy kell végeznünk, hogy a konstans közelı́tés alsó becslést adjon az eredeti távolságokra, a szimbolikus reprezentáció pedig (a szimbólumok

közötti megfelelő távolságfüggvénnyel) alsó becslést adjon a konstans reprezentációra. 2.12 PAA - Piecewise Aggregate Approximation Az idősor l0 -adik elemétől kezdve l elemenként az idősort egy konstans függvénnyel közelı́tjük. Keogh cikkeiben ez az l szám átlaga, de lehetséges más becslés is, pl. a medián vagy a négyzetesen legjobb konstans ([2]). Legyenek C = c1 c2 . cn és Q = q1 q2 qn két idősor C és Q távolságát a következő módon definiáljuk: v u n uX D(C, Q) = t (qi − ci )2 i=1 Legyen C konstans reprezentációja C, Q konstans reprezentációja Q és legyen w = 14 n l. Ekkor C és http://www.doksihu Q távolsága: v r u w X nu t (q − ci )2 D(C, Q) = w i=1 i A függelékben bebizonyı́tjuk, hogy ezekre a távolságfüggvényekre igaz az alsó becslés. 2.13 Más távolságfüggvények Keogh cikkeiben az adatok hagyományos átlagával közelı́ti az

idősor részsorozatait, az eredeti téren pedig az euklideszi távolságot használja. Az átlaggal való a közelı́tés egyszerű, alulról becsüli az idősorok eredeti távolságát és a gyakorlatban jól működik. Érdemes azonban megfontolni, hogy nem érhetnénk-e el még jobb eredményeket más, esetleg bonyolultabb közelı́tési módszerekkel. A legtermészetesebb ötletek a medián és a négyzetesen legjobb közelı́tés. Az eredeti részsorozatok távolságára alternatı́v lehetőség az idővetemı́tés (DTW - Dynamic Time Warping), a szimblikus sorozatok távolságára pedig a szerkesztési távolság. A medián megtalálásához sorba kell rendeznünk a részsorozat értékeit, de mivel a reprezentált szakaszok általában nem túl hosszúak, ez nem lassı́tja jelentősen a futást. A probléma az alsókorlát tulajdonsággal van: a medián nem becsüli alulról az eredeti távolságot

Ez a tény szinte nyilvánvaló, de a függelékben egy ellenpéldával bizonyı́tom is az állı́tást. A négyzetes közelı́tést kétféleképpen is értelmezhetjük: az adatokat egy konstanssal közelı́tjük vagy érthetjük alatta a klasszikus ”legkisebb négyzetek módszerét” is, ahol a közelı́tő függvény egy egyenes. Az első esetben azt kapjuk, hogy a legjobb konstans éppen az átlag, bizonyı́tást a függelékben adunk. A második esetben veszı́tünk egy keveset a reprezentáció egyszerűségéből, hiszen a közelı́tő egyenest két paraméter adja meg. Ezen kı́vül definiálnunk kell két egyenes távolságát, ezt megtehetjük például a következő módon: Legyen a két idősor (x1 , c1 ), (x2 , c2 ), . , (xn , cn ) és (x1 , q1 ), (x2 , q2 ), , (xn , qn ), ahol xi -k a pontok x-koordinátái Legyen a ci -kre illeszkedő egyenes egyenlete y = a1 x + b1 , a qi -kre illeszkedő

egyenes egyenlete y = a2 x + b2 . Ekkor a két egyenes távolsága legyen: D(linC , linQ ) := n X i=1 2 (a1 − a2 )xi + (b1 − b2 ) Ez a távolság alulról becsüli az euklideszi távolságot. (A tapasztalatok szerint, sokszor lefuttatva Bizonyı́tanom még nem sikerült.) Az idővetemı́tés azon az ötleten alapul, hogy azonos forrásból származó idősorok is lehetnek nagyon különbözőek, például egymás nyújtott változatai, illetve tartalmazhatnak lokális torzulásokat. Ilyen például a hangfelismerés, hiszen nem valószı́nű, hogy valaki kétszer teljesen ugyanúgy ejtsen ki egy mondatot, mégis szeretnénk felismerni az elhangzott szavakat vagy adott esetben a beszélő személyt. Szeretnénk tehát egy olyan mértéket, ami tolerálja a lokális torzulásokat Intuitı́van a DTW egy olyan mérték, amely megengedi, hogy az összehasonlı́tandó idősorokat a távolság kiszámı́tása előtt

lokálisan megnyújtsuk vagy összehúzzuk ([6]). A távolság kiszámolásának módját a definı́ciók között már megadtuk. Az idővetemı́tés tehát egy olyan távolság-mérték, ami közelebb áll az idősorok távolságáról alkotott fogalmainkhoz, azaz közelinek nyilvánı́tja a hasonló idősorokat, szemben az euklideszi 15 http://www.doksihu 2.1 ábra Két hasonló idősor euklideszi és DTW távolsága távolsággal, ami ebben ez értelemben nagyon merev. A DTW távolság dinamikus programozási módszerrel lineáris időben számı́tható abban az esetben, amikor korlátozzuk a nyújtás mértékét, ezen kı́vül Keoghék kidolgoztak további távolságmértékeket, amelyek még hatékonyabban számı́thatók és alsó becslést adnak a DTW-re ([6]). Sajnos azonban a PAA nem becsüli alulról, ı́gy ebben a dolgozatban ezzel a módszerrel nem fogunk foglalkozni. Nyilván ha már a

DTW sem becsüli alulról a PAA-t, akkor a belőle levezetett további mértékek sem fogják. Arra, hogy a DTW-re nem igaz az alsó becslés, a függelékben mutatok példát. Tehát a felmerült ötleteket a következő táblázatban foglalhatjuk össze: közelı́tés a PAA-ban: átlag euklideszi idővetemı́tés medián négyzetesen legjobb négyzetesen legjobb konstans szakasz alsó becslést ad nem ad megegyezik alsó becslést ad (bizonyı́tva) alsó becslést az átlaggal (a mérések szerint) nem ad - - - alsó becslést 2.14 Szimbólumok Az értékkészlet részekre bontásához egy sűrűségfüggvényt használunk, amelylyel elérjük, hogy az egyes szimbólumok azonos valószı́nűséggel forduljanak elő. Keogh és társai cikkeikben ([2], [3]) a normális eloszlást javasolják. Érdemes azonban megfontolni más sűrűségfüggvény használatát, például nagy a priori

adatbázis esetén használhatjuk az empirikus eloszlást, vagy konkrét példánkon, a légzési adatokon az inverz sinus függvényt. A szimbólumok megadása a következő módon történik: - Kiválasztjuk a sűrűségfüggvényt és eldöntjük, hogy hány különböző szimbólumot szeretnénk használni, legyen ez a szám k, a szimbólumainkat jelöljük αi -vel. - Az értékkészletet a sűrűségfüggvény segı́tségével azonos valószı́nűségű tartományokra osztjuk, az osztópontokat jelöljük βi -vel! Megegyezés szerint β0 = −∞, βk = ∞. Jelöljük a C részsorozat szimbolikus reprezentánsát Ĉ-pal! Ekkor a következő szabályt ı́rhatjuk fel: Ĉ = αi ⇐⇒ βi−1 ≤ C < βi A szimbólumok között a következő távolságfüggvényt definiálhatjuk: 16 http://www.doksihu 2.2 ábra Reprezentáció szimbólumokkal dist(αi , αj ) = ( 0 ha i = j

βmax(i,j)−1 − βmin(i,j) ha i 6= j Szavakkal: a távolság a nagyobb szimbólum sávjának alsó határa és a kisebb szimbólum sávjának felső határa közötti különbség, ha a két szimbólum különböző, 0, ha a két szimbólum megegyezik. Megjegyezzük, hogy a távolság definı́ció szerint akkor is 0, ha a két szimbólum szomszédos. Nyilvánvaló, hogy ha ı́gy definiáljuk a szimbólumok távolságát, akkor egy szimbólumsorozat távolsága alulról becsüli a PAA közelı́tés távolságát. 2.3 ábra Két idősor euklideszi és PAA távolsága 2.15 Sűrűségfüggvények Az adatok repreztentálásához meg kell találnunk a legmegfelelőbb sűrűségfüggvényt. Célunk, hogy az egyes reprezentáns elemek nagyjából azonos valószı́nűséggel forduljanak elő. Ez azért szükséges, hogy a reprezentáció elég ”finom” legyen, azaz ahol sokféle egymáshoz

közeli értéket vehet fel a függvény, ott a lehetséges reprezentáns elemekből is több kell, hogy ne vesszenek el a részletek. Keogh és társai cikkeikben ([2], [3]) azt állı́tják, hogy ha elég sok normált részsorozatot tekintünk, akkor a felvett értékek eloszlása a normális eloszláshoz tart. Ez azonban korántsem ilyen nyilvánvaló, hiszen a különböző tı́pusú idősorok különböző jellemzőkkel rendelkeznek, ezért (várhatóan) különböző lesz a részsorozataik értékeloszlása. 17 http://www.doksihu Különösen igaz ez, ha a vizsgált adatok valamilyen értelemben periodikusnak mondhatók. Az energia-adatok esetén például napokat illetve heteket vizsgálunk, szemmel is látszik, hogy ezeket a részsorozatokat normálva és átlagolva a sűrűségfüggvény az értékintervallum két szélén, nem pedig középen lesz a maximális. A NASA adatai esetén az egyes

feltöltéseket érdemes részsorozatnak tekinteni, itt még szembetűnőbb a periodikusság jelentősége, a sűrűségfüggvény szinte teljesen két értékre koncentrálódik. Érdekes megvizsgálni a kisbabás adatokat, ahol a periodikusság nem ilyen szembetűnő, a lélegzetek frekvenciája és amplitúdója is változik az alvás során. Sok idősor esetén tehát azt várjuk, hogy találunk a normális eloszlásnál jobb sűrűségfüggvényt is. A választásunkat az idősorról szerzett korábbi ismeretek befolyásolják és ez alapján választhatunk függvényt. Másrészt kézenfekvő az az ötlet is, hogy a birtokunkban levő adatokat elemezve empirikus úton határozzuk meg az ideális eloszlást Az előzetes ismeretek felhasználása mindig azt a veszélyt hordozza magában, hogy helytelen feltételezésekkel befolyásoljuk a mérést és nem találjuk meg az adatokban rejlő valódi, de

előre nem sejtett összefüggéseket. A légzési adatok esetén például felmerül, hogy az inverz sinus függvényt használjuk, feltételezve ezzel, hogy a légzésgörbék a sinus-görbéhez hasonlóak. Ez azonban csak bizonyos alvásszakaszokra jellemző, általánosságban nem igaz. Az empirikus megközelı́tés egy másik hibát, a túltanulást okozhatja könnyen. Szintén probléma, hogy szükségünk van tanuló adatokra. Az empirikus eloszlás majd a különböző valószı́nűségi szintek megállapı́tása időigényes és lehet, hogy a megállapı́tott osztályok csak a tanuló adatokra érvényesek. Mégis, megbı́zható előzetes ismeretek esetén ez a legjobb módszer, ha a feldolgozandó idősor periodikusnak mondható. 2.2 2.21 A SAX alkalmazásai Klaszterezés A klaszterezőknek két nagy fajtáját különböztetjük meg: a hierachikus és a particionáló klaszterezőket.

Keogh-ék egy cikkükben ([2]) részletesen megvizsgálták a PAA hatékonyságát mindkét esetben, összehasonlı́tva a kapott eredményeket a nyers adatokon kapott csoportosı́tással illetve más reprezentáló módszerek teljesı́tményével. Azt várnánk, hogy a nyers adatokon ha lassabban is, de jobb eredményeket kapunk, mint a reprezentáltakon, hiszen sokat veszı́tünk a részletekből. A tapasztalatok viszont pont az ellenkezőjét mutatják, a reprezentálással nem veszı́tünk, sőt, bizonyos esetekben nyerünk, jobb eredményeket érhetünk el. A hierarchikus klaszterezők futási ideje túl nagy, ezért a gyakorlatban nem használjuk őket, viszont kiválóan alkalmasok a különböző távolsági mértékek tesztelésére. A PAA és az euklideszi (négyzetes) távolságfüggvény esetén azt kapjuk, hogy a PAA gyakorlatilag lemásolja az euklideszi mértéket, szinte pontosan ugyanazokat a

csoportokat állı́tja elő. A reprezentált adatok jó szereplése nem is olyan meglepő ha arra gondolunk, hogy a tömörı́tés az adatvesztés mellett előnyökkel is jár: simı́tó, zajszűrő hatása van és csökkenti az egymást követő adatok közötti redundanciát is. A partı́cionáló klaszterezők közül a legismertebb a k-means, a cikkben is ezt használták. Itt az eredmény még meglepőbb: a tömörı́tett adatokon futtatott klaszterezés jobb eredményeket adott, mint amikor a nyers adatokat használták. Ennek az oka az, hogy a k-means az adatok dimenziószáma mellett érzékeny a kezdeti középpontokra is, az algoritmus egyik fő gyengesége, hogy gyakran akad el lokális optimumban. Ezért az adatok tömör reprezentációja két szempontból is javulást okoz: egyrészt sokkal gyorsabb lesz a futás, ı́gy több kı́sérletet végezhetünk, amelyek 18 http://www.doksihu közül a

legjobbat tekintjük végeredménynek, másrészt a tapasztalatok azt mutatják, hogy kisebb dimenziós adatokon kisebb az esélye, hogy elakadunk egy lokális optimumban. Ezért az adatok nagyon durva, nagyon nagy mértékű tömörı́tése is jó eredményt adhat: az ezeken futtatott kmeans optimális középpontjait egy kevésbé tömör reprezentációnak vagy akár az eredeti adatoknak továbbadva a k-means gyorsabban fog konvergálni, mint véletlenül választott középpontok esetén és talált klaszterek is pontosabbak lesznek. 2.22 Osztályozás A SAX nagy előnye az osztályozókat tekintve, hogy a kimenete szimbólumok egy sorozata, amit a legtöbb algoritmus jól kezel. Célunk olyan döntési fák létrehozása, amely áttekinthető, érthető leı́rást ad az egyes osztályokról. Ehhez a szabályoknak rövideknek kell lenniük, a döntési fák pedig nem lehetnek túl mélyek, sem pedig túl

elágazóak. Az osztályozók valós adatokra is jól működnek, mégsem célszerű az eredeti adatokon futtatni őket. Problémát okoz a nagy dimenziószám, ami jelentősen lelassı́tja a futást, ezen kı́vül a nyers adatok rendszerint zajosak és sok redundanciát tartalmaznak, ami miatt a fent leı́rt elvárások nem teljesülnek, az osztályozó nagy és lombos fákat ad eredményül. A reprezentációval a zajt és redundanciát jelentősen tudjuk csökkenteni, ı́gy a szétágazó fa problémáját ki tudjuk küszöbölni. Kimondottan a SAX-ra épülő osztályozó algoritmust az irodalomban nem találtam, de több cikk is beszámolt arról, hogy a klasszikus algoritmusokat a reprezentánsra alkalmazva jó, gyakran az eredeti adatokon végzett elemzésnél jobb eredményeket kapunk ([2]). 2.23 Anomália detektálás Ebben a részben a meglepetés második definı́cióját fogjuk használni, vagyis

azt a részsorozatot keressük, aminél a legnagyobb a hozzá legközelebbi részsorozat távolsága ([3]). A következő jelöléseket fogjuk használni: a T idősorban keressük a legmeglepőbb n hosszúságú részsorozatot. T hosszát jelöljük N -nel Kézenfekvő megoldás a ”brute force” algoritmus, vagyis az, hogy az összes részsorozatot összehasonlı́tjuk az összes elég távoli részsorozattal és ı́gy keressük meg a legmeglepőbbet: Function [dist,loc]=Brute Force(T,n) eddigi legjobb tav=0 eddigi legjobb hely=NaN For p=1 to |T|-n+1 legkoz szomsz tav=infinity For q=1 to |T|-n+1 If |p-q|≥n If Dist(tp , . , tp+n−1 , tq , , tq+n−1 )<legkoz szomsz tav legkoz szomsz tav=Dist(tp , . , tp+n−1 , tq , , tq+n−1 ) End End End If legkoz szomsz tav>eddigi legjobb tav 19 http://www.doksihu eddigi legjobb tav=legkoz szomsz tav eddigi legjobb hely=p End End Return[eddigi legjobb tav,eddigi legjobb hely] Bár ezzel

az algoritmussal biztosan pontos eredményt kapunk, a gyakorlatban nem tudjuk használni. A keresés során minden n hosszúságú részsorozatot összehasonlı́tunk az összes többi n hosszú részsorozattal, tehát a futási idő O(N 2 ) lesz, ami nem megengedhető. Néhány egyszerű ötlettel azonban a futási idő jelentősen csökkenthető: - A belső ciklusban nem szükséges megkeresnünk a tényleges legközelebbi szomszédot, hiszen amint találunk egy olyan nem triviális részsorozatot, amely közelebb van a vizsgált részsorozathoz, mint az eddigi legmeglepőbb részsorozat távolsága a hozzá legközelebbi részsorozathoz, abbahagyhatjuk a legközelebbi szomszéd keresését, a vizsgált részsorozat nem lesz a legmeglepőbb. - A futás ideje függ attól, hogy milyen sorrendben vizsgáljuk át T részsorozatait. Ha gyorsan sor kerül a legmeglepőbb részsorozatra, akkor sok esetben fog a belső ciklus

gyorsan leállni. Ezeket a módosı́tásokat könnyen beépı́thetjük a kódba: Function [dist,loc]=Javitott Kereses(T,n) eddigi legjobb tav=0 eddigi legjobb hely=NaN For Each p a Kulso rendezett listabol legkoz szomsz tav=infinity For Each q a Belso rendezett listabol If |p-q|≥n If Dist(tp , . , tp+n−1 , tq , , tq+n−1 )<eddigi legjobb tav Break End If Dist(tp , . , tp+n−1 , tq , , tq+n−1 )<legkoz szomsz tav legkoz szomsz tav=Dist(tp , . , tp+n−1 , tq , , tq+n−1 ) End End End If legkoz szomsz tav>eddigi legjobb tav eddigi legjobb tav=legkoz szomsz tav eddigi legjobb hely=p End End Return[eddigi legjobb tav,eddigi legjobb hely] Mint látni fogjuk, ”jó” rendezés esetén a futási idő lineárisra csökken. Azt kell tehát megvizsgálnunk, hogy mit várunk a Kulso rendezett és a Belso rendezett listától és hogy mennyi időt és tárat igényel ezek előállı́tása és tárolása. Célunk, hogy mind a

futási idő, mind a tárigény O(N ) legyen. A lehetőségeink a következő skálán mozognak: 20 http://www.doksihu - Véletlen rendezés A legegyszerűbb stratégia, ha mind a külső, mind a belső ciklusban véletlenszerű sorrendben vizsgáljuk meg a részsorozatokat. Bár a tapasztalat azt mutatja, hogy ı́gy is érezhetően gyorsabban fut le a második algoritmus, gyakran fogjuk korán elhagyni a belső ciklust, elméletileg csak keveset tudunk mondani a javulás mértékéről. Mint a következő két pontban látni fogjuk, az elméleti alsó korlát a legjobb rendezés esetén O(N ), a felső korlát a lehető legrosszabb rendezés esetén viszont O(N 2 ). - Legjobb rendezés A legjobb eredményt akkor kapjuk, ha a részsorozatok a Kulso rendezett listában a legközelebbi nem triviális szomszéd távolsága szerint csökkenő sorrendben, a Belso rendezett listában pedig az aktuális jelölttől vett

távolság szerint növekvő sorrendben vizsgáljuk meg az elemeket. Ha egy jóindulatú orákulum előállı́tja nekünk ezt a két listát, a javı́tott algoritmus nagyon gyorsan lefut: rögtön az első részsorozat a legmeglepőbb lesz, vagyis az eddigi legjobb tav változó rögtön a lehető legnagyobb értéket veszi fel, az összes többi részsorozat esetén pedig az első összehasonlı́tásnál azonnal elhagyjuk a belső ciklust. A legjobb rendezés esetén tehát a futási idő O(N ) - Legrosszabb rendezés A lehető legrosszabb rendezést úgy kapjuk, ha a legjobb rendezésben felcseréljük a ”növekvő sorrend” és a ”csökkenő sorrend” szavakat. Ha egy rosszindulatú orákulum ı́gy rendezi a részsorozatokat, akkor ugyanazt az eredményt kapjuk mint a Brute Force algoritmus esetén: egyszer sem fogunk kilépni a belső ciklusból, minden részsorozatot összehasonlı́tunk az összes többi

részsorozattal, a futási idő O(N 2 ) lesz. A legjobb rendezést nyilván nem tudjuk előállı́tani lineáris időben: a belső ciklusban teljes rendezést használunk, ami legalább O(N logN ) időt vesz igénybe. A külső ciklus teljes rendezése még rosszabb, O(N 2 ) futási időt jelent. Néhány engedményt téve azonban ”elég gyorsan” tudunk előállı́tani egy ”elég jó” rendezést. Nem szükséges ugyanis a részsorozatainkat tökéletesen rendezni, elég, ha a külső ciklusban az első néhány lépésben nagyra tudjuk beállı́tani a eddigi legjobb tav változót és ha a belső ciklusban az első néhány lépésben mindig találunk egy közeli részsorozatot, azaz már az első néhány lépés után kiugrunk a belső ciklusból. Keogh és társai cikkükben ([3]) a már ismertetett SAX reprezentációt használják, az elég jó rendezéshez pedig a szimbólumsorozatokból

épı́tettek egy keresőfát és egy indextáblázatot. Az indextáblázat tartalmazza az idősor pozı́cióit, az összes pozı́cióhoz feljegyezzük az onnan induló részsorozat szimbolikus reprezentánsát. Ezen kı́vül a táblázatban tároljuk, hogy az adott szimbolikus sorozatból mennyit találtunk eddig az idősorban A keresőfa éleit a szimbólumokkal cı́mkézzük, a gyökértől egy levélig vezető úton egy szimbolikus reprezentánst tudunk kiolvasni. A levelekhez egy listát láncolunk, amely az idősor azon pozı́cióit tartalmazza, amelyekről kiindulva pontosan ezt a szimbólumsorozatot kapjuk reprezentánsként. Mindkét struktúra előállı́tható lineáris idő és tárhely felhasználásával. Használatuk szintén gyors: az indextábla használatával azonnal meg tudjuk mondani egy adott pozı́cióról induló részsorozat szimbolikus reprezentánsát, a keresőfa segı́tségével

pedig O(1) időben megtaláljuk azokat a pozı́ciókat, amelyek ugyanazzal a reprezentánssal rendelkeznek. A fenti két adatszerkezetet használva tehát a következő módon célszerű elkészı́teni a listákat: - Külső rendezés Feltételezzük, hogy annak a részsorozatnak, ami a leginkább eltér a többitől, a szimbolikus reprezentánsa is ritka lesz a többi szimbólumsorozat között. Mivel az indextáblázatban 21 http://www.doksihu azt is tároltuk, hogy az adott reprezentánsból hányat találtunk az előállı́tás után, gyorsan meg tudjuk keresni azokat, amelyekből csak kevés fordult elő. A gyakorlati tapasztalatok azt mutatják, hogy a minimális érték szinte mindig 1, azaz lesz olyan szimbólumsorozat, amely csak egyetlen részsorozat transzformációjaként áll elő. A külső ciklusban tehát ezeket a részsorozatokat vizsgáljuk meg először (például a megtalálás sorrendjében), a

többit pedig véletlenszerű sorrendben. - Belső rendezés A belső rendezés esetén az a célunk, hogy gyorsan találjunk egy olyan nemtriviális illeszkedésű részsorozatot, aminek a távolsága kicsi a vizsgált részsorozattól, hiszen ha ez a távolság elég kicsi, akkor elhagyhatjuk a belső ciklust és ugorhatunk a következő elemre a Kulso rendezett listában. Itt is élünk a feltételezéssel, hogy hasonló részsorozatoknak hasonló, különböző részsorozatoknak különböző a szimbolikus reprezentánsa, azaz először azokat a részsorozatokat szeretnénk összemérni a vizsgálttal, amelyeknek ugyanaz a szimbólumsorozat a reprezentánsa. Ezeket pontosan a keresőfa adott leveléhez láncolva találjuk meg, először tehát ezt a listát kell átnézni, utána pedig, ha még nem hagytuk el a belső ciklust, a többi elemet véletlenszerű sorrendben vizsgáljuk át. 2.24 Motı́vumkeresés

Szeretnénk elérni, hogy tetszőleges motı́vumot gyorsan megtaláljunk egy rendelkezésre álló idősorban, ne kelljen minden egyes lehetséges részsorozatot megvizsgálnunk. Erre szolgál az idősorok indexelése, vagyis az egyes részsorozathoz egy cı́mkét rendelünk és adott motı́vum érkezésekor már csak a cı́mkék között illetve bizonyos cı́mkékkel rendelkező részsorozatok között keresünk. Az indexet létrehozó szimbólumok száma és a cı́mke hossza korlátozza a lehetőségeinket, hiszen ilyen módon csak véges sok, az idősorból kinyerhető részsorozatok számához képest nagyon kicsi a létrehozható indexek száma. Célunk, hogy ha a keresendő motı́vumhoz kiszámoljuk az indexét, akkor a részsorozatok között már csak keveset kelljen átvizsgálnunk ahhoz, hogy megtaláljuk a motı́vumhoz legközelebbit. Ha megfelelően állı́tjuk be a fenti két paramétert, akkor

elérhetjük, hogy az egyes cı́mkék alá átlagosan még ne túl sok, vagyis kezelhető mennyiségű részsorozat kerüljön. Ez azonban nem működik a gyakorlatban: a valós életből vett adatok között sok a hasonló, ı́gy egyes cı́mkék nagyon sok, kezelhetetlen mennyiségű részsorozatot jelölhetnek, mı́g más cı́mkék esetleg egyáltalán nem fordulnak elő a vizsgált idősor részsorozatai között. Keoghék cikkükben ([5]) úgy módosı́tották a SAX algoritmust, hogy képes legyen szintenként előállı́tani az indexeket, vagyis elérték, hogy a sűrűn előforduló részsorozatokat hosszabb, a ritka részsorozatokat pedig csak rövid indexekkel jelöljük. Ezzel a módszerrel ott alkalmazhatunk pontosabb, részletesebb felbontást, ahol arra tényleg szükség van, a ritkán előforduló részsorozatokat néhány lépés után már nem elemezzük tovább, ezzel jelentős időt

takarı́tva meg. További előny, hogy az ı́gy előállı́tott indexek egy fa-szerkezetet hoznak létre, ezért gyorsan tudunk keresni és mivel a részsorozatokat átfedésmentesen osztja csoportokba, ezért a leghasonlóbb részsorozat megtalálásához elég a fa egyetlen levelében található jelölteket átvizsgálni. Az i SAX index meghatározásához a SAX reprezentáció azon változatait használják, ahol a szimbólumok száma 2n valamely n egészre, magukat a szimbólumokat is bináris alakban adják meg, ami majd az indexek gyors előállı́tásánál lesz hasznos. Ha előre megadjuk, hogy mekkora n értékre szeretnénk 2n különböző cı́mkét előállı́tani, akkor a reprezentáns a már látott módon sorolja be a részsorozatokat. Viszont ha a fent leı́rt finomı́tást szeretnénk használni és továbbra 22 http://www.doksihu is a pontos i SAX reprezentánst szeretnénk megkapni, akkor

újra kellene számolnunk az adott részdorozat beosztását, amit nyilván nem szeretnénk, ı́gy egy közelı́tő módszert alkalmazunk. A reprezentánsokat tehát a következő módon számoljuk ki: - Tegyük fel, hogy már rendelkezésünkre áll a S részsorozat SAX(S, l, 2n ) reprezentánsa, ahol 2n a szimbólumok száma, l pedig a reprezentáció hossza. Ezt szeretnénk a SAX(S, l, 2n+c ) reprezentációra finomı́tani. Továbbá már van egy T részsorozatunk egy finomabb, SAX(T, l, 2n+c ) felbontással. - Ha a SAX(S, l, 2n ) reprezentáció szimbólumonként prefixe a SAX(T, l, 2n+c ) reprezentánsnak, akkor S számolandó koordinátáit a T megfelelő koordinátáival egészı́tjük ki. - Ha nem áll a rendelkezésünkre ilyen T , akkor a kiegészı́tést szimbólumonként végezzük: ha az S reprezentáló szimbólumsorozata lexikografikusan kisebb, mint a T megfelelő szimbólumsorozata, akkor minden

számolandó helyiértékre 1-et ı́runk, az ellenkező esetben pedig minden számolandó helyiértékre 0-t ı́runk. Ez a szó természetesen nem egyezik meg azzal, amit akkor kaptunk volna, ha már kezdetben n + c bittel reprezentáltuk volna az S részsorozatot, de ez az index egy jó alsó becslést ad és sokkal könnyebben számolható, tehát a gyakorlatban jól használható. Másrészt ez a módszer használható akkor is, ha egy szó indexe esetleg különböző bitszámú reprezentációkból állna, hiszen ezzel a becsléssel a rövid koordinátákat gyorsan kiegészı́thetjük a megfelelő hosszúságúvá. Az index előállı́tásához először minden részsorozatot reprezentálunk egy előre meghatározott részletességgel, majd ha van olyan levelünk, amelyhez túl sok részsorozat tartozik, akkor ott tovább finomı́tjuk a reprezentánst, amivel további csoportokba soroljuk a sorozatokat. A

keresésnél élünk azzal a feltételezéssel, hogy hasonló részsorozatoknak hasonló lesz a reprezentánsa, vagyis olyan részsorozatokat vizsgálunk, aminek az indexe megegyezik a motı́vumhoz számolt indexszel, vagy legalábbis nagyon hasonlı́t rá. Amennyiben egy a motı́vumunkhoz ”eléggé hasonló” részsorozatok szeretnénk találni, a keresés nagyon gyors lesz, elég a fában végiglépkedni az indexeken és a levélben átvizsgálni az ott található kis számú részsorozatot. Amennyiben a valóban legközelebbi részsorozatot kell megkeresnünk, az indexelés mellett az alsó becslést adó reprezentációkat is felhasználjuk. A vizsgálatot azokkal a részsorozatokkal kezdjük, amelyek indexe megegyezik a motı́vumhoz számı́tott indexszel és feljegyezzük, hogy melyik részsorozat volt eddig a legközelebb és mennyi ez a távolság, a reprezentánsok hasonlóságára tett feltételezés

miatt remélhetjük, hogy ez a távolság kicsi lesz, esetleg maga a legjobb, de mindenképpen közel hozzá. A többi részsorozat esetén a motı́vumot és az éppen vizsgált részsorozatot is tömörı́tjük egy alsó becslést adó módszerrel és ezek távolságát számoljuk ki, jóval gyorsabban, mintha az eredeti idősorokon számoltunk volna. Ha a reprezentánsok távolsága nagyobb, mint az eddigi legjobb távolság, akkor az alsó becslés tulajdonság miatt már nem kell tovább számolnunk az eredeti idősorokra, biztosan nem az éppen vizsgált lesz a legközelebbi. Ez az eset a feltételezés miatt gyakran be fog következni, ı́gy ezzel módszerrel gyorsan találhatjuk meg a leghasonlóbb részsorozatot. 23 http://www.doksihu 3. fejezet Fourier-sorok és waveletek Ebben a fejezetben a wavelet reprezentációról ı́rok. A bemutatást a Fourier-transzformáció és a waveletek

összehasonlı́tásával kezdem, majd megindokolom, hogy esetünkben miért jobbak a waveletek és leı́rom, hogy egy függvény transzformáltja hogyan áll elő a nyilvánosan is hozzáférhető wavelet-együtthatók segı́tségével. Az alkalmazások részben részletesen bemutatom, hogy a módszer hogyan alkalmazható zajtalanı́tásra és a dimenziószám csökkentésére, majd megvizsgálom, hogy ez milyen előnyökkel jár a különböző adatbányászati feladatok esetén. 3.1 Fourier-sorok Zajos adatoknál nagy problémát jelent a zaj és a valódi jel szétválasztása. A zaj lehet a műszer pontatlansága vagy adódhat abból is, hogy nem elég finom a mérés skálázása. A kisbabás adatok esetén megfigyelhető, hogy a mellkasi légzés mérésekor a szı́vverések is kimutathatók a görbékben, azaz a szı́vverések zajt okoznak. A mérési hibából adódó zaj általában sokkal

kisebb frekvenciájú, mint maga a jel, a szı́vverések frekvenciája nagyjából négyszerese a légzésének, ı́gy a különböző frekvenciájú komponensek szétválasztásával megkaphatjuk azt a jelet, amit valójában vizsgálni szeretnénk. Ehhez használhatjuk a Fourier- vagy a wavelet-transzformációt ([8]) A Fourier-transzformáltat általánosan értelmezhetjük normált csoportokra, de mivel az idősorok értékkészlete a valós számok halmaza és diszkrét sorozatnak tekinthetőek, ezért itt csak néhány speciális esetet definiálunk. 3.11 Definı́ció Legyen f integrálható függvény, x ∈ R, ekkor az Z fˆ(x) := f (t)e−2πixt dt R függvényt az f trigonometrikus Fourier-transzformáltjának nevezzük. k 3.12 Definı́ció Diszkrét m-edrendű ciklikus részcsoport: Mm := { m : k = 0, 1, . , m − 1} 3.13 Definı́ció Legyen f : Mm C Ekkor az 1 X fˆ(n) := f (t)e−2πint (n = 0, 1, .

, m − 1) m t∈Mm függvényt az f diszkrét Fourier-transzformáltjának nevezzük. 24 http://www.doksihu 3.2 FFT - Gyors Fourier-transzformáció Digitális módszerekkel nem tudunk folytonos függvényeket tárolni, legfeljebb tetszőlegesen sok pontjukat. Így egy mérés eredménye is diszkrét pontok összessége még akkor is, ha a mért jel folytonos, ezért a Fourier-transzformációk közül a gyakorlatban a diszkrét változatokat tudjuk használni. Fontos, hogy hatékonyan ki tudjuk számolni egy függvény Fourier-transzformáltját, illetve hogy az együtthatók ismeretében gyorsan vissza tudjuk állı́tani az eredeti függvényt vagy annak egy, a céljainknak megfelelő módosı́tását. Az FFT (Fast Fourier Transzform, Gyors Fouriertranszformáció) segı́tségével ez O(n ∗ logn) művelettel megoldható 3.3 A waveletek A Fourier-transzformáció nagy hátránya, hogy a jelet sinus

függvényekkel közelı́ti, ez sok esetben rossz felbontást eredményez. Mivel a sinus függvény periodikus és kiterjed a teljes számegyenesre, ezért a Fourier-transzformáció csak akkor működik hatékonyan, ha a jel statikus, frekvenciája nagyjából állandó. Az időben változó frekvenciájú jelek a Fourier-transzformációt ”összezavarják”, mindenhol rossz felbontást kapunk a különböző szakaszok elkülönı́tése helyett. A nem statikus jelek feldolgozására ezért célszerűbb egy kompakt tartójú függvényt használni, amellyel külön kezelhetjük az idősor különböző szakaszait és a transzformáló függvény megfelelő paraméterezésével a jel minden szakaszát a saját jellemzőinek megfelelő módszerrel értékelhetjük ki. Ennek a problémának a megoldására dolgozták ki a waveletek elméletét A wavelet transzformációk tehát nagyon hasonlı́tanak a

Fourier transzformációkhoz, van azonban egy jelentős különbség köztük: mı́g a Fourier transzformáció csak a különböző frekvenciákat képes reprezentálni, addig a waveletek segı́tségével az időt és a frekvenciát együtt vizsgálhatjuk, azaz alkalmas nem stacionárius folyamatok elemzésére is. Tekintsük át röviden a waveletek kialakulásának történetét! A Fourier transzformáció a stacionárius idősorok vizsgálatára alkalmas, hiszen a felbontás sinus és cosinus hullámok segı́tségével történik, ezek a hullámok a teljes számegyenesen jelen vannak periodikusan ismétlődve. A nemstacionárius idősorok vizsgálatára fejlesztették ki a rövid idejű Fourier transzformációt (Short Time Fourier Transform, STFS), amely azon alapul, hogy az idősort kis részekre bontjuk és feltételezzük, hogy ezeken a kisebb részeken már stacionáriusnak tekinthető a leı́ró

folyamat. Itt a problémát a felosztás sűrűségének megválasztása okozza. Röviden összefoglalva a következőt mondhatjuk az STFS-ről: hosszabb részek vizsgálatával jobban tudjuk felbontani az adatokat a frekvencia szerint, de kevésbé tudjuk követni az időbeli változásokat, mı́g rövidebb darabokra bontással az időbeliséget tudjuk vizsgálni viszont a frekvenciák szerinti felbontás rosszabbul fog működni. Ezen kı́vül az STFS felbontásból nem tudjuk visszaállı́tani az eredeti hullámot A waveleteket úgy tervezték, hogy magas frekvenciákon jó időfelbontást, alacsony frekvenciákon pedig jó frekvenciafelbontást adjanak. A valódi világból vett idősoroknál ez a felbontás megfelelő, hiszen ezek a jelek gyakran nagy frekvenciájú de rövid ideig tartó részekre és hosszú ideig tartó, de alacsony frekvenciájú részekre, tendenciákra bomlanak. 3.31 Waveletek

előállı́tása A waveletek előállı́tásához az a megfigyelés adja a kulcsot, hogy a waveletek önhasonlóak, azaz előállı́thatók saját maguk nyújtott és eltolt példányaiból. Tekintsük át először a pontos definı́ciót: 25 http://www.doksihu 3.31 Definı́ció Egy ψ(x) ∈L2 (R) függvényt waveletnek nevezünk, ha teljesı́ti a következőket: - R ψ(x)dx = 1 - A véges [a, b] intervallumon kı́vül ψ(x) = 0. - Létezik egy olyan φ(x) függvény, melyre < φ, ψ >= 0 és φ(x) = n P i=0 hi -kre. - Léteznek olyan g0 , g1 , . , gn valós számok, amelyre ψ(x) = n P i=0 hi φ(2x − i) valamilyen gi φ(2x − i) - ψj,k = 2−j/2 ψ(2j x − k) (j, k ∈ Z) egy ortonormált bázis L2 (R)-ben. Az előállı́táshoz induljunk ki egy olyan függvényből, amelyre valamilyen ak valós (vagy komplex) együtthatókkal igaz a következő finomı́tási egyenlet: φ(x) = ∞ X k=−∞

ak φ(2x − k) Ezt a függvényt skálafüggvénynek vagy apawaveletnek, az ak -kat pedig filter együtthatóknak vagy maszkoknak nevezzük. Mallat bizonyı́totta, hogy bizonyos feltételek teljesülése mellett ψ(x) = ∞ X (−1)k bk φ(2x − k) = k=−∞ ∞ X (−1)k a1−k φ(2x − k) k=−∞ egy ortogonális wavelet. A feltételeket a waveletek korábban már leı́rt tulajdonságaiból vezethetjük le. Először is feltételezzük, hogy a φ függvényt az összeg véges sok N tagja már megfelelően jól közelı́ti. ∞ R∞ P Másrészt a ak φ(2x − k) skálafüggvényt úgy választjuk, hogy φ(x)dx = 1 legyen, ezért i=−∞ i=−∞ a következő négy feltételt vezethetjük le: - ∞ P ak = 2 (a finomı́tási egyenletből) k=−∞ - NP −1 k=0 - NP −1 k=0 - NP −1 k=0 (−1)k k m ak = 0 m = 0, 1, . , N2 − 1-re (az eltűnő momentumokból) ak ak+2m = 0 m = 1, 2, . , N2 − 1-re (a

waveletek ortogonalitásából) a2k = 2 (a skálafüggvények ortogonalitásából) Néhány speciális eset: - N=2 esetén: Haar-függvény a0 = a1 = 1 φ(x) = ( 1 0 ha 0 ≤ x < 1 különben 26 http://www.doksihu  1    1 ha 0 ≤ x < 2 1 ψ(x) = −1 ha 2 ≤ x < 1    0 különben - N=4 esetén: Daubechies-4 függvény a0 = √ 1+ 3 4 , a1 = √ 3+ 3 4 , a2 = √ 3− 3 4 , a3 = √ 1− 3 4 3.1 ábra Daubechies függvények - kalapfüggvény (nem ortogonális) a−1 = 12 , a0 = 1, a1 = − 12 φ(x) =        x+1 −(x + 1) 0 ha (−1 ≤ x ≤ 0) ha (0 ≤ x ≤ 1) különben - B-spline (nem ortogonális) a−2 = 18 , a−1 = 12 , a0 = 34 , a1 = 12 , a2 = 3.32 1 8 Multirezolúció A multirezolúciós algoritmust arra a célra fejlesztették ki, hogy a jelet különböző időintervallumokban és különböző frekvenciatartományokon tudjuk elemezni.

Segı́tségével a jel felbontható egy hosszú ideig jelen levő ”átlagos” részre és rövid időkre felbukkanó egyedi eseményekre, részletekre. Intuitı́van átlagos résznek nevezhetjük a jel azon komponenseit, amelyek frekvenciája hosszú ideig jelen van és csak lassan változik. Egyedi részekről akkor beszélünk, ha egy frekvencia csak rövid ideig van jelen, hirtelen változik, intuitı́van azt mondhatjuk, hogy jelenléte meglepetés, a jel korábbi jellemzőiből nem következtethetünk a felbukkanására([12], [8]). 27 http://www.doksihu A multirezolúciós algoritmus során a jel felbontását szintenként finomı́tjuk. Minden lépésben a feldolgozandó adatsor áthalad egy felülvágó és egy alulvágó szűrőn (high-pass, low-pass filter), amelyek a jelet ”közelı́tő” és ”részlet” részekre bontják. A következő szintre a ”közelı́tő” rész értékei lépnek. Az

alulvágó szűrő eltávolı́tja a jel nagy frekvenciás komponenseit, a megmaradt kis frekvenciás komponensek az eredeti jel egy durva közelı́tését adják. Minél több nagy frekvenciát szűrünk ki és minél inkább a kis frekvenciákra szorı́tkozunk, a közelı́tés annál durvább lesz. A részleteket a felülvágó szűrő szűri ki, ezek lesznek a nagyfrekvenciás komponensek, amelyek gyakran a zajt jelentik. Az együtthatók megfelelő szűrésével beállı́thatjuk, hogy melyik komponensre vagyunk kı́váncsiak, erről a zajtalanı́tás fejezetben lesz szó részletesebben 3.33 FWT - Gyors Wavelet Transzformáció Láthatjuk, hogy nem könnyű az összes feltételnek megfelelő φ és ψ függvényeket találni. Ezen kı́vül ha találunk is ilyeneket, a transzformáció bonyolultnak tűnik, sok számolást igényel, ami algoritmikusan sem nem könnyű, sem nem hatékony. Szerencsére a

gyakorlatban elég az ai finomı́tási együtthatókat ismerni, ebből már könnyen és gyorsan, O(N ) időben kiszámı́thatjuk az idősor diszkrét wavelet-transzformáltját ([8]). A finomı́tási együtthatók sok wavelet esetén hozzáférhetőek. A Haar-wavelet esetén már megadtuk ezeket az értékeket: a0 = a1 = 1 A szintén népszerű Daubechies-waveletek együtthatóinak közelı́tését pedig az N=4,6,.,20 esetekre például a wikipedián is megtalálhatjuk A bi együtthatókat szintén az ai együtthatókból kapjuk: bk = (−1)k a1−k , ahol N a Daubechies-transzformáció indexe (azaz például a D4 transzformáció esetén N=4). Tegyük fel, hogy φ kielégı́ti az összes feltételt, azaz valós értékű, kompakt tartójú, ortogonális az eltoltjaira, kielégı́ti a multirezolúciós feltételeket és a finomı́tási egyenletet. Ekkor φ-ből előállı́thatjuk ψ-t is. A

transzformálandó f függvény numerikus közelı́tését szintén a φ függvényt alkalmazva kapjuk meg. Először is eldöntjük, hogy milyen mélységű felbontást szeretnénk, ezt a számot n-nel jelöljük Ekkor a közelı́tés előáll az Sn függvény segı́tségével, ahol: Sn = X fj φj,n j∈Z A fenti képletben az fj együtthatók közül csak véges sok nemnulla szerepel, célunk ezek előállı́tása. Tudjuk, hogy Sn -re igaz a következő egyenlet: S n = Pn S n = P0 S n + n X (Pk Sn − Pk−1 Sn ) = P0 + k=1 ahol Pk f (x) = 1 2k R [j2−k ,(j+1)2−k ) n−1 XX k=0 j∈Z c(j, k)ψ(2k x − j) f minden x ∈ [j2−k , (j + 1)2−k ), j ∈ Z-re. Az alábbi algoritmus segı́tségével gyorsan ki tudjuk számolni a c(j, k) együtthatókat az ai és a bi együtthatók ismeretében. Az alábbi képletekben az s a közelı́tő, t pedig a részlet-együtthatókat jelenti. A k-adik lépésben a

következő képlet segı́tségével számolhatjuk ki az újabb együtthatókat: Z X Z X 1 X ′ s (i) = s(j)φj,k φi,k−1 = s(j)φj, k √ al φ2i+l,k 2 l∈Z R j∈Z R j∈Z amiből a végső képlet: 1 X s′ (i) = √ aj−2i s(j) 2 j∈Z 28 http://www.doksihu Problémát jelent, hogy az általunk használt waveletek esetén a nemnulla filter együtthatók száma véges, sőt, jellemzően nagyon kevés. A véges számú filter együtthatók problémája a ”széleken” jelentkezik, itt nem teljesülnek az ai -kre tett feltételek a sok 0 miatt, de mivel gyakorlati problémák megoldásakor célszerű a lehető legkevesebb filter együtthatót használni a számolások egyszerűsı́tése, gyorsı́tása érdekében, ezért a ”széle”-probléma az wavelet együtthatók nagy részét érinti, és ı́gy pontatlan eredményt ad. Szerencsére ezt a problémát könnyen feloldhatjuk a filter

együtthatók ciklizálásával, azaz: ai = ai+nN és bi = bi+nN n∈Z ahol N a (nemnulla) filter-együtthatók száma. Tehát a végső képlet mátrixos formában: s’ = As, A := (αi,j ), αi,j := √1 aj−2i 2 i = 0, 1, . , N2 − 1 βi,j := √1 bj−2i 2 i = 0, 1, . , N2 − 1 j = 0, 1, , N − 1 j = 0, 1, . , N − 1 hasonlóan: t’ = Bs, B := (βi,j ), s kezdeti értéke a feldolgozandó idősor értékei. Az inverz transzformáció ezekkel a jelölésekkel hasonlóan egyszerű formában áll elő. Jelöljük az inverz transzformáció mátrixát A∗ -gal ill. B ∗ -gal, esetünkben A∗ = AT és B ∗ = B T Tehát az inverz transzformáció mátrixos alakja: A* := (α∗i,j ), α∗i,j := √1 ai−2j 2 i, j ∈ Z ti = B*t’, B := (β∗i,j ), β∗i,j := √1 bi−2j 2 i, j ∈ Z si = A*s’, és végül: s = si + ti 3.4 3.41 A waveletek alkalmazása Alkalmazási területek A wavelet

transzformációt az alább felsorolt előnyös tulajdonságai miatt sok helyen alkalmazzák. Eredetileg képfeldolgozásra, képtömörı́tésre használták, mivel ha szükséges, nagy mértékben csökkenthetjük a kép méretét, másrészt ha arra van szükség, az inverz transzformációval a tömörségtől függően veszteségmentesen vagy kevés adatvesztéssel visszaállı́thatjuk az eredeti fájlt. Később más területeken is felfedezték a hasznosságát, az irodalomjegyzékben található cikkek többek között radar jelek feldolgozására ([11]), internetes biztonsági adatbázis vizsgálatára ([9]) és parciális differenciálegyenletek numerikus megoldására ([8]) használták a módszert. 3.42 Tulajdonságok - Minden wavelet függvény kompakt tartójú, ı́gy az idősor egy részének vizsgálata a wavelettel nincs hatással az idősor többi részére. - Az eltűnő

momentumok biztosı́tják, hogy valóban szét tudjuk választani a lényeges és a lényegtelen információkat, ami nagyon fontos az adatok előfeldolgozásánál. 29 http://www.doksihu - A hullámok nyújthatósága miatt gyors algoritmusokat kaphatunk. - A waveletek sima függvények. - Ortonormált bázist generálnak. - Akár O(N) időben és O(N) tárban számı́thatók. Az eltűnő momentum tulajdonságot felhasználva esetenként hatékonyan tudjuk tisztı́tani a zajos adatokat. 3.41 Definı́ció Legyen az f (x) egy kompakt ω tartójú függvény Azt mondjuk, hogy az f -nek n momentuma eltűnik, ha teljesül a következő: Z f (x)xj dx = 0, j = 0, 1, . , n ω Ezek szerint egy kis fokú polinom és egy wavelet függvény szorzatának integrálja 0. Így ha az idősor egy alacsony polinommal közelı́thető, akkor ezt a polinomot meg tudjuk találni az alacsony wavelet együtthatók megtartásával. A

polinommal való közelı́tés több szempontból előnyös: ı́gy csökkenteni tudjuk a zaj mértékét, másrészt ı́gy sokkal kisebb dimenziójú adathoz jutunk. 3.43 Zajtalanı́tás A valós életből vett adatoknál azt tapasztaljuk, hogy a zaj frekvenciája erősen eltér a megfigyelni kı́vánt jel frekvenciájától, jellemzően jóval kisebb annál. Szintén jellemző, hogy a jel energiája néhány együtthatóra koncentrálódik, azaz néhány ezek közül látványosan kiemelkedik. Ezért a wavelet-transzformációt alkalmazhatjuk zajszűrésre, hiszen ez a felbontás elkülönı́ti az egyes frekvenciákat, ı́gy az együtthatók vizsgálatával megtalálhatjuk azokat, amelyek valójában jellemzik a jelet. A zajszűrés a következő módon történik: - alkalmazzuk a wavelet transzformációt a zajos jelre olyan mélységben, hogy a jel és a zaj már elkülönı́thető legyen -

alkalmasan megválasztott értékhatárokkal minden szinten módosı́tjuk azokat az együtthatókat, amelyek abszolút értéke kisebb, mint a szint határa - az inverz wavelet transzformációval visszaállı́tjuk a zajtalanı́tott jelet Felmerül a kérdés, hogy milyen mélységben célszerű elvégezni a transzformációt és hogy hogyan találhatjuk meg az alkalmas értékhatárokat, amelyek mentén levághatjuk a jelről a zajt. A mélységre triviális határt szab az adatpontok mennyisége, hiszen minden lépésben a közelı́tő és a különbség együtthatók száma fele, mint az előző lépésben. A határ megállapı́tásához alkalmazhatjuk a következő képletet: θ=σ p 2log(N ) ahol N a közelı́tendő részsorozat hossza, σ pedig egy a zaj szintjétől függő konstans. A határok megállapı́tásánál kétféle megközelı́tést alkalmazhatunk: a kemény és a lágy

határokat (hard or soft tresholding). A kemény határok alkalmazásánál nullára állı́tunk be minden olyan együtthatót, ami abszolút értékben kisebb a határnál és nem változtatjuk meg a többit. A lágy határoknál szintén nulla lesz az értéke azoknak az együtthatóknak, amelyek abszolút értéke 30 http://www.doksihu kisebb, mint a határ, viszont a többi együtthatót is módosı́tjuk úgy, hogy az abszolút értéke az értékhatárral csökkenjen. Összefoglalva: - kemény küszöb ′ d (t) = ( d(t) 0 ha |d(t)| > θ ha |d(t)| ≤ θ - lágy küszöb ′ d (t) = 3.44 ( sign(d(t))(|d(t)| − θ) ha |d(t)| > θ 0 ha |d(t)| ≤ θ Dimenzió csökkentés A wavelet-transzformáció során az adat-értékeket az együtthatókkal helyettesı́tjük. Az együtthatókból ortogonális transzformációk esetén információvesztés nélkül, más esetekben közelı́tően

tudjuk visszaállı́tani az eredeti adatsort. Gyakran azonban nem célunk az eredeti adatsor módosı́tatlan előállı́tása, például zajos adatok esetén kimondottan az a célunk, hogy módosı́tsuk a mért értékeket. Az adatok nagy dimenzióját nem csak a mért értékek nagy száma adja, hanem az a tény is, hogy idősorok esetén több egymás utáni értéket kell vizsgálnunk egyszerre, ı́gy csúszóablakok alkalmazásával nagy számú vektort kell tárolnunk. Az ablak méretének növelése gyors méretnövekedést eredményez. Az egymás utáni értékek azonban ritkán függetlenek egymástól Az összes vektor tárolása sok redundanciát is eredményez, ami nagy mérethez és lassú algoritmusokhoz vezet. A dimenzió csökkentésével tehát a következőket szeretnénk elérni: - Az adatok számának csökkentése, ezáltal gyorsabban lefutó algoritmusok - A zaj és a redundancia

csökkentése a lényeges információk kiemelésével - A kisebb dimenziószám esetén érthetőbb, átláthatóbb végeredményt kapunk Az adataink dimenzióját könnyen csökkenthetjük, ha a wavelet-együtthatók közül nem tartjuk meg az összeset. A problémát a tárolandó együtthatók kiválasztása jelenti A két legelterjedtebb módszer k tárolandó együttható kiválasztására az első k és a k legnagyobb (esetleg legkisebb) abszolút értékű együttható tárolása ([11]). Az első k együttható megtartásával az adatsor egy közelı́tését kapjuk, hiszen ezek az értékek az alacsony frekvenciákhoz tartoznak, a nagyobb sorszámú együtthatók tárolják a részleteket, a nagyfrekvenciás jelenségeket. Ez a megközelı́tés akkor alkalmazható, ha nagy vonalakban, az általánosan uralkodó tendenciákra vagyunk kı́váncsiak. A k legnagyobb együttható megtartásával

őrizhetjük meg a legtöbb energiát. Ez a szemlélet tökéletes olyan adatsorokra, amelyeket többé-kevésbé statikusnak tekinthetünk abban az értelemben, hogy leı́rhatjuk őket néhány jellemző frekvencia segı́tségével. Problémába ütközünk azonban, ha több idősorunk is van, vagy egy idősoron belül nagyon változó jellemzőket találunk, mint például a légzésadatokban a különböző alvásfázisokra jellemző légzés. Ez esetben minden idősorra (vagy idősor-részletre) más és más helyeken találjuk a legnagyobb együtthatókat, amiket nehezen tudunk tárolni és még ha tároltuk is, nehéz olyan mértéket találni, ami alapján hatékonyan összehasonlı́thatnánk őket. Mörchen cikkében ([11]) azt javasolja, 31 http://www.doksihu hogy közös k hely keresésével közös együtthatókat tároljuk. Ennek a k helynek a meghatározásához szükség van az

adatsorok, vagy legalább egy reprezentatı́v minta előzetes ismeretére, ami a legtöbb esetben fennáll. A k legjobb helyet az együtthatók négyzetes összege alapján választjuk ki. A tanuló adatokat transzformáljuk majd összeadjuk az egyes együtthatók négyzetét. Mörchen bizonyı́totta, hogy a k legnagyobb négyzetes összeg őrzi meg legjobban az együttes energiát, ı́gy ezeket a helyeket tartjuk meg a további vizsgált adatsorok esetén is. 3.45 Klaszterezés Keogh és társai egy olyan klaszterezőt ajánlanak, amely a wavelet-együtthatókon és a multirezolúciós előállı́táson alapul. Cikkükben a legegyszerűbb klaszterezővel, a k-közép algoritmussal kı́sérleteznek, de az ötlet bármilyen klaszterező esetén felhasználható ([10]). A k-közép algoritmus futási ideje O(kN rD), ahol k az előre megadott klaszterek, N a csoportosı́tandó objektumok, r az iterációk száma, D pedig

az objektumok dimenziója. Nyilvánvaló, hogy a reprezentált, kisebb dimenziós adatokon gyorsabban fut az algoritmus. Még gyorsabban kapunk eredményt, ha kihasználjuk a multirezolúció elvét: a felbontás fokozatosan finomodik, ı́gy a klaszterezőt szintenként kell futtatnunk. Az i-edik szinten az adatok csak 2i−1 dimenziósak, azaz a reprezentáció tömör, nagy az adatveszteség. Cserébe viszont az egyes szinteken a futási idők sokkal jobbak, mint az eredeti adatokon vett futási idők és az egyes szintek eredményeit felhasználhatjuk a következő, finomabb felbontású szinthez, ı́gy az eredményeink is egyre részletesebbek, egyre pontosabbak lesznek. A k-közép algoritmus másik érzékeny pontja a kezdeti középpontok kiválasztása, ha nincs semmi előzetes ismeretünk az adatokról, kénytelenek vagyunk véletlenül választani. Rossz középpontválasztás esetén viszont az algoritmus elakadhat egy

lokális minimumban, ezért a k-közép algoritmust mindig többször is le kell futtatnunk, hogy jobb eséllyel megtaláljuk a globális optimumot. A multirezolúció mindkét problémán segı́t. Kezdetben a közelı́tés nagyon durva, viszont az objektumok nagyon kis dimenziósak. A klaszterezést a multirezolúció második lépésében kezdjük Az első futtatás esetén még véletlenül kell választanunk a középpontot, de ekkor az adatok még csak 2 dimenziósak, ı́gy rövid idő alatt sok kı́sérletet elvégezhetünk. A további iterációkhoz mindig az előző szint végső középpontjait használjuk kezdeti középpontnak, ami a tapasztalatok szerint jelentősen gyorsabb konvergenciához és kevesebb lokális maximumhoz vezet. A szintenként végrehajtott algoritmusnak még egy nagy előnye van: a gyorsan megkapott részeredmények ellenőrzésével gyorsan felderı́thetjük, ha hibásan

állı́tottunk be egy paramétert és kis időveszteséggel indı́thatjuk újra a mérést. 3.46 Klasszifikáció Döntési fák előállı́tásánál problémát okoz a magas dimenziószám, amitől az algoritmus nagyon lassúvá válik. A másik gond a zaj, hiszen ha az adatok nagyon zajosak, az algoritmus nem tud pontos szabályokat gyártani A szabálytalan torzulások miatt a döntési fák mélyek és szétágazóak, az előállı́tott szabályok pedig bonyolultak, érthetetlenek és ráadásul sok esetben pontatlanok lesznek. Mörchen k-legjobb együtthatójával egy megoldást ad erre a problémára, hiszen a k változtatásával meghatározhatjuk az adataink dimenziószámát. A tapasztalatok szerint a kis dimenziószámú, vagyis az erősen tömörı́tett adatok majdnem olyan jó eredményt adnak, mint a kevésbé tömör reprezentáción futtatott algoritmusok, az eredeti adatoknál pedig

szinte mindig jobbak ([11]). 32 http://www.doksihu Ennek az oka a nyers adatokban található zaj és redundancia. Mivel a k-legjobb együtthatóval a leginkább jellemző értékeket nyerjük ki, ezért ez a reprezentáció egy jó tömörı́tést ad. A tömörséggel azt is elérjük, hogy csökkenjen a zaj és a redundancia, ami miatt sekély fákat és rövid, érthető döntési szabályokat kapunk végeredményül. 3.47 Hasonlóság keresés, indexelés Az indexeléssel az a célunk, hogy egy részsorozathoz gyorsan és hatékonyan találjunk egy nagyon hasonló részsorozatot, vagy más alkalmazásokban a rendelkezésünkre álló mintákból a leginkább hasonlót kell megtalálnunk. A wavelet együtthatók az idősor bizonyos frekvenciás részeiről hordoznak információt, ı́gy alkalmasak arra, hogy ez alapján indexeljünk részsorozatokat. Az internetes adatbázisról szóló cikkben ([9])

az együtthatóknak csupán 10-15%-át tartják meg, amellyel már jelentősen gyorsul a keresés. Az index maga a wavelet együtthatók sorozata, a cikkben az első részlet-együtthatókat tartják meg. Az első együtthatók tartalmazzák a legfontosabb információkat az adatsorról, kevés megtartott együtthatónál durva közelı́tését adják a nyers adatoknak. Másrészt a nagy frakvenciákat képviselő együtthatók, amelyek nem szerepelnek az elsők között, legtöbbször a zajt jelentik és ı́gy figylemen kı́vül hagyásuk kifejezetten előnnyel jár. A keresésnél a megtalálandó motı́vum transzformáltjának első néhány együtthatóját vizsgáljuk, a mintahalmazban olyan részsorozatokat keresünk, ami ezeken az együtthatókon csak kis mértékben tér el a keresendőtől. Ez az erősen csökkentett adattér miatt hatékonyan végrehajtható. A cikkben a keresés eredményeképp

az összes hasonló részsorozatot megadják, más alkalmazásokban további részletesebb keresést kezdeményezhetünk ezek között a jelöltek között. Mivel a jelöltek száma tetszőlegesen csökkenthető a keresésnél alkalmazott eltérés-paraméter megfelelő beállı́tásával, ezért ez a részletesebb keresés sem igényel túl sok időt. 33 http://www.doksihu 4. fejezet Mérési eredmények 4.1 WEKA A WEKA (Waikato Environment for Knowledge Analysis) az új-zélandi Waikato egyetemen fejlesztett nyı́lt forráskódú adatbányász szoftver. Főleg előkészı́tő, szűrő és osztályozó algoritmusok alkotják, de lehetőség van klaszterezésre és asszociációs szabályok alkotására is. A felépı́tett modelleket menthetjük, az eredményeinket grafikusan is megjelenı́thetjük A szoftver nyelve JAVA, az algoritmusok átlátható hierarchiába vannak rendezve, ı́gy könnyen

használhatóak a már meglévő algoritmusok, másrészt könnyen illeszthetjük a saját programjainkat is. A bemenő adatokat egy speciális arff (attribute related file format) formában kell megadnunk, de van lehetőség néhány más tı́pusú fájl, például vesszővel tagolt szöveg illetve adatbázis-adatok arff formátumra konvertálására is. Az egyes algorimusoknak sokféle paramétert adhatunk meg, ı́gy személyre szabhatjuk a programot. A paraméterek módosı́tására lehetőség van a grafikus felületen illetve parancssorban is. A WEKA algoritmusait könnyen meghı́vhatjuk a saját programjainkból is. 4.11 Klaszterezők A WEKA klaszterező algoritmusai közül a k-means-t és az EM klaszterezőt használtam. A k-means az egyik legrégebbi és legismertebb particionáló algoritmus. Bemeneti paramétere a k, azaz a várt csoportok száma, az algoritmus pontosan ennyi klasztert fog létrehozni. Az

algoritmus meglehetősen egyszerű: kezdetben véletlenül választunk k db középpontot, majd minden iterációban minden pontot hozzárendelünk a hozzá legközelebb eső középponthoz és új középpontot számolunk az ı́gy kapott csoportoknak. A klaszterezés jóságát a különböző csoportba kerülő elemek távolsága alapján mérjük. Az algoritmus olyan adatokra jó, ahol a klaszterek jól elkülönülő felhő alakúak, ráadásul mivel ki kell számolnunk a középpontokat, csak olyan adatokon alkalmazható, amelyek vektortérben reprezentálhatók. Ezen kı́vül nagy az esélye, hogy a futás egy lokális minimumban áll le, másrészt az algoritmus gyors, ı́gy többszöri lefuttatással jó eredményeket érhetünk el. Az EM (Expectation Maximization) algoritmus hasonló a k-means-hez, de néhány ponton kibővı́ti azt. Először is az EM számára a célfüggvény nem a

különböző csoportba kerülő elemek távolságának maximalizálása, sőt, nem is rögzı́tett klaszter-tagsággal számol. Az egyes elemek bizonyos valószı́nűséggel tartoznak a különböző csoportokhoz, célunk a legnagyobb likelihood-dal rendelkező elosztás megtalálása. A másik előnye a k-means-hez képest, hogy alkalmazható ka34 http://www.doksihu tegórikus adatokra is. A WEKÁ-ban nem kell feltétlen megadnunk a bemeneti k paramétert, bár ı́gy a futási idő nagyon megnövekszik. Az EM algoritmus nagy előnye viszont, hogy nem szükséges többször lefuttatni, az eredmény mindig ugyanaz lesz. 4.12 Osztályozók A WEKÁ-ban az osztályozó rész a leginkább kidolgozott, itt választhatunk a legtöbb módszer közül. Az első fejezetben leı́rt legismertebb módszerek mindegyikét megvalósı́tották, a döntési fákat több módon is. A döntési fák előállı́tása

során olyan attribútumot keresünk, amely mentén felbontva az adathalmazt a lehető legjobban eltérő részeket kapunk. Az algoritmusok közötti különbséget az attribútum kiválasztása adja. Az Id3 algoritmusban azt választjuk, amellyel a legjobban tudjuk csökkenteni az entrópiát, a j48 algoritmus pedig a Gini-indexet minimalizálja. A j48 döntési szabályok létrehozása mellett előrejelzésre is alkalmas, viszont hajlamos jóval terebélyesebb fákat épı́teni, mint az Id3. Sajnos mind az entrópiát, mind a Gini-indexet kategórikus attribútumokra értelmeztük, ı́gy a WEKA megfelelő függvényei is csak ilyen tı́pusú adatokra futnak, ez a wavelet együtthatós reprezentálásnál okoz problémát. 4.2 Energia adatok A különböző előkészı́tési módok és feldolgozó algorimusok tesztelésére az Eamonn Keogh cd-jén található adatok közül válogattam. A jó

értelmezhetőség kedvéért az olaszországi és a hollandiai villamosenergia-kérelmének adatait választottam, hiszen ebben az esetben a klaszterezők és az osztályozók eredményei könnyebben áttekinthetőek és értelmezhetőek. A holland adatok óránként 4, az olasz adatok pedig óránként 1 értéket tartalmaznak, az előbbiből 1 év (1997), az utóbbiból pedig közel 3 és fél év (1995-1998 május) adatai állnak rendelkezésünkre. Keogh a holland adatokat anomália detektálására használta ([3]). Mindkét ország adatain jól látszik a munkarend: a hollandok heti öt napot dolgoznak, mı́g Olaszországban, bár nem egyenrangú a hétfőtől péntekig terjedő időszakkal, a szombat is munka- és tanı́tási nap. Szabad szemmel is láthatjuk, mikor kezdődik egy új nap illetve egy új hét: a holland adatokon 5 nagy hullám után két kisebb következik, az olasz adatokon 5 nagy

fogasztású nap után egy kisebb, majd egy még kisebb következik. Ebben a rendszerben az ünnepnapok jelentik az anomáliát, Keogh cikkében a három legmeglepőbbnek indexelt nap mindegyike nemzeti ünnep volt, ami hétköznapra esett. Az adatokat két nézetből vizsgálom: hetekre és napokra bontva. A heti bontás az olasz adatok esetében értelmes, mivel csak ı́gy lesz megfelelő mennyiségű adatunk. A hetek csoportosı́tásától a hónapok szerinti eloszlást várom, mı́g anomáliának az augusztusi leállást tekinthetjük. A napok esetében a hétköznapok és a hétvégék elkülönülése várható. Kérdés, hogy a hétköznapok között van-e különbség, vagy egyenrangúak Mivel a napi felbontás mindkét adathalmaz esetén megfelelő mennyiségű és minőségű adatot ad, ezért tesztelhetjük őket vegyesen is, az országok szerinti felosztás várható eredményként. Először

napokra bontva vizsgáltam az adatokat. Az olasz adatok esetén óránként egy, a holland adatok esetén óránként négy energia-érték adott, tehát a vizsgált részsorozatok 24 ill. 96 értékből, 35 http://www.doksihu egész számokból állnak. Ezeket előbb a SAX és a diszkrét wavelet transzformáció segı́tségével különböző módokon reprezentáltam, majd a WEKA segı́tségével elemeztem. 4.21 Klaszterezés Az EM algoritmust először klaszterszám megadása nélkül futtattam le a különböző reprezentációkra, majd a kı́sérletet megismételtem rögzı́tett k értékekkel. Ezeket a fix értékeket egyrészt az előzetes feltevések, másrészt a k nélküli futás tapasztalatai alapján választottam. A SAX reprezentáció esetén 3 vagy 4 klasztert kaptam, a különböző klaszterek főleg hétköznapokból, szombatokból és vasárnapokból állnak. A

hétköznapok közül külön klaszterbe kerültek a téli és a nyári napok. 4.1 ábra Az olasz energia adatok klaszterei SAX reprezentációval A wavelet reprezentáció esetén olyan részsorozatokat tudunk feldolgozni, amelyek hosszúsága n 2 valamely n egész számra. Először tehát a rendelkezésre álló adatokat 8, 16, majd 32 hosszúságú részsorozatokra bontottam, bár ezek nem felelnek meg a természetes, naponkénti felbontásnak. Az olasz adatokon részletesen elemeztem azt az esetet, amikor 8 adatot reprezentálok, hiszen ehhez még társı́thatunk szemléletes magyarázatokat: 8 adat éppen egy harmad nap, ı́gy a hét napjai mellett esetleg kaphatunk eredményeket a különböző napszakok jellemzésére is. Az együtthatók közül négyet vagy mind a nyolcat tartottam meg, a négy esetében Mörchen mindhárom variációját, az első négyet, a legjobb négyet és az adap-négyet is

vizsgáltam. A k nélküli futtatás után a k = 2, 3, . , 7 konkrét eseteket vizsgáltam meg Az eredmények a megtartott együtthatók számától és fajtájától függetlenül nehezen kezelhetőek és értelmezhetők. A k nélküli futtatás nagy 13-18 közötti klaszterszámmal zárult, ezekhez sajnos nehezen köthető magyarázat A klaszterek értelmezéséhez a kapott eredményekből háromféle táblázatot hoztam létre: - A klaszterek és a hét napjainak összefüggése A legtöbb táblázat esetén nem láthatunk olyan klasztereket, amelyek a hét egy bizonyos napjához vagy napjaihoz tartoznának. Nem adnak jó eredményt a k = 7 (minden napnak egy klaszter), k = 2 (hétköznapok és hétvégék) és a k = 3 (hétköznapok, szombat, vasárnap) rögzı́tett klaszterszámú, heurisztikus esetek sem, bár kismértékű elkülönülés látható. - A klaszterek és a napszakok

összefüggése Itt megfigyelhető csoportosulás, a napszakok láthatóan meghatározóbbak, mint maguk a napok. Viszont mivel csak három napszakot különböztetünk meg, érthetetlen a klaszterek magas száma, ezen kı́vül nem megnyugtató a rögzı́tett k = 3 klaszterszámú eset eredménye. 36 http://www.doksihu - A klaszterek összefüggése a hét napjaival, napszakokra bonva Ebben az esetben a rendelkezésre álló adatokat 21 csoportra bontottuk és ı́gy figyeltük meg a klaszterhez tartozásukat. Azt tapasztaltuk, hogy az egyes klaszterek itt is gyakran tartalmaztak azonos napszakból származó adatokat, viszont jellemzően az összes hétköznapból (vagy hétvégéből) nagyjából ugyanannyit, gyakran keverednek is a hétköznapok és a hétvégék. Így továbbra sincs magyarázat a nagy számú klaszterre, hiszen több közülük nagyon hasonló jellegű napszakokat gyűjt össze. Magyarázat

lehetne az évszakok változása, de két azonos felépı́tésű klaszterben szereplő elemek rendszerint egymást váltogatva, rendszer nélkül szerepelnek az adatsorban. Ezzel az eredménnyel nem voltam elégedett, ı́gy megkı́séreltem a wavelet reprezentációt is az adatok naponkénti felbontására alkalmazni. A problémát az okozza, hogy a wavelet transzformáció csak kettő-hatványokra működik, a 24 pedig nem az. Az első ötlet az, hogy hármasával átlagolom az energia-értékeket, ı́gy 8 hosszúságú sorozatokat kapok és ezekre futtatom a wavelet-transzformációt. A második ötlet pedig az, hogy a 24 hosszúságú napokból 16 hosszúságú sorozatokat állı́tok elő úgy, hogy minden 3 adatot kettővel helyettesı́tek. Ezt tehetném úgy, hogy páronként átlagolom az energiaértékeket, de ezzel a módszerrel a középső elemnek nagyobb hatása lenne, ı́gy a következő

súlyozást használtam: 2 ∗ tomb24 [3i] + tomb24 [3i + 1] 3 tomb24 [3i + 1] + 2 ∗ tomb24 [3i + 2] tomb16 [2i] = 3 tomb16 [2i] = Az ı́gy kapott klaszterek jobbak, mint a napokat nem figyelembe vevő felosztás esetén, viszont a klaszterezés minősége a megtartott együtthatók számától függően erősen változik, sajnos előre meg nem határozható módon. A módszerek, amelyek szerint a megtartott együtthatókat kiválasztjuk, bizonyos esetekben nagyon jól működnek, bizonyos esetekben viszont nagy mennyiségű, értelmezhetetlen klasztereket adnak, gyakran több olyannal, amelybe alig került elem. Másrészt megállapı́thatjuk, hogy a tömörebb reprezentációkon nem kaptunk rosszabb eredményeket, mint a részletesebbeken. Egyetlen kivétel az az eset, amikor a 8 elemű idősorok mind a 8 együtthatóját megtartottuk, ekkor kaptuk a legjobb besorolást, tehát az eredeti adatokon végzett klaszterezés

pontosabb volt. A hetekre bontás esetén a kevés adat miatt csupán két klasztert kaptunk, ezekhez viszont pontos jelentés társı́tható: őszi-téli (október-március) és tavaszi-nyári (április-szeptember) hetek különülnek el, az eltérést nagy valószı́nűséggel a fűtési szezon okozza. Érdekesség, hogy a kettő helyett időnként 3 klasztert kapunk, amelyek közül az egyik egyelemű, egy augusztusi hetet tartalmaz. 4.22 Osztályozás Az olasz adatokat 24, a holland adatokat 96 hosszúságú részekre, azaz napokra bontottam, majd minden napot a SAX reprezentációval 4, 6, 8, 12, majd 24 karakterrel reprezentáltam, azaz az olasz adatok esetében 6, 4, 3, 2 ill. 1, a holland adatok esetében 24, 16, 12, 8 ill 4 adatot átlagoltam és helyettesı́tettem egy betűvel. A WEKA j48 algorimusát használtam osztályozásra az alapértelmezett 10 részre osztott kereszt-validációval (ten-fold

crossvalidation). Az eredmények minden esetben nagy szórást mutattak, a jól klasszifikált elemek aránya a legjobb esetben is mindössze 45,75%, a legrosszabb esetben pedig 37,26%. A keveredési mátrix 37 http://www.doksihu 38 http://www.doksihu 39 http://www.doksihu 40 http://www.doksihu (confusion matrix) vizsgálatával azonban megállapı́thatjuk, hogy melyik esetben hányféle csoportot hozhatunk létre a napokból, melyik napot tudja azonosı́tani az osztályozó algoritmus és melyek azok, amelyek ebből a szempontból egyformák. Az alábbi táblázatokban a cı́mben az ország neve mellett szereplő szám a reprezentáló szimbólumok számát jelöli, a cı́m mellett a helyesen klasszifikált elemek arányát tüntettem fel. A sorok elnevezése a valódi, az oszlopok elnevezése a besorolt cı́mke. olasz 4 (42,46%) holland 4 (43,84%) H K Sze Cs P Szo V H K Sze Cs P Szo V H 24 9 4 4 7 0 4

49 0 0 0 0 2 1 K 19 5 3 8 14 0 3 29 0 0 18 5 0 0 Sze 13 2 3 9 23 0 2 34 0 0 13 5 1 0 Cs 16 4 7 6 19 0 0 20 2 0 26 2 1 1 P 11 2 10 9 17 2 1 4 0 0 9 27 0 2 Szo 0 1 0 0 1 48 20 0 1 0 3 2 31 15 V 0 0 0 0 0 1 52 2 0 0 1 3 19 27 olasz 6 (38,81%) holland 6 (41,92%) H K Sze Cs P Szo V H K Sze Cs P Szo V H 15 14 5 12 3 1 2 41 3 3 1 2 1 1 K 20 1 8 18 2 1 2 17 6 4 15 10 0 0 Sze 15 13 6 12 5 0 1 22 7 1 12 9 2 0 Cs 15 10 8 14 5 0 0 11 12 1 18 8 0 2 P 12 6 10 17 5 1 1 7 1 0 13 29 1 1 Szo 2 1 0 0 0 48 1 0 0 0 0 0 30 22 V 2 2 0 0 0 0 49 3 0 0 2 2 17 28 olasz 8 (43,56%) holland 8 (45,75%) H K Sze Cs P Szo V H K Sze Cs P Szo V H 28 7 7 7 0 0 3 38 0 4 2 6 2 0 K 16 21 7 3 2 1 2 8 18 9 8 9 0 0 Sze 15 15 6 10 5 0 1 8 15 6 15 7 1 1 Cs

13 11 12 10 4 2 0 5 13 4 20 8 2 0 P 11 11 10 9 6 3 2 1 11 5 6 27 1 1 Szo 0 7 1 1 1 37 5 2 0 0 2 0 35 13 V 0 1 0 0 0 1 51 1 0 0 3 1 24 23 olasz 12 (37,26%) holland 12 (40,82%) H K Sze Cs P Szo V H K Sze Cs P Szo V H 16 13 10 6 3 1 3 43 2 3 1 1 1 1 K 16 3 12 8 11 0 2 16 6 9 13 8 0 0 Sze 13 8 7 9 14 0 1 13 8 10 15 4 1 2 Cs 13 5 15 10 8 1 0 4 8 11 20 6 1 2 P 5 12 15 8 9 1 2 7 6 3 13 21 0 2 Szo 1 4 1 1 0 43 2 0 1 1 1 0 30 19 V 3 0 1 0 1 0 48 1 0 0 2 1 29 19 41 http://www.doksihu Az olasz adatok esetén, amint várható volt, 3 csoportot tudunk elkülönı́teni: a hétfőtől péntekig terjedő munkanapokat, a szombatot és a vasárnapot. A hétköznapok között nem tudunk különbséget tenni, az algoritmus szinte teljesen véletlenszerűen sorolta be őket, viszont mind a szombat, mind

a vasárnap jól elkülönül. Meglepőbbek a holland adatok. Itt is a várakozásainknak megfelelő, hogy a hétköznapok és a hétvégék elkülönülnek, ez esetben a hétvégék részmátrixában jelennek meg szinte azonos számok. Meglepő viszont a hétfők nagy arányú találata, a mátrix többi részéhez képest jelentősen alacsonyabb a rosszul klasszifikált hétfők száma. Másrészt az olasz adatokhoz képest jóval nagyobb azoknak a nem hétfői munkanapoknak a száma, amelyeket az algoritmus hétfőnek ı́télt. Ez alapján kis mértékű elkülönülést figyelhetünk meg a hét első fele (hétfő-kedd-szerda) és a hét második fele (csütörtök-péntek) között. Magukat a döntési fákat vizsgálva szintén különbséget találunk a két ország között. Olaszország esetén az első döntést szinte mindig a koradélutáni órák adják, egyedül a 4

reprezentáns esetén tér el, ott a délelőtti órák jelentik az első döntést. A második döntés már nem ilyen egyhangú, de sok esetben a munkaidő kezdetét (8-9) tartalmazó intervallum szerepel a második helyen. Hollandia esetén viszont az első döntést mindig az első intervallum, vagyis az éjszakai-hajnali órák adják, a másodikat pedig gyakran a késő délutáni-kora esti órák határozzák meg. A reprezentáció elemszáma nem befolyásolta jelentősen az eredményeket, a kis elemszámú reprezentációk (4, 6 karakter) ugyanazt a csoportosı́tást és hasonló döntési fákat adtak, mint azok, ahol csak 2 vagy 3 elemet átlagoltunk, sőt, az elkülönülés 4 ill. 12 reprezentáló elem esetén a legélesebb. Mivel a legtöbb algoritmus érzékeny a dimenziószámra, a 4 karakterre tömörı́tés jelentősen felgyorsı́tja a futást és nem ad rosszabb eredményt 4.3 A

kisbabás adatok A kutatásunk motivációját egy alváslaborban gyűjtött adathalmaz adta. Az adathalmaz körülbelül 1300 alvást tartalmaz, a méréseket néhány hónapos, de legfeljebb 3 éves gyermekeken végezték. Az egy alváshoz tartozó adatok tartalmazzák többek között a légzési adatokat, amit 8 különböző csatornán mérnek, a szı́vritmust és az izomtónust. Célunk a csecsemők légzésének leı́rása, hiszen az alváslaborokban jóval idősebb gyermekeken végzett vizsgálatok alapján értékelik ki a csecsemők alvását. Főleg a nagyon kicsi, néhány hónapos gyermekek esetén feltehető, hogy az ő alvásuk eltérő, elég ha a hirtelen bölcsőhalál szindrómára (SIDS) gondolunk, ami a nagyobb, néhány éves gyermekeket már nem veszélyezteti. A légzési adatok idősornak tekinthetők, ezért igyekszünk az ezen a téren elért eredményeket is felhasználni

a vizsgálatainkhoz. Sajnos a kapott eredmények nehezen értelmezhetők, orvosok, biológusok folyamatos bevonására van szükség. Az adatokat 1024 hosszúságú részekre bontva vizsgáltam. Mivel az adatsor nem túl hosszú, ezért a taranszformált részsorozatok nem diszjunktak, 256 adatonként vettem mintát. Az együtthatók közül 7-et, 15-öt, 31-et, 63-at ill 127-et tartottam meg. Ezt az utolsót már nem tudtam klaszterezni, a WEKA egy csoportba sorolta mindet A kapott klaszterek száma 5-8, ami ilyen komplex adatok esetén bı́ztató. Megpróbáltam a különböző mérések eredményeként kapott klasztereket egymásnak megfeleltetni, de ez még azonos klaszterszám esetén is csak részben sikerült. Sok esetben viszont mind a négy esetben ugyanabba a (feltételezett) klaszterbe kerültek az adatok. A szubjektivitás kizárása érdekében azonban a klaszterek megfeleltetésére biztosabb módszert kell

találnunk. 42 http://www.doksihu 43 4.2 ábra Klaszterek légzési adatokon (függőlegesen eltolva) a) eredeti b) 7 együtthatóval c) 15 együtthatóval http://www.doksihu 4.3 ábra Klaszterek légzési adatokon (függőlegesen eltolva) a) 31 együtthatóval b) 63 együtthatóval 4.4 SAX A SAX reprezentáció nagy előnye, hogy kevés paramétert kell megadnunk, ezek: az ábécé a mérete, az átlagolt adatok l száma és a kezdeti eltolás l0 hossza. További önkényes választás eredménye a szimbolikus reprezentáció alapjául szolgáló sűrűségfügvény. Ebben a szakaszban ezeket fogjuk részletesebben megvizsgálni. 4.41 Függés l-től A legnagyobb kérdés az, hogy mekkora adatveszteséget okoz a reprezentáció. Szeretnénk találni egy optimális l értéket, amelyre az eredeti és a reprezentált függvény távolsága még nem túl nagy, 44 http://www.doksihu de l értéke

már elég nagy ahhoz, hogy a reprezentáló függvény vizsgálata jelentős javulást okozzon a futási időben és/vagy a szükséges tárhelyben. Ez a két igény természetesen ellentmond egymásnak, minél tömörebb ugyanis a reprezentáció, annál nagyobb lesz a távolság az eredeti és a reprezentáló függvény között. Rögzı́tett l0 = 0 mellett az l-től való függést vizsgáltam. Mivel az átlagoláshoz legalább 2 adatra van szükség, másrészt egy légzés a tapasztalatok szerint legfeljebb 100 egység (4 mp) hosszú, ezért l értékét 2 és 100 között változtattam. A 100 nagyon durva becslés, hiszen a reprezentáció csak akkor lesz értelmezhető, ha minden légzest legalább 4-5 különböző szimbólummal ı́runk le. Átlagosan 20-at lélegzünk percenként, tehát az átlagos légzéshossz ezen az adathalmazon 75, ı́gy az ideális értéket tehát l = 15 − 20

körülinek vártam. A rendelkezésre álló nagyjából 1300 alvás 2 csatornáján kiszámoltam az eredeti és a reprezentáló függvény átlagos euklideszi távolságát (a két függvény távolságát osztottam az idősor hosszával). Csatornánként átlagoltam az egyes l-ekre eső távolságokat és ezt grafikonon ábrázoltam. 4.4 ábra Az eredeti és a reprezentált függvény távolsága az átlagolt adatok számának függvényében Azt tapasztaltam, hogy a távolság a reprezentált és az eredeti adatok között kezdetben gyorsan emelkedik, majd 20 átlagolt elem után a távolság növekedése lassulni kezd, végül nagyjából 40 átlagolt elem után szinte már nem változik. 4.42 Sűrűségfüggvények Mind az energia-, mind a légzési adatok sűrűségfüggvénye erősen eltér a normális eloszlásétól. A légzési adatoknál érdekes a kiugrás a 0

értéknél, ami az adatok előfeldolgozása miatt valójában a nyers értékek átlagát jelenti. 45 http://www.doksihu 4.5 ábra Légzés adatok - 1, 2, 3, 5 csatorna sűrűségfüggvénye 4.5 Wavelet-transzformáció A wavelet transzformáció esetén a választható paraméterek a waveletfüggvény, a megtartott együtthatók száma és a megtartott együtthatók kiválasztása. 4.51 Wavelet függvény A minta adatokon a Haar és a D4 waveleteket használtam. A tapasztalataim alapján nagyon kis elemszámú reprezentáció esetén (4-6 együttható) a Haar-wavelet jobb eredményt adott, utána viszont a D4 szerepelt jobban. Az ok a Haar-wavelet egyszerűsége lehet, mivel itt egyszerre csak két adattal számolunk, a D4 esetén viszont már néggyel, magasabb Daubechies-waveletek esetén pedig még többel. Nagyon kevés megtartott együttható esetén a D4 túl kevés információt tartalmaz, nem

reprezentál jól, kevésbé tömör reprezentáció esetén viszont a komplexebb D4 jobb eredményeket ad. 4.52 Együtthatók száma A tömörı́tés nagyságára vonatkozóan meglepő eredményeket kaptunk: a legjobban a nagyon tömör és a nagyon részletes reprezentációk szerepeltek, a közepes együtthatószám sok és értelmezhetetlen klasztert adott, amelyek között előfordult olyan is, amibe alig került elem, az osztályozók esetében pedig szinte nem befolyásolta a végeredményt. Érdemes tehát nagy mértékű tömörı́tést alakalmazni, mivel ezen az eredmények hasonlóan jók, mint a nagy dimenziós adatokon, viszont a futás sokkal gyorsabb. A kis dimenziós adatokon kapott eredményeket esetleg ellenőrizhetjük az eredeti vagy kis mértékben tömörı́tett adatokon, felhasználva a már kinyert tudást. 46 http://www.doksihu 4.53 Legjobb k együttható Az energia adatokon

végzett kı́sérletek nem adtak egyértelmű eredményt arra, hogy melyik a legjobb módszer a k legjobb együttható kiválasztására. A legmegbı́zhatóbban talán az adapegyütthatók szerepeltek, ezek soha nem adtak igazán rossz felosztást, akármelyik wavelet függvényt használtam és akárhány együtthatót tartottam meg. Nagyon tömör reprezentáció esetén, azaz ha csak 4-6 együtthatót tartottam meg, akkor viszont a Haar-wavelet első együtthatói adták a legpontosabb csoportokat. Sok együttható megtartása esetén a k-legnagyobb együttható volt a legpontosabb az összes leı́rt hibája ellenére. Az eredmény nem meglepő, mivel ezzel a módszerrel őrizzük meg a legtöbb energiát és ha az együtthatók nagy részét megtartjuk, akkor az a probléma, hogy sok esetben nem azonos frekvenciához tartozó együtthatókat mérünk össze, nem jelentkezik. Ebben az esetben viszont alig tudtunk

tömörı́teni a kiindulási adatokon Az adap-együtthatók tehát nem szerepeltek olyan jól, mint azt vártuk volna. Ennek az oka lehet, hogy a tanuló adatok mennyisége és minősége nem volt megfelelő, több, gondosabban kiválasztott adatra lett volna szükség. Egy további paraméter a wavelet-transzformáció esetén a felbontás mélysége. A fenti mérések folyamán a maximális mélységet használtam, de végeztem néhány kı́sérletet különböző szintű felbontásokkal is. Azt tapasztaltam, hogy a különböző mélységű felbontások esetén az adap − k együtthatók pozı́ciói közül sok megegyezett, vagyis a jellemző frekvenciák már kis számolás után megtalálhatóak voltak. Ez további kutatásokra ad lehetőséget: érdemes lenne megvizsgálni, hogy egy részsorozat legnagyobb együtthatóinak pozı́ciói milyen mértékben esnek egybe az osztályának adap

együtthatóinak poziciójával. 47 http://www.doksihu 4.6 Összefoglalás A dolgozatban két adattömörı́tési módszert, a szimbolikus reprezentációt és a wavelet-transzformációt hasonlı́tottam össze. A szimbolikus reprezentáció előnye, hogy bármilyen hosszú részsorozatokat tudunk reprezentálni, mı́g a wavelet-együtthatókat csak 2n hosszúságú adatsorokra értelmeztük. A SAX jellemzően kevesebb klasztert állı́tott elő Ez egyrészt előny, mivel ı́gy az egyes csoportok leı́rása, jellemző tulajdonságainak megtalálása könnyebb, másrészt bizonyos alkalmazásunkban éppen a waveletek részletesebb felbontására lehet szükségünk. Az osztályozók esetén problémát jelentett, hogy a WEKA kevés algoritmusa dolgoz fel folytonos értékeket. Mivel az osztályozó algoritmusok ilyen adatokra is értelmesek, ezért ezen a területen további vizsgálatokra van szükség. A

wavelet-transzformáció előnye, hogy folyamatosan finomodva állı́tjuk elő, mı́g SAX algoritmusok esetén az adatokat egy alkalommal reprezentáljuk és a továbbiakban ezt használjuk. A waveletek multirezolúciós előállı́tását több algortimus kihasználja, a tömörebb adatokon elért részeredményeket a finomabbakon futtatott algoritmus paramétereinek beállı́tására használhatjuk, ami csökkenti a hibázás esélyét és gyorsı́tja a futást is. A legfrissebb cikkek között szerepelnek kı́sérletek a SAX szintenkénti előállı́tására is. A SAX egy további hátránya, hogy a waveletek gondosan kidolgozott elméletével szemben sok heurisztikát, közelı́tést használ. A legtöbb állı́tást a mérési eredmények alátámasztják, de a cikkekben általában csak leı́rás található, bizonyı́tás nem Néhány egyszerűbb állı́tást a Függelékben bizonyı́tok,

viszont például a sűrűségfüggvényekre vonatkozó állı́tásnak az adatok elemzésével nyert grafikonok ellentmondanak. Összességében a SAX gyorsabban adtak eredményt és ezek könnyebben is értelmezhetőek, de egyes esetekben szükség lehet a waveletek részletességére és a háttérben álló elméletre. 4.7 Köszönetnyilvánı́tás Szeretnék köszönetet mondani a témavezetőmnek, Lukács Andrásnak és a SZTAKI dolgozóinak, különösen Lukács Lászlónak, aki a kezdeti időkben nagyon sokat segı́tett. Köszönöm a családomnak és a barátaimnak, hogy tanulmányaimban és munkámban mindig támogattak. 48 http://www.doksihu Irodalomjegyzék [1] Dr. Bodon Ferenc: Adatbányászati algoritmusok, wwwcsbmehu/bodon/magyar/adatbanyaszat, 2008 [2] Jessica Lin, Eamonn Keogh, Stefano Lonardi, Bill Chiu. A Symbolic Representation of Time Series, with Implication for Streaming Algorithms, ACM

SIGKDD International Conference on Knowledge Discovery and Data Mining, Seattle, WA, 2004 [3] Eamonn Keogh, Jessica Lin, Ada Fu. HOT SAX: Finding the Most Unusual Time Series Subsequence: Algorithms and Applications, 5th IEEE International Conference on Data Mining, pp. 226-233,2005 [4] Eamonn Keogh, Kaushik Chakrabarti, Michael Pazzani, Sharad Mehrotra. Dimensionality Reduction for Fast Similarity Search in Large Time Series Databases,Knowledge and Information Systems 3(3): 263-286, 2000 [5] Jin Shieh, Eamonn Keogh. iSAX: Indexing and Mining Terabyte Sized Time Series, SIGKDD 2008 [6] Ada Wai-Chee Fu, Eamonn Keogh, Leo Yung, Hang Lau, Chotirat Ann Ratanamahatana, Raymond Chi-Wing Wong. Scaling and Time Warping in Time Series Querying, VLDB 2005 [7] Tao Li, Qi Li, Shenguo Zhu, Mitsunori Ogihara. A Survey on Wavelet Applications in Data Mining, SIGKDD Explorations, Volume 4, Issue 2, pp. 49-68, 2003 [8] Ronald A. DeVore, Bradley J Lucier Wavelets, Acta Numerica, A Iserles, ed, Cambridge

University Press, pp. 1-56, 1992 [9] Wu Liu, Hai-Xin Duan, Ping Ren, Xing Li, Jian-Ping Wu. Wavelet Based Data Mining and Querying in Network Security Databases, 2003 [10] Jessica Lin, Michail Vlachos, Eamonn Keogh, Dimitrios Gunopulos. Iterative Incremental Clustering of Time Series, IX Conference on Extending Database Technology, 2004 [11] Fabian Mörchen. Time Series Feature Extraction for Data Mining Using DWT and DFT, Department of Mathematics and Computer Science Philips-University Marburg, Technical Report, 33., 2003 [12] Jamel Baili, Samer Lahouar, Mounir Hergli, Adel Amimi, Kamel Besbes. Applications of the Discrete Wavelet Transform to Denoise GPR Signals, Second International Symposium on Communication, Control and Signal Processing, 2006 49 http://www.doksihu 5. fejezet Függelék 5.01 Tétel Az átlaggal becsült PAA reprezentáció alulról becsüli az euklideszi távolságot 5.02 Bizonyı́tás Az alsó becslést elég szakaszonként bizonyı́tani

Tehát az állı́tás: l X i=1 2 2 (qi − ci ) ≥ l(q − c) = l l X i=1 (qi − ci )2 ≥ l Pl i=1 qi l − Pl i=1 ci l 2 2 (q − c ) i i i=1 Pl l2 Jelöljük (qi − ci )-t xi -vel! Így: l X x2i i=1 Pl ( i=1 xi )2 ≥ l Másrészt a Cauchy-Schwarz-Bunyakovszkij egyenlőtlenség szerint: l X ai 2 i=1 l X i=1 bi 2 ≥ X l i=1 ai bi 2 Ekkor az ai = xi , bi ≡ 1 helyettesı́téssel éppen a keresett egyenlőtlenséget kapjuk. 5.03 Tétel A mediánnal becsült PAA reprezentáció nem becsüli alulról az euklideszi távolságot 5.04 Bizonyı́tás Tekintsük a következő két, az egyszerűség kedvéért nagyon rövid idősort: C = 0, 0, 0, 1, 1, Q = 0, 0, 1, 1, 1. Természetesen az ellenpélda tetszőleges hosszúságú idősorra felı́rható A két függvény euklideszi távolsága 1, C mediánja 0, Q mediánja 1. ı́gy C = 0, 0, 0, 0, 0, Q = 1, 1, 1, 1, 1, ezek távolsága 5 > 1.

Tehát ezzel a közelı́téssel nem tudjuk alulról becsülni az euklideszi távolságot. ÁBRA!!! 5.05 Tétel A c1 , c2 , , cn adatokat négyzetesen legjobban közelı́tő konstans az n érték átlaga 5.06 Bizonyı́tás Legyen a négyzetesen legjobb konstans c Ezekkel a jelölésekkel tehát a következő függvényt szeretnénk minimalizálási feladatot szeretnénk megoldani: min f (c) = n X i=1 (ci − c)2 = 50 n X i=1 c2i − 2c n X i=1 ci + nc2 http://www.doksihu A minimumhelyet a c szerinti első és második derivált vizsgálatával találhatjuk meg: ′ f (c) = −2 6 −2 n X i=1 n X ci + 2nc i=1 ci + 2nc = 0 ⇐⇒ c = Pn i=1 ci n f ′′ (c) = 2n Tehát a célfüggvény a szélsőértékét az értékek átlagánál veszi fel és mivel n > 0, ezért ez a szélsőérték minimum. 5.07 Tétel A PAA távolság nem becsüli alulról a DTW távolságot 5.08 Bizonyı́tás

Ellenpéldaként két 5 elemű idősort adunk meg, de az állı́tás hosszabbakra is igaz (legegyszerűbb ellenpéldaként ezeket az öteleműeket azonosan folytatva). Legyen tehát C=1,2,2,4,5 és Q=1,1,2,3,5. A DTW kiszámı́tását dinamikusan egy távolságmátrix kitöltésével számoljuk, majd a mártixban megkeressük a legrövidebb utat. A két idősor távolságmátrixa: 1 1 2 3 5 1 0 0 1 5 21 2 1 1 0 1 10 2 2 2 0 1 10 4 11 11 4 1 2 5 27 27 13 5 1 A két idősor DTW-távolsága tehát 1, a C idősor átlaga 2,4, a Q idősor átlaga 2,8, tehát a PAA távolságuk az átlaggal 2, ami nagyobb, mint 1, azaz a PAA nem becsüli alulról a DTW-t. 51 http://www.doksihu Daubechies-együtthatók (kettőre normálva, 2-10) D2 (Haar) D4 D6 D8 D10 a0 1 0.6830127 0.47046721 0.32580343 0.22641898 a1 1 1.1830127 1.14111692 1.01094572 0.85394354 a2 0.3169873 0.650365 0.8922014

1.02432694 a3 -0.1830127 -0.19093442 -0.03957503 0.19576696 a4 -0.12083221 -0.26450717 -0.34265671 a5 0.0498175 0.0436163 -0.04560113 a6 0.0465036 0.10970265 a7 -0.01498699 -0.00882680 a8 -0.01779187 a9 4.71742793e-3 Daubechies-együtthatók (kettőre normálva, 12-20) D12 D14 D16 D18 D20 a0 0.15774243 0.11009943 0.07695562 0.05385035 0.03771716 a1 0.69950381 0.56079128 0.44246725 0.34483430 0.26612218 a2 1.06226376 1.03114849 0.95548615 0.85534906 0.74557507 a3 0.44583132 0.66437248 0.82781653 0.92954571 0.97362811 a4 -0.31998660 -0.20351382 -0.02238574 0.18836955 0.39763774 a5 -0.18351806 -0.31683501 -0.40165863 -0.41475176 -0.35333620 a6 0.13788809 0.1008467 6.68194092e-4 -0.13695355 -0.27710989 a7 0.03892321 0.11400345 0.18207636 0.21006834 0.18012745 a8 -0.04466375 -0.05378245 -0.02456390 0.043452675 0.13160299 a9 7.83251152e-4 -0.02343994 -0.06235021 -0.09564726 -0.10096657 a10

6.75606236e-3 0.01774979 0.01977216 3.54892813e-4 -0.04165925 a11 -1.52353381e-3 6.07514995e-4 0.01236884 0.03162417 0.04696981 a12 -2.54790472e-3 -6.88771926e-3 -6.67962023e-3 5.10043697 e-3 a13 5.00226853e-4 -5.54004549e-4 -6.05496058e-3 -0.01517900 a14 9.55229711e-4 2.61296728e-3 1.97332536 e-3 a15 -1.66137261e-4 3.25814671e-4 2.81768659 e-3 a16 -3.56329759e-4 -9.69947840 e-4 a17 -5.5645514e-5 -1.64709006 e-4 a18 1.32354367 e-4 a19 -1.875841 e-5 52

Mathematics | Mathematical analysis » Dömötör Csilla - Idősorok analízise, diplomamunka

Datasheet

What did others read after this?

Balázsi Tamás - Hozamgörbék vizsgálata globális és országspecifikus faktorokkal

Csuka Anita - Az e szám

Citroen C3 kezelési útmutató

Dancs István - Analízis

Content extract

Our best articles

How to write a Literary Analysis?

Our best textbooks

Contents

Navigation

Mathematics | Mathematical analysis » Dömötör Csilla - Idősorok analízise, diplomamunka

Datasheet

Embed document viewer

What did others read after this?

Balázsi Tamás - Hozamgörbék vizsgálata globális és országspecifikus faktorokkal

Csuka Anita - Az e szám

Citroen C3 kezelési útmutató

Dancs István - Analízis

Content extract

Our best articles

How to write a Literary Analysis?

Our best textbooks

Contents

Navigation