## Contents

Introduction to local (nonparametric) density estimation methods

Partly based on the ECE662 Spring 2014 lecture material of Prof. Mireille Boutin.

**1. Introduction **

This slecture introduces two local density estimation methods which are Parzen density estimation and k-nearest neighbor density estimation. Local density estimation is also referred to as non-parametric density estimation. To make things clear, let’s first look at parametric density estimation. In parametric density estimation, we can assume that there exists a density function which can be determined by a set of parameters. The set of parameters are estimated from the sample data and are later used in designing the classifier. However, in some practical situations the assumption that there exists a parametric form of the density function does not hold true. For example, it is very hard to fit a multimodal probability distribution with a simple function. In this case, we need to estimate the density function in the nonparametric way, which means that the density function is estimated locally based on a small set of neighboring samples. Because of this locality, local (nonparametric) density estimation is less accurate than parametric density estimation. In the following text the word “local” is preferred over “nonparametric.”

It is noteworthy that it is very difficult to obtain an accurate local density estimation, especially when the dimension of the feature space is high. So why do we bother using local density estimation? This is because our goal is not to get an accurate estimation, but rather to use the estimation to design a well performed classifier. The inaccuracy of local density estimation does not necessarily lead to a poor decision rule.

**2. General Principle**

In local density estimation the density function *p _{n}*(

*x*) can be approximated by

where *v _{n}* is the volume of a small region

*R*around point

*x*,

*n*is the total number of samples

*x*

_{i}(

*i*=1, 2…,

*n*) drawn according to

*p*(

_{n}*x*), and

*k*

_{n}is the number of

*x*

_{i}’s which fall into region

*R*. The reason why

*p*(

_{n}*x*) can be calculated in this way is that

*p*

_{n}(

*x*) does not vary much within a relatively small region, thus the probability mass of region

*R*can be approximated by

*p*

_{n}(

*x*)

*v*

_{n}, which equals

*k*

_{n}/

*n*.

Some examples of region *R* in different dimensions: i) line segment in one-dimension, ii) circle or rectangle in two-dimension, iii) sphere or cube in three-dimension, iv) hyper sphere or hypercube in *d*-dimension (*d* > 3).

Three conditions we need to pay attention to when using formula (1) are:

i). This is because if *v*_{n} is fixed, then *p*_{n}(*x*) only represents the average probability density as *n* grows larger, but what we need is the point probability density, so we should have when .

ii). This is to make sure that we do not get zero probability density.

iii). This is to make sure that *p*_{n}(*x*) does not diverge.

**3. Parzen Density Estimation**

In Parzen density estimation *v*_{n} is directly determined by *n* while *k*_{n} is a random variable which denotes the number of samples that fall into *v*_{n}. Assume that the region *R* is a *d*-dimensional hypercube with its edge length *h*_{n}, thus

*v*

_{n}= (

*h*

_{n})

^{d}The equivalent conditions which meet the aforementioned three conditions are:

Therefore *v*_{n} can be chosen as or , where *h* is an adjustable constant. Now that the relationship between *v*_{n} and *n* is defined, the next step is to determine *k*_{n}. To determine *k*_{n}, we define a window function as follows:

where *x*_{i}’s (*i* = 1, 2, …, *n*) are the given samples and *x* is the point where the density is to be estimated. Thus we have

The function is called a Parzen window function, which enables us to count the number of sample points in the hypercube with its edge length *h*_{n}. According to [2], using hypercube as the window function may lead to discontinuity in the estimation. This is due to the superimposition of sharp pulses centered at the given sample points when h is small. To overcome this shortcoming, we can consider a more general form of window function rather than the hypercube. Note that if the following two conditions are met, the estimated *p*_{n}(*x*) is guaranteed to be proper.

Therefore a better choice of window function which removes discontinuity can be Gaussian window:

The estimated density is given by

Consider a one-dimension case, assume that , thus , where *h* is an adjustable constant. Substitute into formula (2) we have

We can see that if *n* equals one, *p*_{n}(*x*) is just the window function. If *n* approaches infinity, *p*_{n}(*x*) can converge to any complex form. If *n* is relatively small, *p*_{n}(*x*) is very sensitive to the value of *h*. In general small *h* leads to the noise error while large *h* leads to the over-smoothing error, which can be illustrated by the following example.

