prikaz prve stranice dokumenta Algoritmi poravnavanja vremenskih nizova
  Download
PDF 1.62 MB
master's thesis
Algoritmi poravnavanja vremenskih nizova
Zagreb: University of Zagreb, Faculty of Science, 2017. urn:nbn:hr:217:712841
Jukić-Bračulj, Mirjana
University of Zagreb
Faculty of Science
Department of Mathematics

Institutional repository: Repository of the Faculty of Science

Cite this document

Jukić Bračulj, M. (2017). Algoritmi poravnavanja vremenskih nizova (Master's thesis). Zagreb: University of Zagreb, Faculty of Science. Retrieved from https://urn.nsk.hr/urn:nbn:hr:217:712841

Jukić Bračulj, Mirjana. "Algoritmi poravnavanja vremenskih nizova." Master's thesis, University of Zagreb, Faculty of Science, 2017. https://urn.nsk.hr/urn:nbn:hr:217:712841

Jukić Bračulj, Mirjana. "Algoritmi poravnavanja vremenskih nizova." Master's thesis, University of Zagreb, Faculty of Science, 2017. https://urn.nsk.hr/urn:nbn:hr:217:712841

Jukić Bračulj, M. (2017). 'Algoritmi poravnavanja vremenskih nizova', Master's thesis, University of Zagreb, Faculty of Science, accessed 23 December 2024, https://urn.nsk.hr/urn:nbn:hr:217:712841

Jukić Bračulj M. Algoritmi poravnavanja vremenskih nizova [Master's thesis]. Zagreb: University of Zagreb, Faculty of Science; 2017 [cited 2024 December 23] Available at: https://urn.nsk.hr/urn:nbn:hr:217:712841

M. Jukić Bračulj, "Algoritmi poravnavanja vremenskih nizova", Master's thesis, University of Zagreb, Faculty of Science, Zagreb, 2017. Available at: https://urn.nsk.hr/urn:nbn:hr:217:712841

Metadata
TitleAlgoritmi poravnavanja vremenskih nizova
AuthorMirjana Jukić-Bračulj
MentorLuka Grubišić (mentor)
Committee memberLuka Grubišić (predsjednik povjerenstva)
Committee memberSaša Singer (član povjerenstva)
Committee memberIvica Nakić (član povjerenstva)
Committee memberLjiljana Arambašić (član povjerenstva)
GranterUniversity of Zagreb
Faculty of Science
(Department of Mathematics)
Zagreb
Defense date and country2017-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
Keywords (english)
Languagecroatian
URN:NBNurn:nbn:hr:217:712841
Study programmeTitle: 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 resourceText
File originBorn digital
Access conditionsOpen access
Terms of useLicence In copyright icon
Created on2018-01-31 11:17:27