Cykl w algorytmie k-średnich

9

Według wiki najczęściej stosowanym kryterium konwergencji jest „przypisanie się nie zmieniło”. Zastanawiałem się, czy może wystąpić cykl, jeśli zastosujemy takie kryterium konwergencji? Byłbym zadowolony, gdyby ktokolwiek wskazał odniesienie do artykułu, który podaje przykład jazdy na rowerze lub dowodzi, że jest to niemożliwe.

clustering algorithms k-means

— Tomek Tarczyński
źródło

2

Podkreślę (ponieważ to często pomijane), że dowody zbieżności potrzebują (kwadrat) odległości euklidesowej , aby funkcja odległości i funkcja średnia optymalizowały to samo kryterium. Jeśli użyjesz innej odległości (właściwie nie powinieneś używać odległości, ale „najmniejszej sumy kwadratów”), możesz stracić zbieżność w k-średnich.

— Ma ZAKOŃCZENIE - Anony-Mousse

7

Ten dokument wydaje się potwierdzać zbieżność w skończonej liczbie kroków.

— Simon Byrne
źródło

1

Dokładnie tego szukałem!

— Tomek Tarczyński

4

The $k$ -Oznacza, że funkcja celu ściśle zmniejsza się z każdą zmianą przypisania, co automatycznie oznacza zbieżność bez zmiany cyklu. Ponadto partycje produkowane na każdym etapie $k$ - oznacza spełnienie „właściwości Voronoi”, ponieważ każdy punkt jest zawsze przypisany do najbliższego centrum. Oznacza to górną granicę całkowitej liczby możliwych partycji, co daje skończoną górną granicę czasu zakończenia dla $k$ -znaczy.

— Suresh Venkatasubramanian
źródło

Dzięki, intuicyjne jest to, że funkcja celu maleje, ale nie byłam pewna, czy spada ona ściśle. Chciałem się upewnić, że nie ma przypadku patologicznego, tak jak w programowaniu liniowym

— Tomek Tarczynski

No tak i nie. Chociaż jest zbieżny, może zająć wykładniczy czas, podobnie jak simplex. Co więcej, w przypadku obu problemów można pokazać, że „wygładzone” warianty zbiegają się w czasie wielomianowym

— Suresh Venkatasubramanian

2

Ze skończoną precyzją może pojawić się jazda na rowerze.

Jazda na rowerze jest częsta z pojedynczą precyzją, wyjątkowa z podwójną precyzją.

Kiedy wartość jest bliska lokalnego minimum, funkcja celu może czasem nieznacznie wzrosnąć z powodu błędów zaokrąglania. Jest to często nieszkodliwe, ponieważ funkcja algorytmu ponownie maleje i ostatecznie osiąga lokalne minimum. Ale czasami algorytm wkracza na poprzednio odwiedzane zadanie i rozpoczyna cykl.

Obserwowanie cykli w rzeczywistych implementacjach kryteriów zatrzymania jest łatwe i bezpieczne.

— François Pays
źródło