Wyjaśnienie wzoru na medianę najbliższego punktu początkowego N próbek z kuli jednostkowej

11

W Elements of Statistics Learning wprowadzono problem podkreślenia problemów z k-nn w przestrzeniach o dużych wymiarach. Istnieje punktów danych, które są równomiernie rozmieszczone w kuli jednostkowej wymiarowej.pNp

Mediana odległości od początku do najbliższego punktu danych jest wyrażona przez wyrażenie:

d(p,N)=(1(12)1N)1p

Gdy , formuła rozkłada się do połowy promienia kuli i widzę, jak najbliższy punkt zbliża się do granicy jako , co powoduje, że intuicja za knn rozpada się w dużych wymiarach. Ale nie rozumiem, dlaczego formuła jest zależna od N. Czy ktoś mógłby wyjaśnić?p N=1p

Również książka rozwiązuje ten problem dalej, stwierdzając: „... przewidywanie jest znacznie trudniejsze w pobliżu krawędzi próbki treningowej. Trzeba ekstrapolować z sąsiednich punktów próbki, a nie interpolować między nimi”. To wydaje się głębokim stwierdzeniem, ale nie mogę zrozumieć, co to znaczy. Czy ktoś mógłby przeredagować?

użytkownik64773
źródło
1
Musisz trochę edytować wyświetlane równanie. Czy ten wykładnik ma zastosowanie tylko do tego w liczniku tak, jak wygląda teraz, czy też chciałbyś, aby dotyczył całego ? 111N112
Dilip Sarwate
1
Pomogłoby to odróżnić „hipersferę” (która w jest kolektorem wymiaru ) od „kuli jednostkowej” (która ma wymiar ). Hipersfera jest granicą piłki. Jeśli, jak mówi twój tytuł, wszystkie punkty są próbkowane z hipersfery , wówczas - z definicji - wszystkie mają odległość od początku, mediana odległości wynosi i wszystkie są jednakowo blisko początku. p-1p11Rpp1p11
whuber
@DilipSarwate Jest stosowany do całego . W książce jest przykład, w którym więc N=500,p=10d(p,N)0,5212N=500,p=10d(p,N)0.52
64773

Odpowiedzi:

8

Objętość hiperfery wymiarowej o promieniu r ma objętość proporcjonalną do r p .prrp

Tak więc proporcja objętości większej niż odległość od początku wynosi r p - ( k r ) pkr.rp(kr)prp=1kp

Prawdopodobieństwo, że wszystkie losowo wybrane punkty są na odległość większą niż k r z pochodzenia ( 1 - k p ) N . Aby uzyskać medianę odległości do najbliższego losowego punktu, ustaw to prawdopodobieństwo na 1Nkr(1kp)N . Tak więc(1-kp)N=112

(1kp)N=12
k=(1121/N)1/p.

Intuicyjnie ma to pewien sens: im więcej jest losowych punktów, tym bliżej spodziewasz się punktu początkowego, więc powinieneś spodziewać się, że k będzie funkcją malejącą . Tutaj 2 1 / N jest funkcją malejącą N , więc 1N21/NN jest rosnącą funkcjąN, a zatem1-1121/NN jest malejącą funkcjąN,podobnie jak jegop-ty pierwiastek.1121/NNp

Henz
źródło
Ach, fajny sposób na to spojrzeć. Czy byłbyś w stanie ponownie zinterpretować cytat w moim drugim pytaniu?
user64773
Podejrzewam, że może to sugerować, że w dużych wymiarach punkty do przewidzenia znajdują się w znacznej odległości od danych treningowych, jak na krawędzi kuli, więc tak naprawdę nie interpolujesz, ale raczej ekstrapolujesz, a więc niepewności są znacznie większe. Ale tak naprawdę nie wiem.
Henry
Nie rozumiem - rozumiem, dlaczego to wyrażenie jest prawdopodobieństwem, że wszystkie punkty są dalej niż kr, ale dlaczego ustawienie tego prawdopodobieństwa na 1/2 daje medianę odległości?
ihadanny,
1
@ihadanny: wartość daje ułamek promienia, w którym prawdopodobieństwo, że wszystkieNpunkty są dalej, wynosi1k=(1121/N)1/pN , a więc tam, gdzie prawdopodobieństwo co najmniej jednego punktu jest bliższe, wynosi1-112 , więckrjest medianą rozkładu odległości najbliższego punktu. 112=12kr
Henry,
Definicja mediany, połowa jest większa, a połowa mniejsza.
Grant Izmirlian,
1

A teraz bez machania ręką

  1. Dla dowolnej sekwencji iid rv, gdzie F jest wspólnym CDF

    P(min1iNYi>y)=(1F(y))N,
    F
  2. NXip

    P(min1iN||Xi||>r)=(1F(r))N,
    F||Xi||,i=1,2,,NFRp

F(r)=P(||Xi||r)=Crp/(C1p)=rp

Tak więc rozwiązanie

1/2=P(min1iN||Xi||>r)=(1rp)N

jest

r=(1(1/2)1/N)1/p.

Np

kRp

Grant Izmirlian
źródło
0

Jak zwięzłe, ale słownie:

NprNthrrrrp. Możemy teraz zapisać wyrażenie [1] jako

P(min1iN||Xi||>r)=(1rp)N.

1/2r

Grant Izmirlian
źródło