Algoritmi poravnavanja vremenskih nizova

master's thesis

• Author: Mirjana Jukić-Bračulj
• Mentor: Luka Grubišić (mentor)
• Committee member: Luka Grubišić (predsjednik povjerenstva)
• Committee member: Saša Singer (član povjerenstva)
• Committee member: Ivica Nakić (član povjerenstva)
• Committee member: Ljiljana Arambašić (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2017-07-19, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

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.

Abstract (english)

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.

• Keywords: 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
• Keywords (english): 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
• Language: croatian
• URN:NBN: urn:nbn:hr:217:712841
• Study programme: Title: Computer Science and Mathematics; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra računarstva i matematike (magistar/magistra računarstva i matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2018-01-31 11:17:27