K-Means Clustering

K-means kümeleme, verileri her biri kendisine atanmış noktaların ortalaması olan merkeziyle temsil edilen k gruba ayıran bir denetimsiz öğrenme algoritmasıdır. Küme içindeki karesel uzaklıklar toplamını, yani atalet adı verilen değeri en aza indiren kümelendirmeyi arar; böylece kümedeki noktalar merkeze yakın olur. Standart yöntem, Stuart Lloyd'un 1957'de Bell Labs'te sinyalleri nicelemek amacıyla geliştirdiği Lloyd algoritmasıdır; "k-means" adı ise James MacQueen'in 1967 tarihli makalesinden gelir. Basit, hızlı ve milyonlarca noktaya ölçeklenebilir olması sayesinde k-means, veri madenciliği, sıkıştırma ve etiketsiz verilerin yapısını keşfetmek için varsayılan araçtır.

Algoritmanın Çalışma Şekli#

Başlangıç merkezleri seçildikten sonra Lloyd algoritması, kümeler değişmeyi bırakana kadar atama ve güncelleme adımları arasında dönüşümlü olarak ilerler:

1. Başlatma: Başlangıç için k merkezi seç. Scikit-learn'ün varsayılanı olan k-means++, ilk merkezi rastgele seçer; sonraki merkezlerin her birini ise önceden seçilmiş en yakın merkeze olan karesel uzaklığıyla orantılı olasılıkla seçerek başlangıç noktalarının birbirinden uzak olmasını sağlar.
2. Atama: Her noktayı, genellikle Öklid uzaklığını kullanarak en yakın merkeze ata.
3. Güncelleme: Her merkezi, o anda kendisine atanmış noktaların ortalamasına taşı.
4. Tekrarlama: Hiçbir nokta küme değiştirmeyene veya merkezler tolerans eşiğinden daha az hareket edene kadar atama adımına dön.

Her iki adım da eylemsizliği artıramaz; bu nedenle döngü her zaman yakınsar, ancak başlangıç merkezlerine bağlı yerel bir minimuma ulaşır. Küresel optimumu bulmak NP-zordur; bu yüzden uygulamalar birkaç başlatma yapar ve eylemsizliği en düşük olanı seçer. scikit-learn KMeans içinde varsayılan n_init="auto", k-means++ ile başlangıçlandırıldığında bir kez, rastgele başlatıldığında 10 kez çalışır.

Küme Sayısını Seçme#

K-means, k değerinin baştan verilmesini gerektirir. k büyüdükçe daha fazla merkez noktalara yaklaşacağından atalet her zaman azalır; bu nedenle dirsek yöntemi ataleti k değerine göre çizer ve düşüşün yataylaşmaya başladığı noktayı arar. Siluet puanı, her nokta için kendi kümesindeki ortalama uzaklığı en yakın diğer kümedeki ortalama uzaklıkla karşılaştırır; -1 ile 1 arasında değişir ve yüksek değerler sıkı, iyi ayrılmış kümeleri gösterir. Bu örnek, dört merkez çevresinden örneklenen verilerde k değerini 2'den 6'ya kadar puanlar:

from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs
from sklearn.metrics import silhouette_score

# 600 unlabeled points drawn around 4 hidden centers
X, _ = make_blobs(n_samples=600, centers=4, cluster_std=1.0, random_state=7)

# Fit k-means for several k and score each partition
for k in range(2, 7):
    kmeans = KMeans(n_clusters=k, n_init="auto", random_state=0)
    labels = kmeans.fit_predict(X)
    print(f"k={k}  inertia={kmeans.inertia_:8.0f}  silhouette={silhouette_score(X, labels):.3f}")

Atalet, k=2 için 18.363 değerinden k=3 için 5.241'e ve k=4 için 1.127'ye düşer; ardından k=5 için yalnızca 1.039'a, k=6 içinse 922'ye iner. Bu nedenle dirsek k=4 noktasındadır. Siluet puanı da aynı sonucu verir: k=4 için 0.811 ile zirveye ulaşır ve k=5'te 0.687'ye düşerek verinin örneklendiği dört merkezi ortaya çıkarır.

