Czy powinniśmy użyć k-znaczy ++ zamiast k-średnich?

Question

k-means++ algorytm pomaga w dwóch następujących punktach oryginalnej K oznacza algorytm:

1. Oryginalny k oznacza algorytm ma najgorszy przypadek czasu super wielomianu wielkości wejściowej działa, natomiast k-means ++ twierdził być O (log k).
2. Znalezione przybliżenie może dać niezadowalający wynik pod względem funkcji celu w porównaniu z optymalnym skupieniem.

Ale czy są jakieś wady k-znaczy ++? Czy powinniśmy od tej pory używać go zamiast k-środków?

Answer 1

Nikt nie twierdzi, że k-means++ działa w O (lg k) czas; jego jakość rozwiązania to O (lg k) - konkurencyjne rozwiązanie optymalne. Zarówno k -maszyny ++, jak i popularna metoda, zwana algorytmem Lloyda, są przybliżeniami do problemu optymalizacji NP-hard.

Nie jestem pewien, w najgorszym przypadku czas działania k -sans ++; zauważ, że w oryginalnym opisie Arthur & Vassilvitskii's kroki 2-4 algorytmu odnoszą się do algorytmu Lloyda. Twierdzą, że w praktyce działa zarówno lepiej, jak i szybciej, ponieważ zaczyna się od lepszej pozycji.

Wady k -means ++ są zatem:

1. To też może znaleźć nieoptymalne rozwiązanie (to wciąż przybliżenie).
2. Nie jest to konsekwentnie szybsze niż algorytm Lloyda (zobacz Tabele Arthura & Vassilvitskii).
3. To bardziej skomplikowane niż ali Lloyda.
4. Jest stosunkowo nowy, a Lloyd's udowodnił, że jest wart ponad 50 lat.
5. Dla niektórych przestrzeni metrycznych mogą istnieć lepsze algorytmy.

Powiedział, że jeśli biblioteka k -means obsługuje k -means ++, to za wszelką cenę go wypróbować.

Answer 2

Nie twoja sprawa, ale łatwym przyspieszenie do jakiejkolwiek metody kmeans dla dużych N:

1) najpierw zrobić kmeans na losowej próbie powiedzieć sqrt (n) punktów
2) Następnie uruchom pełne k-środki z tych ośrodków.

Znalazłem to 5-10 razy szybciej niż kmeans ++ dla N 10000, k 20, z podobnymi wynikami.
jak to działa dla Ciebie będzie zależeć, jak dobrze sqrt (N) próbka przybliża całość, jak również N, DIM, k, ninit, delta ...

Jakie są twoje N (numer punktów danych), dim (liczba funkcji) i k?
Ogromny zakres użytkowników N, dim, k, szum danych, metryki ... nie wspominając o braku publicznych testów porównawczych, sprawiają, że trudno jest porównać metody.

Dodano: kod Pythona dla kmeans() i kmeanssample() to here na SO; komentarze są mile widziane.