Újfajta, automatikus, döntési fa alapú adatbányászati módszer idősorok osztályozására

VÉGZŐS KONFERENCIA 2009 2009. május 20, Budapest

Újfajta, automatikus, döntési fa alapú adatbányászati módszer idősorok osztályozására Hidasi Balázs [email protected]

Konzulens: Gáspár-Papanek Csaba Budapesti Műszaki és Gazdaságtudományi Egyetem Villamosmérnöki és Informatikai Kar Távközlési és Médiainformatikai Tanszék 2009. Május 20.

Tartalom Motiváció Célok A ShiftTree algoritmus A módszer alapjai Tanulás (ötlet) Osztályozás példa Optimalizálás: többszörös modellezés

Eredmények Benchmark Verseny

Alkalmazási lehetőségek Beszélő felismerése Gesztusfelismerés (+felhasználó azonosítás) „Gondolatok” felismerése

Összefoglalás

2

Motiváció Idősorok osztályozása Sok az idősor-jellegű adat Előtérbe kerülő alkalmazási területek Nyomkövetés Hangfelismerés Diagnosztika Gesztusfelismerés

Tanítás

Modell

Modell Osztályozás

Jelenlegi algoritmusok hátrányai Klasszikus módszerek Jelentős emberi munka (előkészítés) Nem erre találták ki Információvesztés (pontatlanság)

Általában nem magyaráz

Terület-specifikus algoritmusok Más területen nem hatékony

3

Célok Automatikus Kevés emberi munka Rövid előkészítési fázis

Minél több típus általános kezelése Változók száma, osztályok száma, idősorok hossza, stb.

Több területen használható (általános)

Pontos osztályozás Magas találati arány

Magyarázó Könnyen értelmezhető modellt épít Ellenőrizhető

4

ShiftTree – A módszer alapjai Hibrid algoritmus Döntési fa alap Szerkezet Vágások jóság értékei Leállási feltételek

Cs1 ES: Szem beállítása

Módosított csomópont-szerkezet

Moduláris felépítés Szemtologató (EyeShifter) ES-Operator (ESO) Szem (pointer) mozgatás F(x)

CB: Érték számítása

L1

Cs2 Modell

Feltételállító (ConditionBuilder) CB-Operator (CBO) Érték származtatás a szem által mutatott értékből

Cs3

D: Feltétel választása

L2 Felt?

(és környezetéből)

Döntő (Decider) M

Vágási helyek vizsgálata Jóságérték számítás Optimális vágás választása a lehetségesekből Feltétel kiszámítása

L3

L4

5

ShiftTree – Tanulás (ötlet) „Dinamikus attribútumok” Hol nézzük? (ESO) 25 időegységgel előrefele (ESONext(25)) A globális maximumnál (ESOMax) 60 méretű intervallumon belül a legkisebb értéknél …

Mit nézzünk? (CBO) F(x)

A pontbeli értéket (CBOSimple) Az érték környezetének normális eloszlás szerinti súlyozott átlagát (CBONormal) Az ugrás során a lokális maximumok számát Az ugrás hosszát …

Tanulás egy csomópontban Leállási feltételek vizsgálata Lehetséges attribútumok kiszámolása (ESO-CBO párok) Az (első) optimális vágás megtalálása (ezt végzi a Decider) Attribútumok közül egy Feltétel érték

Operátorok és a feltétel érték megjegyzése Vágás az attribútum és a feltétel alapján Kettéosztani a tanítópontokat a jobb és bal gyermeknek

Rekurzívan ugyanez a gyermek csomópontokban 6

ShiftTree – Osztályozás példa 0. szint ESOMax CBOSimple Felt: 2,028

1. szint

1. szint ESONext(25)

Levél

CBOSimple Felt: 0,201982

2. szint

2. szint

Levél

Levél

7


1. szint


Levél


2. szint

2. szint

Levél

Levél

7

ShiftTree – Osztályozás példa 0. szint ESOMax CBOSimple Felt: 2,028 Érték: 1,89136

1. szint


Levél


Érték: 2,15333

2. szint

2. szint

Levél

Levél

7 Érték: 2,97557

ShiftTree – Osztályozás példa 0. szint ESOMax CBOSimple Felt: 2,028 Érték: 1,89136

1. szint


Levél


Érték: 2,15333

2. szint

2. szint

Levél

Levél

7 Érték: 2,97557


1. szint


Levél


2. szint

2. szint

Levél

Levél

7


1. szint


Levél


2. szint

2. szint

Levél

Levél

7


1. szint


Levél


Érték: -0,953538

2. szint

2. szint

Levél

Levél

7 Érték: 1,32432


1. szint


Levél


Érték: -0,953538

2. szint

2. szint

Levél

Levél

7 Érték: 1,32432


1. szint


Levél


2. szint

2. szint

Levél

Levél

7


1. szint


Levél


2. szint

2. szint

Levél

Levél

7

Optimalizálás: többszörös modellezés Több optimális attribútum esetén Az összeset kiválasztjuk Az összes szerint vágunk Többszörös fát építünk De csak ott sokszorozunk, ahol kell, nem az egész fát

