k nearest neighbors in search of a metric

摘要

The finite-sample risk of the k-nearest neighbor classifier thatuses a weighted L_p metric as a measure of class similarity isexamined. For a family of multiclass, classification problems withsmooth distributions in Rn, the risk is representedas an asymptotic expansion in decreasing fractional powers of thereference sample size. An analysis of the leading coefficients revealsthat the optimal metric (i.e., the metric that minimizes the risk) tendsto a weighted Euclidean (i.e., L₂) metric as the sample sizeis increased. Numerical calculations corroborate this finding