K-Means Algoritmasının temel mantığı

Bu yazıda K-Means algoritmasını çok basit bir şekilde, siz okuyucuları matematik formüllerine boğmadan anlatmaya çalışacağım. Algoritmanın kodlanma kısmına değinmeyeceğim, çünkü bu konuda zaten internetten yeterince kaynak bulabilirsiniz. Ama eğer matematik bilginiz yeterli düzeyde değilse konunun mantığını araştırdığınız zaman karşınıza çıkan o formüller, terimler biraz korkutucu gelebilir. Hiç merak etmeyin bu yazıda ne o korkutucu formüller ne de anlamadığınız terimler kullanılmayacaktır. Hesaplama kısmına geçmeden önce K-MEANS algoritması hakkında çok kısa, yüzeysel bir bilgi vermek iyi olur. İşe algoritmanın ismiyle başlayalım. Algoritma kümeleme (Cluster)  algoritmasıdır ve burada k bir sayı anlamına geliyor ve küme sayısı için kullanılıyor. Means ise ortalamalar anlamına geliyor. Yani biz eğer elimizdeki veriyi 5 kümeye böleceksek, 5 kümeli ortalamalar algoritması veya 5-Means algoritması diye biliriz. Kümeleme algoritmaları içerisinde en çok kullanılan algoritmalardan biridir. Özellikle müşteri segmentasyonu, belge sınıflandırılması, dolandırıcılık tespiti gibi konularda işe yarar çıktılar vere biliyor. Algoritma temel olarak elimizdeki veriyi alır ve veriler arasındaki uzaklıklara göre onları gruplamaya çalışır. Az önce söylediğim gibi konunun teorik bilgilerine çok rahatlıkla internette ulaşa bilirsiniz o yüzden teorik bilgi kısmını uzatmadan algoritmanın nasıl çalıştığına bakalım. Bunun için öncelikle kendimizden rastgele bir veri uyduralım. X ve Y değişkenlerinden ibaret 10 adet (x,y) sayıları yazalım. (5,8); (7,4); (8,11); (10,15); (12,16);  (1,8); (2,10); (3,6); (4,9); (8,13). Öncelikle yapacağımız ilk şey kaç kümeye bölmek istediğimizi belirlemektir. Bunun için bir çok yöntem var ama onlara değinerek kafanızın karışmasını istemiyorum. Belki başka yazılarda onlar hakkında da bilgiler vere bilirim. Yöntemlerden en yaygını elbow yöntemidir. Arama motorlarına elbow yöntemi yazarsanız türkçe olarak da birçok kaynak mevcuttur. Biz şimdi bu konuya değinmeden bunlardan birini kullanarak küme sayımızı 3 seçtiğimizi varsayalım. Algoritma küme sayı belirlendikten sonra o kadar merkez bulur. Yani 3 küme derseniz 3, n küme derseniz n tane merkez nokta seçer. Ve bu noktaları ayrılan kümelerin merkezi yapana kadar bir işlem gerçekleştirir. Ne dediğimi birazdan çok daha iyi anlayacaksınız. Öncelikle 3 tane merkez noktası olarak (2,10), (10,15) ve (7,4) olarak seçildiğini varsayalım. (Bu işlem otomatik olarak gerçekleştirilir. K-Means algoritmasının en büyük dezavantajıdır). Daha sonra her noktanın o noktalara uzaklığını hesaplayalım. Kolaylık olsun diye ben Manhattan uzaklık yöntemini kullanacağım. Ama siz Oklid de kullana bilirsiniz, sonuç değişmez.

Birinci noktamızın ilk merkez (2,10) noktasına uzaklığı = (|5-2|)+(|8-10|)=5. Birinci noktamızın ikinci merkez (10,15) noktasına uzaklığı=(|5-10|)+(|8-15|)=13. Birinci noktamızın üçüncü merkez (7,4) noktasına uzaklığı=(|5-7|)+(|4-4|)=2

Bu işlem her bir nokta için tek tek yapılır. Ve Manhattan uzaklığına göre en küçük değer alan nokta o kümeye eklenir. Daha iyi görünmesi ve anlaşılması için bunları bir tabloda yerleştirelim.

Burada yaptığımız şey her noktanın seçilen merkez noktalarına göre uzaklığını ölçmek ve küçük çıkan değerleri ilgili kümeye eklemekti. Mesela (1,8) noktası neden birinci kümeye eklendi diye soracak olursak o noktanın her merkez noktasına uzaklığı hesaplandı. Daha sonra çıkan değerler 3,16,10 oldu. Bu değerler içerisinde en küçük değer uzaklık_1 (2,10) noktasına göre olduğu için küme 1e atandı. Eğer en küçük değeri uzaklık_2 de alsaydı ikinci kümeye eklenecekti. Her noktada işlem ayni şekilde gerçekleştirilir. Artık kümelerimiz hazır. Simdi bu kümeleri optimize etmeliyiz. Bunun için her kümede ayrı ayrı olarak kümelerin elemanlarını toplayıp eleman sayısına böleceğiz ve yeni merkez noktamızı bulmuş olacağız. Daha sonra yukardaki işlemi tekrar gerçekleştireceğiz. Öyleyse kümelerin merkezlerini yeniden bulalım. 3cü kümede 2 eleman var. Yukardaki tabloda da görüldüğü gibi (5,8) ve (7,4) noktaları. Bu iki noktanın ortalaması bize 3cü kümenin yeni merkez noktasını verecektir. Yeni merkez noktamız (5+7)/2 ve (8+4)/2 yani (6,6). Bu işlem her küme için aynı şekilde hesaplanırsa küme 2 için merkez noktamız (8+10+12+8)/4  ve (11+15+16+13)/4  yani (9.5, 13.75) ve küme 1 için merkez noktamız (1+2+3+4)/4 ve (8+10+6+9)/4 yani (2.5, 8.25) olarak bulunur. Şimdi yeni merkez noktalarımıza göre kümelerimizi şekillendirelim. Bunun için daha iyi bir görüntü sağlaması sebebinden yine tablo kullanacağım.

Elde ettiğimiz tabloyu birinci tabloyla kıyaslarsanız kümelerin değişmediğini göreceksiniz. Kümelerde bir değişiklik olmadığında işlem durdurulur. Eğer herhangi bir eleman küme değiştirseydi üçüncü iterasyona geçilecekti. Bu yazıda kullandığım veri tamamen rastgele kendimden üretdiğim bir veriydi. Ve hesaplanmasının kolay olması için 2 boyutlu elemanlardan ibaret bir küme seçtim. Tabiki gerçek veriler çok daha fazla boyutu kapsayabilir. Ama hesaplama algoritmasının temeli her boyut için aynıdır. Kümelerimizin grafiksel görünümü asağıdaki gibi olacaktır. 

Küme sayısını rastgele olarak 3 belirledim. Burada o noktaya takılmayın. Anlatmak istediğim şey algoritmanın nasıl çalıştığına dair bilgi edinmenizdir. Okuduğunuz için teşekkürler.