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.p
Mediana odległości od początku do najbliższego punktu danych jest wyrażona przez wyrażenie:
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 → ∞
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ć?
źródło
Odpowiedzi:
Objętość hiperfery wymiarowej o promieniu r ma objętość proporcjonalną do r p .p r rp
Tak więc proporcja objętości większej niż odległość od początku wynosi r p - ( k r ) pkr .rp−(kr)prp=1−kp
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 1N kr (1−kp)N . Tak więc(1-kp)N=112
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ę, żek będzie funkcją malejącą . Tutaj 2 1 / N jest funkcją malejącą N , więc 1N 21/N N jest rosnącą funkcjąN, a zatem1-1121/N N jest malejącą funkcjąN,podobnie jak jegop-ty pierwiastek.1−121/N N p
źródło
A teraz bez machania ręką
Dla dowolnej sekwencji iid rv, gdzie F jest wspólnym CDF
Tak więc rozwiązanie
jest
źródło
Jak zwięzłe, ale słownie:
źródło