Konwergencja w metodzie k-średnich Hartigana-Wonga i innych algorytmach

10

Próbowałem zrozumieć różne algorytmy grupowania k-średnich, które są głównie zaimplementowane w statspakiecie Rjęzyka.

Rozumiem algorytm Lloyda i algorytm online MacQueena. Sposób ich rozumienia jest następujący:

Algorytm Lloyda:

Początkowo wybiera się losowe obserwacje „k”, które będą służyć jako centroidy gromad „k”. Następnie w iteracji następują następujące kroki, aż centroidy zbiegną się.

  1. Obliczana jest odległość euklidesowa między każdą obserwacją a wybranymi centroidami.
  2. Obserwacje najbliższe każdemu z centroidów są oznaczone wewnątrz segmentów „k”.
  3. Średnia wszystkich obserwacji w każdym wiadrze służy jako nowe centroidy.
  4. Nowe centroidy zastępują stare centroidy, a iteracja powraca do kroku 1, jeśli stare i nowe centroidy nie zbiegły się.

Warunki zbieżności są następujące: stare i nowe centroidy są dokładnie identyczne, różnica między centroidami jest niewielka (rzędu 10 ^ -3) lub osiągnięto maksymalną liczbę iteracji (10 lub 100).

Algorytm MacQueena:

Jest to wersja online, w której pierwsze wystąpienia „k” są wybierane jako centroidy.

Następnie każde wystąpienie jest umieszczane w wiadrach w zależności od tego, który środek ciężkości znajduje się najbliżej tego wystąpienia. Odpowiedni środek ciężkości jest ponownie obliczany.

Powtarzaj ten krok, aż każda instancja zostanie umieszczona w odpowiednim wiadrze.

Ten algorytm ma tylko jedną iterację, a pętla działa dla instancji „x”

Algorytm Hartigan-Wong:

  1. Przypisz wszystkie punkty / wystąpienia do losowych segmentów i oblicz odpowiedni centroid.
  2. Zaczynając od pierwszej instancji, znajdź najbliższy środek ciężkości i przypisz wiadro. Jeśli segment zmienił się, należy ponownie obliczyć nowe centroidy, tj. Centroid nowo przypisanego segmentu i centroid starego przypisania segmentu, ponieważ są to dwa centroidy, na które zmiana ma wpływ
  3. Zapętlaj wszystkie punkty i zdobywaj nowe centroidy.
  4. Wykonaj drugą iterację punktów 2 i 3, która wykonuje operację czyszczenia i ponownie przypisuje zbłąkane punkty do prawidłowych segmentów.

Ten algorytm wykonuje 2 iteracje, zanim zobaczymy wynik konwergencji.

Nie jestem pewien, czy to, co myślę w punkcie 4 algorytmu Hartigan-Wong, jest poprawną metodą algorytmu. Moje pytanie brzmi, czy następująca metoda Hartigana-Wonga jest poprawna do implementacji k-średnich? Czy są tylko dwie iteracje dla tej metody? jeśli nie, jaki jest warunek konwergencji (kiedy przestać)?

Innym możliwym wyjaśnieniem implementacji, co rozumiem, jest.

  1. Przypisz wszystkie punkty / wystąpienia do losowych segmentów i oblicz odpowiedni centroid.
  2. Zaczynając od pierwszej instancji, znajdź najbliższy środek ciężkości i przypisz to wiadro. Jeśli segment zmienił się, należy ponownie obliczyć nowe centroidy, tj. Centroid nowo przypisanego segmentu i centroid starego przypisania segmentu, ponieważ są to dwa centroidy, na które zmiana ma wpływ.
  3. Po zmianie w wiadrze dla dowolnego punktu, wróć do pierwszej instancji i powtórz kroki ponownie.
  4. Iteracja kończy się, gdy wszystkie instancje są iterowane i żaden z punktów nie zmienia segmentów.

W ten sposób istnieje wiele iteracji, które zaczynają się od początku zestawu danych za każdym razem, gdy instancja zmienia segmenty.

Wszelkie wyjaśnienia byłyby pomocne i proszę dać mi znać, jeśli nie rozumiem żadnej z tych metod.

Sid
źródło
Co to jest „wiadro”?
Ma ZAKOŃCZENIE - Anony-Mousse,
@ Anony-Mousse „wiadro” to „klaster”. Na przykład: k-średnich służy do dzielenia danych na segmenty / klastry „k”
Sid
Ale potem brzmi jak algorytm MacQueensa.
Ma ZAKOŃCZENIE - Anony-Mousse,
@ Anony-Mousse. tak, oprócz pierwszego kroku, algorytm Hartigan-Wong wydaje się być algorytmem MacQueensa. Ale nie jestem pewien, czy to jest właściwe zrozumienie. Być może brakuje mi koncepcji iteracji i zbieżności.
Sid

Odpowiedzi:

1

Algorytm HW z artykułu z 1979 roku przyjmuje jako początkowe klastry wejściowe. Jednak autorzy sugerują metodę ich uzyskania w ostatnim rozdziale. Piszą, że gwarantuje się, że żaden klaster nie będzie pusty po początkowym przypisaniu do podprogramu . Wygląda to następująco:

  1. x¯
  2. x¯||xix¯||2
  3. {1+(L1)[M/K]}L=1,,K[  ]1

Jeśli chodzi o główny algorytm, opisano go w artykule o nazwie K-Means Hartigana kontra K-Means Lloyda - Czy to czas na zmianę? autor: N Słonim, E Aharoni, K Crammer, opublikowany w 2013 r. przez AJCAI . Pamiętaj, że ta wersja używa po prostu losowej partycji początkowej. To idzie w następujący sposób.

xXK

  1. CXKCCvC

  2. XxX

    s=1

    xCC=C{x}

    C+={argminC(CC)C 1nd(x,vC)+1nyC[d(y,vCx)d(y,vC)]}{x}

    C+CCCCC+vCvCs0

  3. s=0

CargminxCdvCvC{x}

Myślę, że odpowiedzi na wszystkie twoje pytania są zawarte w powyższym algorytmie ... Jednak wciąż muszę upewnić się, że ta implementacja algorytmu jest standardowa . W szczególności, jeśli jest to ten wdrożony w R. Wszelkie komentarze / edycje są mile widziane.

Perochkin
źródło