Dlaczego odległość euklidesowa nie jest dobrym miernikiem w dużych wymiarach?

239

Czytałem, że „odległość euklidesowa nie jest dobrą odległością w dużych wymiarach”. Myślę, że to stwierdzenie ma coś wspólnego z przekleństwem wymiarowości, ale co dokładnie? Poza tym, co to są „wysokie wymiary”? Stosuję hierarchiczne grupowanie przy użyciu odległości euklidesowej ze 100 funkcjami. Do ilu funkcji można bezpiecznie korzystać z tych danych?

herbata
źródło
5
Ściśle powiązane: odległość euklidesowa zwykle nie jest dobra dla rzadkich danych? jak wskazał facuq .
kardynał
5
Jest to prawdopodobnie zbyt podstawowe dla ciebie; Napisałem serię postów na blogu na temat metryki euklidesowej w wyższych wymiarach i jej wpływu na wyszukiwanie przestrzeni wektorowych dla najbliższych dopasowań. blogs.msdn.com/b/ericlippert/archive/tags/…
Eric Lippert
1
@ HorstGrünbusch zapoznaj się z odpowiedziami poniżej dla niektórych odniesień. Wariancja odległości staje się niewielka w porównaniu do średniej. W pewnym momencie masz problem z wyborem progów, wag, porządku; i możesz nawet mieć problemy z precyzją liczbową. Ale jeśli twoje dane są rzadkie, prawdopodobnie mają znacznie niższą wewnętrzną wymiarowość.
Anony-Mousse
3
„wysokie wymiary” wydają się być mylącym określeniem - niektóre odpowiedzi traktują 9-12 jako „wysokie wymiary”, ale w innych obszarach wysoka wymiarowość oznaczałaby tysiące lub milion wymiarów (powiedzmy, mierzenie kątów między wektorami worków słów, gdzie każdy wymiar to częstotliwość jakiegoś słowa w słowniku), a 100 wymiarów nazwano by niskimi, a nie wysokimi.
Peteris,
2
To pytanie może naprawdę mieć związek z pewnym kontekstem. Nie nadaje się do czego?
Szabolcs

Odpowiedzi:

242

Świetne podsumowanie nieintuicyjnych wyników w wyższych wymiarach pochodzi z „ Kilka przydatnych rzeczy, które warto wiedzieć o uczeniu maszynowym ” Pedro Domingos z University of Washington:

[O] intuicje, które pochodzą z trójwymiarowego świata, często nie mają zastosowania w przypadku wielowymiarowych. W wysokich wymiarach większość masy wielowymiarowego rozkładu Gaussa nie jest zbliżona do średniej, ale w coraz bardziej odległej „powłoce” wokół niej; a większość objętości wielowymiarowej pomarańczy znajduje się w skórze, a nie w miazdze. Jeśli stała liczba przykładów jest równomiernie rozmieszczona w hipersześcianie o dużych wymiarach, poza pewną wymiarowością większość przykładów znajduje się bliżej powierzchni hipersześcianu niż najbliższego sąsiada. A jeśli przybliżymy hiperferę poprzez wpisanie jej w hipersześcianie, w wysokich wymiarach prawie cała objętość hipersześcianu znajduje się poza hiperferą. To zła wiadomość dla uczenia maszynowego, w którym kształty jednego rodzaju są często zbliżone do kształtów innego.

Artykuł jest również pełen wielu dodatkowych pereł mądrości do uczenia maszynowego.

Inną aplikacją, poza uczeniem maszynowym, jest wyszukiwanie najbliższego sąsiada: po obserwacji zainteresowania znajdź najbliższych sąsiadów (w tym sensie, że są to punkty o najmniejszej odległości od punktu zapytania). Ale w wysokich wymiarach pojawia się dziwne zjawisko: stosunek najbliższych i najdalszych punktów zbliża się do 1, tzn. Punkty zasadniczo stają się jednakowo od siebie oddalone. Zjawisko to można zaobserwować dla wielu różnych mierników odległości, ale jest ono bardziej wyraźne dla miernika euklidesowego niż, powiedzmy, miernika odległości na Manhattanie. Założeniem wyszukiwania najbliższego sąsiada jest to, że „bliższe” punkty są bardziej odpowiednie niż „dalsze” punkty, ale jeśli wszystkie punkty są zasadniczo równomiernie oddalone od siebie, rozróżnienie nie ma znaczenia.

