alexa-tracking
Kategori
Kategori
Home / FORUM / All / Tech / ... / Programmer Forum /
Algoritma Dynamic Time Warping
1024
1024
KASKUS
51
244
https://www.kaskus.co.id/thread/5d9c8dcf28c991644c2c8880/algoritma-dynamic-time-warping

Algoritma Dynamic Time Warping

Algoritma Dynamic Time Warping

Algoritma Dynamic Time Warping

Kita sebut saja dengan DTW  (jangan kebalik dengan DWT) Dynamic time warping (DTW) adalah algoritma penyelarasan time series yang dikembangkan awalnya untuk pengenalan suara (1). Ini bertujuan menyelaraskan dua urutan vektor fitur dengan memutar sumbu waktu secara iteratif hingga kecocokan optimal (menurut metrik yang sesuai) antara dua urutan ditemukan.
Bagaimana mengukur tingkat jarak pada kasus diatas?
Quote:





Algoritma Dynamic Time Warping


Gambar kiri (non elastis) : Jarak manapun (Euclidean, Manhattan,…) yang menyelaraskan titik (i) pada satu seri waktu dengan titik ke (i) di sisi yang lain akan menghasilkan skor kesamaan yang buruk.
Gambar kanan (elastis): Perataan non-linear (elastis) menghasilkan ukuran kesamaan yang lebih intuitif, memungkinkan bentuk-bentuk serupa untuk dicocokkan bahkan jika mereka keluar (beda fase) dalam domain waktu.
Fungsi Dynamic Time Warping

Algoritma Dynamic Time Warping

Time-Normalized Distance Measure
Algoritma Dynamic Time Warping

Perhitungan DTW
Membuat 2 sinyal yang akan dibandingkan, kita akan mengukur jarak/kemiripan 2 sinyal dibawah ini yang mempunyai time yang berbeda

Algoritma Dynamic Time Warping


Code:
x = [1, 1, 2, 3, 2, 0]; 
y = [0, 1, 1, 2, 3, 2, 1];


Kita akan menghitung distances menggunakan eucledian distances

Code:
distances = zeros(length(y),length(x));
for i=1:length(y)
    for j=1:length(x)
        distances(i,j) = (y(i)-x(j))^2;
    end
end



menghasilkan
Code:
distances =

    1    1    4    9    4    0
    0    0    1    4    1    1
    0    0    1    4    1    1
    1    1    0    1    0    4
    4    4    1    0    1    9
    1    1    0    1    0    4
    0    0    1    4    1    1


Kita visualisasikan dalam bentuk plot seperti berikut

Algoritma Dynamic Time Warping

Menghitung accumulated_costmulai dari baris pertama

Code:
accumulated_cost = zeros(length(y),length(x));
accumulated_cost(1,1) = distances(1,1);
for i=2:length(x)
    accumulated_cost(1,i) = distances(1,i) + accumulated_cost(1, i-1);
end


Algoritma Dynamic Time Warping

Dilanjutkan sisi kolom pertama dari y
Code:
for i=2:length(y)
    accumulated_cost(i,1) = distances(i,1) + accumulated_cost(i-1,1);
end



Algoritma Dynamic Time Warping

Menghitung untuk semua element (yaitu baris dan kolom ke 2) yang lain, dengan rumus berikut
Accumulated Cost (D(i,j))=min{D(i−1,j−1),D(i−1,j),D(i,j−1)}+distance(i,j)
Code:
for i=2:length(y)
    for j=2:length(x)
        accumulated_cost(i, j) = min([accumulated_cost(i-1, j-1), accumulated_cost(i-1, j), accumulated_cost(i, j-1)]) + distances(i, j);
    end
end



 Algoritma Dynamic Time Warping
Mencari path optimal : sekarang perlu menemukan jalan yang meminimalkan jarak yang kita lakukan dengan teknik backtracking (mundur). Prosedur backtracking cukup sederhana dan melibatkan upaya untuk kembali dari titik terakhir (M, N) dan menemukan tempat mana yang akan dicapai (dengan meminimalkan biaya) dan melakukan ini dengan cara berulang.
Algoritma Dynamic Time Warping




Code:
path(1,emoticon-Smilie = [length(x), length(y)];
i = length(y);
j = length(x);
index = 2;
while i>1 && j>1
    if i==1
        j = j - 1;
    elseif j==1
        i = i - 1;
    else
        minimal = min([accumulated_cost(i-1, j-1), accumulated_cost(i-1, j), accumulated_cost(i, j-1)]);
        if accumulated_cost(i-1, j) == minimal
            i = i - 1;
        elseif accumulated_cost(i, j-1) == minimal
            j = j - 1;
        else
            i = i - 1;
            j = j- 1;
        end
    end
    path(index,emoticon-Smilie=[j, i];
    index = index+1;
end
path(index,emoticon-Smilie=[1,1];



menghasilkan


Code:
path =

    6    7
    5    6
    4    5
    3    4
    2    3
    2    2
    1    2
    1    1




Kemudian menghitung cost dari path (index distances) yang telah diketahui

Code:
cost  = 0;
for i=1:length(path)
    cost = cost+distances(path(i,2),path(i,1));
end






menghasilkan

Code:
cost = 2



Kode ditulis menggunakan tools matlab, biar mudah dipelajari!
ref:

https://www.softscients.web.id/2018/...e-warping.html
Beri apresiasi terhadap thread ini Gan!


×
GDP Network
© 2019 KASKUS, PT Darta Media Indonesia. All rights reserved
Ikuti KASKUS di