prikaz prve stranice dokumenta Algoritmi poravnavanja vremenskih nizova
  Preuzmi
PDF 1.62 MB
diplomski rad
Algoritmi poravnavanja vremenskih nizova
Zagreb: Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, 2017. urn:nbn:hr:217:712841
Jukić-Bračulj, Mirjana
Sveučilište u Zagrebu
Prirodoslovno-matematički fakultet
Matematički odsjek

Institucijski repozitorij: Repozitorij Prirodoslovno-matematičkog fakulteta

Citirajte ovaj rad

Jukić Bračulj, M. (2017). Algoritmi poravnavanja vremenskih nizova (Diplomski rad). Zagreb: Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet. Preuzeto s https://urn.nsk.hr/urn:nbn:hr:217:712841

Jukić Bračulj, Mirjana. "Algoritmi poravnavanja vremenskih nizova." Diplomski rad, Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, 2017. https://urn.nsk.hr/urn:nbn:hr:217:712841

Jukić Bračulj, Mirjana. "Algoritmi poravnavanja vremenskih nizova." Diplomski rad, Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, 2017. https://urn.nsk.hr/urn:nbn:hr:217:712841

Jukić Bračulj, M. (2017). 'Algoritmi poravnavanja vremenskih nizova', Diplomski rad, Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, citirano: 23.12.2024., https://urn.nsk.hr/urn:nbn:hr:217:712841

Jukić Bračulj M. Algoritmi poravnavanja vremenskih nizova [Diplomski rad]. Zagreb: Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet; 2017 [pristupljeno 23.12.2024.] Dostupno na: https://urn.nsk.hr/urn:nbn:hr:217:712841

M. Jukić Bračulj, "Algoritmi poravnavanja vremenskih nizova", Diplomski rad, Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, Zagreb, 2017. Dostupno na: https://urn.nsk.hr/urn:nbn:hr:217:712841

Za citiranje koristite ovu mrežnu adresu: https://urn.nsk.hr/urn:nbn:hr:217:712841
Podaci o radu
NaslovAlgoritmi poravnavanja vremenskih nizova
AutorMirjana Jukić-Bračulj
MentorLuka Grubišić (mentor)
Član povjerenstvaLuka Grubišić (predsjednik povjerenstva)
Član povjerenstvaSaša Singer (član povjerenstva)
Član povjerenstvaIvica Nakić (član povjerenstva)
Član povjerenstvaLjiljana 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 obrane2017-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
Ključne riječi (engleski)
Jezikhrvatski
URN:NBNurn:nbn:hr:217:712841
Studijski programNaziv: 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 resursaTekst
Način izrade datotekeIzvorno digitalna
Prava pristupaOtvoreni pristup
Uvjeti korištenjaIkona licence Zaštićeno autorskim pravom.
Datum i vrijeme pohrane2018-01-31 11:17:27