K-means kümeleme algoritması (K-means clustering algorithm) C#

Bu algoritma yapay zekada kümeleme algoritmalarının en bilinen ve en basit yöntemlerinden biridir.

Hemen proje kodlarımızı paylaşalım sonra algoritmanın basit anlatımına geçelim.

https://github.com/muhammedtanriverdi/K_mean_Clustering

"K" harfi küme sayısını işaret eder. Yani bu algoritma verilen küme sayısına göre bir yol izler. Küme sayısının belli olduğu durumlarda kullanılır.

İşletim süresi (time complexity) -> O(ndkt)

n -> Veri sayısı
d -> Uzay sayısı (Yani verilerin sahip olduğu özellik sayısı)
                        (2 boyutlu koordinat düzleminde, x-y özellikleri varsa 2;
                         ya da yaş-boy-günlük tüketilen su miktarı özellikleri varsa(3 boyutlu) 3 )
k -> Küme sayısı
t -> İterasyon sayısı

Yukarıdan anlaşıldığı gibi bu algoritma;
her veri için
her özellik için
her küme için
içiçe döngü oluşturuyor.

Algoritması hakkında bahsedelim (2 boyutlu koordinat sistemi üzerinden anlatacağım)

2 boyutlu düzlemde (x,y) koordinatları belli 1000 tane veri yerleştirdik. Gözle görüldüğü üzere 4 farklı küme var.

Peki neye göre 4 farklı küme var deriz?
Koordinat düzlemindeki (öklit) uzaklığa göre diyebiliriz.

1. ADIM : İlk adımda 4 küme olduğunu bildiğimiz için koordinat düzleminde 4 kümeyi rastgele noktalara atarız ve her veriyi herhangi bir kümeye sokarız.

Görüldüğü gibi kümeler (farklı renkte büyül kare işaretleri) rastgele x,y özelliklerine sahip oldular ve her veri rastgele bir kümeye sokuldu.

Tekrar bahsetmek istiyorum, burada (x,y) özelliklerine sahip verileri kümelemeye çalışıyoruz. Veriler her zaman x,y koordinatına sahip olmak zorunda değiller. Mesela kütüphanedeki kitaplar kümelenmek istenirse ve kümeleme işlemi basım yılına ve sayfa sayısına göre yapılacaksa, ilk başta her kümeye rastgele bir basım yılı ve sayfa sayısı atanacaktır.

2. ADIM : Bu adımda her veri kendine en yakın olan (uzaklık olarak) kümeye atanacaktır.

Resimde görüldüğü gibi her veri kendine yakın olan kümelere sokuldu. Bu aşamada farkettiyseniz, küme merkezleri sahip olduğu verilere göre farklı yerlerde.

3. ADIM : Bu adımda ise küme merkezlerini yeniden hesaplamak gerekiyor. Yani kümeleri sahip oldukları verilerin ortasına götürüyoruz.

Resimde görüldüğü gibi kümelerin merkezleri sahip oldukları verilerin ortasına işaret etti.

4. ADIM : 2. adım ve 3. adımlar tekrarlanacak.
Ne zamana kadar?
Küme merkezleri değişmeyene kadar.

Resimlerle bir iki iterasyon gösterelim.

2. Adım

3. Adım

2. Adım

3. Adım

....

Görüldüğü gibi anlaşılması çok basit bir algoritmadır.
Bazı eksiklikleri vardır. Her zaman doğru kümeleme işlemi yapamıyor.
Mesela : Bu örnekte 2 farklı küme var ve bariz şekilde farklı olduğu görülüyor; fakat k-means algoritması bu verileri doğru kümeleyemiyor.

Ya da bu örnekte 3 farklı küme varken dağınık verilerden bazılarını toplu kümelere sokacaktır.

Bu algoritmayı iyileştirebilmek için "Enhancing K-means Clustering Algorithm with Improved Initial Center" adlı makaledeki iyileştirme yöntemlerini koda eklemeye çalıştım.

Makale adresi