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

Odpowiedzi:

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 etapiek- 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 dlak-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