Egy másik halmazzal kiválasztjuk a legjobbat 1. szint ESONext(25) CBOSimple Feltétel1

Az 1. optimális (25-öt előre)

1. szint ESOPrev(25) CBOSimple Feltétel2

Ez is optimális

2. szint

2. szint

Levél

Levél

2. szint

2. szint

Levél

Levél

(25-öt vissza) 8

Eredmények: benchmark adatokon 20 adatsor különböző területekről Egy változó Eltérő tulajdonságok 7 másik algoritmussal szemben KNN, C4.5 döntési fa, Logistic Model Tree, MLP, SVM, Naív Bayes háló, Random Forest

Konfiguráció Nincs optimalizálás Legegyszerűbb operátorok Ugrás előre/hátra fix távot Ugrás a következő lokális maximumra/minimumra Ugrás a maximumra/minimumra Pontbeli érték, normális súlyozás, exponenciális súlyozás ShiftTree vs más osztályozók

Optimalizálás hatása

2

3

4

5 Helyezés

6

7

8

Többszörös modellezés Egyszerű modellezés

Adatsorok

Yoga

Wafer

Trace

OSULeaf

OliveOil

Lighting7

TwoPatterns

Többszörös modellezés nyeséssel

SyntheticControl

1

SwedishLeaf

0

Lighting2

2

GunPoint

4

Fish

50Words

6

FaceAll

8

FaceFour

10

ECG200

12

CBF

14

Coffee

Pontosság (%)

16

100,00% 90,00% 80,00% 70,00% 60,00% 50,00% 40,00% 30,00% 20,00% 10,00% 0,00% Beef

18

Adiac

20

9

Eredmények: verseny körülmények SIGKDD’07 Time Series Challange adatsorain 20 adatsor Kombinált osztályozók ellen

Helyezések megoszlása

Erősebb konfiguráció

7

Fejlettebb operátorok Több futtatás, többségi szavazás De a paraméterek nincsenek finomhangolva 6 4 2 8

5 4

első helyezés (legtöbb) adatsoron még lehetne nyerni adatsoron lehetne javítani adatsoron kevés a tanítóminta

3

Modell alapú algoritmusok itt elvéreznek

0

Összesítésben: 6-8 hely

ShiftTree

Db

Eredmények

6

Győztes

2 1

1

2

3

4

5

6

7

8

9

10

11

12

13

Helyezés

Holtversenyben (a 13-ból)

10

Alkalmazás: hang- és, gesztusfelismerés Személy felismerése az ae magánhangzó kiejtése alapján

Hangfelismerés (AE): pontosság 100,00%

12 változó 9 személy (osztály)

90,00%

Találati arány (%)

80,00%

Egyszerű operátorok Nincs optimalizálás Találati arány kellően magas

70,00% 60,00% 50,00% 40,00% 30,00% 20,00% 10,00% 0,00% 0%

10%

20%

30%

40%

50%

60%

70%

80%

90%

100%

Tanítópontok aránya (%)

Gesztus adatai gyorsulásmérővel

Felhasználó felismerés a "love" gesztusnál: pontosság

3 változó (koordináta tengelyek) 10 gesztus, 4 felhasználó Kevés adat

100,00% 90,00%

Találati arány (%)

80,00% 70,00%

Lehetséges feladatok:

60,00% 50,00%

Gesztus felismerése Adott gesztusnál a felhasználó felismerése (nehéz feladat)

40,00% 30,00% 20,00% 10,00% 0,00% 0%

10%

20%

30%

40%

50%

60%

Tanítópontok aránya (%)

70%

80%

90%

100%

Bonyolult gesztusnál jobb eredmény 11 Kiemelkedő találati arány

Alkalmazás: „Gondolat” felismerés EEG hullámok osztályozása Adatsor: Két osztály: FEL, LE 6 változó

Jelenleg ~90% körüli pontosság 2003-as versenyen a top3-ban

Alkalmazás típusai Offline osztályozás Alkatrészek tesztelésének automatikus kiértékelése

Stream adatsorban jelek felismerése Még sok nyitott kérdés Folyamatban lévő kutatás 12

Összefoglalás Új idősor-osztályozó: ShiftTree Automatikus Minden egydimenziós idősorral működik Operátorok definiálása a szakértő feladata Nem automatikus

Pontos Már egyszerű operátorokkal, optimalizálás nélkül is kellően pontos Optimalizálással kifejezetten hatékony Ha a tanítóminta nem túl kicsi

Magyarázó Könnyen értelmezhető modellek, ellenőrizhető

Legnagyobb előnye: általános Tématerülettől függetlenül hatékonyan használható

13

További ShiftTree-vel kapcsolatos kutatási anyagok az oldalamon: http://www.hidasi.eu

Köszönöm a figyelmet! ES: Szem beállítása CB: Érték számítása Modell

Modell


ES: Szem beállítása

ES: Szem beállítása




Modell


Újfajta, automatikus, döntési fa alapú adatbányászati módszer idősorok osztályozására

Recommend Documents