İçeriğe atla
Arama sonuçlarına dön

K-ortalama Kümeleme

Ortaya koyan
MacQueen, J. B.; Lloyd, S. P.
Yıl
1967 (formalized 1982)
Tür
Partitional clustering
Aile
Machine learning

Bu metin makine çevirisidir ve henüz incelenmedi. Asıl metni İngilizce oku

Yazı boyutu

Ne işe yarar?

K-ortalama, bir veri setini K adet çakışmayan gruba ayıran klasik bir denetimsiz bölümlemeli kümeleme algoritmasıdır.

Her gözlemi en yakın merkezine atayarak ve merkezleri atanan noktaların ortalaması olarak güncelleyerek yinelemeli bir şekilde çalışır. Makine öğrenimi ve veri analizinde en yaygın kullanılan keşif araçlarından biridir.

Yöntemin mantığı

Veri noktaları haritasına K adet mıknatıs bıraktığınızı hayal edin. Her nokta en yakın mıknatısına çekilir ve ardından her mıknatıs çektiği noktaların ağırlık merkezine doğru hareket eder. Hiçbir şey hareket etmeyene kadar bu çekme ve hareket ettirme döngüsünü tekrarlayın: mıknatıslar K doğal grubu bulmuştur. K-ortalama tam olarak bu fikri resmileştirir, her noktanın küme merkezine olan toplam karesel uzaklığını, yani küme içi kareler toplamını (WCSS veya eylemsizlik) minimize eder.

Tarih

K-ortalama fikri, terimi ortaya atan MacQueen tarafından 1967'de bağımsız olarak tanıtılmış ve 1950'lerde Bell Labs'ta Stuart Lloyd tarafından verimli bir yinelemeli algoritma olarak resmileştirilmiştir (1982'de yayınlanmıştır). Arthur ve Vassilvitskii'nin 2007'deki k-means++ başlatma iyileştirmesi, yerel minimum duyarlılık sorununu ele almıştır. Bugün k-ortalama, hemen hemen her veri bilimi müfredatında öğretilen temel bir denetimsiz öğrenme yöntemi olmaya devam etmektedir.

Ne zaman kullanılır?

K-ortalama, hızlı, ölçeklenebilir bölümlemeye ihtiyaç duyduğunuzda ve K'yi önceden belirtmekten veya dirsek veya siluet yöntemiyle aramaktan çekinmediğinizde, büyük, tamamen sayısal veri setlerinin keşifsel kümelenmesi için uygundur. Müşteri segmentasyonu, görüntü sıkıştırma, belge konu gruplaması ve denetimli öğrenme öncesi ön işleme için iyi çalışır. Kümeler küresel değilse, boyutları veya yoğunlukları çok farklıysa, öznitelikler kategorik veya sıralıysa (bunun yerine k-modları veya k-prototipleri kullanın), küme sayısı tamamen bilinmiyorsa ve farklı K deneyleri mümkün değilse veya veriler çok sayıda aykırı değer içeriyorsa (bunun yerine DBSCAN veya sağlam varyantlarını kullanın) kaçının.

Sınırlar ve dikkat edilmesi gerekenler

  • K'nin önceden belirtilmesini gerektirir; K'nin kötü seçilmesi anlamsız kümeler üretir.
  • Küresel, benzer büyüklükteki kümeler varsayar; uzatılmış, düzensiz veya farklı ölçekli kümeler yanlış bölünür veya birleştirilir.
  • Aykırı değerlere duyarlıdır: tek bir aşırı nokta, bir merkezi kümenin büyük kısmından uzağa çekebilir.
  • Yalnızca sayısal sürekli özniteliklerle çalışır; kategorik veriler farklı bir algoritma (k-modları) gerektirir.
  • Yerel bir minimuma yakınsar; k-means++ veya çoklu yeniden başlatmalar kullanılmadıkça, farklı rastgele tohumlarla yapılan çalıştırmalar arasında sonuçlar değişebilir.

Kaynak metnin koşulları, bağımsız bilimsel inceleme veya analiz motoru doğrulaması yerine geçmez.

Güçlü yönleri

  • Hızlı ve ölçeklenebilir: Her yinelemede O(nKdi), orta K ve boyutlarla milyonlarca gözlem üzerinde pratiktir.
  • Uygulaması basit, her büyük ML çerçevesinde yaygın olarak bulunur ve teknik olmayan kitlelere açıklaması kolaydır.
  • Büyük, iyi ayrılmış, kabaca küresel ve benzer büyüklükteki kümelerde iyi çalışır.
  • k-means++ başlatma, rastgele başlatmaya kıyasla başlangıç koşullarına duyarlılığı önemli ölçüde azaltır.
  • Sabit bir rastgele tohum içinde deterministiktir, bu da sonuçların tekrarlanabilir olmasını sağlar.

Uygulama alanları

  • Davranışsal veya demografik özelliklere dayalı pazarlama ve kişiselleştirme için müşteri segmentasyonu.
  • Piksel renklerini K temsili değere nicelleştirerek görüntü sıkıştırma (renk nicemlemesi).
  • Vektörleştirmeden sonra konu modelleme boru hatlarında bir adım olarak belge ve metin kümelemesi.
  • Anomali tespiti ön işleme: herhangi bir merkezden uzak noktalar aday aykırı değerlerdir.
  • Gauss karışım modelleri veya hiyerarşik kümeleme gibi daha karmaşık algoritmalar için başlatma adımı.
  • Benzer ifade profillerine sahip genleri veya örnekleri gruplamak için gen ifade analizi.

Nasıl çalışır?

Nasıl çalışır?

1