Charu C. Aggarwal, Alexander Hinneburg, Daniel A. Keim, „ O zaskakującym zachowaniu wskaźników odległości w przestrzeni wielowymiarowej ”:

Argumentowano w [Kevin Beyer, Jonathan Goldstein, Raghu Ramakrishnan, Uri Shaft, „ When Is„ Nearest Neighbor ”Sensowne? ”], Że przy pewnych rozsądnych założeniach dotyczących dystrybucji danych stosunek odległości najbliższych i najdalszych sąsiadów do danego celu w przestrzeni wielowymiarowej wynosi prawie 1 dla szerokiej gamy rozkładów danych i funkcji odległości. W takim przypadku problem najbliższego sąsiada staje się źle zdefiniowany, ponieważ kontrast między odległościami do różnych punktów danych nie istnieje. W takich przypadkach nawet pojęcie bliskości może nie mieć znaczenia z perspektywy jakościowej: problem, który jest nawet bardziej fundamentalny niż pogorszenie wydajności algorytmów wielowymiarowych.

... Wiele struktur indeksowania i algorytmów wielowymiarowych wykorzystuje metrykę odległości [e] uclidean jako naturalne rozszerzenie jej tradycyjnego zastosowania w dwu- lub trójwymiarowych zastosowaniach przestrzennych. ... W tym artykule przedstawiamy zaskakujące wyniki teoretyczne i eksperymentalne w analizie zależności normy od wartości . Mówiąc dokładniej, pokazujemy, że względne kontrasty odległości do punktu zapytania zależą w dużej mierze od metryki . Dostarcza to znacznego dowodu, że normy pogarsza się szybciej w miarę wzrostu wymiarów dla wyższych wartości . Zatem dla danego problemu o ustalonej (wysokiej) wartości wymiaru k L k L k k d k L 1 L 2LkkLkLkkd, może być preferowane użycie niższych wartości . Oznacza to, że odległości (metryka odległości Manhattanu) jest najbardziej preferowana dla aplikacji wielowymiarowych, a następnie metryka euklidesowa ( ). ...kL1L2

Autorzy artykułu „Zaskakujące zachowanie” proponują następnie zastosowanie norm dla . Dają pewne wyniki, które pokazują, że te „normy ułamkowe” wykazują właściwość zwiększania kontrastu między najdalszymi i najbliższymi punktami. Może to być przydatne w niektórych kontekstach, jednak istnieje pewne zastrzeżenie: te „normy ułamkowe” nie są właściwymi miernikami odległości, ponieważ naruszają nierówność trójkąta. Jeśli nierówność trójkąta jest istotną cechą w badaniach, wskaźniki ułamkowe nie będą niezwykle przydatne. k < 1Lkk<1

Sycorax
źródło
7
to odniesienie jest niesamowite
Antoine
1
Czytam jeszcze raz ... Piękny ...
Richard Hardy
113

Pojęcie odległości euklidesowej, która działa dobrze w dwuwymiarowych i trójwymiarowych światach badanych przez Euclida, ma pewne właściwości w wyższych wymiarach, które są sprzeczne z naszą (być może tylko moją ) intuicją geometryczną, która jest również ekstrapolacją z dwóch i trzech wymiary

