Difference between revisions of "KnnDensityEstimation" - Rhea

Revision as of 09:27, 30 April 2014

Introduction

This slecture discusses about the K-Nearest Neighbors(k-NN) approach to estimate the density of a given distribution. The approach of K-Nearest Neighbors is very popular in signal and image processing for clustering and classification of patterns. It is an non-parametric density estimation technique which lets the region volume be a function of the training data. We will discuss the basic principle behind the k-NN approach to estimate density at a point X and then move on to building a classifier using the k-NN Density estimate.

Basic Principle

The general formulation for density estimation states that, for N Observations x₁,x₂,x₃,...,x_n the density at a point x can be approximated by the following function,

where V is the volume of some neighborhood(say A) around x and k denotes the number of observations that are contained within the neighborhood. The basic idea of k-NN is to extend the neighborhood, until the k nearest values are included. If we consider the neighborhood around x as a sphere, the volume of the sphere is given by, $ v_{k}(x_{0}) = \underset{h}{min}\left \{ \frac{\pi ^{h/2}}{\Gamma (\frac{n}{2} + 1)} \right \} $

where

If x_l is the k^th closest sample point to x, then

We approximate the density p(x) by,

Most of the time this estimate is, and

How to classify data using k-NN Density Estimate

Having seen how the density at a given point x is estimated based on the value of k and the given observations x₁,x₂,x₃,...,x_n, let's discuss about using the k-NN density estimate for classification. </br>

Method 1:

Let x₀ from Rⁿ be a point to classify.

Given are samples x_i1,x_x2,..,x_xn for i classes.

We now pick a k_i for each class and a window function, and we try to approximate the density at x₀ for each class and then pick the class with the largest density based on,

{equation here}

If the priors of the classes are unknown, we use ROC curves to estimate the priors, based on,

{equation here}

Method 2: </br>

Given are samples x_i1,x_x2,..,x_xn from a Gaussian Mixture. We choose a single value of k and and one window function,

We then approximate p(x, w_i) by,
{equation here}</br>

where V_i is the volume of the smallest window that contains k samples and k_i is the number of samples among these k that belongs to class i.

We pick a class i₀ such that, Prob(wi0|x0) >= Prob(wi|x0), for all i = 1,2,...,C

It boils down to assigning a class based on the majority vote of the k-nearest neighbors.

Computational Complexity

k-NN Algorithm stores all the training data samples. Suppose we have n samples each of dimension k, k-NN takes,

• O(d) time to calculate a single distance
• O(nd) time to find one closest neighbor
• O(knd) time to find k closest neighbors
• Giving a total complexity of O(knd)

Advantages and DisAdvantages of k-NN

K-NN is a simple and intuitive algorithm that can be applied to any kind of distribution. It gives a very good classification rate when the number of samples is large enough. But choosing the best "k" for the classifier may be difficult. The time and space complexity of the algorithm is very high, and we need to make several optimizations for efficiently running the algorithm.

Neverthless, it's one among the most popular techniques used for classification.

Post your slecture material here. Guidelines:

• If you are making a text slecture
  • Type text using wikitext markup languages
  • Type all equations using latex code between <math> </math> tags.
  • You may include links to other Project Rhea pages.

Questions and comments

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

Back to ECE662, Spring 2014