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

62

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

ciekawy
źródło
To pytanie zostało zadane około 10 razy na Stackoverflow i tej stronie. Proszę skorzystać z funkcji wyszukiwania.
Anony-Mousse
3
@ Anony-Mousse: Chociaż całkowicie się z tobą zgadzam i podniosłem ostatnio kilka flag na SO, niepokoi mnie brak podwójnego zamknięcia większości tych pytań.
Nikana Reklawyks
4
To jest strona, która jest na pierwszym miejscu podczas przeglądania tego tematu.
haripkannan

Odpowiedzi:

62

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

ttnphns
źródło
Czy możesz przytoczyć przykłady dokumentów opisujących wspomniane podejście?
ciekawy
4
@Douglas, proszę. Powiedziałem, że k-średnich nie używa par odległości. Jest to wyraźnie stwierdzone. Wykorzystuje odległości do środka ciężkości. Ale to automatycznie oznacza, że ​​jest ona domyślnie związana z zadaniem optymalizacji pary w obrębie klastrów.
ttnphns
1
@ttnphns: W liczbie napisanych przez ciebie znaków możesz But a Euclidean distance b/w two data points can be represented in a number of alternative ways. For example, it is closely tied with cosine or scalar product b/w the points. If you have cosine, or covariance, or correlation, you can always (1) transform it to (squared) Euclidean distancerównie łatwo napisać: distance(x,y) = 1 - cosine_sim(x,y)lub coś równie zwięzłego i pouczającego.
stackoverflowuser2010
1
Wygląda to na uzasadnioną i konstruktywną krytykę: lepiej jest umieszczać informacje bezpośrednio w poście niż polegać na linku; i zwykle lepiej jest być wyraźnym niż niejasnym. (cc @stackoverflowuser)
whuber
3
O co walczysz Czy w tym przypadku lepiej jest polegać na łączu, lepiej być niejasnym, czy też jednym i drugim? I dlaczego?
whuber
46

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.

Anony-Mus
źródło
Ale na pierwszym etapie k-średnich każdy punkt jest umieszczany w gromadzie z najbliższą odległością euklidesową od środka gromady ... Więc istnieje metryka odległości
ciekawe
@AnonyMousse @ttnphns answer refers to pairwise Euclidean distances!W mojej odpowiedzi, akapit pierwszy, wyraźnie odnoszę się zarówno do interpretacji „błąd SS” (bezpośredni), jak i „parami d ^ 2” (niejawne).
ttnphns
3
Zgadzam się z tobą odpowiedź. Pamiętaj, że twoje konto operacyjne k-means may stop converging with other distance functionsjest homologiczne do mojej teoretycznej Non-euclidean distances will generally not span euclidean space.
ttnphns
bardzo dobre wytłumaczenie. Nigdy nie zastanawiałem się nad odległością euklidesową i nie zdawałem sobie sprawy, że tak naprawdę minimalizuje sumę kwadratów skupienia.
Verena Haunschmid
Nadal nie rozumiem, dlaczego średnia minimalizuje odległości pod względem odległości euklidesowych, a pod względem cosinusa nie jest to częścią dowodu
ciekawe
9

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.

użytkownik1669710
źródło
„metryki inne niż euklidesowe” Być może jestem trochę bardziej pedantyczny, ale te rozbieżności w ogóle nie są metrykami :)
mic
prawdziwe :); prawdopodobnie powinienem edytować odpowiedź.
user1669710,
8

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

Rreφ:RpH.rere(x,y)=φ(x)-φ(y)H.{φ(xja)}φk(x,y)=φ(x),φ(y)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.

Dougal
źródło
Nie rozumiem, jak można zastosować sztuczkę jądra z algorytmem Lloyda. Wydaje mi się, że aby obliczyć centroid (nawet pośrednio w przestrzeni Hilberta), potrzebujemy wyraźnej mapy φ (x_i)? Aby przypisać punkty do klastrów, potrzebujemy tylko jądra, ale do ponownego obliczenia centroidów nie możemy uciec od samego jądra, ponieważ centroid jest średnią z {φ (x_i)} przypisanego do tego klastra. Czy coś brakuje?
user2428107,
1njajotdojaφ(xjot)xφ(x)-1njajotdojaφ(xjot)2)=k(x,x)+1nja2)jot,jotk(xjot,xjot)-2)njajotk(x,xjot)
5

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.

Francesco Napolitano
źródło
2
cosinecorrelationcityblockL.1hammingcityblock
@Dougal, Jak mediana jest dostosowana do algorytmu? Czy to nie zmienia k- oznacza zasadniczo inny algo?
ttnphns
1
Należy również zauważyć, że w przypadku danych binarnych „odległość hamowania” = blok miejski = kwadratowa odległość euklidesowa.
ttnphns
1
=L.2)2)=L.1
1
@Dougal, zauważ, że procedura matlab powiązana z mówi o różnych odległościach między punktem danych a centrum klastra; co nie jest tym samym, co rodzaje odległości parowych.
ttnphns
2

Od tutaj :

wprowadź opis zdjęcia 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.

DL Dahly
źródło
To jest ogólna odpowiedź. Nie wyjaśnia, dlaczego w k-oznacza nie ma podobieństwa cosinus. Na przykład w zgrupowaniu hierarchicznym jest szeroko stosowany
ciekawe
3
@DLDahly: Czasami ważna jest wielkość, czasem hałas. To zależy od dziedziny badań i jest kwestią standaryzacji danych.
ttnphns