Parzen and k nearest neighbor

Question

I have this formula for the density estimation. $$p_n(x) = \frac{k_n / n}{V_n}$$

I have been told that with a Parzen window approach you can specify $V_n$ as a function of $n$. So if $V$ decreased when $n$ increased it is clear that it is a fixed volume.

I have also been told that with a knn approach you specify $k_n$ as a function of $n$. So if you increase as $n$ is raised, it is clear that the volume is dependent of the volume.

So can anyone explains me the above statements. I think it is somewhat clear to me how knn and Parzen works. (knn count the $k$ nearest neighbor, at the new sample is assigned to the class which has most votes. In Parzen the volume is fixed).

I also do not understand the two formulas in the figure. The figure illustrated two methods for estimating the density at a point $x$ at the center of each square. The top knn, bottom Parzen

Answer 1

The probability that a vector $x$ is drawn from $p(x)$ in some region $R$ of a sample space is given by $ P = \int_{R} p(x')dx'$. Given a set of N vectors drawn from the distribution; it should be obvious that the probability k of these N vectors fall in $R$ is given by $P(k) = \binom{N}{k} p^{k} (1-p)^{N-k}$. From the properties of a binomial p.m.f the mean and variance of the ratio $\frac{k}{N}$ are ${E}[\frac{k}{N}] = P$ and ${var}[\frac{k}{N}] = \frac{P(1-P)}{N}$. Therefore, as $N \rightarrow \infty$ the distribution becomes more defined and the variance smaller. Hence, we can expect a decent estimate of the probability P to be obtained from the mean fraction of points that fall within the region $R$. Hence $P \cong \frac{k}{N}$,

Now consider if the region $R$ is small such that $p(x)$ does not vary considerably within it, then $\int_{R} p(x')dx' \cong p(x)V $. Combining this result with the one above. We see that $p(x) \cong \frac{k}{NV}$.

That's where the formula you found basically comes from. Therefore if we want to improve $p(x)$ we should let V approach 0. However, then $R$ would become so small that we would find no examples. Thus we really only have two choices in practice. We have to let V be large enough to find examples in $R$ or small enough such that p(x) is constant within $R$.

The basic approaches include using KDE (parzen window) or kNN. The KDE fixes V while kNN fixes k. Either way, it can be shown that both methods converge to the true probability density as N increases providing that V shrinks with N and that k grows with N.

The formulas used in the picture are just arbitrary examples that fulfill this requirement.