How to compute the unconditioned density in $1NN$ classier?

Question

Suppose I have $50$ training points $x_1$, $x_2,\ldots,x_{50}$ and they are distributed via bimodal Gaussian on real line. Now, given a new point, for $1NN$, I am trying to find a interval around $x$ so that it contains exactly 1 point from my training points.

From some online lecture notes, i.e., this one, I know the unconditioned density can be computed as $$ P(x)=\frac{1}{50V} $$ where $V$ is the length of the interval around $x$ which contains 1 point from training set.

I am trying to compute $P(x)$ but got confused on how to compute $V$.

Answer 1

If you refer back to the slides you linked to you'll see that $V$ is not a constant. It is a function of $x$. As it states you compute the distance from $x$ to it's $k^{th}$ closest neighbour, we'll call this distance $r(x)$. Then in order to compute $V(x)$, find the volume of the $d$-dimensional sphere with radius $r(x)$. For instance if you are in two dimensions, $V(x) = \pi \cdot (r(x))^2.

Intuitively, the further you are away from the training points, the larger $r(x)$ will be, the larger $V(x)$ will be, and the smaller our estimate for $P(x)$ will be.

Any questions?

import numpy as np
import matplotlib.pyplot as plt

d = 1
k = 5000
N = 100000

data = np.random.normal(size=N)
grid = np.arange(-3.0, 3.0, 0.1)
D = [[np.linalg.norm(x-y) for y in data] for x in grid]
_ = [l.sort() for l in D]
R = [l[k-1] for l in D]
P = [k/(N*2*r) for r in R]

plt.plot(grid, P)
plt.show()