Python - Hiyerarşik Kümeleme

Bir veriyi kümelere ayırmak basit olarak birbirine benzer olan elemanları aynı grupta toplama işlemidir (Neye göre benzer bu önemli!). Kümelere ayırma işlemi için kullanılan en yaygın ve basit algoritma k-means algoritmasıdır. Bu algoritma girdi olarak belirtilen (k) adet küme için farklı merkez koordinatlar seçerek, bir iterasyon dahilinde ilgili kümeye en yakın elemanların eklenmesi suretiyle küme merkezlerinin yerleri değişmeyene kadar tüm elemanların bir kümeye atanması mantığına göre çalışır. Bu yöntemde (k) küme sayısının baştan belirlenmesi gerekmektedir. Fakat çeşitli uygulamalarda veriler gruplara ayrılırken birbirlerine benzer olan kaç küme olduğu/olabileceği her zaman bilinemeyebilir. Bu gibi durumlarda hiyerarşik kümelemeyi kullanmak daha mantıklı olacaktır. 

Hiyerarşik kümelemede iki farklı yaklaşım kullanılabilir. Bunlar; tüm elemanlar tek bir küme gibi düşünülüp kümeleri ayırarak farklı kümeler oluşturmak veya her bir elemanı başlangıçta bir küme kabul edip birbirlerine benzer olan kümeleri tek bir küme altında toplamaktır. Python kullanarak gerçekleştireceğimiz uygulamada ikinci yaklaşımı kullanılmıştır. Zaten her iki yaklaşım da sonuç olarak aynı kapıya çıkacaktır.

Hiyerarşik kümeleme için ilk olarak veri setini oluşturan her bir elemanın ( herhangi bir bilgiyi içeren vektör olabilir, görüntü olabilir ...vs ) birbirleri arasındaki benzerliği/mesafeyi ölçmek ve bunu bir matriste saklamak gerekmektedir. Örneğin; N adet veriyi kümelere ayırmak istediğimizde, bu işlem sonucunda NxN lik bir distance_matrix elde etmiş olacağız. Verilerin birbirleri arasındaki benzerliği ölçmek için birçok metrik kullanılabilir, bu verinin içeriğine ve yapılacak olan uygulamaya göre değişkenlik gösterebilir. Bu ilk aşamadan yani distance_matrix i oluşturduktan sonra yapılacak iş birbirine benzer iki eleman tek bir küme oluşturacak şekilde tüm elemanları bir eleman ile eşleştirip yeni kümeler oluşturmak ve oluşan bu kümelerin de birbirleri arasındaki mesafeleri hesaplayıp tekrar yeni bir distance matrix oluşturmaktır. Bu işlem tekrarlanarak tüm elemanlar tek bir küme altında toplanana dek devam edildiğinde, bir ağaç yapısı şeklinde birbirine benzer elemanlar bir kümede toplanmış olacaktır. Bu işlem yapılırken önemli olan birleştirilen kümelerin birbirlerine olan uzaklıklarını hesaplamaktır. Bunun için çeşitli yöntemler bulunmaktadır ve bunlar linkage strategies olarak isimlendirilir. Seçilecek herhangi bir stratejiye göre hiyerarşik kümeleme yapıldığında birbirinden farklı ağaç yapıları oluşabilir. Kullanılabilecek bazı birleştirme stratejileri şunlardır;

Örneğin; Single stratejisinde her iki küme içerisinden birbirlerine en yakın elemanların arasındaki uzaklık kümeler arasındaki uzaklık olarak kabul edilir, Average stratejisinde ise her iki küme içerisindeki tüm elemanların birbirleri ile olan uzaklıklarının ortalaması alınır. Ayrıntılı bilgilere şuradan ulaşılabilir ( python linkage strategies  )

-> d sayıda veriden(sütun) oluşan data matrisinin sütunlarındaki verileri hiyerarşik kümeleme ile gruplara ayıracak olursak;

Benzerlik kriteri olarak Normalized Mutual Information (NMI) kullanıyoruz, NMI Entropi ile aşağıdaki formülde verildiği gibi hesaplanır. ( Entropi için bakınız. )

NMI ölçütüne göre her bir elemanın birbiri ile benzerliği ölçülüp distance_matrix oluşturuluyor.

from sklearn.metrics.cluster import normalized_mutual_info_score d = data.shape[1] distance_matrix = np.zeros((d,d),dtype=np.float) for i in range(d): for j in range(d): distance_matrix[i,j] = normalized_mutual_info_score(data[:,i], data[:,j])


Daha sonra ise seçilen birleştirme yöntemine göre linkage_matrix(birleştirilen kümeler ile ilgili bilgiyi tutar)  oluşturulup, oluşan ağaç yapısı ekrana çizdiriliyor.


#linkage_matrix = linkage(distance_matrix, method='average') linkage_matrix = linkage(distance_matrix, method='ward') # draw full dendrogram plt.figure(figsize=(25, 10)) plt.title('Hierarchical Clustering Dendrogram') plt.xlabel('sample index') plt.ylabel('distance') dendogram = scipy.cluster.hierarchy.dendrogram( linkage_matrix, leaf_rotation=90., # rotates the x axis labels leaf_font_size=8., # font size for the x axis labels ) plt.show()

Örnek bir veri setinin hiyerarşik kümeleme sonucu oluşturulmuş ağaç yapısı aşağıda verilmiştir. Hiyerarşik kümelemede k-means algoritmasının aksine kaç adet küme oluşturulacağı bilgisi girilmek zorunda değildir. Oluşan ağaç yapısı ile birbirlerine benzer olan kaç farklı grubun olduğu ve oluşan bu grupların yine birbirlerine ne kadar yakın olduğu bilgisi elde edilebilir. Dikey eksen, kümeler arasındaki mesafeyi ifade etmektedir. Buna göre; ağaç yapısı oluşturulduktan sonra, kümeler arasındaki mesafelere bakılarak istenilen sayıda farklı küme elde elde edilebilir.