Dinamik Zaman Bükme Algoritması

Dinamik zaman bükme (dynamic time warping, DTW) algoritması, zaman serilerinin benzerlik ölçümünde kullanılan bir eşleştirme yöntemidir. Yöntemin farklı farklı kullanım alanları var. Örneğin bir sesten sözcük tanıma sisteminde öznitelik vektörleri karşılaştırılırken bu yönteme başvurulabilir.

Zaman Serileri Ve Benzerlik Ölçümleri

Zaman serileri, değerleri zamana bağlı olan elemanlardan oluşan sayı dizileri olarak düşünülebilir. Örneğin belli bir zaman dilimi boyunca örneklenmiş ses sinyali, bir zaman serisi oluşturur. Bu tür serilerin, zamana bağımlı katı yöntemler ile eşleştirilmesi mümkün değildir.

Benzerlik ölçümü iki serinin elemanları arasındaki öklid uzaklıklarının toplamı bulunarak yapılabilir. Bu toplam, sıfıra ne kadar yakınsa seriler birbirlerine o kadar benziyor demektir.

t  = 0 1 2 3 4 5 6 7 8 9
s1 = 3 7 9 1 6 2 1 7 0 0
s2 = 3 0 7 9 1 6 2 1 7 0

Yukarıdaki örneği ele alalım. s1 ve s2 farklı zamanlarda örneklenmiş iki sinyal olsun. Zamana bağımlı kalındığında elemanlar t=0 anı hariç hiçbir t anında birbirlerine eşit değerlere sahip değildir. İkililer arasındaki öklid uzaklıklarının toplamı hesaplandığında bu iki serinin birbirine benzemediği sonucu çıkarılabilir. Sonuç doğru değildir. Çünkü s2 serisi 1 birim gecikmeyle diğer serinin elemanlarını tekrar etmektedir.

Zaman Bağımlılığını Ortadan Kaldırma

Aynı örnekte, zaman bağımlılığı ortadan kaldırıldığında, yani her eleman, öklid uzaklıkları dikkate alınarak kendisine en yakın eleman ile eşleştirildiğinde tüm elemanlar için en uygun eşler bulunabilir. Eşleştirme sonunda s2'nin t=2 anının, s1'in t=1 anına, s1'nin t=8 anının, s2'nin t=9 anına kaymış veya 'bükülmüş' olduğu gözlenir. (Yöntem, ismini işte bu bükülmelerden alıyor. Yukarıda ekran görüntüsü bulunan program yardımıyla bükülmeler daha iyi gözlemlenebilir.)

Dinamik Zaman Bükme (Dynamic Time Warping, DTW) Algoritması

Bu yöntem yukarıda bahsettiğimiz zaman bağımlılığı sorununu gidermeyi amaçlar. Vektörlerin birbirlerine en yakın elemanları eşleştirilerek, uzaklıklar toplamının olabilecek en küçük değerde tutulması sağlanır. Bu yöntem ile farklı boyutlardaki vektörler için de benzerlik ölçümü yapılabilabilir.

Algoritma koda dökülürken öncelikle kümülatif öklid uzaklıkları hesaplanır. Tek boyutta iki değer arasındaki öklid uzaklığı, bu iki değerin farkının karesinin karekökü, yani aslında farkının mutlak değeri alınarak bulunur. Kümülatif uzaklık, bir elemanın eşine olan uzaklığı ile kendisinden önce eşleşen elemanların tümünün eşlerine olan uzaklıklarının toplamıdır. Kümülatif uzaklık hesaplanırken, her bir eleman çifti arasında hesaplanan öklid uzaklığına, bu elemanlardan bir birim gerideki eleman çiftleri için hesaplanan kümülatif uzaklıkların en küçüğü eklenir. Böylece eşleşen son elemanlara varıldığında, hesaplanan son kümülatif uzaklık değeri olabilecek en küçük değerinde olur.

Kumulatif[i][j]=Uzaklik[i][j]+EnKucuk(Kumulatif[i-1][j],Kumulatif[i][j-1],Kumulatif[i-1][j-1])

