Doğa | Veri bölümleme algoritması ( d ) |
---|
İçinde Kisimlandirmaya k anlamına gelmektedir (veya k anlamına gelmektedir İngilizce) yöntemidir bölünmesi veri ve kombinatoryal optimizasyon problemi . Noktalar ve bir tamsayı k verildiğinde sorun, belirli bir işlevi en aza indirmek için noktaları genellikle küme adı verilen k gruplarına bölmektir . Bir noktanın, kümesinin noktalarının ortalamasından uzaklığını ele alıyoruz; minimize edilecek fonksiyon, bu mesafelerin karelerinin toplamıdır.
Bu problem için, çoğu uygulamada kullanılan ve genellikle k- ortalamaları yöntemleri olarak adlandırılan klasik bir buluşsal yöntem vardır . Problem aynı zamanda, örneğin yaklaşım algoritmaları ile klasik bir optimizasyon problemi olarak incelenmiştir .
K - ortalamaları, özellikle gözlemlerin k bölümlere ayrıldığı gözetimsiz öğrenmede kullanılır . Dinamik kümeler her bölüm ortalama daha karmaşık olabilen bir halka ile temsil edildiği için prensip bir genelleme bulunmaktadır. Klasik bir k -ortalama algoritması , Lloyd-Max niceleme algoritması ile aynıdır .
Bir nokta kümesi verildiğinde ( x 1 , x 2 ,…, x n ), n noktaları k kümelerine S = { S 1 , S 2 ,…, S k } ( k ≤ n ) en aza indirerek bölmeye çalışırız . her bölümün içindeki noktalar arasındaki mesafe:
burada μ I noktaların ağırlık merkezi olan S i .
Orijinal fikir 1957'de Hugo Steinhaus tarafından önerilmiş olmasına rağmen, " k-anlamına gelir " terimi ilk kez 1967'de James MacQueen tarafından kullanıldı . Klasik algoritma , 1957'de Stuart Lloyd tarafından darbe kod modülasyonu amacıyla önerildi , ancak piyasaya sürülmedi. Bell Labs dışında 1982'den önce. 1965'te, EW Forgy esasen benzer bir yöntem yayınladı, bu yüzden bazen "Lloyd Forgy'nin yöntemi" olarak adlandırılıyor. Fortran'da kodlanmış daha verimli bir versiyon, 1975 / 1979'da Hartigan ve Wong tarafından yayınlandı.
Problem için, bazen k-ortalamaları yöntemi olarak adlandırılan , pratikte yaygın olarak kullanılan ve ne optimalliği ne de polinom hesaplama süresini garanti etmese de verimli olduğu düşünülen klasik bir algoritma vardır .
Başlatma, sonuçların kalitesinde belirleyici bir faktördür (yerel minimum). Birçok eser bu noktayla ilgilenir. İki genel başlatma yöntemi vardır: Bir yandan Forgy'nin yöntemi ve diğer yandan rastgele bölümleme. Forgy'nin yöntemi, başlangıçtaki araçların k noktasını rastgele seçilen k girdi verisine atar. Rastgele bölümleme, her veri parçasına rastgele bir küme atar ve ardından ilk ortalama noktaların (ilk) hesaplanmasına geçer.
K-ortalama ++, optimum çözümü (global minimum) elde etme olasılığını artıran bir başlatma öneren bir k noktası başlatma algoritmasıdır. Bu yaklaşımın arkasındaki önsezi, başlangıçtaki araçların k noktalarını dağıtmaktır. İlk kümenin ilk ortalama noktası verilerden rastgele seçilir. Daha sonra, her bir ilk ortalama nokta, nokta ile en yakın küme arasındaki mesafenin karesiyle orantılı bir olasılıkla, kalan noktalardan seçilir.
K sınıfları ile sınırlı sayıda olası bölüm vardır . Ek olarak, algoritmanın her adımı maliyet fonksiyonunu kesin olarak azaltır, pozitiftir ve daha iyi bir bölüm ortaya çıkarır. Bu, algoritmanın her zaman sonlu zamanda yakınsadığını, yani sona erdiğini onaylamayı mümkün kılar.
Son bölümleme her zaman optimum değildir. Ek olarak, hesaplama süresi düzlemde bile nokta sayısında üstel olabilir. Uygulamada, yinelemelerin sayısına bir sınır veya yinelemeler arasındaki iyileştirmeye bir ölçüt koymak mümkündür.
At sabit k , pürüzsüz karmaşıklığı noktaları dahil olmak üzere bazı yapılandırmalar için polinom olan Öklid uzayında ve durumda Kullback-Leibler sapma . Eğer k girdinin bir parçasıysa, pürüzsüz karmaşıklık Öklid durumu için hala polinomdur. Bu sonuçlar, algoritmanın pratikteki verimliliğini kısmen açıklamaktadır.
Genel durumda k- ortalamaları sorunu NP-zordur . Öklid durumunda, yerel aramayla oran 9 olan bir polinom yaklaşım algoritması vardır .
Bölümleme için k-araçlarının olası bir dezavantajı, kümelerin başlatmaya ve seçilen mesafeye .
Önceden k parametresini seçmek zorunda olma gerçeği, bir dezavantaj veya bir avantaj olarak algılanabilir. Örneğin, kelime torbasının hesaplanması durumunda , bu, istenen sözlüğün boyutunu tam olarak sabitlemeyi mümkün kılar. Aksine, verilerin belirli bölümlendirilmesinde, böyle bir kısıtlamadan vazgeçilmesi tercih edilecektir.