The Projection Method for Finding Nearest Neighbors

Pattern Recognition (308-644B)

School of Computer Science, McGill University, Winter 1999

Term Project prepared by Jean-Sébastien Perrier (perrier@ai.polymtl.ca)

and Benoit Anctil (benoit@maude.biomed.mcgill.ca)

Table of content :

• Introduction
• How does it work?
• Expanded Method in D-dimensions
• Performance
• Important things to know
• References
• Also, see our Nearest Neighbors Java Applet.

Introduction

The essential purpose of a pattern recognition system consists of taking in raw data and yielding a category [1]. Even if this definition is very simple, the problem is usually more complex in real life. Once the raw data has been acquired, it is preprocessed and segmented to obtain the useful information. Then, the features or the properties of this pattern are evaluated by the feature extractor. Finally, these features are sent to a classifier, which determines the class membership.

If a training set of patterns with known class membership is available, we can use non-parametric decision rules to make decision on the membership of unknown patterns. One of these rules, called the k-nearest neighbors decision rule, classifies an unknown pattern to the class most heavily represented among its k-nearest neighbors (see figure below). This method is widely used because:

no prior knowledge of the distributions is required;

it is extremely simple to implement;

it gives a low probability of error.

On the other hand, this technique requires brute force computation of all distances in the entire data set and the storage of all these values into the computer's memory. To solve that problem, Friedman et al. [2] proposed a simple and efficient method for finding nearest neighbors which reduces significantly the amount of distance computation.

Figure 1. Decision based on the 3-nearest neighbors.

In this example, a decision based on the 3-nearest neighbors would classify the unknown pattern (green point) into class B.

How does it work?

The basic idea behind this method consists of using the projection of every point on an axis to limit the search for finding nearest neighbors. Let's look at the following example where we have a training set (prototype points) with known class membership and a test point to be classified:

Figure 2. Set of prototype points and a test point.

The following instructions describe the method suggested by Friedman to find the nearest neighbor of a test point in two dimensions:

Preprocessing
 

Finding Nearest Neighbor(s)
 

Figure 3. Illustration of steps 0 to 3.

Now we must ask ourselves if it's possible to have another point closer than the prototype A. The answer is yes, but we can also say that all the prototypes located at a distance greater than r_d from the test point should not be considered. Why? Because any point closer than the prototype A can only be located within the circle defined by the radius r_dand centered at the test point. This leads us to the next step:
 

Figure 4. Illustration of step 4.

Figure 5. Illustration of steps 5 and 6.

Until now, we have found only one nearest neighbor. If it is required to find the k-nearest neighbors, then we must add one more step to the algorithm:
 

Expanded Method in D-dimensions

The previous example illustrates the method for a data set in two dimensions. We now present the general method for finding the k-nearest neighbors for training set in d-dimensions. The idea is to find the best projection axis that minimizes the number of distance computations. In other words, for a given test point, we want to find the axis with the smallest density of prototypes around the test point.

Figure 6. Example of how the selection of the axis with the smallest density can reduce the number of distance computations. (a) All the prototypes must be verified. (b) Only 4 prototypes need to be verified.

Here are the instructions to do this:

Preprocessing
 

Metric	p	n
Manhattan	1
Euclidean	2
Maximum coordinate distance	¥

k = number of nearest neighbors, d = number of dimensions, N = number of prototypes
 
 

Finding Nearest Neighbor(s)
 

Figure 7. Illustration of the local projected density (step 0.1 to 3) for n = 10.

The following steps are the same as the first example:
 

Performance

From simulation experiments with a training set of 1000 points, it was possible to quantify the improvement made with this method (n = number of distance computations):
 

Important things to know

A uniform distribution represents a worst case for the performance of the algorithm e.g. better results are obtained with a normal (Gaussian) distribution.

The number of test points ( N_t) required for the preprocessing procedure to be profitable (step 0.1 and 0.2 in the expanded method) can be evaluated with the following equation
 

Np is the number of prototypes.

  In the computation of the distances, the Minkowski metric for p = ¥ (maximum coordinate distance) should be considered first because it also minimizes the number of distance calculations:

References
 

Here is a link to an other method:

Fast Nearest Neighbor Search in High-dimensional Space