Dlaczego algorytm klastrowania k-oznacza używa wyłącznie metryki odległości euklidesowej?

Czy jest jakiś konkretny cel pod względem wydajności lub funkcjonalności, dlaczego algorytm k-średnich nie wykorzystuje na przykład podobieństwa (dis) cosinusa jako metryki odległości, a może jedynie stosować normę euklidesową? Zasadniczo, czy metoda K-oznacza jest zgodna i poprawna, gdy rozważa się lub stosuje inne odległości niż euklidesowe?

[Dodane przez @ttnphns. Pytanie jest dwojakie. „(Nie) euklidesowa odległość” może dotyczyć odległości między dwoma punktami danych lub odległości między punktem danych a centrum klastrów. Do tej pory próbowano rozwiązać oba sposoby w odpowiedziach.]

Procedura K-Means - która jest metodą kwantyzacji wektorowej często stosowaną jako metoda grupowania - w ogóle nie używa jawnie par danych odległości czarno-białych punktów danych (w przeciwieństwie do hierarchicznej i niektórych innych klastrów, które pozwalają na dowolne pomiary bliskości). Sprowadza się to do wielokrotnego przypisywania punktów najbliższemu centroidowi, wykorzystując w ten sposób odległość euklidesową od punktów danych do centroidu . Jednak K-średnie jest pośrednio oparte na parach danych euklidesowych odległości b / w punktów danych, ponieważ suma kwadratowych odchyleń od środka ciężkości jest równa sumie par kwadratowych odległości euklidesowych podzielonych przez liczbę punktów. Sam termin „centroid” pochodzi z geometrii euklidesowej. Jest to wielowymiarowa średnia w przestrzeni euklidesowej. Przestrzeń euklidesowa dotyczy odległości euklidesowych. Odległości inne niż euklidesowe zasadniczo nie obejmują przestrzeni euklidesowej. Dlatego K-Means jest przeznaczony wyłącznie na odległości euklidesowe.

Ale odległość euklidesowa między dwoma punktami danych może być reprezentowana na wiele alternatywnych sposobów . Na przykład jest ściśle związany z cosinusem lub iloczynem skalarnym między punktami. Jeśli masz cosinus, kowariancję lub korelację, zawsze możesz (1) przekształcić ją na (kwadrat) odległość euklidesową, a następnie (2) utworzyć dane dla tej macierzy odległości euklidesowych (za pomocą głównych współrzędnych lub innych form metrycznych Wielowymiarowe skalowanie) do (3) wprowadź te dane do grupowania K-średnich. Dlatego możliwe jest, aby K-środki „działały” z parami cosinusów lub tym podobne; w rzeczywistości istnieją takie implementacje klastrowania K-średnich. Zobacz też o implementacji „K-średnich dla macierzy odległości”.

Oczywiście możliwe jest zaprogramowanie średnich K w sposób, który oblicza bezpośrednio na macierzy kwadratowej par euklidesowych odległości, oczywiście. Ale będzie działać powoli, więc bardziej efektywnym sposobem jest tworzenie danych dla tej macierzy odległości (przekształcanie odległości w produkty skalarne i tak dalej - przejście, które opisano w poprzednim akapicie) - a następnie zastosowanie standardowej procedury K-średnich do tego zestawu danych.

Zauważ, że dyskutowałem na ten temat, czy odmienność euklidesowa lub zerowa między punktami danych jest zgodna z K-średnich. Jest to związane z, ale nie do końca tym samym pytaniem, czy odchylenia nonuclidean od środka ciężkości (w szerokim znaczeniu, środka lub kwaziczycy) mogą być włączone do K-średnich lub zmodyfikowanych „K-średnich”.

Zobacz powiązane pytanie K-średnie: Dlaczego minimalizowanie WCSS maksymalizuje Odległość między klastrami? .

Zobacz także odpowiedź @ttnphns na interpretację k-średnich, która faktycznie obejmuje punktowe odległości euklidesowe.

Sposób, w jaki k-średnich jest konstruowany, nie opiera się na odległościach .

Średnie K minimalizuje wariancję wewnątrz klastra. Teraz, jeśli spojrzysz na definicję wariancji, jest ona identyczna z sumą kwadratowych odległości euklidesowych od centrum. (Odpowiedź @ttnphns odnosi się do par euklidesowych odległości!)

Podstawową ideą k-średnich jest minimalizacja błędów kwadratu . Nie ma tu mowy o „odległości”.

