Dlaczego k-znaczy nie daje globalnego minimum?

17

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?

Prateek Kulkarni
źródło
4
Gdy gładka funkcja ma wiele lokalnych minimów, to koniecznie każdy z nich będzie punktem krytycznym (gdzie wszystkie pochodne cząstkowe znikną), więc twój algorytm jest poprawny, ale zazwyczaj jest bezużyteczny: możesz uzyskać strasznie skomplikowane równanie z dużą liczbą rozwiązań (nawet nieskończenie wiele). Ale jest jeszcze jeden problem: skąd wiesz, że funkcja celu k-średnich jest wszędzie zróżnicowana?
whuber
1
Uważam, że kiedy częściowo różnicuję funkcję celu względem 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.
Prateek Kulkarni
3
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ć. Co więcej, jest kombinatorycznie złożony: istnieją O(nk) sposoby przypisywania n punktów do k klastrów. Rzeczywiście, nie ma potrzeby używania opadania gradientu, aby znaleźć centroidy.
whuber
Zgadzam się, części zadania nie można bezpośrednio wprowadzić do postaci matematycznej. Tylko dzięki temu odizolowanemu krokowi możemy przesuwać centroidy, aby zminimalizować funkcję. Oto jak patrzę na zejście gradientu: Jeśli przy złej inicjalizacji jesteśmy blisko lokalnych minimów, zejście gradientu pociągnie cię w dół do lokalnych minimów. Jeśli jesteś blisko globalnych minimów poprzez dobrą inicjalizację, pociągnie to w dół globalnych minimów. Ale sposób, w jaki ten ruch odwzorowuje przypisania do klastrów, jest rozmazany.
Prateek Kulkarni
Nierozróżnialność jest przereklamowana: Leon Bottou wykonał pewne prace nad oszacowaniem K-średnich ze stochastycznym spadkiem gradientu na bardzo dużych zestawach danych, z dużym powodzeniem. Nierozróżnialność nie stanowi tam tak dużego problemu, jak w wielu problemach ze względu na wiele punktów danych. (np. sieci splotowe są również lokalnie nierozróżnialne, ale i tak działają świetnie, podobnie jak wiele architektur sieci neuronowych z rektyfikowaną funkcją transferu liniowego). Prawdziwym powodem są tutaj liczne minima.
bayerj

Odpowiedzi:

10

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 pμjaja{μja}pμip

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 }μi{μ^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.

Piotr
źródło
Dobrze wyłożone! Oznaczę to jako odpowiedź!
Prateek Kulkarni
4

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

minxi=1nj=1kxij||picj||2subject to:j=1kxij=1icj is the centroid of cluster jxij{0,1}i,j

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 dxijijpicjijRdd

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 jjxij

cj=ixijpijixij

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:

minxi=1nj=1kxij||piyj||2subject to:j=1kxij=1ixij{0,1}i,jyjRdj

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 zmiennychyj
  2. Napraw wartości i znajdź optymalne wartości dla zmiennych .yjxij
  3. Napraw wartości zmiennych i znajdź optymalne wartości dla .xijyj

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 . xijyjyjxijyj

Behrouz Babaki
źródło
2

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}

?

użytkownik25611
źródło
0

[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.

Prateek Kulkarni
źródło
0

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ąć.

poszukiwacz
źródło
Myślę, że masz na myśli raczej „unimodal” niż Gaussa
Peter Leopold