K-Ortalamalar Kümeleme — Algoritma ve Nasıl Çalışır

K-ortalamalar kümeleme, sayısal verileri $k$ kümeye ayırmanın bir yoludur. $k$ değerini seçip standart Öklid sürümünü kullanırsanız, algoritma tek bir döngüyü tekrarlar: her noktayı en yakın merkeze atar, sonra her merkezi ona atanmış noktaların ortalamasına taşır.

Basitçe söylemek gerekirse, aynı gruptaki noktaların birbirine yakın, farklı gruplardaki noktaların ise daha uzak olmasını sağlamaya çalışır. Hızlı ve kullanışlıdır, ancak yalnızca bu "gruplar" makul ölçüde kompakt olduğunda ve uzaklık anlamlı olduğunda iyi çalışır.

K-ortalamalar kümelemenin optimize ettiği şey

Standart Öklid biçiminde k-ortalamalar, her kümenin içindeki noktaları o kümenin merkezine mümkün olduğunca yakın yapmaya çalışır. Yaygın bir amaç fonksiyonu şudur:

$$\sum_{j=1}^{k} \sum_{x_i \in C_j} \|x_i - \mu_j\|^2$$

Burada $C_j$, $j$'inci kümedir ve $\mu_j$ onun merkezidir.

Bu, küme içi kareler toplamıdır. Daha küçük değerler, atanmış noktaların merkezlerinin etrafında daha sıkı toplandığı anlamına gelir.

Bu amaç fonksiyonu, algoritmanın iki bölümünü açıklar:

• Merkezler sabitse, en iyi hareket her noktayı en yakın merkeze atamaktır.
• Atamalar sabitse, en iyi merkez atanmış noktaların ortalamasıdır.

Bu yüzden güncelleme kuralı keyfi değildir. K-ortalamalardaki "ortalamalar", gerçekten aritmetik ortalamalardır.

K-ortalamalar algoritması nasıl çalışır

Tipik döngü kısadır:

1. Başlangıç için $k$ merkez seçin.
2. Her noktayı en yakın merkeze atayın.
3. Her merkezi, ona atanmış noktaların ortalaması olarak yeniden hesaplayın.
4. Atamalar değişmeyi bırakana veya iyileşme çok küçük hale gelene kadar tekrarlayın.

Bu süreç genellikle hızlı yakınsar, ancak mutlaka mümkün olan en iyi kümelenmeye ulaşmaz. Farklı başlangıç merkezleri farklı nihai sonuçlara yol açabilir, bu yüzden başlangıç seçimi önemlidir.

Adım adım k-ortalamalar kümeleme örneği

Şu tek boyutlu veri noktalarını ele alalım:

$$1,\ 2,\ 3,\ 10,\ 11,\ 12$$

Diyelim ki $k = 2$ küme istiyoruz ve başlangıç merkezlerini $1$ ve $10$ olarak alıyoruz. Bu iyi bir örnektir çünkü merkezler ilk güncellemeden sonra gerçekten yer değiştirir.

Adım 1: noktaları en yakın merkeze atayın

$1, 2, 3$ noktaları, $1$'e daha yakındır.

$10, 11, 12$ noktaları, $10$'a daha yakındır.

Dolayısıyla kümeler şunlardır:

$$C_1 = \{1,2,3\}, \qquad C_2 = \{10,11,12\}$$

Adım 2: merkezleri güncelleyin

İlk kümenin yeni merkezi şudur:

$$\mu_1 = \frac{1+2+3}{3} = 2$$

İkinci kümenin yeni merkezi şudur:

$$\mu_2 = \frac{10+11+12}{3} = 11$$

Her iki merkez de yer değiştirdi: biri $1$'den $2$'ye, diğeri $10$'dan $11$'e.

Adım 3: yeniden atama yapın

Şimdi $2$ ve $11$ kullanarak en yakın merkezi tekrar kontrol edin.

$1, 2, 3$ noktaları hâlâ birinci kümeye, $10, 11, 12$ noktaları da hâlâ ikinci kümeye aittir. Atamalar artık değişmediği için algoritma yakınsamıştır.

