K-średnich jest dobrze znanym algorytmem do tworzenia klastrów, ale istnieje również wariant online takiego algorytmu (K-średnich online). Jakie są zalety i wady tych podejść i kiedy należy je preferować?
K-średnich jest dobrze znanym algorytmem do tworzenia klastrów, ale istnieje również wariant online takiego algorytmu (K-średnich online). Jakie są zalety i wady tych podejść i kiedy należy je preferować?
Odpowiedzi:
K-średnie online (bardziej znane jako sekwencyjne k-średnie ) i tradycyjne k-średnie są bardzo podobne. Różnica polega na tym, że k-średnich online umożliwia aktualizację modelu po otrzymaniu nowych danych.
Online k-średnich należy używać, gdy oczekujesz, że dane będą odbierane jeden po drugim (a może w kawałkach). Umożliwia to aktualizację modelu w miarę uzyskiwania dodatkowych informacji na jego temat. Wadą tej metody jest to, że zależy ona od kolejności odbierania danych ( ref ).
Oryginalna publikacja k-oznacza MacQueen (pierwsza, która używa nazwy „kmeans”) jest algorytmem online.
MacQueen, JB (1967). „Niektóre metody klasyfikacji i analizy obserwacji wielowymiarowych”. Materiały z 5. sympozjum Berkeley na temat statystyki matematycznej i prawdopodobieństwa 1. University of California Press. s. 281–297
Po przypisaniu każdego punktu średnia jest stopniowo aktualizowana za pomocą prostej formuły średniej ważonej (stara średnia jest ważona n, nowa obserwacja jest ważona 1, jeśli średnia miała n obserwacji wcześniej).
O ile mi wiadomo, miało to również być pojedyncze przejście tylko przez dane, chociaż można to wielokrotnie powtarzać w trywialny sposób, aby ponownie przypisać punkty do zbieżności.
MacQueen zwykle zbiera mniej iteracji niż Lloyds, jeśli dane są tasowane (ponieważ aktualizuje średnią szybciej!). Na zamówionych danych może to mieć problemy. Z drugiej strony wymaga więcej obliczeń dla każdego obiektu, więc każda iteracja trwa nieco dłużej (oczywiście dodatkowe operacje matematyczne).