Examkin

Soru

Zorluk: Çok zorTek Bağlantı (En Yakın Komşu) Yöntemi

Aşağıda 5 farklı gözlem birimi (A, B, C, D, E) için hesaplanmış Öklid uzaklık matrisi verilmiştir:

[026109205986504510940398530] \begin{bmatrix} 0 & 2 & 6 & 10 & 9 \\ 2 & 0 & 5 & 9 & 8 \\ 6 & 5 & 0 & 4 & 5 \\ 10 & 9 & 4 & 0 & 3 \\ 9 & 8 & 5 & 3 & 0 \end{bmatrix}

(Matris simetrik olup, satır ve sütunlar sırasıyla A, B, C, D ve E gözlemlerini temsil etmektedir.)

Bu veri seti üzerinde tek bağlantı (en yakın komşu - single linkage) yöntemi kullanılarak hiyerarşik kümeleme analizi yapıldığında, tüm gözlemlerin tek bir küme altında toplandığı son adımda (iki ana kümenin birleştiği adım) hesaplanan birleşme uzaklığı kaçtır ve bu algoritmanın doğasından kaynaklanan, literatürde sıkça eleştirilen temel yapısal sorun aşağıdakilerden hangisinde doğru verilmiştir?

  1. Son birleşme uzaklığı 5'tir; temel sorun kümelerin zincirleme (chaining) eğilimi göstererek ipliksi bir yapıya uzamasıdır.Cevap
  2. B
    Son birleşme uzaklığı 10'dur; temel sorun kümelerin zincirleme (chaining) eğilimi göstererek ipliksi bir yapıya uzamasıdır.
  3. C
    Son birleşme uzaklığı 5'tir; temel sorun kümelerin her zaman küresel (spherical) bir yapıya zorlanmasıdır.
  4. D
    Son birleşme uzaklığı 8'dir; temel sorun merkezî eğilimlerin (ortalama) kullanılması nedeniyle uç değerlere aşırı duyarlılık oluşmasıdır.
  5. E
    Son birleşme uzaklığı 10'dur; temel sorun kümelerin her zaman küresel (spherical) bir yapıya zorlanmasıdır.

Cevap

Son birleşme uzaklığı 5'tir ve yöntemin temel sorunu kümelerin zincirleme (chaining) eğilimi göstermesidir.
Verilen uzaklık matrisinde adım adım tek bağlantı yöntemi uygulandığında; önce (A,B) 2'de, sonra (D,E) 3'te, ardından C ve (D,E) 4'te birleşir. Son aşamada (A,B) kümesi ile (C,D,E) kümesi arasındaki minimum uzaklık B ve C arasındaki 5 birimlik mesafe üzerinden gerçekleşir. Bu algoritmanın karakteristik dezavantajı kümelerin köprü noktalarla 'zincirleme' şeklinde uzamasıdır.

Adım Adım Çözüm

1
Matristeki en küçük uzaklık tespit edilerek ilk küme oluşturulur.
Sıfır dışındaki en küçük uzaklık d(A,B)=2d(A,B) = 2'dir. A ve B birleştirilerek (A,B) kümesi oluşturulur.
Hiyerarşik kümelemede her zaman birbirine en yakın iki eleman veya küme ilk önce birleştirilir.
2
Kalan öğeler arasındaki en küçük uzaklık tespit edilir ve yeni birleştirme yapılır.
d(D,E)=3d(D,E) = 3 olduğundan D ve E gözlemleri birleştirilerek (D,E) kümesi oluşturulur.
Sıradaki en küçük mesafe 3'tür ve (A,B) kümesinden bağımsızdır.
3
Aktif kümeler olan (A,B), C ve (D,E) arasındaki tek bağlantı (minimum) uzaklıkları hesaplanır.
C ile (D,E) arasındaki uzaklık min⁡(d(C,D),d(C,E))=min⁡(4,5)=4\min(d(C,D), d(C,E)) = \min(4,5) = 4'tür. C, (D,E) ile birleşerek (C,D,E) kümesini oluşturur.
Diğer alternatif mesafe olan C ile (A,B) arası min⁡(6,5)=5\min(6,5) = 5'tir. 4 < 5 olduğu için C, (D,E) kümesine katılır.
4
Kalan iki ana küme olan (A,B) ve (C,D,E) arasındaki en kısa uzaklık hesaplanarak son birleştirme yapılır.
Tüm kombinasyonlar içerisindeki en küçük değer d(B,C)=5d(B,C) = 5'tir. İki ana küme 5 uzaklık seviyesinde birleşir.
Tek bağlantı yönteminde iki küme arasındaki mesafe, birbirlerine en yakın iki elemanlarının mesafesi olarak tanımlanır.
5
Tek bağlantı algoritmasının literatürde eleştirilen temel yapısal sorunu tanımlanır.
Bu algoritma kümeleri yalnızca birer köprü (en yakın eleman) üzerinden birleştirdiği için, uzamsal olarak kümeler ipliksi bir yapıya bürünerek uzar. Buna 'zincirleme (chaining) etkisi' denir.
Bu durum, birbirine hiç benzemeyen iki ucun sırf aralarında bir köprü var diye aynı kümede yer almasına sebep olur.

Anahtar Kavram

Tek Bağlantı Yönteminde Uzaklık Hesaplama ve Zincirleme Etkisi
Tahmini Süre:2m 30s
Bu soruyu puanla

Konular

Tek Bağlantı (En Yakın Komşu) Yöntemi

Bu konudan daha fazla soru