leadership-training

Yığınsal (Agglomerative) Kümeleme – #4

Yığınsal (Agglomeratıve) Kümeleme Algorİtması

Hiyerarşik kümelemede yukarıdan aşağıya doğru önceden belirlenmiş sıraya sahip kümeler oluşturulur. Agglomerative Clustering ‘de bunun bir türüdür. K-Means’ten farkı, kaç küme oluşturulacağı belirtilmez. Başlangıçta bütün örnekler (samples) birer küme olarak kabul edilir. Daha sonra her bir küme kendisine en yakın diğer bir küme ile birleşir. En sonunda ortaya dendrogram şeması ve tek bir küme çıkar. Dendrogram, kümeler arasındaki hiyerarşik yapıyı göstermek için kullanılan ağaç şemasıdır. Dendrogram şemesı yorumlanarak, kaç tane küme oluşturulacağı belirlenir.

  1. Her bir öğeyi kendi kümesine ata. (N örnek, N küme)
  2. Birbirine en yakın kümeleri bul ve bunları tek bir kümeye birleştir.
  3. Yeni küme ile eski kümelerin her biri arasındaki uzaklıkları hesapla.
  4. Tüm öğeler tek bir küme halinde kümeleninceye kadar 2. ve 3. adımları tekrarla.

Aşağıdaki görselde algoritmanın çalışma prensibini şekil üzerinden anlatmaya çalıştım.

agglomerative

 

1- İlk olarak  A ve B kümelendi.

(A,B)

 

 

2- E ve F kümelendi.

  (E,F)

3- D, EF kümesine en yakın küme olduğundan Bu 2 küme, kümelendi.

 (D,(E,F))

4- C, DEF’ ye yakın olduğundan bunlar kümelendi.

(C, (D,(E,F)))

5- Bütün kümeler tek bir kümede toplandı. DENDROGRAM ‘ımız oluştu.

((A,B),(C, (D,(E,F))))

 

Dendrogram Yorumlama:

En uzun bacaktan çizilen yatay bir çizgi yardımıyla kaç küme oluşacağı tahmin edilebilir.

dendrogram-min

Fakat kümeleme işlemi yapılmadan önce, mesafe fonksiyonunu kullanarak her bir nokta arasındaki mesafeyi içeren yakınlık matrisini belirlemeniz gerekir. Daha sonra matris, her küme arasındaki mesafeyi  göstermek için güncellenir. Mesafe Euclidean ve Manhattan formulleriyle bulunur. Metric türüne göre kullanılan formul değişir. Mesela Text için genellikle Hamming Distance kullanılır. Mesafe hesaplama formullerine ek olarak Agglomerative algoritmasında mesafe hesaplamak için birçok method vardır. Dendrogram oluşturmada da kullanılırlar. En spesifikler;

agglomerative_linkage

 

1- Single Linkage: 

2 küme arasındaki en yakın mesafeyi hesaplar.

 

 

2- Complete Linkage:

2 küme arasındaki en uzak mesafeyi hesaplar.

 

 

3-Average Linkage:

2 küme arasındaki ortalama mesafeyi hesaplar.

 

 

 

Bunların dışında ward, weighted, centroid ve median methodu mevcuttur. Bknz.

Seçilen method ve mesafe hesaplama formulü sonucuda etkiler. Kullanılan yöntemlerin sonucu nasıl etkilediğini buradan test edebilirsiniz.

Python ile uygulaması:

Iris Dataset’i Agglomerative Clustering  ile kümelere ayırma

Kaynaklar:

1-http://www.analytictech.com/networks/hiclus.htm

2-http://www.saedsayad.com/clustering_hierarchical.htm

56 Paylaşımlar

Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir