Daha önce de belirtildiği gibi, birçok kümelendirme algoritması, makine öğrenimde kullanılan ve genellikle milyonlarca örnek içeren veri kümeleriyle ölçeklendirilemez. Örneğin, birleştirme veya bölme hiyerarşik kümeleme algoritmaları tüm nokta çiftlerini inceler ve sırasıyla \(O(n^2 log(n))\) ve \(O(n^2)\)karmaşıklığına sahiptir.
Bu kurs, kullanıcı tarafından seçilen küme sayısı \(k\)olduğunda \(O(nk)\)olarak ölçeklendirildiği için k-ortalama yöntemine odaklanır. Bu algoritma, her bir nokta ile kümesinin merkez noktası arasındaki mesafeleri en aza indirerek noktaları\(k\) kümeler halinde gruplandırır (Şekil 1'e bakın).
Sonuç olarak k-ortalama, verileri yaklaşık olarak dairesel bir dizi dağılımdan oluştuğu şekilde etkili bir şekilde ele alır ve bu dağılımlara karşılık gelen kümeler bulmaya çalışır. Ancak gerçek dünyadaki veriler aykırı değerler ve yoğunluğa dayalı kümeler içerir ve k-ortalama yönteminin temelindeki varsayımlarla eşleşmeyebilir.
k-ortalama kümeleme algoritması
Algoritma şu adımları izler:
\(k\)için daha sonra düzeltilebilecek ilk tahmininizi girin. Bu örnekte \(k = 3\)seçeneğini belirleyeceğiz.
Rastgele \(k\) merkez noktaları seçin.
Şekil 1: İlk kullanıma hazırlama sırasında k-ortalama. \(k\) İlk kümeleri elde etmek için her noktayı en yakın merkez noktaya atayın.
Şekil 2: İlk kümeler. Her küme için kümedeki tüm noktaların ortalama konumunu alarak yeni bir merkez noktası hesaplayın. Şekil 4'teki oklar, ağırlık merkezi konumlarındaki değişikliği gösterir.
Şekil 3: Yeniden hesaplanan ağırlık merkezleri. Her noktayı en yakın yeni merkez noktaya yeniden atayın.
Şekil 4: Yeniden atama sonrası kümeler. Noktaların küme değiştirmesi durana kadar 4. ve 5. adımları tekrarlayın, ağırlık merkezlerini ve küme üyeliğini yeniden hesaplayın. Büyük veri kümelerinde, diğer ölçütlere göre algoritmayı yakınsamadan önce durdurabilirsiniz.
Orta nokta konumları başlangıçta rastgele seçildiğinden k-ortalama, art arda çalıştırmalarda önemli ölçüde farklı sonuçlar döndürebilir. Bu sorunu çözmek için k-means'i birden fazla kez çalıştırın ve en iyi kalite metriklerini içeren sonucu seçin. (Kalite metriklerini bu kursun ilerleyen bölümlerinde açıklayacağız.) Daha iyi ilk merkez nokta konumları seçmek için k-ortalamaların gelişmiş bir sürümüne ihtiyacınız vardır.
Matematik hakkında ayrıntılı bilgi sahibi olmanız gerekmese de merak edenler için k-ortalama, beklenti maksimizasyon algoritmasının özel bir durumudur. UPenn'deki konuyla ilgili konferans notlarına bakın.