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?
clustering
k-means
convergence
gradient-descent
minimum
Prateek Kulkarni
źródło
źródło
Odpowiedzi:
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μja ja { μja} p μ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 }μ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.
źródło
To jest problem, który chcesz rozwiązać:
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 dxij i j pi cj i j Rd 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 jj xij
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:
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:
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 .xij yj yj xij yj
źródło
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:
Tutaj celem jest 2. W rzeczywistości jest to punkt siodłowy (spróbuj
center1 = 1 + epsilon
icenter1 = 1 - epsilon
)Ustawienie 1:
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}
ustawieniecluster1={1,2}
icluster2={3,4,5}
wynikałoby z tej samej wartości celu cocluster1={1,2,3}
icluster2={4,5}
Wreszcie, co by się stało, gdybyś wybrał
vs
?
źródło
[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:
Byłoby wspaniale, gdyby ktoś miał coś więcej do dodania.
źródło
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ąć.
źródło