Adaptive Gaussian Filtering
Consider the following generalization of a k-nearest neighbours scheme:
where x is a test point, W is a constant, c[i] is the class associated with the i th sample and w[i] is a weight calculated via a filter function or "kernel":
were f is the kernel and h is the width of the filter or "bandwidth".
There parameter, W, is equivalent to the number of nearest neighbours in a k-nearest neighbours classifier and is held fixed by varying the bandwidth. This keeps a uniform number of samples within the central region of the kernel.
An obvious choice for f would be a Gaussian:
where the upright brackets denote the Cartesian metric, or "l2 norm". The width of the Gaussian can be solved for by numerical root-finding.
The primary advantage of the above over a k-nearest-neighbours, is that it generates estimates that are both continuous and differentiable. Both features may be exploited, first, to find the class border, then to perform classifications and finally to estimate the conditional probabilities. Let R be the difference in conditional probabilities:
where 1 and 2 are the class labels. The border between the two is found by setting this expression to zero. The procedure used is to pick pairs points that straddle the class border and then solve along the lines between the two. Analytical derivative are used as an aid to root-finding:
The class of the test point is estimated as follows:
where the set of vectors, {b[i]}, sample the class border and c is the retrieved class. The value of R may be extrapolated to the test point:
This algorithm is robust, general and efficient, yet still supplies knowledge of the conditional probabilities which are useful for gauging the accuracy of estimates in the absence of prior knowledge of the true values.
Peter Mills (2012). "Efficient statistical classification of satellite measurements," International Journal of Remote Sensing 32(21): 6109-6132.
Terrel and Scott (1992). "Variable kernel density estimation," Annals of Statistics 20: 1236-1265