Dlaczego k-znaczy nie daje globalnego minimum?

Czytałem, że algorytm k-średnich jest zbieżny tylko z lokalnym minimum, a nie globalnym minimum. Dlaczego to? Mogę logicznie myśleć o tym, w jaki sposób inicjalizacja mogłaby wpłynąć na końcowe grupowanie i istnieje możliwość nieoptymalnego grupowania, ale nie znalazłem niczego, co matematycznie to udowodni.

Ponadto, dlaczego k-oznacza proces iteracyjny? Czy nie możemy po prostu częściowo rozróżnić funkcji celu wrt na centroidy, zrównując ją do zera, aby znaleźć centroidy, które minimalizują tę funkcję? Dlaczego musimy używać opadania gradientu, aby krok po kroku osiągnąć minimum?

Możesz zobaczyć k-średnich jako specjalną wersję algorytmu EM, która może trochę pomóc.

Załóżmy, że szacujesz wielowymiarowy rozkład normalny dla każdego klastra z macierzą kowariancji ustaloną dla macierzy tożsamości dla wszystkich, ale zmienna średnia gdzie jest indeksem klastra. Oczywiście, jeśli parametry są znane, możesz przypisać każdemu punktowi jego klaster maksymalnego prawdopodobieństwa (tj. dla którego odległość do minimalna). Algorytm EM dla tego problemu jest prawie równoważny z k-średnich. i { μ i } p μ i$\mu_i$$i$$\{\mu_i\}$$p$$\mu_i$$p$

