07.01. Kümeleme Algoritmaları: k-means Algoritması

Bu yazımda gözetimsiz öğrenme algoritmalarından bir kümeleme algoritması olan k-means (k-ortalama) algoritmasını bir örnek ile anlatmaya çalışacağım. k-means verilen bir veri seti üzerinden belirli sayıda kümeyi (k adet) gruplamak için geliştirilmiş en sade ve basit algoritmadır. Bu yazımda bu algoritmayı bir sayısal örnek üzerinden anlatmaya çalışacağım. Bu yöntemin adımları:

  1. Nesneleri al, küme sayısını belirle ve başlangıç kitle merkezlerini (centroid) belirle. 
  2. Her nesneyi en uygun gruba ata ve her atama işleminden sonra atama yapılan k kitle merkezini hesapla.
  3. Yeni oluşan grubu geçmişteki grup ile kıyasla. Grupta değişim yok ise algoritmayı bitir, aksi takdirde adım 2’ye geri dön.
Öncelikle belirtmek isterim ki bu algoritmayı ve bir çoğunu anlatan “Şadi Evren Şeker” hocamız hem bir blog yazısı ile hemde video ile bu konuyu süper bir şekilde anlatmış. Ben sadece sayısal bir örnek üzerinden konunun daha iyi anlaşılması ve özellikle k-means algoritması kendi programla dilleri ile kodlamak isteyen arkadaşlar için sayısal bir örnek üzerinden anlatmayı deneyeceğim.
 
Adım 1: Başlangıç değerleri belirleyelim. k değerimiz 2 olsun, başka bir deyişle küme sayımız 2 tane olsun. 2 kümemiz olduğu için iki tane kitle merkezi (centroid) belirlememiz gerekiyor. Bu noktada bir çok çözüm var. Örneğin ilk iki nesne centroid olarak alınabilir veya her nokta arasındaki mesafeler hesaplanır ve en uzak mesafe iki nesne centroid olarak seçilebilir. Ben en uzak mesafeli olan iki noktayı seçiyorum.
 

Peki mesafe hesabını nasıl yapacağız. Öklid uzaklığı (Euclidean distance) aynı koordinatlar arasındaki farkların karelerinin toplamının kare köküdür.

{\begin{aligned}\mathrm {d} (\mathbf {p} ,\mathbf {q} )=\mathrm {d} (\mathbf {q} ,\mathbf {p} )&={\sqrt {(q_{1}-p_{1})^{2}+(q_{2}-p_{2})^{2}+\cdots +(q_{n}-p_{n})^{2}}}\\[8pt]&={\sqrt {\sum _{i=1}^{n}(q_{i}-p_{i})^{2}}}.\end{aligned}}
wikipedia
Bende x ve y koordinatları olduğu için iki boyutta bir hesaplama yapacağım. Tüm hesaplamalarımı excel ile yaptım ve excel dosyasını yazının sonuna ekledim. Örneğin Nesne 1 ile Nesne 2 arasındaki uzaklığı hesaplayalım.
KareKök((1-1.5))^2+ (1-2))^2) = 1.118
Tüm nesneler arasındaki uzaklığı hesapladıktan sonra en uzak iki nesneyi seçtim. Seçim sonucunu grafiksel olarak ta verilerin yanında görüyoruz.
Adım 2: Her nesneyi en uygun gruba ata ve her atama işleminden sonra atama yapılan k kitle merkezini hesapla.
İterasyon 1
 
Nesne 1 ve Nesne 4 centroid olarak belirlendikleri için direkt gruplarına eklenirler. Nesneler için tekrar oklid uzaklıkları hesaplanır. Ancak oklid uzaklığı hesaplanırken her seferinde yeni Centroid noktaları da hesaplanır. Yeni centroid noktası hesaplanırken küme elemanlarının aynı koordinatlarının değerleri toplamı bölü nesne sayısı şeklinde hesaplanmıştır. Örneğin Nesne 2 için birinci centroid’e uzaklı 1.118 iken ikinci centroid’e uzaklık 6.103’tür. Kazanan centroid birdir. Yeni centroid noktası X için (1+1.5)/2 = 1.250 ve Y için (1+2)/2 = 1.5′ tur. Küme içindeki eleman sayısı arttırkça bölen sayısını arttırmayı unutmayın 🙂 Şimdi oluşan gruplara bir de grafiksel bakalım.

Tüm nesneler için işlemler yapıldıktan sonra gruplar ve yeni centroid değerleri de ortaya çıkmıştır.
 
Adım 3’teki kıyasla işlemi yapabilmek için tek iterasyonla işlem bitirilmez. İkinci iterasyonla tekrar bir grupları oluşturalım. Bunun için bir önceki iterasyonun centroid değerlerini alıyoruz. Tüm nesneler için tekrar grup belirleme işlemi yapıyoruz. 
İterasyon 2
Grafik üzerinde görsel olarak sonuçları görelim.
İki iterasyonun son bölümünde oluşan grupları kıyasladığımızda bir farklılık olduğunu görürüz. 3 nolu nesne ikinci kümeye girmeye karar vermiş. Bu durumda tekrar adım 2’ye döneriz. 
Adım 3:  Yeni oluşan grubu geçmişteki grup ile kıyasla. Grupta değişim yok ise algoritmayı bitir, aksi takdirde adım 2’ye geri dön (1 defa adım 2’ye döndük).
3. iterasyon sonunda gruplarda değişim olmaz. Bu durumda algoritma sonladırılır. En son oluşan centroid değerleri küme 1 için (1.3, 1.5) iken küme 2 için (3.9, 5.1)’dir.