Burada Kumulatif[i][j], birinci vektörün i. elemanı ile ikinci vektörün j. elemanının kümülatif uzaklığı, Uzaklık[i][j] ise bu iki eleman arasındaki öklid uzaklığıdır. (Kumulatif[0][0]=0 alınır.) Sırasıyla m ve n boyutlu v1 ve v2 vektörleri için Kumulatif[m][n] değeri, benzerlik hakkında yorum yapılabilmesini sağlar. Bu değer dinamik zaman bükme algoritmasının sonucudur. Karşılaştırılan vektörlerin benzerlikleri, sonucun sıfıra yakınlığı ile doğru orantılıdır.

Zaman Kaymasını Sınırlama Ve Süreci Hızlandırma

Algoritma, olası her eşleşme için kümülatif uzaklıkları hesaplar. Ancak hesaplanan değerlerin sadece bir kısmı kullanılır. Sonuca varma süresini hızlandırmak amacıyla her bir eleman ile bu elemana zaman değeri bakımından yakın sadece belli sayıda elemanın kümülatif uzaklığı hesaplanabilir. Örneğin birinci vektöre ait t=20 anındaki eleman, ikinci vektöre ait sadece t=[15,25] aralığındaki elemanlar ile karşılaştırılabilir. Böylece zaman kayması +-5 birim ile sınırlandırılırken sonuca ulaşma süresi de kısaltılmış olur. Ancak, kaymayı sınırlamanın, en kısa kümülatif uzaklığın bulunmasına engel olmamasına dikkat edilmelidir. Ayrıca kayma aralığı daraltıldıkça algoritmanın eşleştirme esnekliği azalır.

Kümülatif Uzaklık Tablosu ve Bükme Fonksiyonu (Warping Function)

Vektörlere ait elemanların olası tüm eşleşmelerinin kümülatif uzaklıkları, kümülatif uzaklık tabosunu, bu tabloda sadece eşleşen elemanların kümülatif uzaklıkları da bükme fonksiyonunu oluşturur. Bu fonksiyonun grafiğine bakılarak da vektörlerin birbirlerine benzerlikleri konusunda yorum yapılabilir. İki vektörün düzgün bir biçimde eşleştirilmesini sağlayabilecek iyi bir bükme fonksiyonu şu özelliklere sahip olmalıdır:

• Bükme fonksiyonu artan fonksiyon olmalıdır; eşleştirme anında zaman ekseninde geri gidilmemelidir.
• Bükme fonksiyonu (0,0) noktasından başlayıp (m,n) noktasında sonlanmalıdır. Aksi halde bir vektörün, diğer vektörün sadece bir kısmı ile eşleştirildiği anlaşılır.
• Bükme fonksiyonu (0,0) ile (m,n) arasında çizgisellikten ne kadar uzaksa, karşılaştırılan iki vektör de birbirine o kadar uzaktır.
• Bükme fonksiyonunun belli bölgelerde dikey veya düşey ilerleyişi, az sayıda elemanın çok sayıda elemanla eşleştiği anlamına gelir.
• Bükme fonksiyonu sürekli bir fonksiyon olmalıdır; zaman eksenlerinde ilerlenirken belli değerlerde sıçramalara rastlanmamalıdır.

Dinamik Zaman Bükme Algoritması Program Örneği

Sayfanın başında ekran görüntüsü bulunan programda, algoritamanın işleyişinin anlaşılabilirliğine katkı sağlayacağını umarak, adımları ve sonuçları elimden geldiği kadar görselleştirmeye çalıştım. Program, girilen iki vektörün elemanlarını DTW ile eşleştirir, bu vektörleri ve eşleşmeleri grafiğe yansıtır. Ayrıca uzaklık tablosunu hazırlayıp eşleşen elemanların kümülatif uzaklıklarını tablo üzerinde mavi renk ile işaretleyerek bükme fonksiyonunu görselleştirir.

Programda, her vektörün en az 2 elemana sahip olması gerekir ve her bir eleman 0 ile 100 arasında bir tamsayı olmalıdır. Vektörler farklı boyutlarda olabilir. Boyut farkı arttıkça bükme fonksiyonunun sahip olması gereken özelliklerden uzaklaştığı ve eşleştirmenin kötüleştiği gözlenebilir...

Leave Comment

Comments