Dynamic Time Warping Distance [PDF]

Citation preview

Dynamic Time Warping Distance DTW (DynamicTime Warping) adalah metode untuk menghitung jarak antara dua data time series. Keunggulan DTW dari metode jarak yang lainnya adalah mampu menghitung jarak dari dua vector data dengan panjang yang berbeda. Jarak DTW diantara dua vektor dihitung dari jalur pembengkokkan optimal (optimal warping path) dari kedua vektor tersebut.



(a)



(b)



Gambar Pencocokan sequence (a) alignment asli dari 2 sequence (b) alignment dengan DTW.



Dari beberapa teknik yang digunakan untuk menghitung DTW, salah satu yang paling handal adalah dengan metode pemrograman dinamis. Jarak DTW dapat dihitung dengan rumus:



D(U , V ) = γ (m, n) γ (i − 1, j )  γ (m, n) = d base (u i , v j ) + min γ (i − 1, j − 1) γ (i, j − 1)  γ (0,0) = 0, γ (0, ∞) = ∞, γ (0,0) = 0, γ (∞,0) = ∞ (i = 1,2,3...m; j = 1,2,3...n) Nilai pada kolom (i,j) terlihat sebagai nilai penjumlahan jalur pembengkokkan dari kolom (1,1) hingga (i,j). Kolom dengan nilai γ (i, j )(1 ≤ i ≤ m,1 ≤ j ≤ n) dinamakan matriks jarak terjumlahkan. Berikut ini adalah contoh matriks jarak terjumlahkan: 2 5 2 5 3



0 4 29 33 58 67



3 5 8 9 13 13



6 21 6 22 10 19



0 25 31 10 35 19



6 41 26 26 11 20



1 42 42 27 27 15



Gambar Ilustrasi matrik jarak terjumlahkan (cumulative distance matrix) antara 2 vektor. U={2,5,2,5,3}, V={0,3,6,0,6,1} Metode DTW sudah banyak digunakan untuk sistem pengenalan suara dan sistem pencocokkan tandatangan.