# Estimate density from neighbor distances

Assuming I have a data set of known size, and there is one object that I want to test for being in an approximately uniform distributed region of the data set.

For the query object, I know the $k$ nearest neighbors and the associated distances. If the data set is uniform there, the distances should be $c\cdot\chi(d)$ distributed, I believe (with $c$ a constant, representing some kind of data set diameter).

So I have a spherical subset of the total data set that contains $k$ objects and has a known radius of $d_k$, the distance to the $k$th object, or equally the maximum distance within the $k$ nearest neighbors.

Note that the $d_k$s - if I would be looking at more than one such subset - likely are not $\chi(d)$ distributed, as they are derived from the distances. Is there any assumption that I can make on the distribution of the $d_k$ for a dataset?

So what is the best way to test if the object is in a somewhat uniformly distributed area of the data set (should I try a Kolmogorov-Smirnov goodness of fit test to $\chi(d)$ of the known distances? But I'm probably not seeing the complete distribution!), and what is the best guess at the density? My key idea is that the object might be an outlier if is in a low-density and approximately uniform area of the data set. Methods such as LOF fail here, because the outlier is too far out. LOF works good for detecting outliers nearby the actual data, but not within a uniform sparse area.

First, I don't think that the distances are distributed as a $\chi(d)$, assuming that $d$ is the dimension of the space. We know that the $k$ nearest neighbors will be farther if they are sampled from $k$ neighbors than if they are sampled from $1,000,000,000$ neighbors. So it is not possible that they are both distributed as a $\chi(d)$.

In dimension $d$, say that the object $x_0$ is the center of a locally uniform ball of total probability $\alpha$ and of radius $R$. The probability that a point of this ball is at a distance smaller than $\delta$ from $x_0$ is $(\delta/R)^d$, so the pdf is $\delta^{d-1} d/R^d$. Given that all $n$ points of the sample are in the ball, the $k$ nearest neighbors the $k$ smallest order statistics, so their joint pdf is locally

$$\propto y_1^{d-1}y_2^{d-1}...y_k^{d-1}(1-(y_k/R)^d)^{n-k}, (y_1 \leq y_2 \leq ... \leq y_k).$$

This looks nice, but you do not know $R$ if I understood. The local uniform domain may be extremely small ($R$ very small) so that the $k$ nearest neighbors may not all be contained within it. So you do not know how high the distances of the nearest neighbors can go before they stop following this distribution. Some of the neighbors may be in the domain, and some may not.

Even if you knew $R$, note that the distances of the $k$ nearest neighbors are not independent. I am not aware of any test that does not assume IID sampling, so I do not think you can answer that question with so little information.

• I think a lot of your reasoning may be correct, but did you notice the OP specified a chi distribution, not chi-squared? (This doesn't really change anything important, but it would be good to address the question as stated.)
– whuber
Jun 16, 2012 at 20:10
• Good point @whuber, I did not notice this. I changed it. Let me know if you think further edit is needed. Jun 16, 2012 at 20:43
• chi and chi squared pretty much interchange here, because when d is chi, then d^2 is chi^2 distributed, and losing the square root can make things easier. I'm fine in working with d^2 if it is easier. Jun 17, 2012 at 9:12
• Well, I don't sample again from the $k$ nearest neighbors. They are the $k$ nearest in the whole set; the whole set probably is not uniformly distributed (there is a cluster somewhere), but maybe the $2k$NN or $10k$NN are. I do know $R$ indirectly, it is the distance to the farthest of the $k$NN that I have. Jun 17, 2012 at 9:19
• @Anony-Mousse I edited the answer to explain a bit more what R is and why I believe that, as is, the question has no answer. Jun 17, 2012 at 10:55