Algoritmi poravnavanja vremenskih nizova

diplomski rad

• Autor: Mirjana Jukić-Bračulj
• Mentor: Luka Grubišić (mentor)
• Član povjerenstva: Luka Grubišić (predsjednik povjerenstva)
• Član povjerenstva: Saša Singer (član povjerenstva)
• Član povjerenstva: Ivica Nakić (član povjerenstva)
• Član povjerenstva: Ljiljana Arambašić (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Prirodoslovno-matematički fakultet; (Matematički odsjek); Zagreb
• Datum i država obrane: 2017-07-19, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

Vremenski nizovi imaju široku primjenu u praksi pa je potrebno osmisliti nove i prilagoditi postojeće algoritme za računanje s takvom vrstom podataka. Jedan od algoritama koji se koristi za pronalazak udaljenosti između dva vremenska niza proizvoljne duljine je algoritam poravnavanja vremenskih nizova. Algoritam uzima u obzir varijacije u vremenu prilikom nastanka niza i na taj način dobiva točniju usporedbu vremenskih nizova. Ima kvadratnu složenost pa se uvode algoritmi koji korištenjem donjih ograda daju ubrzanje početnog algoritma. U prvom poglavlju rada opisana je ideja i osnovi oblik algoritma. Prikazane su jednostavne varijacije u koraku algoritma i ograničenja koja mogu djelomično ubrzati računanje udaljenosti nizova. Drugo poglavlje uvodi Keoghovu i poboljšanu Keoghovu donju granicu kao oblike ubrzanja algoritma osvrćući se na njihovu složenost i usporedbu s početnim algoritmom. Osim donjih granica kao jednog načina ubrzanja algoritma, koriste se još metoda podijeli pa vladaj i upotreba rijetko popunjenih matrica. Osim za usporedbu vremenskih nizova algoritam dinamičkog poravnavanja vremena koristi se za dobivanje srednje vrijednosti skupa vremenskih nizova. Metoda baricentričnog usrednjavanja, opisana u trećem poglavlju, nizom iteracija u kojima se računanju udaljenosti nizova pomoću algoritma dolazi do tražene srednje vrijednosti. U praktičnom dijelu rada napravljena je primjena algoritma u prepoznavanju govora i rukopisa. Prikazan je način pripremanja podataka, dobivanje osnovnih svojstava uzorka i rezultati njihove usporedbe dobiveni korištenjem algoritma.

Sažetak (engleski)

Time series appear in many application domains like biology, finance, image analysis, etc. It is necessary to adapt techniques and algorithms to this kind of data. Dynamic time warping algorithm is dynamic programming paradigm to compute the alignment between two time series with arbitrary lengths. Algorithm has quadratic time complexity and because of that many speed-up techniques are introduced. In the first chapter we introduce classical dynamic time warping algorithm and give examples of step function. Simple techniques to speed up the algorithm are shown. In the second chapter we describe algorithms that have better time and space complexity than classical dynamic time warping algorithm. Some of them are: Keogh lower bound, improved Keogh lower bound, divide and conquer and sparse dynamic time warping algorithm. A global averaging method for dynamic time warping is presented in third chapter. The method is called dynamic time warping barycenter averaging. The method iteratively refines an initial average sequence in order to minimize its squared dynamic time warping distances to averaged sequences. In the fourth and fifth chapter we present case studies that use the algorithm for speech and handwriting recognition and measure accuracy of different types of algorithm.

• Ključne riječi: vremenski nizovi; algoritam poravnavanja vremenskih nizova; Keoghova donja granica; poboljšana Keoghova donja granica; metoda podijeli pa vladaj; upotreba rijetko popunjenih matrica; algoritam dinamičkog poravnavanja vremena; metoda baricentričnog usrednjavanja
• Ključne riječi (engleski): time series; dynamic time warping algorithm; Keogh lower bound; improved Keogh lower bound; divide and conquer; sparse dynamic time warping algorithm; dynamic time warping barycenter averaging
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:712841
• Studijski program: Naziv: Računarstvo i matematika; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra računarstva i matematike (mag. inf. et math.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2018-01-31 11:17:27