Odległość euklidesowa zwykle nie jest dobra dla rzadkich danych?

72

Widziałem gdzieś, że klasyczne odległości (takie jak odległość euklidesowa) stają się słabo dyskryminujące, gdy mamy wielowymiarowe i rzadkie dane. Dlaczego? Czy masz przykład dwóch rzadkich wektorów danych, w których odległość euklidesowa nie działa dobrze? W takim przypadku, jakiego podobieństwa powinniśmy użyć?

shn
źródło
1
Ten artykuł może być również pomocny. W tym artykule autorzy wyjaśniają problem podobieństwa cosinusowego w danych wielowymiarowych i proponują nowy pomiar podobieństwa w celu złagodzenia tego problemu. journalofbigdata.springeropen.com/articles/10.1186/…
Sahar

Odpowiedzi:

33

Oto prosty przykład zabawki ilustrujący wpływ wymiaru na problem dyskryminacji, np. Problem, z którym się zmagasz, gdy chcesz powiedzieć, czy coś jest obserwowane lub czy zaobserwowano tylko efekt losowy (ten problem jest klasyczny w nauce).

Heurystyczny. Kluczową kwestią jest tutaj to, że norma euklidesowa przywiązuje taką samą wagę do każdego kierunku. Stanowi to brak wcześniejszego, a jak z pewnością wiesz w dużym wymiarze, nie ma darmowego lunchu (tj. Jeśli nie masz wcześniejszego pojęcia, czego szukasz, to nie ma powodu, dla którego hałas nie wyglądałby tak jak jesteś szukanie, to jest tautologia ...).

Powiedziałbym, że w przypadku każdego problemu istnieje limit informacji niezbędnych do znalezienia czegoś innego niż hałas. Limit ten jest w jakiś sposób związany z „rozmiarem” obszaru, który próbujesz zbadać w odniesieniu do poziomu „szumu” (tj. Poziomu treści nieinformacyjnych).

W dużym wymiarze, jeśli masz wcześniejszy sygnał, że twój sygnał jest rzadki, możesz usunąć (tj. Ukarać) rzadki wektor za pomocą metryki, która wypełnia przestrzeń rzadkim wektorem lub za pomocą techniki progowej.

Framework Załóżmy, że jest wektorem gaussowskim o średnim i przekątnej kowariancji ( jest znany) i że chcesz przetestować prostą hipotezęν σ I d σξνσIdσ

θ R n θ

H0:ν=0,VsHθ:ν=θ
(dla danego ) niekoniecznie jest z góry znany.θRnθ

Testuj statystyki energią . Intuicja, którą z pewnością masz, polega na tym, że dobrym pomysłem jest ocena normy / energii twojej obserwacji aby zbudować statystykę testową. W rzeczywistości można zbudować znormalizowaną, wyśrodkowaną (pod ) wersję energii . To sprawia, że ​​region krytyczny na poziomie formy dla dobrze wybranego ξH0TnTn=iξ 2 i -σ2En=1ni=1nξi2ξH0Tn α{Tnv1-α}v1-αTn=iξi2σ22nσ4α{Tnv1α}v1α

Moc testu i wymiar. W takim przypadku jest to proste ćwiczenie prawdopodobieństwa, aby pokazać następującą formułę mocy testu:

ZnE[Z]=0Var(Z)=1

Pθ(Tv1α)=P(Zv1α1+2θ22/(nσ2)θ222nσ4+2σ2θ22/(nσ2))
z suma iid zmiennych losowych z i .ZnE[Z]=0Var(Z)=1

Oznacza to, że moc twojego testu jest zwiększana przez energię twojego sygnału i zmniejszana o . Praktycznie oznacza to, że gdy zwiększa się rozmiar Twojego problemu, jeśli nie zwiększa siłę sygnału w tym samym czasie, a następnie dodajesz uninformative informacje do obserwacji (lub jesteś zmniejszenie odsetka użytecznych informacji w informacji masz): to jest jak dodawanie hałasu i zmniejsza moc testu (tzn. jest bardziej prawdopodobne, że powiesz, że nic nie jest obserwowane, podczas gdy w rzeczywistości coś jest). n nθ22nn