Rozważ kwadrat z wierzchołkami w ( ± 2 , ± 2 ) . Narysuj cztery okręgi o promieniu jednostkowym wyśrodkowane na ( ± 1 , ± 1 ) . Te „wypełniają” kwadrat, przy czym każde koło dotyka boków kwadratu w dwóch punktach, a każde koło dotyka jego dwóch sąsiadów. Na przykład okrąg wyśrodkowany w ( 1 , 1 ) dotyka boków kwadratu w ( 2 , 1 ) i ( 1 , 2 )4×4(±2,±2)(±1,±1)(1,1)(2,1)(1,2), i sąsiednie okręgi w i ( 0 , 1 ) . Następnie narysuj mały okrąg wyśrodkowany na początku, który dotyka wszystkich czterech okręgów. Ponieważ odcinek linii, którego punktami końcowymi są środki dwóch kół oscylacyjnych, przechodzi przez punkt oscylacji, łatwo jest zweryfikować, że mały okrąg ma promień r 2 = (1,0)(0,1) i dotykanie dotyka czterech większych kół w(±r2/r2=21. Zauważ, że małe kółko jest „całkowicie otoczone” czterema większymi okręgami, a zatem jest również całkowicie wewnątrz kwadratu. Zauważ też, że punkt(r2,0)leży na małym kółku. Zauważ też, że od początku nie można „zobaczyć” punktu(2,0,0)na krawędzi kwadratu, ponieważ linia wzroku przechodzi przez punkt oscylacji(1,0,0)dwóch wyśrodkowanych kół w(1,1)i(1,(±r2/2,±r2/2)(r2,0)(2,0,0)(1,0,0)(1,1) . To samo dotyczy linii wzroku do innych punktów, w których osie przechodzą przez krawędzie kwadratu.(1,1)

Następnie rozważ kostkę z wierzchołkami w ( ± 2 , ± 2 , ± 2 ) . Wypełniamy go 8 kulkami o promieniu jednostkowym, wycentrowanym w ( ± 1 , ± 1 , ± 1 ) , a następnie umieszczamy mniejszą kulę oscylującą, wycentrowaną na początku. Zauważ, że mała kula ma promień r 3 = 4×4×4(±2,±2,±2)8(±1,±1,±1) a punkt(r3,0,0)leży na powierzchni małej kuli. Zauważ jednak, że w trzech wymiarachmożna„zobaczyć” punkt (2,0,0)od początku; nie ma większych większych kul blokujących widok, jak dzieje się to w dwóch wymiarach. Te wyraźne linie wzroku od początku do punktów, w których osie przechodzą przez powierzchnię sześcianu, występują również we wszystkich większych wymiarach.r3=31<1(r3,0,0)(2,0,0)

Uogólniając, możemy rozważyć wymiarową hipersześcię strony 4 i wypełnić ją 2 n hipersferami o promieniu jednostkowym wyśrodkowanym w ( ± 1 , ± 1 , , ± 1 ), a następnie umieścić „mniejszą” kulę oscylacyjną o promieniu r n = n42)n(±1,±1,,±1)u źródła. Punkt(rn,0,0,,0) leży na tej „mniejszej” sferze. Zauważ jednak z(1),że gdyn=4,rn=1,a zatem „mniejsza” kula ma promień jednostkowy, a zatem naprawdę nie zasługuje na soubriquet „mniejszej” dlan4

(1)rn=n-1
(rn,0,0,,0)(1)n=4rn=1n4. Rzeczywiście byłoby lepiej, gdybyśmy nazwali to „większą sferą” lub po prostu „sferą centralną”. Jak zauważono w ostatnim akapicie, istnieje wyraźna linia wzroku od początku do punktów, w których osie przechodzą przez powierzchnię hipersześcianu. Jeszcze gorzej, gdy mamy z ( 1 ) , że R n > 2 , a tym samym punktu ( R n , 0 , 0 , ... , 0 ) o środkowej dziedzinie leży poza hipersześcianu bocznych 4n>9(1)rn>2)(rn,0,0,,0)4 nawet jeśli jest „całkowicie otoczony” hipersferami o promieniu jednostkowym, które „wypełniają” hipersześcian (w sensie pakowania). Kula centralna „wybrzusza się” poza hipersześcianem w przestrzeni o dużych wymiarach. Uważam to za bardzo sprzeczne z intuicją, ponieważ moje mentalne tłumaczenia pojęcia odległości euklidesowej do wyższych wymiarów, używając intuicji geometrycznej, którą rozwinąłem z 2-przestrzeni i 3-przestrzeni, które znam, nie opisują rzeczywistości przestrzeń wielowymiarowa.

Moja odpowiedź na pytanie PO „Poza tym, czym są„ wysokie wymiary ”? wynosi .n9

