Dowód zbieżności średnich k

20

W przypadku zadania poproszono mnie o przedstawienie dowodu, że k-średnie zbiega się w skończonej liczbie kroków.

Oto co napisałem:

$C$
$E (C) = \sum_{x} {min}_{i = 1}^{k} {‖ x - c_{i} ‖}^{2}$ $E(C)=\sum_{\mathbf{x}}\min_{i=1}^{k}\left\Vert \mathbf{x}-\mathbf{c}_{i}\right\Vert ^{2}$ $E(C)$

Krok 2 odnosi się do kroku, który oznacza każdy punkt danych najbliższym centrum skupienia, a krok 3 jest krokiem, w którym centra są aktualizowane przy użyciu średniej.

Nie wystarczy to do wykazania zbieżności w skończonej liczbie kroków. Energia może być coraz mniejsza, ale nie wyklucza to możliwości, że punkty centralne mogą skakać bez znacznej zmiany energii. Innymi słowy, może istnieć wiele minimów energii i algorytm może przeskakiwać między nimi, nie?

mathematical-statistics k-means

— jkabrg
źródło

5

Wskazówka: ile może być możliwych zbiorów punktów środkowych?

— whuber

35

Po pierwsze, istnieje co najwyżej sposobów podziału punktów danych na klastrów; każdą taką partycję można nazwać „klastrowaniem”. To duża, ale skończona liczba. Dla każdej iteracji algorytmu tworzymy nowe grupowanie oparte tylko na starym klastrowaniu. Zauważ, że $k^N$ $N$ $k$

jeśli stare grupowanie jest takie samo jak nowe, następne grupowanie będzie znowu takie samo.
Jeśli nowe grupowanie różni się od starego, to nowsze kosztują mniej

Ponieważ algorytm iteruje funkcję, której domeną jest zbiór skończony, iteracja musi ostatecznie wejść w cykl. Cykl nie może mieć długości większej niż ponieważ w przeciwnym razie (2) miałbyś pewne grupowanie, które ma niższy koszt niż sam, co jest niemożliwe. Dlatego cykl musi mieć długość dokładnie . Stąd k-średnie zbiega się w skończonej liczbie iteracji. $1$ $1$

— jkabrg
źródło

Dlaczego zamówienie ma znaczenie? To znaczy, dlaczego

wybieramy

klasterów?

N

$N$

k

$k$

— rrrrr

{\binom{n}{k}}

$\lbrace{n\atop k}\rbrace$

{\binom{n}{k}}

$\lbrace{n\atop k}\rbrace$

k^{N}

$k^N$

6

Aby dodać coś: To, czy algorytm jest zbieżny, zależy również od kryterium zatrzymania. Jeśli zatrzymasz algorytm, gdy przypisania klastra już się nie zmienią, możesz faktycznie udowodnić, że algorytm niekoniecznie jest zbieżny (pod warunkiem, że przypisanie klastra nie ma deterministycznego przerywacza powiązań w przypadku, gdy wiele centroidów ma taką samą odległość).

Tutaj masz 8 punktów danych (kropki) i dwa centroidy (czerwone krzyżyki). Teraz zielone punkty danych mają tę samą odległość zarówno od lewej, jak i od prawej centroidu. To samo dotyczy niebieskich punktów danych. Załóżmy, że w tym przypadku funkcja przypisania nie jest deterministyczna. Dalej zakładamy, że w iteracji 1 zielone kropki zostają przypisane do lewej gromady, a niebieskie kropki są przypisane do prawej gromady. Następnie aktualizujemy centroidy. Okazuje się, że w rzeczywistości pozostają w tym samym miejscu. (jest to łatwe obliczenie. Dla lewego środka ciężkości uśredniasz współrzędne dwóch lewych czarnych kropek i dwóch zielonych kropek -> (0, 0,5). To samo dla prawego środka ciężkości).

Następnie w iteracji 2 sytuacja wygląda ponownie tak samo, ale teraz zakładamy, że nasza (w przypadku powiązań) niedeterministyczna funkcja przypisywania przypisuje zielone kropki do prawego skupienia, a niebieskie kropki do lewego skupienia. Znów centroidy się nie zmienią.

Iteracja 3 jest znowu taka sama jak iteracja 1. Mamy zatem przypadek, w którym przypisania klastra ciągle się zmieniają, a algorytm (z tym kryterium zatrzymania) nie jest zbieżny.

$\leq$ $\lt$

— Rauwuckl
źródło