W kierunku testu ze statystyką progową. Jeśli nie masz dużo energii w swoim sygnale, ale znasz liniową transformację, która może pomóc ci skoncentrować tę energię w małej części twojego sygnału, możesz zbudować statystykę testową, która będzie oceniać energię tylko dla małej część twojego sygnału. Jeśli wiesz z góry, gdzie jest ono skoncentrowane (na przykład wiesz, że w twoim sygnale nie może być wysokich częstotliwości), możesz uzyskać moc w poprzednim teście, gdzie zastąpione małą liczbą, a prawie to samo ... Jeśli nie wiesz tego z góry, musisz to oszacować, co prowadzi do dobrze znanych testów progowych.θ 2 2nθ22

Zauważ, że ten argument jest dokładnie u podstaw wielu dokumentów, takich jak

  • A Antoniadis, F Abramowicz, T Sapatinas i B. Vidakovic. Metody falkowe do testowania w analizie funkcjonalnej modeli wariancyjnych. International Journal on Wavelets i jego zastosowania, 93: 1007–1021, 2004.
  • MV Burnashef i Begmatov. Problem wykrycia sygnału prowadzący do stabilnej dystrybucji. Teoria prawdopodobieństwa i jej zastosowania, 35 (3): 556–560, 1990.
  • Y. Baraud. Niesymptotyczna minimalna szybkość testowania w wykrywaniu sygnału. Bernoulli, 8: 577–606, 2002.
  • J Fan. Test istotności oparty na progowaniu falkowym i obcinaniu neymana. JASA, 91: 674–688, 1996.
  • J. Fan i SK Lin. Test znaczenia, gdy dane są krzywymi. JASA, 93: 1007–1021, 1998.
  • V. Spokoiny. Adaptacyjne testowanie hipotez za pomocą falek. Annals of Statistics, 24 (6): 2477–2498, grudzień 1996.
Robin Girard
źródło
51

Uważam, że to nie tyle rzadkość, co wysoka wymiarowość zwykle związana z rzadkimi danymi. Ale może jest jeszcze gorzej, gdy dane są bardzo rzadkie. Ponieważ wtedy odległość dowolnych dwóch obiektów będzie prawdopodobnie kwadratową średnią ich długości lub

limdimd(x,y)=||xy||p||x||2+||y||2

To równanie jest trywialne, jeśli . Jeśli zwiększysz wymiarowość i rozrzedzenie wystarczająco, aby obejmowało prawie wszystkie atrybuty, różnica będzie minimalna.ixi=0yi=0

Co gorsza: jeśli znormalizujesz swoje wektory, aby miały długość , wówczas odległość euklidesowa dowolnych dwóch obiektów będzie z dużym prawdopodobieństwem .||x||=12

Zasadniczo więc, aby odległość euklidesowa była użyteczna (nie twierdzę, że jest użyteczna lub znacząca), obiekty powinny być niezerowe w atrybutów. Wtedy powinna istnieć rozsądna liczba atrybutów, w którychwięc różnica wektora staje się użyteczna. Dotyczy to również każdej innej różnicy wywołanej normą. Ponieważ w powyższej sytuacji3/4|yi||xiyi||xi||xy|p|x+y|

Nie wydaje mi się, aby było to pożądane zachowanie funkcji odległości w dużej mierze niezależnych od rzeczywistej różnicy lub różnicy absolutnej zbliżającej się do sumy absolutnej!

Częstym rozwiązaniem jest stosowanie odległości takich jak odległość Cosinus. W przypadku niektórych danych działają one bardzo dobrze. Z grubsza mówiąc, patrzą tylko na atrybuty, w których oba wektory są niezerowe. Ciekawe podejście omówiono w poniższym piśmiennictwie (nie wymyślili go, ale podoba mi się ich eksperymentalna ocena właściwości) polega na użyciu wspólnych najbliższych sąsiadów. Więc nawet jeśli wektory xiy nie mają wspólnych atrybutów, mogą mieć wspólnych sąsiadów. Zliczanie liczby obiektów łączących dwa obiekty jest ściśle związane z odległościami na wykresie.

