Algoritma Dynamic Time Warping

Dynamic Time Warping atau kita singkat saja dengan DTW  (jangan kebalik dengan DWT) 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.

(1) Sakoe, H. And Chibam, S. Dynamic Programming algorithm optimization for spoken word recognition. IEEE Trans. On Acoust, Speech, and Signal Processing, ASSP 26, 43-49 (1978)

Bagaimana mengukur tingkat jarak pada time series diatas?

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.

Ilustrasi Fungsi Dynamic Time Warping

Time Normalized Distance measure

Cara Perhitungan Dynamic Time Warping

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

Perhatikan variabel berikut

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

Kita akan menghitung distances menggunakan eucledian distances

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

hasilnya

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 bisa visualisasikan dalam heatmap plot

Menghitung accumulated_cost mulai dari baris pertama

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

Dilanjutkan sisi kolom pertama dari y

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

Menghitung untuk semua element (yaitu baris dan kolom ke 2) yang lain, dengan rumus berikut

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

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.

path(1,:) = [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,:)=[j, i];
    index = index+1;
end
path(index,:)=[1,1];

menghasilkan

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

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

hasil cost yang merupakan DTW yaitu

2