Asymptotic expansions of the k nearest neighbor risk

• 成果类型: Article
• 署名作者: Snapp, RR; Venkatesh, SS
• 署名单位: University of Vermont; University of Pennsylvania
• 刊物名称: ANNALS OF STATISTICS
• ISSN/ISSBN: 0090-5364
• 发表日期: 1998
• 页码: 850-878
• 关键词: error

摘要

The finite-sample risk of the k nearest neighbor classifier that uses a weighted L-p-metric as a measure of class similarity is examined. For a family of classification problems with smooth distributions in R-n, an asymptotic expansion for the risk is obtained in decreasing fractional powers of the reference sample size. An analysis of the leading expansion coefficients reveals that the optimal weighted L-p-metric, that is, the metric that minimizes the finite-sample risk, tends to a weighted Euclidean (i.e., L-2)metric as the sample size is increased. Numerical simulations corroborate this finding for a pattern recognition problem with normal class-conditional densities.