izpis_h1_title_alt

Algoritmi za izračun razdalje med časovnimi vrstami z dinamičnim prilagajanjem časa
ID PREMK, LEON (Author), ID Mihelič, Jurij (Mentor) More about this mentor... This link opens in a new window

.pdfPDF - Presentation file, Download (3,19 MB)
MD5: 1A468CCC44CAD448E92920A88390372B

Abstract
Diplomska naloga obravnava možne pohitritve računanja razdalje med časovnima vrstama. S časovnimi vrstami se v računalništvu srečujemo zelo pogosto in so ena izmed najpomembnejših vrst podatkov za strojno učenje. S pomočjo razpoznave trendov znotraj časovnih vrst lahko lažje razumemo, kaj te predstavljajo, jih razvrščamo v razrede in pripravimo za nadaljnje raziskave. Doprinos diplomske naloge so novi pristopi optimizacije algoritma dinamičnega prilagajanja časa s pomočjo vzporednega izvajanja. Predstavljena sta dva načina izboljšave. Prvi način temelji na principu srečanja na sredini, kjer se en del algoritma začne računati na začetku, drugi na koncu, srečata pa se na sredini, kjer se združita in vrneta rezultat. Drugi način opisuje prilagoditev zaporedja računanja tako, da problem dinamičnega programiranja v vsaki iteraciji lahko računamo vzporedno. Prednost prve izboljšave je, da je preprosta za razumevanje in izvedbo ter že na majhnih časovnih vrstah dosega pričakovano pohitritev. Druga izboljšava je za izvedbo malenkost bolj kompleksna in se zaradi tehničnih omejitev bolje izkaže na dolgih časovnih vrstah.

Language:Slovenian
Keywords:dinamično prilagajanje časa, vzporedni algoritem, dinamično programiranje, k najbližjih sosedov, časovna vrsta
Work type:Bachelor thesis/paper
Typology:2.11 - Undergraduate Thesis
Organization:FRI - Faculty of Computer and Information Science
Year:2020
PID:20.500.12556/RUL-119414 This link opens in a new window
COBISS.SI-ID:28690179 This link opens in a new window
Publication date in RUL:08.09.2020
Views:1487
Downloads:224
Metadata:XML RDF-CHPDL DC-XML DC-RDF
:
Copy citation
Share:Bookmark and Share

Secondary language

Language:English
Title:Algorithms for distance calculation between time series using dynamic time warping
Abstract:
This BSc thesis deals with speeding up distance calculations between time series. We deal with time series very often in computer science. They are one of the most common forms of data for machine learning. By recognizing trends within them, we can understand them better, split them into classes and prepare them for further research. The contribution of this BSc thesis are new approaches for optimising dynamic time warping (DTW) algorithm by parallelizing its computation. Two approaches of optimisation are described. First approach is based on \textit{meet in the middle} principle, where we begin calculating from each end of time series and meet in the middle. Second approach is based on changing the sequence of calculations in order to be able to compute each iteration of this dynamic programming problem in parallel. First approach is easier to understand and implement and performs as expected even on shorter time series. Second approach is more complex to implement and because of technical limitations only gives optimal results on longer time series.

Keywords:dynamic time warping, parallel algorithms, dynamic programming, k nearest neighbours, time series

Similar documents

Similar works from RUL:
Similar works from other Slovenian collections:

Back