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

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?

Ś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 $L_k$$k$$L_k$$L_k$$k$$d$, 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 ( ). ...$k$$L_1$$L_2$

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 < $L_k$$k<1$

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\times 4$$(\pm 2, \pm 2)$$(\pm 1, \pm 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/$r_2 = \sqrt{2}-1$. 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$(\pm r_2/\sqrt{2}, \pm r_2/\sqrt{2})$$(r_2,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\times 4 \times 4$$(\pm 2, \pm 2, \pm 2)$$8$$(\pm 1, \pm 1, \pm 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.$r_3 = \sqrt{3}-1 < 1$$(r_3,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 = $n$$4$$2^n$$(\pm 1, \pm 1, \ldots, \pm 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” dlan≥

$$r_n = \sqrt{n}-1\tag{1}$$ $(r_n,0,0, \ldots, 0)$$(1)$$n = 4$$r_n = 1$$n\geq 4$. 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 4$n > 9$$(1)$$r_n >2$$(r_n, 0, 0, \ldots, 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 .$n \geq 9$

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,y \rightarrow x,y,x,y,x,y,x,y,...,x,y$

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

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.

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.

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.

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

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.