önce M. AKÇA tarafından yazılmıştır. k-Means Kümeleme Algoritması Nedir?

k-Means Kümeleme Algoritması Nedir?

En eski kümeleme algoritmalarından olan k-means, 1967 yılında J.B. MacQueen  tarafından geliştirilmiştir (MacQueen, 1967) *

k-Means Kümeleme Algoritması Data Mining Dünyasında En Çok Kullanılan Algoritmaların başında yer almaktadır.  Kümeleme algoritmaları ile Sınıflandırma algoritmaları arasında bir takım farklılıklar bulunmaktadır. k-means algoritması bir kümeleme algoritmasıdır. Kümeleme algoritmaları otomatik olarak verileri daha küçük kümelere yada alt kümelere ayırmaya yarayan algoritmalardır. Algoritma istatistiksel olarak benzer nitelikteki kayıtları aynı gruba sokar. Bir elemanın yalnızca bir kümeye ait olmassına izin verilir.  Küme merkezi kümeyi temsil eden değerdir.

Alogritmanın isminde yer alan “k” harfi, aslında küme sayısını belirtir: Algoritma, hata hesaplamada yaygın olarak kullanılan Karasel Hata Fonksiyonunu en aza indirgiyecek “k” küme sayısını da arar. Verilen “n” sayıdaki veri seti “k” tane kümeye bu hata fonksiyonunu en aza indirgeyecek şekilde yerleştirilir. Bu nedenle küme benzerliği kümedeki değerlerin ortalamaya yakınlıkları ile ölçülür. Bu da kümenin ağırlık merkezidir. Kümenin merkezinde yer alan değer kümenin temsilci değeridir ve medoid olarak adlandırılır.

Burada en önemli iki amaç şudur:

1- Küme içindeki değerler birbirlerine en çok benzemeli,

2- Kümeler birbirine mümkün olduğunca benzememeli

Bu istekleri gerçekleştirmek için algoritma tarafında sırasıyla şu adımlar gerçekleştirilmelidir:

1- Sınıf merkezlerinin belirlenmesi

2- Örneklerin mesafelere göre sınıflandırılması

3- Yapılan sınıflandırma sonrasında yeni merkezlerin belirlenmesi

4- İstenilen hale gelinceye kadar 2. ve 3. adımların algoritmik olarak tekrarlanması.

 

Yeni geliştirdikleri T-Shirtleri pazara sunmaya hazırlanan bir şirket düşünün. Bütün insan tipleri için uygun t-shirt büyüklüklerinde üretmeleri gerekiyor. Dolayısı ile müşterilerinin kilo ve ağırlıklarına bağlı bir dağılım grafiğini alttaki gibi elde edeceklerdir.

tshirt

Firma tüm insan kilo-boy tipleri için farklı t-shirt üretmeyeceği için, bunları gruplandırmak isteyecektir. Firma 3 farklı tipte Small(Küçük)-Medium(Orta)-Large(Büyük) şeklinde ürünlerini guruplayarak müşterilerine sunduğunda müşterileri memnun kalacaklarsa bu 3 tipteki ürünü kullancak, aksi taktirde XS, XL gibi yeni gruplar da eklemek zorunda kalacaktır.

guruplanmış t-shirt

 

 

Bu işlemleri yaparken kullanılan algoritma yinelemeli bir algoritmadır ve bu algoritmanın nasıl işlediğini adım adım anlatmaya çalışacağım:

Alttaki veri setini düşünecek olursak. İki ayrı guruba ayırmaya çalıştığımızı varsayalım.

 

testdata

Adım 1- İki farklı guruba ayırmak istediğimiz için. C1 ve C2 adında rastgele iki sınıf merkezi belirleriz.

Adım 2- Her bir kaydın(noktanın) bu noktalara uzunluğunu hesaplayarak C1’nolu merkeze yakın ise “1”, C2 nolu merkeze yakın ise altta görüldüğü gibi “2” şeklinde etiketleriz.

noktaları etiketleme

 

Adım 3- Daha sonra bütün mavi ve kırmızı noktaları merkez kabul edilerek bu işlemler yeniden yapılır ve üyeler bu yeni merkezlere göre yeniden kümelere ayrılır. Bu merkez güncelleme işlemi alttaki gibi resmedilebilir.

merkezi guncelle

Adım 2 ve Adım 3 bizim belirlediğimiz ortalama uzaklıklar, ya da bizim belirlediğimiz iterasyon sayısı kadar çalıştırılarak,sapmaların minimum olduğu değer bulunur. Bu sapma minimizasyonu hesabında bir fonksiyon kullanılır.

minimize etmek

K sayıdaki iterasyonu da modelde göstermek istersek alttaki gözterimi kullanabiliriz.

minimize etmek-2

Burada her bir merkez çifti için gruplardaki tüm noktaların aralarındaki tüm mesafelerin toplamı alınır. Ve merkez çiftleri değiştirile değiştirile, bu işlem için en uygun merkez çiftleri seçilir.

Burada bu algoritmayı basitçe anlatmaya çalıştım, daha ayrıntılı bir inceleme için Makine Öğrenmesi çalışmalarına ve kitaplarına bakabilirsiniz.

 

* İstanbul Ticaret Üniversitesi Fen Bilimleri Dergisi Yıl: 6 Sayı:11Bahar 2007/1 s. 31-45