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?
239
Odpowiedzi:
Ś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:
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 ”:
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 < 1L.k k < 1
źródło
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)= 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,( ± 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)= 3-√- 1 < 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 = √n 4 2)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” dlan≥4
Moja odpowiedź na pytanie PO „Poza tym, czym są„ wysokie wymiary ”? wynosi .n ≥ 9
źródło
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:
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.
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
źródło
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.
źródło
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.
źródło
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.
źródło
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
źródło
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.
źródło