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.

parzen and knn

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


1 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.