Dużo dyskusji dotyczy funkcji odległości w:

  • Czy odległości dzielone przez sąsiadów mogą pokonać przekleństwo wymiaru?
    ME Houle, H.-P. Kriegel, P. Kröger, E. Schubert i A.
    Zimek SSDBM 2010

a jeśli nie wolisz artykułów naukowych, również na Wikipedii: Curse of Dimensionality

Anony-Mus
źródło
2
Ciekawy papier. Istnieje również algorytm grupowania związany z tą miarą podobieństwa. Czy dzielonego najbliższego sąsiada można w jakiś sposób wyrazić w prawidłowym jądrze Mercer?
Seeda
Jeśli pamiętam, odpowiadają one euklidesowi w przestrzeni . Tak, dają dobre jądro. Rn
Anony-Mousse
44

Sugerowałbym rozpoczęcie od odległości Cosinus , a nie euklidesowej, dla wszystkich danych z większością wektorów prawie ortogonalnych, 0. Aby zobaczyć dlaczego, spójrz na . Jeśli 0, zmniejsza się to do : marna miara odległości, jak wskazuje Anony-Mousse.xy
|xy|2=|x|2+|y|22 xy
xy|x|2+|y|2

Odległość cosinus polega na użyciulub rzutowanie danych na powierzchnię kuli jednostkowej, więc wszystkie= 1. Zatem to zupełnie inna i zwykle lepsza metryka niż zwykły euklides. może być mały, ale nie jest maskowany przez głośne .x/|x||x||xy|2=22 xy
xy|x|2+|y|2

xy jest prawie bliski zeru dla rzadkich danych. Na przykład, i mają po 100 terminów niezerowych 900 zer, to obie są niezerowe tylko w 10 warunkach (jeśli niezerowe warunki rozpraszają losowo).xy

Normalizowanie / =może być powolny w przypadku rzadkich danych; jest szybki w scikit-learn .x|x|

Podsumowanie: zacznij od odległości cosinusowej, ale nie oczekuj cudów na starych danych.
Pomyślne pomiary wymagają oceny, strojenia, znajomości domeny.

denis
źródło
1
+1 To dodaje przemyślaną i przydatną analizę do innych odpowiedzi.
whuber
1
Średni kąt losowo rozmieszczonych punktów w jest zawsze bliski 90 ° dla dużych (patrz wykresy tutaj )[1,1]nn
Martin Thoma
10

Częścią przekleństwa wymiarowości jest to, że dane zaczynają się rozprzestrzeniać z dala od centrum. Dotyczy to normalnej wielowymiarowej normalnej, a nawet gdy komponentami są IID (normalna sferyczna). Ale jeśli chcesz ściśle mówić o odległości euklidesowej, nawet w małej przestrzeni wymiarowej, jeśli dane mają strukturę korelacji, odległość euklidesowa nie jest odpowiednią miarą. Jeśli przypuszczamy, że dane są wielowymiarowe normalne z pewnymi niezerowymi kowariancjami i dla celów argumentu załóżmy, że znana jest macierz kowariancji. Zatem odległość Mahalanobisa jest odpowiednią miarą odległości i nie jest taka sama jak odległość euklidesowa, do której zmniejszyłaby się tylko, gdyby macierz kowariancji była proporcjonalna do macierzy tożsamości.

Michael Chernick
źródło
1
Dzięki za sugestię odległości Mahalanobisa zamiast odległości euklidesowej, gdy dane są skorelowane. Czy potrafisz wyjaśnić, dlaczego odległość euklidesowa nie obsługuje skorelowanych danych, a także odległość Mahalanobisa?
Jubbles
5

Wierzę, że jest to związane z przekleństwem wymiarowości / koncentracji miary, ale nie mogę już znaleźć dyskusji, która uzasadnia tę uwagę. Wydaje mi się, że na metaoptimize pojawił się wątek, ale nie udało mi się go Google ...