Dilip Sarwate
źródło
9
@ stackoverflowuser2010: Jeśli ta odpowiedź jest całkowicie niezrozumiała, w jaki sposób możesz stwierdzić, czy odnosi się ona do pierwotnego pytania, czy próbuje odpowiedzieć? Bardziej konstruktywnym podejściem może być prośba o wyjaśnienie wszelkich punktów, które uważasz za niejasne, zamiast odrzucenia całej sprawy z ręki.
Scortchi
8
@ stackoverflowuser2010 Ponieważ ta odpowiedź ma wiele dziesiątków pozytywnych opinii, wydaje się, że wiele osób uważa, że ​​jest ona zarówno zrozumiała, jak i odpowiada w zadowalający sposób na pytanie. Być może mógłbyś spróbować bardziej konstruktywnej krytyki - jak, twoim zdaniem, poprawiona zostanie ta odpowiedź? Co powinno zawierać, że nie?
Glen_b
1
@Scortchi: Może oczekuję zbyt wiele, ale jednoznaczna odpowiedź na to pytanie, która mogłaby pomóc społeczności, brzmiałaby: „Odległość euklidesowa nie jest dobrą miarą, ponieważ <X>”.
stackoverflowuser2010
7
@ stackoverflow2010 Nigdy nie zobaczysz takiej „dobrej” odpowiedzi, ponieważ <rzeczy są znacznie bardziej skomplikowane niż instrukcje if-then>. Jeśli chcesz prostej odpowiedzi, najprawdopodobniej jest ona fałszywa. Podobnie jak przeklęci kłamcy Brexitu, byli dobrzy w oferowaniu łatwych odpowiedzi (fałszywych, ale łatwych).
Anony-Mousse
42

Jest to kwestia sygnału do szumu . Odległość euklidesowa, ze względu na kwadraty, jest szczególnie wrażliwa na hałas; ale cierpią nawet odległość Manhattanu i odległości „ułamkowe” (niemetryczne).

Uważam, że badania w tym artykule są bardzo pouczające:

Zimek, A., Schubert, E. i Kriegel, H.-P. (2012),
Ankieta na temat nadzorowanego wykrywania wartości odstających w wielowymiarowych danych liczbowych.
Analiza danych statystycznych, 5: 363–387. doi: 10.1002 / sam.11161

Ponownie przypomina obserwacje poczynione np. Przez Aggarwal, Hinneburg i Keim o zaskakującym zachowaniu metryki odległości w przestrzeni wielowymiarowej, wspomniane przez @Pat. Ale pokazuje również, w jaki sposób eksperymenty syntetyczne wprowadzają w błąd i że w rzeczywistości dane wielowymiarowe mogą stać się łatwiejsze . Jeśli masz dużo (redundantnych) sygnałów, a nowe wymiary powodują niewielki hałas.

x,rx,r,x,r,x,r,x,r,...,x,r

Tak więc ostatecznie zależy to od twoich danych. Jeśli masz wiele bezużytecznych atrybutów, odległość euklidesowa stanie się bezużyteczna. Jeśli możesz łatwo osadzić swoje dane w małej przestrzeni danych, odległość euklidesowa powinna również działać w przestrzeni pełnowymiarowej. W szczególności w przypadku rzadkich danych, takich jak wektory TF z tekstu, wydaje się, że dzieje się tak w przypadku, gdy dane mają znacznie mniejszą wymiarowość niż sugeruje model przestrzeni wektorowej.

Niektórzy uważają, że odległość cosinus jest lepsza niż euklidesowa w przypadku danych wielowymiarowych. Nie sądzę: odległość cosinus i odległość euklidesowa są ze sobą ściśle powiązane; więc musimy spodziewać się, że będą cierpieć z powodu tych samych problemów. Jednak dane tekstowe, w których cosinus jest popularny, są zwykle rzadkie , a cosinus jest szybszy w przypadku danych, które są rzadkie - więc w przypadku danych rzadkich istnieją dobre powody, aby używać cosinusa; a ponieważ dane są rzadkie, wewnętrzna wymiarowość jest znacznie mniejsza niż wymiar przestrzeni wektorowej.

Zobacz także odpowiedź, którą udzieliłem na wcześniejsze pytanie: https://stats.stackexchange.com/a/29647/7828

