Properties of bagged nearest neighbour classifiers

• 成果类型: Article
• 署名作者: Hall, P; Samworth, RJ
• 署名单位: University of Cambridge; Australian National University
• 刊物名称: JOURNAL OF THE ROYAL STATISTICAL SOCIETY SERIES B-STATISTICAL METHODOLOGY
• ISSN/ISSBN: 1369-7412
• DOI: 10.1111/j.1467-9868.2005.00506.x
• 发表日期: 2005
• 页码: 363-379
• 关键词: cross-validation; CLASSIFICATION; error; regression; RULE

摘要

It is shown that bagging, a computationally intensive method, asymptotically improves the performance of nearest neighbour classifiers provided that the resample size is less than 69% of the actual sample size, in the case of with-replacement bagging, or less than 50% of the sample size, for without-replacement bagging. However, for larger sampling fractions there is no asymptotic difference between the risk of the regular nearest neighbour classifier and its bagged version. In particular, neither achieves the large sample performance of the Bayes classifier. In contrast, when the sampling fractions converge to 0, but the resample sizes diverge to infinity, the bagged classifier converges to the optimal Bayes rule and its risk converges to the risk of the latter. These results are most readily seen when the two populations have well-defined densities, but they may also be derived in other cases, where densities exist in only a relative sense. Cross-validation can be used effectively to choose the sampling fraction. Numerical calculation is used to illustrate these theoretical properties.