K küme merkezleri, ya K veri noktasının rastgele seçilmesiyle (Forgy) ya da daha akıllı k-means++ stratejisiyle, kötü yerel minimum olasılığını azaltmak için başlangıç merkezlerini yayarak öznitelik uzayına yerleştirilir. Başlatma seçimi önemlidir: k-means++ genellikle daha hızlı yakınsama ve daha iyi nihai çözümler sağlar.

2

Her gözlem, Öklid mesafesine göre merkezi en yakın olan kümeye atanır. Bu kesin atama, verinin K adet çakışmayan bölümünü oluşturur. Biçimsel olarak, her x_i noktası c_i = argmin_k ||x_i - mu_k||^2 kümesine atanır.

Formül
c_i = \arg\min_k \|x_i - \mu_k\|^2
3

Her merkez, o kümeye atanmış tüm noktaların aritmetik ortalaması olarak yeniden hesaplanır: mu_k = (1/|C_k|) çarpı C_k'deki tüm x_i'lerin toplamı. Bu adım, mevcut atama göz önüne alındığında yeni merkezin her küme içindeki WCSS'yi minimize etmesini garanti eder.

Formül
\mu_k = \frac{1}{|C_k|} \sum_{x_i \in C_k} x_i
4

Atama ve güncelleme adımları, merkez konumları değişmeyi durdurana (veya bir tolerans eşiğinden daha az değişene) veya maksimum yineleme sayısına ulaşılana kadar dönüşümlü olarak devam eder. Algoritma, WCSS'nin yerel bir minimumuna yakınsamayı garanti eder, ancak bu mutlaka global minimum olmak zorunda değildir.

5

Çözüm kalitesi, J = kümeler üzerindeki toplam, atanan noktalar üzerindeki toplam ||x_i - mu_k||^2 ile değerlendirilir. K'yi seçmek, dirsek yöntemi, siluet skorları veya boşluk istatistikleri ile ele alınan ayrı bir konudur, çünkü algoritmanın kendisi K'nin önceden belirtilmesini gerektirir.

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

Sık yapılan hatalar

  • Kümelemeden önce öznitelikleri standartlaştırmayı unutmak — büyük ölçekli değişkenler mesafe hesaplamalarına hakim olacaktır.
  • K'yi yalnızca dirsek grafiği veya siluet doğrulaması olmadan örnek içi WCSS'yi inceleyerek seçmek, önemsiz derecede küçük veya büyük K'ye yol açar.
  • Yalnızca tek bir başlatma çalıştırmak ve kötü yerel minimumlara karşı korunmak için çoklu yeniden başlatmalar yapmadan ilk sonucu kabul etmek.
  • Uygun kodlama yapmadan veya k-modlarına geçmeden kategorik veya sıralı değişkenleri öznitelik matrisine dahil etmek.
  • Özellikle kümeler iyi ayrılmamışsa, küme etiketlerini harici doğrulama olmadan anlamlı grup kimlikleri olarak ele almak.

Sık sorulan sorular

Doğru küme sayısı K'yi nasıl seçerim?

K-ortalamayı bir dizi K değeri için çalıştırın, küme içi kareler toplamını K'ye karşı çizin ve azalma oranının keskin bir şekilde yavaşladığı bir 'dirsek' arayın. Bunu, her noktanın kendi kümesine komşu kümelere göre ne kadar benzer olduğunu ölçen siluet skorlarıyla destekleyin; daha yüksek ortalama siluet, daha iyi tanımlanmış kümeleri gösterir.

Her çalıştırmada neden farklı sonuçlar alıyorum?

K-ortalama, başlatmaya duyarlıdır ve WCSS'nin global minimumundan ziyade yerel bir minimumuna yakınsar. Tekrarlanabilirlik için k-means++ başlatmayı kullanın ve sabit bir rastgele tohum ayarlayın. Algoritmayı farklı tohumlarla birden çok kez çalıştırmak ve en düşük eylemsizliğe sahip çözümü saklamak iyi bir uygulamadır.

K-ortalama kategorik verilerle çalışır mı?

Hayır. K-ortalama, kategorik değişkenler için tanımlanmamış olan Öklid mesafesine ve merkez ortalamalarına dayanır. Tamamen kategorik veriler için k-modlarını; karışık sayısal ve kategorik veriler için k-prototiplerini kullanın.

DBSCAN veya GMM'yi k-ortalamaya ne zaman tercih etmeliyim?

Kümeler düzensiz şekillere sahip olduğunda veya K'yi belirtmeden otomatik aykırı değer tespitine ihtiyacınız olduğunda DBSCAN'ı kullanın. Daha yüksek hesaplama karmaşıklığı pahasına, yumuşak (olasılıksal) küme atamaları veya farklı boyut ve yönelimlerde kümeler istediğinizde Gauss Karışım Modellerini (GMM) kullanın.

Özniteliklerimi ölçeklendirmem gerekiyor mu?

Evet, neredeyse her zaman. K-ortalama Öklid mesafesini kullanır, bu nedenle geniş sayısal aralıklara sahip öznitelikler kümelemeye hakim olacaktır. Tüm öznitelikler zaten aynı ölçekte değilse, k-ortalamayı uygulamadan önce z-skor standardizasyonu veya min-max ölçeklendirme uygulayın.

İlgili yöntemler

Kaynaklar

  1. Lloyd, S. P. (1982). Least squares quantization in PCM. IEEE Transactions on Information Theory, 28(2), 129–137.

    DOI kaynağını aç
    Kopyalandı.
  2. MacQueen, J. B. (1967). Some methods for classification and analysis of multivariate observations. Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability, 1, 281–297.

    Yayın kaynağını aç
    Kopyalandı.