Nearest Neighbor Pattern Classification

Inside the paper

The problem

If the distribution of categories and measurements is unknown, the ideal classifier based on that distribution cannot be applied directly. A simple alternative uses labelled examples, but its error needs to be understood relative to the best possible rule.

The idea

Assign a new point the label of its nearest labelled example and analyze its error as the sample grows. The analysis compares the resulting limiting error with the Bayes error, which assumes the underlying distribution is known.

How it works

• Collect labelled points in a space equipped with a distance, and find the training point closest to the new observation.
• Use the nearest point's label as the prediction, with a rule for resolving distance ties.
• As the sample increases, study when the nearest observation approaches the point being classified.
• Relate the limiting classification error to the conditional category probabilities and compare it with the Bayes decision rule.

What it showed

Under the paper's conditions, the limiting nearest-neighbor error is at most twice the Bayes error, and the paper gives sharper bounds. It also gives a finite-sample example and analyzes rules using more than one neighbor.

Read it for

Read Sections II, IV and VI for the rule and the error comparison, using Section V for the convergence argument. Section VII supplies a worked example; the proofs can be skimmed first and revisited for their assumptions.

Written in our own words from the paper itself. A draft the editors have not yet reviewed.