W przypadku danych tekstowych normalizacja wektorów za pomocą TF-IDF, a następnie zastosowanie podobieństwa kosinusowego prawdopodobnie przyniesie lepsze wyniki niż odległość euklidesowa, ponieważ długie dokumenty (z wieloma słowami) mogą mieć te same tematy, a zatem są bardzo podobne do krótkich dokumentów o dużej liczbie wspólnych słowa. Odrzucenie normy wektorów pomaga w tym konkretnym przypadku.

ogrisel
źródło
4

Aksjomatyczną miarą rzadkości jest tak zwana liczba , która zlicza (skończoną) liczbę niezerowych wpisów w wektorze. Za pomocą tej miary wektory i mają tę samą rzadkość. I absolutnie nie ta sama norma. I (bardzo rzadki) ma takie samo normę , bardzo płaski, nieliczny wektor. I absolutnie nie ta sama liczba.0(1,0,0,0)(0,21,0,0)2(1,0,0,0)2(14,14,14,14)0

Ta funkcja, ani norma, ani quasinorm, nie jest gładka i nie wypukła. W zależności od dziedziny jej nazwy to legion, na przykład: funkcja liczności, miara liczebności lub po prostu parsymonia lub rzadkość. Jest to często uważane za niepraktyczne ze względów praktycznych, ponieważ jego stosowanie prowadzi do trudnych problemów NP .

Podczas gdy standardowe odległości lub normy (takie jak odległość ) są bardziej przystępne, jednym z ich problemów jest ich -jednorodność:dla . Może to być postrzegane jako nieintuicyjne, ponieważ iloczyn skalarny nie zmienia proporcji zerowych wpisów w danych ( jest -jednorodny). 1 a . x = | a | X a 0 0 021

a.x=|a|x
a000

Tak więc, w praktyce, niektóre z nich na kombinacje ( ), takie jak regulacje lasso, kalenica lub elastyczna siatka. Szczególnie norma (odległość Manhattan lub taksówka) lub jej wygładzone awatary. Od prac E. Candèsa i innych można wyjaśnić, dlaczego jest dobrym przybliżeniem do : objaśnienie geometryczne . Inni zrobili w , za cenę problemów .p 1 1 1 0 p < 1 p ( x )p(x)p1110p<1p(x)

Inną interesującą ścieżką jest ponowna aksjomizacja pojęcia rzadkości. Jednym z ostatnich godnych uwagi prac jest „ Porównywanie miar rzadkości” autorstwa N. Hurleya i in., Zajmujących się rzadkością dystrybucji. Z sześciu aksjomatów (o śmiesznych nazwach, takich jak Robin Hood, Skalowanie, Rising Tide, Cloning, Bill Gates i Babies), pojawiło się kilka indeksów rzadkości: jeden oparty na indeksie Giniego, drugi oparty na wskaźnikach norm, zwłaszcza jeden ponad two stosunek norm, pokazany poniżej:12

wprowadź opis zdjęcia tutaj

Chociaż nie jest wypukła, niektóre dowody zbieżności i kilka odniesień historycznych są wyszczególnione w Euklidesa w taksówce: Sparse Blind Dekonwolucja z wygładzone regularyzacji12 .

Laurent Duval
źródło
4

W artykule o zaskakującym zachowaniu wskaźników odległości w przestrzeni wielowymiarowej omawia się zachowanie wskaźników odległości w przestrzeniach wielowymiarowych.

Biorą na normy i zaproponować manhattan normę jako najbardziej skuteczny w dużych przestrzeniach wymiarowych dla celów grupowania. Wprowadzają także normę ułamkową podobną do normy ale z .LkL f L k f ( 0..1 )L1 LfLkf(0..1)

Krótko mówiąc, pokazują, że w przypadku przestrzeni o dużych wymiarach stosowanie normy euklidesowej jako domyślnej prawdopodobnie nie jest dobrym pomysłem; zwykle mamy mało intuicji w takich przestrzeniach, a wykładniczy wybuch ze względu na liczbę wymiarów jest trudny do uwzględnienia przy odległości euklidesowej.

facuq
źródło
1
Dobry. dla są quasi-normy zamiast norm. 0 < f < 1Lf0<f<1
Laurent Duval,