AtasoyWeb | Anasayfa | Arşiv | Dosya Deposu | Anketler | RSS Besleme | Tema Seçim Sayfası

Sık Kullanılanlara Ekle | Hakkında | İletişim

Gereksinimler:	Microsoft .Net Framework 3.5
İndirme Linki:	Tıklayınız

   Dinamik zaman bükme (dynamic time warping, DTW) algoritması, zamana bağımlı vektörlerin benzerlik ölçümünde kullanılan bir eşleştirme yöntemidir. Yöntemin kullanıldığı pekçok alan var. Örneğin ses tanıma sistemlerinin bir kısmında öznitelik vektörleri karşılaştırılırken bu yönteme sıkça başvurulur.

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ü ise iki vektörün elemanları arasındaki öklit uzaklıklarının toplamı bulunarak yapılır. Bu toplam, sıfıra ne kadar yakınsa vektörler birbirlerine o kadar benziyor demektir.

t=  0 1 2 3 4 5 6 7 8 9
v1= 3 7 9 1 6 2 1 7 0 0
v2= 3 0 7 9 1 6 2 1 7 0    Yukarıdaki örneği ele alalım. s1 ve s2, farklı zamanlarda örneklenmiş ses sinyalleri olsun. Zamana bağımlı kalındığında elemanlar t=9 anı hariç hiçbir t anında birbirlerine eşit değerlere sahip değildir. İkililer arasındaki öklit uzaklıklarının toplamı hesaplandığında bu iki vektörün birbirlerine benzemediği sonucu çıkarılır. Sonuç doğru değildir. Çünkü bu vektörler birbirlerine benzemektedir.

Zaman Bağımlılığını Ortadan Kaldırma
   Aynı örnekte, zaman bağımlılığı ortadan kaldırıldığında, yani her eleman, öklit 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 v2'nin t=2 anının, v1'in t=1 anına, v1'nin t=8 anının, v2'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 öklit uzaklıkları hesaplanır. İki değer arasındaki öklit 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 öklit 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]+EnKucugu(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 öklit 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...
Onaylı yorum bulunmuyor.

Atasoy Blog v3.0 © 2009-2012 Hüseyin Atasoy | Tema Tasarımı: Hüseyin Atasoy

AtasoyWeb Anasayfa | Yukarı Çık