Anony-Mus
źródło
[-1,1]nn
A jaki byłby z tego wniosek? Na [-1; 1] ^ d nie należy używać Cosinusa, ponieważ nie jest zdefiniowany na 0, średnia nie mówi nam nic o klątwie, a jednolite dane są nierealne.
Anony-Mousse,
Do tej pory tego nie próbowałem, ale wydaje mi się, że kąty wyglądają podobnie dla prawdziwych danych. Fakt, że nie jest zdefiniowany jako 0, nie powinien mieć tak naprawdę znaczenia, ponieważ jest to tylko jeden punkt. Moja konkluzja jest podobna do Ciebie: Cosinus odległość nie jest dobrze nadaje się do wysokich-wymiarowej przestrzeni (choć może być domenami były nadal działa)
Martin Thoma
Bardziej realistycznym scenariuszem byłyby punkty na nieujemnej sferze jednostek. Miarą zainteresowania byłaby prawdopodobnie wariancja, a nie średnia.
Anony-Mousse,
Aby dostać się do nieujemnej sfery jednostkowej, wystarczy dodać +1 i podzielić przez 2 ...
Martin Thoma
34

Najlepszym miejscem na początek jest lektura Aggarwal, Hinneburg i Keim O zaskakującym zachowaniu wskaźników odległości w przestrzeni wielowymiarowej. Tutaj znajduje się obecnie działający link (pdf) , ale jeśli się zepsuje, powinien być bardzo łatwy w obsłudze w Google. Krótko mówiąc, wraz ze wzrostem liczby wymiarów, względna odległość euklidesowa między punktem w zbiorze a jego najbliższym sąsiadem oraz między tym punktem a jego najdalszym sąsiadem zmienia się w nieoczywisty sposób. To, czy wpłynie to negatywnie na twoje wyniki, zależy w dużej mierze od tego, co próbujesz osiągnąć i jakie są twoje dane.

Poklepać
źródło
6

Dystans euklidesowy bardzo rzadko jest dobrym wyborem w uczeniu maszynowym, a staje się to bardziej widoczne w wyższych wymiarach. Wynika to z faktu, że przez większość czasu w uczeniu maszynowym nie masz do czynienia z euklidesową przestrzenią metryczną, lecz probabilistyczną przestrzenią metryczną, dlatego powinieneś używać probabilistycznych i teoretycznych funkcji odległości, np. Opartych na entropii.

Ludzie lubią przestrzeń euklidesową, ponieważ łatwo ją konceptualizować, a ponadto jest ona matematycznie łatwa ze względu na właściwości liniowości, co oznacza, że ​​możemy zastosować algebrę liniową. Jeśli zdefiniujemy odległości w kategoriach, powiedzmy, rozbieżności Kullbacka-Leiblera, wówczas trudniej jest wyobrazić sobie i pracować matematycznie.

samthebest
źródło
2
Może to być problematyczne, ponieważ dywergencja KL nie jest miarą. :-)
agarie
2
Jeśli potrzebna jest symetria, można użyć informacji wzajemnych, które zgodnie z podaną wskazówką można zdefiniować w kategoriach KL.
samthebest
3

Jako analogię, wyobraź sobie koło wyśrodkowane na początku. Punkty są rozdzielane równomiernie. Załóżmy, że losowo wybrany punkt to (x1, x2). Odległość euklidesowa od źródła wynosi ((x1) ^ 2 + (x2) ^ 2) ^ 0,5

Teraz wyobraź sobie punkty równomiernie rozmieszczone w kuli. Ten sam punkt (x1, x2) będzie teraz prawdopodobnie (x1, x2, x3). Ponieważ w parzystym rozkładzie tylko kilka punktów ma jedną ze współrzędnych jako zero, przyjmujemy, że [x3! = 0] dla naszego losowo wybranego równomiernie rozmieszczonego punktu. Zatem nasz losowy punkt jest najprawdopodobniej (x1, x2, x3), a nie (x1, x2, 0).

Skutkuje to tym, że dowolny losowy punkt znajduje się teraz w odległości ((x1) ^ 2 + (x2) ^ 2 + (x3) ^ 2) ^ 0,5 od początku kuli trójwymiarowej. Odległość ta jest większa niż dla losowego punktu w pobliżu początku okręgu 2D. Problem ten nasila się w wyższych wymiarach, dlatego wybieramy dane inne niż wymiary euklidesowe do pracy z wyższymi wymiarami.

EDYCJA: Przypominam sobie teraz: „Większość masy wielowymiarowej pomarańczy znajduje się w skórze, a nie w miazdze”, co oznacza, że ​​w wyższych wymiarach równomiernie rozmieszczone punkty są bardziej „bliskie” (odległość euklidesowa) granicy niż pochodzenie.