Dlaczego niewłaściwe jest stosowanie arbitralnych odległości: ponieważ średnie k mogą przestać zbieżne z innymi funkcjami odległości . Powszechny dowód na konwergencję jest taki: krok przypisania i średni krok aktualizacji optymalizują to samo kryterium. Możliwa jest skończona liczba zadań. Dlatego musi zbiegać się po skończonej liczbie ulepszeń. Aby użyć tego dowodu do innych funkcji odległości, musisz pokazać, że średnia (uwaga: k- oznacza ) również minimalizuje Twoje odległości.

Jeśli szukasz wariantu k-średnich na Manhattanie, są mediany-k. Ponieważ mediana jest znanym najlepszym estymatorem L1.

Jeśli chcesz dowolnych funkcji odległości, spójrz na k-medoidy (aka: PAM, partycjonowanie wokół medoidów). Medoid minimalizuje dowolne odległości (ponieważ jest zdefiniowany jako minimum), a istnieje także skończona liczba możliwych medoidów. Jest jednak znacznie droższy niż średnia.

Być może jestem tu trochę pedantyczny, ale K-średnich to nazwa nadana określonemu algorytmowi, który przypisuje etykiety do punktów danych, tak że wariancje klastrów są zminimalizowane, i nie jest to nazwa „ogólnej techniki”.

Algorytm K-średnich został niezależnie zaproponowany z kilku pól, z silnymi interpretacjami mającymi zastosowanie do tego pola. Ładnie okazuje się, że jest to także euklidesowa odległość do centrum. Aby zapoznać się z krótką historią K-średnich, przeczytaj Grupowanie danych: 50 lat ponad K-średnich

Istnieje wiele innych algorytmów klastrowych, które wykorzystują metryki inne niż euklidesowe. Najbardziej ogólny przypadek, jaki znam, polega na wykorzystaniu Dywergencji Bregmana do grupowania, z których Euklides jest szczególnym przypadkiem.

Ponieważ jest to najwyraźniej teraz pytanie kanoniczne i nie zostało tu jeszcze wspomniane:

$\mathbb R^d$$\varphi : \mathbb R^p \to \mathcal H$$d$$d(x, y) = \lVert \varphi(x) - \varphi(y) \rVert_{\mathcal H}$$\{ \varphi(x_i) \}$$\varphi$$k(x, y) = \langle \varphi(x), \varphi(y) \rangle_{\mathcal H}$

W tej sytuacji, w standardowym (Lloyda) algorytmie k-średnich, możemy łatwo przypisywać punkty do ich klastrów, ale pośrednio reprezentujemy centra klastrów (jako liniowe kombinacje punktów wejściowych w przestrzeni Hilberta). Znalezienie najlepszej reprezentacji w przestrzeni wejściowej wymagałoby znalezienia środka Frécheta , który jest dość drogi. Łatwiej jest więc uzyskać zadania klastra za pomocą jądra, trudniej jest zdobyć środki.

Poniższy artykuł omawia ten algorytm i odnosi go do grupowania widmowego:

I. Dhillon, Y. Guan i B. Kulis. K-średnie jądra, klastry spektralne i znormalizowane cięcia. KDD 2005.

Przeczytałem tutaj wiele interesujących komentarzy, ale dodam, że „osobista” implementacja k-średnich Matlaba obsługuje 4 nie-euklidesowe odległości [między punktami danych a centrami klastrów]. Jedyny komentarz z dokumentacji, którą widzę na ten temat, to:

Miara odległości, w przestrzeni p-wymiarowej, używana do minimalizacji, określona jako para oddzielona przecinkami, składająca się z „Odległości” i łańcucha.

kmeans oblicza klastry centroidów inaczej dla różnych obsługiwanych miar odległości. Ta tabela podsumowuje dostępne miary odległości. We wzorach x jest obserwacją (czyli rzędem X), a c jest centroidem (wektorem rzędu).

Następnie lista funkcji ci xnastępuje. Biorąc zatem pod uwagę pwymiarowość danych wejściowych, wydaje się, że żadne osadzanie euklidesowe nie jest wcześniej przeprowadzane.

BTW w przeszłości używałem k-średnich Matlaba z odległością korelacji i (co nie jest zaskoczeniem) robiło to, co powinno.

Od tutaj :

Rozważmy dwa dokumenty A i B reprezentowane przez wektory na powyższym rysunku. Cosinus traktuje oba wektory jako wektory jednostkowe, normalizując je, co daje miarę kąta między dwoma wektorami. Zapewnia dokładną miarę podobieństwa, ale bez względu na wielkość. Ale wielkość jest ważnym czynnikiem przy rozważaniu podobieństwa.