Varsayımlar ve Çeşitler#

K-means, kümeler kabaca küresel olduğunda, benzer boyutlardayken ve Öklid uzayında birbirinden ayrıldığında en iyi sonucu verir. Büyük ölçekli özellikler uzaklığa daha fazla etki eder; bu nedenle veriler genellikle önce standartlaştırılır. Her nokta bir kümeye katılır ve birkaç uç aykırı değer merkezi ait olduğu kümeden uzaklaştırabilir. Birkaç çeşidi bu sınırlamaları gevşetir:

• Mini-yığın k-means: Merkezleri küçük rastgele yığınlardan günceller; büyük veri kümelerinde çok daha hızlı eğitim için az miktarda doğruluktan ödün verir.
• K-medoids: Küme merkezleri olarak gerçek veri noktalarını kullanır; bu sayede aykırı değerlere karşı daha dayanıklıdır ve her türlü uzaklık ölçüsüyle çalışır.
• Bulanık c-means: Tek bir kesin atama yapmak yerine, bulanık mantık yaklaşımına benzer biçimde her noktaya her küme için bir üyelik derecesi verir.
• Gauss karışım modelleri: Her küme için bir olasılık dağılımı uydurur; böylece farklı boyutlarda eliptik kümelere olanak tanır ve yumuşak, olasılıksal atamalar üretir.

Yapay Zekâ ve Bilgisayarlı Görüde Uygulamalar#

• Renk niceleme: Bir görüntünün piksel renklerini kümeleyip her pikseli küme merkezindeki renkle değiştirmek, binlerce renk içeren bir fotoğrafı k renkli bir palete indirger; bu, görüntüyü sıkıştırırken hızlı ve kabaca bir görüntü segmentasyonu biçimi de sağlar.
• Kod kitapları ve vektör niceleme: Küme merkezleri bir kod kitabı oluşturur ve her vektör, en yakın küme merkezinin indeksi olarak saklanır. Görsel sözcük torbası yaklaşımını kullanan klasik görüntü erişim yöntemleri, söz varlıklarını yerel görüntü tanımlayıcılarından bu şekilde oluşturmuştur.
• Çapa kutusu tasarımı: YOLOv2, çapa kutularını seçmek için eğitim kutularının genişlik ve yüksekliklerine, uzaklık ölçütü olarak 1 eksi IoU kullanarak k-means uyguladı.
• Ağırlık paletleştirme: YOLO26 modelini quantize=8 ile Core ML biçimine aktarırken, her büyük ağırlık tensörünün değerleri k-means ile 256 küme merkezine ayrılır; böylece dışa aktarılan model her ağırlığı 8 bitlik bir indeks ve küçük bir arama tablosuyla saklar.
• Müşteri segmentasyonu: Perakendeciler, teklifleri her segmente uyarlamak için müşterileri satın alma sıklığına, sepet büyüklüğüne ve son alışveriş zamanına göre gruplandırır.

K-Means ve İlgili Algoritmalar#

• K en yakın komşu (KNN): Ortak olan "k" harfi kafa karışıklığına yol açar. KNN, yeni bir noktayı en yakın k etiketli örneğine göre etiketleyen denetimli bir algoritmayken k-means denetimsizdir ve k, oluşturduğu küme sayısıdır.
• DBSCAN: Noktaları yoğunluklarına göre gruplandırır, küme sayısını kendisi bulur, her şekilden kümeyi izler ve seyrek noktaları bir kümeye zorla atamak yerine gürültü olarak etiketler.
• Hiyerarşik kümeleme: En yakın grupları tekrar tekrar birleştirerek iç içe kümelerden oluşan bir ağaç kurar; böylece ağaç herhangi bir seviyeden kesilerek k sonradan seçilebilir. Bunun bedeli, nokta sayısıyla en az ikinci dereceden artan hesaplama maliyetidir.