Bu temiz bir örnektir çünkü veri doğal olarak iki kompakt gruba ayrılır. Gerçek veri kümeleri daha dağınıktır; k-ortalamaların yanıltıcı olmaya başlayabildiği yer de burasıdır.

K-ortalamalar ne zaman iyi çalışır

K-ortalamalar en iyi şu koşullar yaklaşık olarak sağlandığında çalışır:

• Özellikler sayısaldır.
• Öklid uzaklığı, benzerliği ölçmek için makul bir yoldur.
• Kümeler uzun veya eğri değil, oldukça kompakttır.
• Özellikler ölçeklenmiştir; böylece bir değişken diğerlerine baskın çıkmaz.

Bu koşullar sağlanmazsa, çıktı düzenli görünebilir ama verideki gerçek yapıyı kaçırabilir.

K-ortalamalarda yaygın hatalar

K-ortalamaları evrensel bir kümeleme yöntemi sanmak

K-ortalamalar, kümeler makul ölçüde kompakt olduğunda ve ortalama anlamlı bir özet olduğunda en iyi çalışır. Her veri kümesi için iyi bir varsayılan yöntem değildir.

Özellik ölçeklemeyi göz ardı etmek

Bir özellik diğerine göre çok daha büyük bir ölçekte ölçülüyorsa, uzaklık hesabına o özellik baskın olabilir. K-ortalamaları çalıştırmadan önce özellikleri standartlaştırmak veya normalize etmek çoğu zaman önemlidir.

Cevabın tek olduğunu varsaymak

K-ortalamalar, farklı başlangıç noktalarından farklı yerel minimumlara yakınsayabilir. Bu yüzden tekrarlı çalıştırmalar veya k-means++ başlatma gibi yöntemler yaygın olarak kullanılır.

Sayısal olmayan ya da kötü kodlanmış özellikler kullanmak

Merkezler ortalama olduğu için, standart k-ortalamalar sayısal değişkenler için tasarlanmıştır. Bir özellik kategorikse, aritmetik ortalama almak anlamlı olmayabilir.

Güçlü biçimde küresel olmayan kümelerde kullanmak

Gerçek gruplar uzun, eğri veya yoğunluk bakımından çok dengesizse, k-ortalamalar tek bir doğal grubu bölebilir ya da iki farklı grubu birleştirebilir. Yöntem, kompakt ve merkez tabanlı kümeleri tercih eder.

Aykırı değerlerin merkezleri çekebileceğini unutmak

Merkezler ortalama olduğu için, uç değerler onları belirgin biçimde kaydırabilir. Verinizde aykırı değerler önemliyse, sonuca güvenmeden önce bunu kontrol edin.

K-ortalamalar kümeleme nerelerde kullanılır

K-ortalamalar; keşif amaçlı gruplama, müşteri veya davranış segmentasyonu, görüntü renk niceleme ve denetimsiz öğrenmede hızlı bir başlangıç modeli olarak sık kullanılır.

En çok, sayısal özellikleriniz olduğunda, hızlı ve basit bir model istediğinizde ve kümelerin Öklid uzayında yaklaşık olarak kompakt olmasını beklediğinizde faydalıdır.

Basit bir zihinsel model

Bir saçılım grafiğine hareket edebilen $k$ adet raptiye yerleştirdiğinizi hayal edin. Her nokta en yakın raptiyeye bağlanır. Sonra her raptiye, kendisine bağlanan noktaların ortalama konumuna kayar. Raptiyeler artık pek hareket etmeyene kadar bunu tekrarlayın.

Bu resim sadece sezgisel bir anlatım değildir. Neredeyse algoritmanın tamamıdır.

Benzer bir kümeleme problemini deneyin

Bir doğru üzerindeki küçük bir nokta kümesi alın, $k = 2$ seçin ve tam bir atama-güncelleme döngüsünü elle uygulayın. Sonra başlangıç merkezlerini değiştirin veya bir aykırı değer ekleyin ve sonucun nasıl değiştiğine bakın. Bir adım daha ileri gitmek isterseniz, küçük bir veri kümesi üzerinde kendi sürümünüzü deneyin ve özellik ölçeklemeden önce ve sonra ne olduğuna bakın.