Jeśli grupowanie k-średnich jest formą modelowania mieszanki Gaussa, czy można go zastosować, gdy dane nie są normalne?

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.

— eddie.xie
źródło

Jeśli pytasz, czy poprawne jest wykonywanie k-średnich w grupowaniu danych niestandardowych, odpowiedź brzmi „tak”, jeśli zakłada się, że dane są ciągłe. Dane binarne nie są ciągłe. Niektóre osoby używają k-średnich na takich danych, co jest heurystycznie dopuszczalne, ale teoretycznie nieprawidłowe.

— ttnphns

Nie ma modelu prawdopodobieństwa dla średnich k, więc nie ma założenia, że normalność unieważnia. (nie oznacza to, że będzie działać dobrze)

— przypuszcza

@conjectures Hmm ... Ale k-menas jest równoważny GMM, a GMM zakłada normalność.

— eddie.xie

@ttnphns Dziękujemy za odpowiedź! Więc sądzę, że jeśli użyję TF-IDF do przeniesienia tekstu na partytury i uczynienia go ciągłym, to mogę złożyć wniosek i jest ważny?

— eddie.xie

Nagle zdaję sobie sprawę, że GMM jest mieszanką (sumą) kilku gaussów i powinien być w stanie wyrazić dowolny rozkład przy wystarczającej ilości mieszanek. Tak więc, nawet GMM i K-średnie są równoważne, nie oznacza, że K-średnie nie mogą wykorzystywać niestandardowych danych, ponieważ GMM może wyrażać dowolną dystrybucję. Czy to jest poprawne?

— eddie.xie

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

przypadkowo zminimalizuj kwadratową odległość euklidesową, ponieważ udział wariancji WCSS (suma kwadratów w obrębie klastra) = kwadratowa odległość euklidesowa
przypadkowo przypisz obiekty do najbliższego skupienia według odległości euklidesowej, ponieważ funkcja sqrt jest monotoniczna (zauważ, że średnia nie optymalizuje odległości euklidesowych, ale funkcja WCSS)
reprezentują klastry za pomocą tylko środka ciężkości
uzyskać klastry w kształcie komórki Voronoi, tj. wielokąty
działa najlepiej z kulistymi gromadami

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 .

{argmin}_{S.} \sum_{ja = 1}^{k} \sum_{x_{jot} \in {S.}_{ja}} \sum_{re = 1}^{re} {(x_{jot re} - μ_{ja re})}^{2)}

$\text{argmin}_S \sum_{i=1}^{k} \sum_{x_j \in S_i} \sum_{d=1}^{D} \left(x_{jd} - \mu_{id} \right)^2$

S = {S_{1} \dots S_{k}}

$S=\{S_1 \ldots S_k\}$

k

$k$

D

$D$

x_{j d}

$x_{jd}$

j

$j$

d

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

— Anony-Mus-Przywróć Monikę
źródło

Pozwól, że zasugeruję ci trochę ulepszenia wyrażeń - dla większej dokładności. Na przykład, co to jest minimize squared euclidean distancelub minimize the variances? Muszą być słowa „suma” lub „pula” lub podobne, ponieważ mamy ponad 2 klastry, prawda?

— ttnphns

BTW, ponieważ k-średnie minimalizuje sumę d ^ 2 w obrębie klastra podzieloną przez liczbę obiektów w odpowiednim klastrze, twój punkt coincidentally minimize Euclidean distance, because the sqrt function is monotonejest, mówiąc precyzyjnie, niepoprawny.

— ttnphns

Właściwą funkcją celu, dla której można wykazać zbieżność, jest WCSS, suma kwadratów wewnątrz klastra . I rzeczywiście, nie minimalizuje to odległości euklidesowych, ale najbliższa odległość centroid-przez-euklidesowa jest również optymalnym przypisaniem WCSS.

— Anony-Mus-Przywróć Monikę

Twoje sformułowanie pozostaje niestety wątpliwe . Co oznacza wyrażenie 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?

— ttnphns

Oczywiście k-średnich jest dobrym wyborem tylko wtedy, gdy chcesz mieć model centroidu swoich danych. Jeśli chcesz zoptymalizować odległości parami, użyj hierarchicznego grupowania.

— Anony-Mus-Przywróć Monikę

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

$R^n$

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

— Władca Smoków
źródło

Zauważ, że oba algorytmy domyślnie zakładają również, że osie kosmiczne są jednakowo gęste we wszystkich punktach, dlatego dopasowanie danych wykładniczo, logarytmicznie lub sinusoidalnie zwykle korzysta z transformacji wstępnej w celu zmiany mapowania danych na domenę zmienną w przybliżeniu liniowo.

— DragonLord