Matlab-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?
Sakoe,H. and Chiba, S. Dynamic programming algorithm optimization for spoken word recognition. IEEE Trans. on Acoust., Speech, and Signal Process., ASSP 26, 43-49 (1978).

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

Time-Normalized Distance Measure

Perhitungan DTW

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

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

menghasilkan

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

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
Accumulated Cost (D(i,j))=min{D(i−1,j−1),D(i−1,j),D(i,j−1)}+distance(i,j)

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

menghasilkan

cost = 2