Uwaga dodatkowa: Odległość euklidesowa nie jest ZBYT zła w przypadku problemów w świecie rzeczywistym ze względu na „błogosławieństwo niejednorodności”, które zasadniczo stwierdza, że ​​w przypadku danych rzeczywistych dane prawdopodobnie NIE będą rozmieszczone równomiernie w przestrzeni o wyższych wymiarach, ale będzie zajmować mały, klastrowany podzbiór przestrzeni. Ma to intuicyjny sens: jeśli mierzysz 100 wielkości dotyczących ludzi, takich jak wzrost, waga itp., Równomierny rozkład w przestrzeni wymiarowej po prostu nie ma sensu, np. Osoba z (wzrost = 65 cali, waga = 150 funtów, avg_calorie_intake = 4000), co jest po prostu niemożliwe w prawdziwym świecie.

Abhishek Divekar
źródło
Jeśli jakikolwiek przyszły czytelnik jest zainteresowany cytatem „pomarańczowy / miąższ” lub uwagą „błogosławieństwo niejednolitości”, oba pojawiają się w „Kilka przydatnych rzeczy do nauczenia się o uczeniu maszynowym”, do których link znajduje się w mojej odpowiedzi na ten temat wątek.
Sycorax,
1

Innym aspektem tego pytania jest:

Bardzo często duże wymiary problemów (uczenie maszynowe / statystyki) są wynikiem nadmiernie ograniczonych funkcji.

Oznacza to, że wymiary NIE są niezależne (lub nieskorelowane), ale wskaźniki euklidesowe zakładają (przynajmniej) brak korelacji, a zatem mogą nie dawać najlepszych wyników

Aby odpowiedzieć na twoje pytanie, liczba „wysokich wymiarów” jest związana z tym, ile funkcji jest zależnych, nadmiarowych lub nadmiernie ograniczonych

Ponadto: Csiszar (i in.) Twierdzą, że mierniki euklidesowe są „naturalnymi” kandydatami do wnioskowania, gdy cechy mają pewne formy

Nikos M.
źródło
3
Wskaźniki euklidesowe „nie zakładają… braku korelacji”. Odległości euklidesowe działają najgorzej w dużych wymiarach przy nieskorelowanych zmiennych. Rozważ skrajny przypadek: masz bardzo wiele wymiarów, które są doskonale skorelowane, r = 1, teraz twoje dane są w rzeczywistości jednowymiarowe, a odległość euklidesowa działa dobrze w / jednowymiarowych danych.
gung
Nie, nie sądzę, odległość euklidesowa z definicji zakłada niepowiązane dane (z wyjątkiem sytuacji, gdy używa się uogólnionej odległości euklidesowej z macierzą korelacji)
Nikos M.
Funkcje z całkowitą korelacją (r = 1) to trywialny przykład i odpowiednik „trywialnej macierzy korelacji”, ale być może się mylę
Nikos M.
@gung Stratę euklidesową można zinterpretować jako utratę entropii krzyżowej Gaussów ze stałą jednostkową macierzą wariancji izotropowej. Myślę, że to dobra uwaga, ale można to lepiej wyjaśnić.
Neil G,
1
(0,0)(1,1)remi=jot(x2)jot-x1jot)2)2)X1=X2)12)door(X1,X2))=02)
0

Ten artykuł może ci również pomóc „Ulepszony pomiar podobieństwa sqrt-cosinus” odwiedź https://journalofbigdata.springeropen.com/articles/10.1186/s40537-017-0083-6 Ten artykuł wyjaśnia, dlaczego odległość euklidesowa nie jest dobrą miarą w wysokich wymiarach danych i jaki jest najlepszy zamiennik odległości euklidesowej w danych wielowymiarowych. Odległość euklidesowa jest normą L2, a zmniejszając wartość k w normie Lk, możemy złagodzić problem odległości w danych wielowymiarowych. Można również znaleźć odniesienia w tym dokumencie.

Sahar
źródło
2
Witamy na stronie. Staramy się zbudować stałe repozytorium wysokiej jakości informacji statystycznych w formie pytań i odpowiedzi. Dlatego też obawiamy się odpowiedzi typu „tylko link” z powodu linkrot. Czy możesz zamieścić pełny cytat i streszczenie informacji pod linkiem, na wypadek gdyby nie działał?
gung