Examkin

Soru

Zorluk: Çok zorWard Yöntemi

Bir araştırmacı, çok boyutlu sürekli değişkenlerden oluşan bir veri seti üzerinde yığılmalı (agglomerative) hiyerarşik kümeleme analizi yapmaktadır. Araştırmacı, analizinde hem Ward yöntemini hem de Merkezcil (Centroid) yöntemi uygulamış ve her iki yönteme ait dendrogramları karşılaştırmıştır. İnceleme sonucunda, Merkezcil yönteme ait dendrogramda bazı birleştirme adımlarında 'tersine dönme' (inversion / dendrogram dallarının aşağı doğru uzaması) problemi yaşandığını, Ward yönteminde ise birleşme uzaklıklarının her iterasyonda monoton olarak arttığını ve tersine dönme durumunun kesinlikle oluşmadığını gözlemlemiştir.

Bilindiği üzere, her iki yöntem de temel olarak kümelerin ağırlık merkezleri (centroid) üzerinden işlem yapmaktadır.

Buna göre, Ward yönteminde Merkezcil yöntemden farklı olarak tersine dönme (inversion) probleminin hiçbir zaman ortaya çıkmamasının temel matematiksel nedeni aşağıdakilerden hangisidir?

  1. Ward yönteminde birleşme uzaklığının, kümelerin ağırlık merkezleri arasındaki karesel mesafenin ninjni+nj\frac{n_i n_j}{n_i+n_j} katsayısıyla ağırlıklandırılarak hesaplanması ve bu sayede Lance-Williams güncelleme formülünde monotonluk koşullarının daima sağlanması.Cevap
  2. B
    Ward yönteminin, tek bağlantı (single linkage) yöntemine benzer şekilde kümeler arası uzaklığı uç noktalar üzerinden tanımlayarak zincirleme (chaining) etkisini işe koşması ve birleşme uzaklıklarının azalmasını her adımda engellemesi.
  3. C
    Ward yönteminin, hiyerarşik algoritmanın her adımında karesel Öklid uzaklığı yerine, değişkenlerin varyans-kovaryans yapısını ve korelasyonlarını dikkate alan Mahalanobis uzaklığını zorunlu olarak kullanıp grup içi homojenliği standartlaştırması.
  4. D
    Ward yönteminde algoritmanın, birleşme mesafesini dendrogram kesim noktasındaki optimum grup sayısına göre geriye dönük olarak ayarlayarak küme içi hata kareler toplamını (ESS) sürecin sonunda daima sıfıra eşitlemesi.
  5. E
    Ward yönteminin, her iterasyonda kümeler arası genel farklılığı test eden ve ayırım gücünü gösteren Wilks' Lambda istatistiğini sürekli olarak 1 değerine yaklaştırma prensibiyle çalışarak kümeleri homojenleştirmesi.

Cevap

Ward yönteminde Merkezcil yöntemden farklı olarak tersine dönme probleminin yaşanmamasının temel nedeni, uzaklık ölçüsünün ninjni+nj\frac{n_i n_j}{n_i+n_j} faktörü ile ağırlıklandırılarak Lance-Williams formülünde monotonluk koşulunu sağlamasıdır.
Hiyerarşik kümeleme algoritmalarında, birleşme uzaklıklarının her adımda büyümesi 'monotonluk' olarak adlandırılır. Merkezcil (Centroid) yöntemde iki küme birleşirken oluşan yeni ağırlık merkezinin konumu, Lance-Williams formülünde monotonluğu bozabilen (negatif beta katsayısı üreten) bir yapıya sahiptir ve bu da dendrogramda 'tersine dönme' (inversion) yaratır. Ward yöntemi de ağırlık merkezlerini kullanmasına rağmen, uzaklık fonksiyonu merkezler arası mesafeyi ninjni+nj\frac{n_i n_j}{n_i+n_j} faktörü ile (hata kareler toplamındaki artış formunda) ağırlıklandırır. Bu faktör, algoritmanın matematiksel olarak Lance-Williams monotonluk koşulunu (αi+αj+β≥1\alpha_i + \alpha_j + \beta \geq 1) her iterasyonda kusursuz olarak sağlamasını garanti eder.

Adım Adım Çözüm

1
Tersine dönme (inversion) probleminin hiyerarşik kümeleme algoritmalarındaki matematiksel karşılığını tanımlamak.
Tersine dönme (inversion), Lance-Williams birleştirme formülünde birleşme mesafesinin önceki adımdan daha küçük çıkması, yani monotonluğun bozulması durumudur.
Merkezcil yöntemde bu problemin neden yaşandığını ve Ward yönteminde neden engellendiğini karşılaştırmak için temel teorik altyapıyı kurmak.
2
Merkezcil (Centroid) yöntemin uzaklık fonksiyonunu ve monotonluk ihlalini değerlendirmek.
Merkezcil yöntem, birleşme uzaklığını doğrudan ağırlık merkezleri arası Öklid uzaklığı olarak tanımlar. Lance-Williams formülündeki β\beta katsayısının negatif ve mutlak değerce büyük olabilmesi nedeniyle formül monotonluk koşulunu (αi+αj+β≥1\alpha_i + \alpha_j + \beta \geq 1) her zaman sağlamaz.
Tersine dönmenin asıl kaynağını tespit etmek.
3
Ward yönteminin uzaklık fonksiyonunu ve Lance-Williams katsayılarını incelemek.
Ward yöntemi, iki küme arasındaki mesafeyi doğrudan merkezler arası uzaklık olarak değil, ninjni+nj∣∣xˉi−xˉj∣∣2\frac{n_i n_j}{n_i+n_j} ||\bar{x}_i - \bar{x}_j||^2 şeklinde eleman sayılarıyla ağırlıklandırarak (Grup İçi Hata Kareler Toplamındaki artış olarak) hesaplar.
Ağırlıklandırma faktörünün yöntemin matematiksel işleyişine olan etkisini belirlemek.
4
Ward yöntemindeki ağırlıklandırmanın Lance-Williams formülüne etkisini bağlamak.
Eleman sayılarına dayalı bu spesifik ağırlıklandırma, Lance-Williams güncelleme formülündeki parametrelerin toplamının monotonluk şartını daima güvence altına almasına neden olur ve inversion problemini kesin olarak ortadan kaldırır.
Soruda istenen temel matematiksel kanıtı sonuçlandırmak.

Anahtar Kavram

Ward Yönteminde Monotonluk ve Lance-Williams Formülü
Tahmini Süre:2m 30s
Bu soruyu puanla

Konular

Ward Yöntemi

Bu konudan daha fazla soru