K-oznacza: ile iteracji w sytuacjach praktycznych?

10

Nie mam doświadczenia w branży eksploracji danych ani dużych zbiorów danych, więc chciałbym usłyszeć, jak dzielisz się doświadczeniami.

Czy ludzie faktycznie używają k-średnich, PAM, CLARA itp. Na naprawdę dużym zbiorze danych? Czy po prostu losowo wybierają z niego próbkę? Jeśli po prostu pobiorą próbkę zestawu danych, czy wynik byłby wiarygodny, gdyby zestaw danych nie był normalnie dystrybuowany?

Czy w praktycznych sytuacjach podczas uruchamiania tych algorytmów możemy powiedzieć, ile iteracji normalnie zajmie, dopóki nie nastąpi konwergencja? Czy liczba iteracji zawsze rośnie wraz z rozmiarem danych?

Pytam o to, ponieważ myślę o opracowaniu podejścia do zakończenia algorytmów iteracyjnych przed konwergencją, a mimo to wyniki są nadal do przyjęcia. Myślę, że warto spróbować, jeśli liczba iteracji wynosi, powiedzmy, ponad 1000, abyśmy mogli zaoszczędzić trochę czasu i kosztów obliczeń. Co myślisz?

bla
źródło
number of iterations always grow with the data sizeNiekoniecznie.
ttnphns
Istnieją różne kryteria zatrzymania iteracji w K-średnich. Co ciekawe, jednym z rozsądnych sposobów jest po prostu ustawienie liczby iteracji na stałą wartość (powiedzmy 10 lub 20). Środki K są przeznaczone do szybkich metod, dlatego jeśli chcesz, aby kryterium konwergencji było sprawdzane po każdej iteracji, kryterium to musi być łatwe / szybkie do obliczenia.
ttnphns
1
Czy istnieje jakiś „naukowy” sposób ustalenia maksymalnej liczby iteracji, które należy wykonać?
foo
Twój ostatni komentarz to dobre pytanie. Szczerze mówiąc nie wiem. może inni ludzie odpowiedzą na to pytanie.
ttnphns

Odpowiedzi:

6
  1. K-znaczy jest tani. Możesz sobie pozwolić na uruchomienie go przez wiele iteracji.

  2. Istnieją złe algorytmy (standardowy) i dobre algorytmy. W przypadku dobrych algorytmów późniejsze iteracje często kosztują znacznie mniej niż 1% pierwszej iteracji.

  3. Są naprawdę powolne wdrożenia. Nie używaj ich.

  4. Środki „K” na „dużych” danych nie istnieją. Ponieważ działa tylko na niskowymiarowych danych wektorowych. Z takimi danymi nie przekroczysz pamięci nowoczesnego serwera. tak, istnieją większe dane - ale nie można użyć k-średnich, powiedzmy miesiąc danych na Twitterze, ponieważ nie przyniesie to nic użytecznego.

Przy dobrej implementacji, na nowoczesnym serwerze, największy zbiór danych, w którym można znaleźć, gdzie k-średnich nadal daje użyteczny wynik, prawdopodobnie potrzebuje mniej niż 1 minutę do obliczenia aż do konwergencji. Po co więc zastanawiać się nad limitem iteracji?

Ma ZAKOŃCZENIE - Anony-Mus
źródło
1
Zgodzić się. W tym artykule ( Skalowalne K-średnie przez wyszukiwanie rankingowe ) autorzy stwierdzili, że K-średnie zbiega się po 20-50 iteracjach we wszystkich praktycznych sytuacjach, nawet w testowanych zestawach danych o dużych wymiarach. Czy oprócz K-średnich znasz jakiś algorytm, który wymaga ogromnej liczby iteracji aż do konwergencji?
foo
Może trenujesz SVM? Wierzę, że jest iteracyjny, próbuje znaleźć najlepszy (i najmniejszy, ponieważ przewidywanie zależy od tego!) Zestaw wektorów pomocniczych.
Ma ZAKOŃCZENIE - Anony-Mousse
Oczywistym rozwiązaniem dla uruchomienia k-średnich na zestawach danych o dużych wymiarach jest uruchomienie PCA lub innej metody redukcji wymiarów, a następnie uruchomienie k-średnich
nico