Nearest Neighbor Pattern Classification

Proved that the 1-nearest neighbor error rate is asymptotically bounded by at most twice the optimal Bayes error rate.

Theoretical anchor proving that simple instance-based memorization achieves within 2x of the theoretical minimum error limit.

Assumptions

• Conditional probability densities are smooth and continuous across feature space; infinite sample limit

Limitations

• Severe performance degradation in high dimensions due to distance concentration (curse of dimensionality)