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

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.

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. $\bar{x}$
2. $\bar{x}$$||x_i - \bar{x}||_2$
3. $\{ 1 + (L-1) [M/K] \}$$L=1, \dots, K$$[\ \cdot\ ]$$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.

$x \in \mathcal{X}$$K$

1. $\mathcal{C}$$\mathcal{X}$$K$$C \in \mathcal{C}$$v_C$

2. $\mathcal{X}$$x \in \mathcal{X}$

   $s = 1$

   $x$$C$$C^{-} = C \setminus \{ x \}$

   $$\begin{align*} C^+ = \Big\{ \mathrm{argmin}_{C^* \in (\mathcal{C} \setminus C) \cup C^{-}}\ \frac{1}{n} d(x,v_C^*) + \frac{1}{n} \sum_{y \in C^*} [d(y,v_{C^* \cup x}) - d(y,v_{C^*})] \Big\} \cup \{ x \} \end{align*}$$

   $C^{+} \neq C$$C \leftarrow C^{-}$$C^* \leftarrow C^{+}$$v_{C}$$v_{C^*}$$s \leftarrow 0$

3. $s=0$

$C^*$$\mathrm{argmin}$$x$$C^*$$d$$v_C$$v_{C^* \cup \{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.