Czytam Bishopa o algorytmie EM dla GMM i związku między GMM a k-średnich.
W tej książce jest napisane, że k-średnich jest trudną wersją GMM. Zastanawiam się, czy to implikuje, że jeśli dane, które próbuję skupić, nie są gaussowskie, nie mogę użyć k-średnich (a przynajmniej nie nadaje się do użycia)? Na przykład, co jeśli dane są obrazami cyfr odręcznych, składających się z 8 * 8 pikseli, każdy o wartości 0 lub 1 (i zakładając, że są one niezależne, więc powinna być mieszanką Bernoulli)?
Jestem trochę zdezorientowany i docenię wszelkie przemyślenia.
clustering
data-mining
k-means
gaussian-mixture
eddie.xie
źródło
źródło
Odpowiedzi:
W typowych sytuacjach EM GMM bierze się pod uwagę wariancję i kowariancję. Nie odbywa się to w k-średnich.
Ale w rzeczywistości jedna z popularnych heurystyk dla k-średnich (uwaga: k-średnich jest problemem, a nie algorytmem) - algorytm Lloyda - jest zasadniczo algorytmem EM, wykorzystującym model centroidu (bez wariancji) i trudne przypisania.
Kiedy robisz grupowanie w stylu k-średnich (tj. Minimalizowanie wariancji), ty
Funkcję celu k-średnich można sformalizować w następujący sposób: gdzie to wszystkie możliwe partycje zestawu danych na partycji, to wymiarowość zbioru danych, a np. jest współrzędną tej instancji w wymiarze . S = { S 1 … S k } k D x j d j d
Powszechnie mówi się, że k-średnie zakłada skupiska sferyczne. Powszechnie wiadomo również, że k-średnie klastry to komórki Voronoi, tj. Nie sferyczne. Oba są poprawne i oba są błędne. Przede wszystkim gromady nie są kompletnymi komórkami Voronoi, a jedynie znanymi w nich obiektami. Nie ma potrzeby uwzględniania martwej przestrzeni między klastrami jako części obu klastrów, ponieważ posiadanie obiektu wpłynęłoby na wynik algorytmu. Ale nie jest o wiele lepiej nazywać to „sferycznym”, tylko dlatego, że odległość euklidesowa jest sferyczna. K-oznacza nie przejmuje się odległością euklidesową. Wszystko to, to heurystyka, aby zminimalizować wariancje . I to właśnie powinno być k-oznacza: minimalizacja wariancji.
źródło
minimize squared euclidean distance
lubminimize the variances
? Muszą być słowa „suma” lub „pula” lub podobne, ponieważ mamy ponad 2 klastry, prawda?coincidentally minimize Euclidean distance, because the sqrt function is monotone
jest, mówiąc precyzyjnie, niepoprawny.minimize squared Euclidean distance, because WCSS variance contribution = squared euclidean distance
myśli ? Czy mówisz „kwadraty d między obiektami w klastrach zostają zminimalizowane, ponieważ minimalizuje się odchylenia WCSS”, czy po prostu „minimalizuje się odchylenia WCSS, które - odchylenia - są z natury odległościami euklidesowymi”? Czy coś jeszcze?GMM wykorzystuje zachodzące na siebie wzgórza, które rozciągają się do nieskończoności (ale praktycznie liczą się tylko dla 3 sigma). Każdy punkt otrzymuje wszystkie wyniki prawdopodobieństwa wzgórz. Ponadto wzgórza mają „jajowaty kształt” [w porządku, są to symetryczne elipsy ] i przy użyciu pełnej macierzy kowariancji można je przechylać .
K-znaczy twardo przypisuje punkt do jednego skupienia, więc wyniki innych ośrodków skupień są ignorowane (domyślnie są zerowane / nie przejmuj się). Wzgórza to kuliste bańki mydlane. Tam, gdzie dotykają się dwa bańki mydlane, granica między nimi staje się płaską (hiper) płaszczyzną. Podobnie jak podczas dmuchania piany z wielu baniek mydlanych, bąbelki wewnątrz nie są płaskie, ale są pudełkowate, więc granice między wieloma (hiper) sferami faktycznie tworzą przegrodę Voronoi przestrzeni. W 2D wydaje się to niejasno przypominać sześciokątne ciasne upakowanie, pomyśl o ulu pszczół (chociaż oczywiście komórki Voronoi nie są gwarantowane jako sześciokąty). Wzgórze K oznacza, że jest okrągłe i nie przechyla się, więc ma mniejszą siłę reprezentacji; ale obliczenia są znacznie szybsze, szczególnie w wyższych wymiarach.
Ponieważ K-oznacza używa metryki odległości euklidesowej, zakłada, że wymiary są porównywalne i mają taką samą wagę. Więc jeśli wymiar X ma jednostki mil na godzinę, w zakresie od 0 do 80, a wymiar Y ma jednostki funtów, w zakresie od 0 do 400, a ty dopasowujesz koła w tej przestrzeni XY, to jeden wymiar (i jego rozpiętość) będzie silniejszy niż inny wymiar i przyćmie wyniki. Dlatego zwyczajowo znormalizuje się dane podczas przyjmowania K-średnich.
Zarówno GMM, jak i K-znaczy modelują dane, dopasowując najlepsze przybliżenia do podanych danych. GMM pasuje do jaja przechylonego, a K-oznacza pasuje do kuleczek rozłożonych. Ale podstawowe dane mogą mieć dowolny kształt, może to być spirala lub obraz Picassa, a każdy algorytm nadal działałby i strzelał jak najlepiej. To, czy wynikowy model wygląda jak rzeczywiste dane, zależy od leżącego u podstaw fizycznego procesu generującego dane. (Na przykład pomiary opóźnienia czasowego są jednostronne; czy Gaussa dobrze pasuje? Może.)
W ten sposób twój obraz binarny 8x8 będzie interpretowany jako 64-wymiarowy hipersześcian w pierwszej hiperkwadrantu. Algorytmy wykorzystują analogie geometryczne do znajdowania klastrów. Odległość, wraz ze średnimi K, pojawia się jako odległość euklidesowa w 64-wymiarowej przestrzeni. To jeden ze sposobów, aby to zrobić.
źródło