In this experiment samples are 5000 points on 2-D plane with Gaussian distribution. The mean vector is [1 2], and the covariance matrix is [1 0; 0 1]. Choose rectangle Parzen window with , thus . Fig. 1 shows the sample distribution. Fig. 2 shows the ideal probability density distribution. Fig. 3 shows the result of Parzen density estimation.

Next we change the value of *h*_{n} and see how it affects the estimation. Fig. 4 shows the result of Parzen density estimation when *h*_{n} is twice its initial value. Fig. 5 shows the result of Parzen density estimation when *h*_{n} is its initial value divided by two. We can see that the results agree with the aforesaid property of *h*_{n}.

*h*

_{n}is twice its initial value

*h*

_{n}is its initial value divided by two

To design a classifier using Parzen window method [3], we estimate the densities for each class and classify the test point by the label corresponding to the maximum posterior. Below lists some advantages and disadvantages of Parzen density estimation:

Advantages: i) *p*_{n}(*x*) can converge to any complex form when *n* approaches infinity; ii) applicable to data with any distribution.

Disadvantages: i) need a large number of samples to obtain an accurate estimation; ii) computationally expensive, not suitable for feature space with very high dimensions; iii) the adjustable constant *h* has a relatively heavy influence on the decision boundaries when *n* is small, and is not easy to choose in practice.

**4. K-Nearest Neighbor Density Estimation**

In *k*-nearest neighbor density estimation (use acronym “*k*-NN” in the following text) *k* is directly determined by *n* while *v* is a random variable which denotes the volume that encompasses just *k* sample points inside *v* and on its boundary. If *v* is a sphere, it can be given by

where *h* is the radius of the sphere with center *x*. *h*_{k} equals ||*x*_{lk} - *x*|| where *x*_{lk} is the *k*^{th} closest sample point to *x*. Then the probability density at *x* is approximated by

where *k*_{1} is number of sample points on the boundary of *v*_{k}(*x*). Most of the time formula (3) can be rewritten as

In Parzen density estimation *v*_{n} only depends on *n* and is the same for all the test points, while in *k*-NN *v _{n}*

__is smaller at high density area and is larger at low density area. This strategy seems more reasonable than the strategy to determine__

*v*

_{n}in Parzen density estimation since now

*v*

_{n}is adaptive to the local density. In practice, when we want to classify data using

*k*-NN estimation, it turns out that we can get the posterior

*p*(

*w*

_{i}|

*x*) directly without worrying about

*p*(

*x*). If we have

*k*samples fall into volume

*v*around point

*x*, and among the

*k*samples there are

*k*

_{i}samples belonging to class

*w*

_{i}, then we have

The posterior *p*(*w*_{i}|*x*) is given by

where *m* is the number of classes. Formula (4) tells us one simple decision rule: the class of a test point *x* is the same as the most frequent one among the nearest *k* points of *x*. Simple and intuitive, isn’t it? Having said that, choosing *k* in *k*-NN is still a nontrivial problem as choosing *h* in Parzen density estimation. Small *k* leads to noisy decision boundaries while large *k* leads to over-smoothed boundaries, which is illustrated by the following example. In this experiment samples are 200 pre-labeled (red or blue) points. The task is to find the classification boundaries under different *k* values. Fig. 6-9 show the results.

*k*-NN decision boundaries experiment (

*k*=2)

*k*-NN decision boundaries experiment (

*k*=3)

*k*-NN decision boundaries experiment (

*k*=5)

*k*-NN decision boundaries experiment (

*k*=8)

In practice we can use cross-validation to choose the “best” *k*. Below lists some advantages and disadvantages of *k*-NN:

Advantages: i) decision performance is good if *n* is large enough; ii) applicable to data with any distribution; iii) simple and intuitive.

Disadvantages: i) need a large number of samples to obtain an accurate estimation, which is inevitable in local density estimation; ii) computationally expensive, low efficiency for feature space with very high dimensions; iii) choosing the “best” *k* is nontrivial.

**5. Reference**

[1] Mireille Boutin, “ECE662: Statistical Pattern Recognition and Decision Making Processes,” Purdue University, Spring 2014

[2] http://www.cse.buffalo.edu/~jcorso/t/CSE555/files/annote_28feb_nonprm.pdf

[3] http://www.csd.uwo.ca/~olga/Courses/CS434a_541a/Lecture6.pdf

## Questions and comments

If you have any questions, comments, etc. please post them on this page.