Daha önce de belirtildiği gibi, birçok kümeleme algoritması veri kümelerine bu teknoloji genellikle milyonlarca örneğe sahiptir. Örneğin, toplayıcı veya bölünmüş hiyerarşik kümeleme algoritmaları tüm çiftlere bakar \(O(n^2 log(n))\) ve \(O(n^2)\) komplekslerine sahiptir. sırasıyla.
Bu kurs, \(O(nk)\)olarak ölçeklendirildiğinden k-ortalamaya odaklanıyor. Burada \(k\) kullanıcı tarafından seçilen küme sayısıdır. Bu algoritma, öğeleri \(k\) kümeleri, her bir nokta ile bu nokta arasındaki mesafeyi en aza indirerek kümenin merkezi (bkz. Şekil 1).
Sonuç olarak, k-ortalaması, verileri kabaca bir dizi öğeden oluşan bir şekilde etkili bir şekilde ele alır benzer kümeler bulmaya çalışır ve bunlar için en iyi uygulamaları içerir. Ancak gerçek dünya verileri aykırı değerler ve yoğunluğa dayalı kümeler içerir ve k-ortalamaların altında yatan varsayımlarla eşleşmeyebilir.
k-ortalama kümeleme algoritması
Algoritma şu adımları izler:
\(k\)için bir ilk tahmin girin. Bu tahmin daha sonra gözden geçirilebilir. Bunun için için \(k = 3\)değerini seçiyoruz.
Merkezleri rastgele \(k\) seçin.
Şekil 1: Başlatmada k-ortalaması. İlk kümeleri almak için her noktayı en yakın merkeze \(k\) atayın.
Şekil 2: Başlangıç kümeleri. Her küme için ortalama konumunu alarak yeni merkezi noktalarından birini seçin. Şekil 4'teki oklar, tablodaki yardımcı olabilir.
Şekil 3: Yeniden hesaplanan merkezler. Her noktayı en yakın yeni merkeze yeniden atayın.
Şekil 4: Yeniden atama işleminden sonra kümeler. Merkezleri ve küme üyeliğini yeniden hesaplayana kadar 4. ve 5. adımları tekrarlayın. noktaları artık kümeleri değiştirmiyor. Büyük veri kümeleri söz konusu olduğunda, diğer ölçütlere göre yakınlaşmadan önce algoritmayı durdurması gerekir.
Merkez konumları başlangıçta rastgele seçildiğinden, k-ortalamalar birbirini izleyen çalıştırmalarda belirgin ölçüde farklı sonuçlar döndürebilir. Bu sorunu çözmek için k-ortalamayı birkaç kez çalıştırın ve en iyi kaliteye sahip sonucu seçin kullanabilirsiniz. (Kalite metriklerini bu kursun ilerleyen bölümlerinde açıklayacağız.) Şunlar gerekir: daha iyi başlangıç merkez konumları seçmek için k-ortalamanın gelişmiş sürümünü kullanmak.
Matematik hakkında derinlemesine bilgi sahibi olmak gerekli olmasa da k-ortalaması farklı bir olgunun beklentileri maksimuma çıkarma algoritmasını inceleyin. Görüntüleyin konuyla ilgili ders notlarını inceleyin.