Wiem, że k-średnie jest zwykle optymalizowane przy użyciu Maksymalizacji oczekiwań . Jednak moglibyśmy zoptymalizować jego funkcję utraty w ten sam sposób, w jaki zoptymalizowaliśmy każdy inny!
Znalazłem kilka artykułów, które faktycznie używają stochastycznego spadku gradientu dla dużych k-średnich, ale nie mogłem uzyskać odpowiedzi na moje pytanie.
Czy ktoś wie, dlaczego tak jest? Czy to dlatego, że maksymalizacja oczekiwań zbiega się szybciej ? Czy ma jakąś szczególną gwarancję? Czy jest to powód historyczny ?
Odpowiedzi:
Jak wspomina PO, możliwe jest rozwiązanie k-średnich za pomocą opadania gradientu, co może być przydatne w przypadku problemów na dużą skalę.
Z pewnością istnieją historyczne powody występowania algorytmów w stylu EM do rozwiązywania średnich k (tj. Algorytmu Lloyda). Algorytm Lloyda jest tak popularny, że ludzie nazywają go czasem „algorytmem k-średnich”, a nawet nie zdają sobie sprawy z istnienia innych podejść. Ale ta popularność nie jest niezasłużona.
Bottou i Bengio (1995) wykazali, że algorytm Lloyda jest równoważny z optymalizacją funkcji kosztu k-średnich metodą Newtona. W ogólnych problemach z optymalizacją metody drugiego rzędu, takie jak metoda Newtona, mogą zbiegać się szybciej niż metody pierwszego rzędu, takie jak opadanie gradientu, ponieważ wykorzystują informacje na temat krzywizny funkcji celu (a metody pierwszego rzędu nie). W eksperymencie na znanym zestawie danych Iris wykazano, że algorytm Lloyda rzeczywiście zbiegał się szybciej niż spadek gradientu. Byłoby interesujące zobaczyć to porównanie w szerszej gamie zestawów danych.
Bibliografia:
Bottou and Bengio (1995) . Właściwości zbieżności algorytmów k-średnich.
źródło
K-oznacza, że grupowanie nie jest nadzorowane, a najbliższą nienadzorowaną techniką wykorzystującą EM jest klastrowanie oparte na modelach (modele mieszanki Gaussa, GMM). Irytujący problem z klastrowaniem opartym na modelu GMM występuje, gdy wiele cech jest skorelowanych, co powoduje prawie osobliwość w macierzy kowariancji (korelacji) opartej na cechach. W tej sytuacji funkcja prawdopodobieństwa staje się niestabilna, a indeksy warunków osiągają nieskończoność, powodując całkowity rozkład GMM.
Zatem porzućcie ideę EM i kNN - ponieważ opiera się ona na macierzach kowariancji (korelacji) do analizy bez nadzoru. Twoje zapytanie dotyczące optymalizacji przypomina mapowanie Sammon oraz klasyczne metryczne i niemetryczne skalowanie wielowymiarowe (MDS). Mapowanie Sammona jest oparte na iteracji pochodnych, podczas gdy różne formy MDS są zwykle iteracyjnymi lub jednoetapowymi kompozycjami eigend, które można jednak zoptymalizować podczas jednoetapowej operacji macierzowej.
Spoglądając jeszcze raz na twoją prośbę: odpowiedź brzmi: zostało to już zrobione w mapowaniu Sammon.
źródło