Odwrotnie, jeśli wiesz, które punkty należą do której grupy, możesz oszacować optymalne . Rozwiązanie tego zamkniętego formularza (które znajduje globalne optimum) w zasadzie mówi, że aby znaleźć modele o maksymalnym prawdopodobieństwie , integrujesz wszystkie możliwe przypisania punktów do klastrów. Ponieważ nawet przy zaledwie trzydziestu punktach i dwóch klastrach istnieje około miliarda takich możliwych zadań, jest to niemożliwe do obliczenia. { μ I$\mu_i$$\{\hat\mu_i\}$

Zamiast tego możemy zgadywać parametry ukryte (lub parametry modelu) i iterować dwa kroki (z możliwością uzyskania lokalnego maksimum). Jeśli pozwolisz, aby każda klaster wzięła częściową odpowiedzialność za punkt, skończysz na EM, jeśli po prostu przydzielisz optymalną klaster, otrzymasz k-średnich.

Podsumowanie: w ujęciu probabilistycznym istnieje rozwiązanie globalne, ale wymaga iteracji we wszystkich możliwych klastrach. Oczywiście, jeśli masz funkcję celu, to samo jest prawdą. Możesz iterować wszystkie rozwiązania i maksymalizować funkcję celu, ale liczba iteracji ma wykładniczy rozmiar twoich danych.

To jest problem, który chcesz rozwiązać:

$$\begin{align} &\min_{x} \sum_{i=1}^n \sum_{j=1}^k x_{ij} || p_i - c_j||^2\\ &\text{subject to:} \\ &\sum_{j=1}^k x_{ij} = 1 \quad \forall i\\ & c_j\textit{ is the centroid of cluster j}\\ &x_{ij} \in \{0,1\} \quad \forall i, j \\ \end{align}$$

Zmienna binarna wskazuje, czy punkt jest przypisany do klastra . Symbole i oznaczają współrzędne tego punktu ciężkości i z p klastra, odpowiednio. Oba znajdują się w , gdzie to wymiarowość punktów danych. i j p i c j i j R d$x_{ij}$$i$$j$$p_i$$c_j$$i$$j$$\mathbb{R}^d$$d$

Pierwsza grupa ograniczeń mówi, że każdy punkt powinien być przypisany do dokładnie jednego klastra. Druga grupa ograniczeń (której nie zdefiniowaliśmy matematycznie) mówi, że współrzędne środka ciężkości gromady faktycznie zależą od wartości zmiennych . Możemy na przykład wyrazić to ograniczenie w następujący sposób: x i j c j = ∑ i x i j p i $j$$x_{ij}$

$$\begin{equation} c_j = \frac{\sum_{i} x_{ij} p_{ij}}{\sum_{i} x_{ij}} \end{equation}$$

Jednak zamiast radzić sobie z tymi nieliniowymi ograniczeniami, w K-środkach (w przybliżeniu) rozwiązujemy inny problem, który ma takie samo optymalne rozwiązanie jak nasz pierwotny problem:

$$\begin{align} &\min_{x} \sum_{i=1}^n \sum_{j=1}^k x_{ij} || p_i - y_j||^2\\ &\text{subject to:} \\ &\sum_{j=1}^k x_{ij} = 1 \quad \forall i\\ &x_{ij} \in \{0,1\} \quad \forall i, j \\ &y_j \in \mathbb{R}^d \quad \forall j \end{align}$$

Zamiast minimalizować odległość do centroidów, minimalizujemy odległość do dowolnego zestawu punktów, który da lepsze rozwiązanie. Okazuje się, że te punkty to dokładnie centroidy.

Aby rozwiązać ten problem, wykonujemy kroki 2-3 tego algorytmu, aż do uzyskania zbieżności:

1. Przypisz niektóre wartości do zmiennych$y_j$
2. Napraw wartości i znajdź optymalne wartości dla zmiennych .$y_{j}$$x_{ij}$
3. Napraw wartości zmiennych i znajdź optymalne wartości dla .$x_{ij}$$y_{j}$

Na każdym etapie funkcja celu poprawia się (lub pozostaje taka sama, gdy algorytm się zbiega), ponieważ rozwiązanie znalezione w poprzednim kroku znajduje się w przestrzeni wyszukiwania bieżącego kroku. Ponieważ jednak naprawiamy niektóre zmienne na każdym etapie, jest to procedura wyszukiwania lokalnego, która nie gwarantuje optymalności.

Na szczęście problemy optymalizacji w krokach 2 i 3 można rozwiązać w formie zamkniętej. Jeśli wiemy (tzn. Jeśli wiemy, do którego klastra przypisano każdy punkt), najlepszymi wartościami dla zmiennych są centroidy klastrów. Jeśli znamy wartości dla , oczywiście najlepszym wyborem dla zmiennych jest przypisanie każdego punktu do najbliższego . $x_{ij}$$y_j$$y_j$$x_{ij}$$y_j$

Prosty przykład może pomóc ...

Zdefiniujmy zbiór punktów, które mają być grupowane jako A = {1,2,3,4}.

Załóżmy, że próbujesz znaleźć 2 odpowiednie klastry dla A (2-średnie). Istnieją (co najmniej) dwa różne ustawienia, które spełniają warunek stacjonarny k-średnich.

Ustawienie 1:

Center1 = 1, Cluster1 = {1}
Center2 = 3, Cluster1 = {2,3,4}

Tutaj celem jest 2. W rzeczywistości jest to punkt siodłowy (spróbuj center1 = 1 + epsiloni center1 = 1 - epsilon)

Ustawienie 1:

Center1 = 1.5, Cluster1 = {1,2}
Center2 = 3.5, Cluster1 = {3,4}

tutaj celem jest 1/4.

Gdyby k-średnich zostało zainicjowanych jako pierwsze ustawienie, wówczas utknęłoby ... i to wcale nie jest globalne minimum.

Możesz użyć wariantu z poprzedniego przykładu, aby utworzyć dwa różne lokalne minima. Za A = {1,2,3,4,5}ustawienie cluster1={1,2}i cluster2={3,4,5}wynikałoby z tej samej wartości celu co cluster1={1,2,3}icluster2={4,5}

Wreszcie, co by się stało, gdybyś wybrał

A = {1,2,3,4,6}
center1={2.5} cluster1={1,2,3,4} and 
center1={6} cluster1={6}

vs

center1={2} cluster1={1,2,3} and 
center1={5} cluster1={4,6}

?

[To było przed odpowiedzią @Peter]
Po krótkiej dyskusji (w sekcji komentarzy) czuję, że muszę odpowiedzieć na własne pytanie.

Wierzę, że kiedy częściowo różnicuję funkcję celu w odniesieniu do jednego centroidu, punkty w gromadzie innego centroidu znikają w pochodnej. Tak więc centroid, który możemy uzyskać, zminimalizuje tylko sumę kwadratowych odległości tylko określonej gromady.

@whuber dodaje:

To po części to, ale tak naprawdę nie wyjaśnia zachowania. Bardziej istotny jest fakt, że przypisanie punktów do centroidów jest dużą częścią tego, co robi k-średnie. (Po wykonaniu przypisania centroidy można łatwo obliczyć i nie ma już nic do zrobienia.) To przypisanie jest dyskretne: w ogóle nie można go rozróżnić.

Byłoby wspaniale, gdyby ktoś miał coś więcej do dodania.

Wszyscy wszystko wyjaśnili, ale chciałbym dodać, że jeśli przykładowe dane nie są dystrybuowane jako rozkład Gaussa, wówczas mogą utknąć w lokalnych minimach. W algorytmie K-średnich próbujemy to osiągnąć.