Ich arbeite an Hasties ESL-Buch und habe es mit Frage 2.3 schwer. Die Frage lautet wie folgt:
Wir betrachten eine Schätzung des nächsten Nachbarn am Ursprung, und der mittlere Abstand vom Ursprung zum nächsten Datenpunkt wird durch diese Gleichung angegeben. Ich habe keine Ahnung, wo ich anfangen soll, um dies abzuleiten.
Ich weiß, dass die meisten Datenpunkte näher an der Grenze des Probenraums liegen als an jedem anderen Datenpunkt (Fluch der Dimensionalität), aber ich habe Probleme, dies in den Sinn für lineare Algebra / Wahrscheinlichkeit zu übersetzen.
Vielen Dank!
Antworten:
Sei der Abstand vom Ursprung und sei das Volumen der Einheitshypersphäre in Dimensionen. Dann wird das Volumen in einer Hypersphäre mit dem Radius enthalten istV 0 [ p ] p rr V0[p] p r
Wenn wir den Bruchteil des in dieser Hypersphäre enthaltenen Volumens bezeichnen lassen und , dannR = r pP=V[r]/V0[p] R=rp
Wenn die Datenpunkte gleichmäßig innerhalb der Einheitskugel verteilt sind, dann für die obige Formel eine kumulative Verteilungsfunktion (CDF) für . Dies entspricht einer einheitlichen Wahrscheinlichkeitsdichte für über das Einheitsintervall, dh . Wie von Mark Stone in den Kommentaren angedeutet, können wir den dimensionalen Fall auf ein äquivalentes 1D-Problem reduzieren.R R p [ R ] = P ' [ R ] = 1 p0≤R≤1 R R p[R]=P′[R]=1 p
Wenn wir nun einen einzelnen Punkt , dann haben wir per Definition einer CDF und . Wenn der kleinste Wert von Punkten ist und die Punkte alle unabhängig sind, ist die CDF für gegeben durch (dies ist ein Standardergebnis der univariaten Extremwerttheorie ).R Pr[R≤ρ]=P[ρ] Pr[R≥ρ]=1−P[ρ] Rmin n
Nach Definition des Medians haben wir was wir können schreibe um als was dem gewünschten Ergebnis entspricht.
BEARBEITEN: Versuch einer Antwort im " ELI5 " -Stil in drei Teilen.
Für den 1D-Fall mit einem einzelnen Punkt ist der Abstand gleichmäßig über , sodass der Median .[0,1] 12
In 1D ist die Verteilung für das Minimum über Punkte der erste Fall zur ten Potenz.n n
In Dimensionen ist der Abstand nicht gleichmäßig verteilt, aber ist.p r rp
quelle