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ć?
72
Odpowiedzi:
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 θ
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=1n∑ni=1ξ2i ξ H0 Tn α{Tn≥v1-α}v1-αTn=∑iξ2i−σ22nσ4√ α {Tn≥v1−α} v1−α
Moc testu i wymiar. W takim przypadku jest to proste ćwiczenie prawdopodobieństwa, aby pokazać następującą formułę mocy testu:
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∥θ∥22 n n
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
źródło
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
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=0∨yi=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||=1 2–√
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|≠|xi−yi|≠|xi| |x−y|→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:
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
źródło
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.x⋅y≈
|x−y|2=|x|2+|y|2−2 x⋅y
x⋅y≈ |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| |x−y|2=2−2 x⋅y
x⋅y |x|2+|y|2
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.
źródło
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.
źródło
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.
źródło
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 0ℓ2 1
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) p≥1 ℓ1 ℓ1 ℓ0 p<1 ℓp(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:ℓ1ℓ2
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 regularyzacjiℓ1ℓ2 .
źródło
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 .Lk L f L k f ∈ ( 0..1 )L1 Lf Lk f∈(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.
źródło