K-means: Veriyi K Gruba Bölen "En Eski" Kümeleme Algoritması

Etiketsiz veride yapı arama

Denetimli öğrenmede $(x, y)$ çiftleri var. Peki sadece $x$'ler varsa? Denetimsiz öğrenme.

En basit denetimsiz görev: kümeleme. Benzer örnekleri gruplandır.

En klasik algoritma: K-means — 1957'de Stuart Lloyd (Bell Labs), 1967'de James MacQueen yayınladı.

Algoritma

Verilen: $N$ veri noktası, K (küme sayısı).

1. Başla: K merkez (centroid) rastgele yerleştir.
2. Atama: her noktayı en yakın merkeze ata.
3. Güncelle: her merkezi atanmış noktaların ortalaması olarak güncelle.
4. Tekrarla 2-3, değişiklik olmayana kadar.

Bu kadar. Üç satır kodla yazılır.

Matematik

Hedef fonksiyonu (within-cluster sum of squares):

$J = \sum_{k=1}^{K} \sum_{x_i \in C_k} \|x_i - \mu_k\|^2$

K-means bu fonksiyonu yerel olarak minimize eder. Konveks değildir — başlangıca duyarlı.

Avantajlar

• Çok hızlı: $O(NKT)$, T iterasyon sayısı.
• Çok ölçeklenebilir: mini-batch versiyonu milyarlarca veri.
• Anlaşılır: her küme bir centroid ile temsil edilir.

Sınırlamalar

• K'yı önceden bil: kaç küme var bilmiyorsanız sorun.
• Yerel minimum: başlangıca duyarlı.
• Küresel kümeler varsayar: uzun, eğri kümeler yakalayamaz.
• Outlier'lara hassas: ortalamayı bozarlar.
• Boyut laneti: yüksek boyutta uzaklık anlamsız.

K'yı seçmek

Klasik yöntemler:

Elbow (dirsek) yöntemi

$K$ değerlerine göre $J$ değerini çiz. Dirsek (kırılma) noktası en iyi K.

Silhouette skoru

Her nokta için:

• $a_i$: kendi kümesindeki ortalama uzaklık.
• $b_i$: en yakın diğer kümeye ortalama uzaklık.

$s_i = \frac{b_i - a_i}{\max(a_i, b_i)} \in [-1, 1]$

Yüksek skor → iyi kümeleme.

Gap istatistiği

Rastgele veri ile karşılaştırma — fazla küme yapma cezası.

Başlangıç stratejisi: K-means++

Sıradan rastgele başlatma yerine:

• İlk centroid'i rastgele seç.
• Sonraki centroid'i mevcutlardan uzak olma olasılığıyla seç.

Bu, K-means'in çok daha iyi sonuçlar vermesini sağlar. Arthur ve Vassilvitskii, 2007.

Varyantlar

• Mini-batch K-means: her iterasyonda küçük örnek → hızlı.
• K-medoids: ortalama yerine gerçek bir nokta centroid (outlier dirençli).
• Fuzzy C-means: her nokta birden fazla kümeye kısmen ait.
• Spherical K-means: küresel uzayda (cosine similarity).

Modern AI'da kullanımı

1. Embedding kümeleme

LLM'in ürettiği vektörler — semantik olarak benzer cümleler gruplandırılır.

2. Görüntü Renk Kuantizasyonu

256 → 16 rengin "tipik renk" olarak temsil edilmesi.

3. Anomali tespiti

Bir nokta hiçbir kümeye yakın değilse → outlier.

4. Veri sıkıştırma

Vektör nicemleme (vector quantization) — modern LLM tokenizer'ları K-means tabanlı.

5. Mixture of Experts router

Hangi expert hangi token'i alacak → benzerlik tabanlı atama (router K-means'tan ilham alır).

Türk endüstrisi

• Müşteri segmentasyonu (RFM analizi + K-means).
• Bayilik konum optimizasyonu.
• Kaza/hasar analizi sigorta.
• Yerel hava analizi TMMOB projeleri.

Pratik tavsiyeler

• Veriyi ölçeklendir (standardize): K-means uzaklık tabanlı.
• K-means++ ile başlat.
• Birkaç farklı seed ile çalıştır, en düşük $J$ seç.
• Silhouette ile K seç.
• Outlier'ları baştan temizle.

Lloyd ve MacQueen

Stuart Lloyd 1957'de bir Bell Labs teknik raporunda yazdı ama 30 yıl yayınlanmadı! James MacQueen 1967'de bağımsız keşfedip K-means adını verdi.

Modern Wikipedia'da algoritma genelde "Lloyd's algorithm" olarak anılır.

Kapanış

K-means basit, hızlı, etkili — denetimsiz öğrenmenin Hello World'ü. Modern derin öğrenme döneminde bile production'da yerini koruyor. Yeni bir veri setiniz varsa: önce K-means dene.