Dinamik Zaman Bükmesi (DTW)

Dynamic Time Warping nedir?

Dynamic Time Warping (DTW), iki zaman serisi arasındaki benzerliği, bu seriler farklı hızda, uzunlukta veya farklı zamanlarda gerçekleşmiş olsa bile ölçen bir yöntem. Aynı kelimeyi biri yavaş biri hızlı söyleyen iki kişiyi düşün: ses dalgaları zaman ekseninde kaymıştır ama şekil aynıdır. DTW tam olarak bu tür "şekli benzer ama zamanlaması farklı" durumları yakalamak için tasarlandı.

Nasıl çalışır?

Klasik nokta-nokta mesafe (ör. Öklid mesafesi •iki nokta arasındaki düz çizgi uzaklığı•) T anındaki değeri yalnızca diğer serinin T anındaki değeriyle karşılaştırır. Seriler faz kaymışsa bu yöntem, şekiller birebir örtüşse bile yüksek fark üretir. DTW ise bir noktayı diğer serinin komşu noktalarıyla da (T+1, T−1 ...) eşleştirmeye izin vererek esnek bir hizalama kurar.

Yöntem bir maliyet matrisi üzerine kurulur. Matristeki her hücre, iki serinin o konumdaki yerel farkı ile komşu hücrelerin birikmiş en küçük maliyetini toplar — bu bir dynamic programming •büyük problemi küçük alt problemlere bölüp çözümleri biriktiren teknik• özyinelemesidir:

M(i, j) = |P(i) − Q(j)| + min( M(i−1, j−1), M(i, j−1), M(i−1, j) )

Matris dolduktan sonra en düşük maliyetli yol (warping path) izlenir. Bu yol üç kurala uyar: başlangıç ve bitiş köşeleri sabittir (boundary), yol geri gitmez (monotonicity) ve hücre atlamaz (continuity). Yol üzerindeki toplam maliyet, iki serinin DTW mesafesidir.

Neden önemli?

DTW, farklı uzunluktaki serileri hizalayabildiği ve zaman kaymasına, tempo farkına dayanıklı olduğu için basit mesafe ölçütlerinin başarısız olduğu yerde iş görür. Böylece benzerlik skoru zamanlamadan çok şekli yansıtır. Bedeli hesap maliyetidir: temel algoritma iki serinin uzunluklarının çarpımı kadar (O(M·N)) zaman ve bellek ister; FastDTW gibi hızlandırılmış türevleri bu yükü azaltmak için geliştirildi.

Kullanım alanları

Konuşma tanıma ve ses doğrulama DTW'nin en klasik alanıdır. Bunun yanında jest ve imza tanıma, zaman serisi sınıflandırma, finansal seri karşılaştırma, giyilebilir cihazlardan sinyal analizi (ör. kalp atışı) ve biyoinformatik yaygın kullanım örnekleri. Tekrarlayan bir sinyaldeki faz kaymasını tespit etmek için de kullanılır.