Bagging the Nearest Neighbour Exactly: Closed-Form Weights, an Effective Neighbour Count of (2 − s)/s, and When Bagging Cannot Change a 1-NN Classifier, Tested on Seven UCI Data Sets

Bagging, averaging a learner over many resampled training sets, is usually run by Monte Carlo. For the one-nearest-neighbour rule no simulation is needed. I prove that bagging 1-NN over all subsamples of size m from n training points is exactly a weighted nearest-neighbour rule in which the i-th nearest point gets weight C(n minus i, m minus 1) divided by C(n, m), and that with bootstrap samples of size m the weight is ((n minus i plus 1)/n) to the power m minus ((n minus i)/n) to the power m. With subsampling fraction s the weights approach the geometric sequence s(1 minus s) to the power i minus 1, so the effective number of neighbours approaches (2 minus s)/s; at n = 1,000 the exact values are 2.999, 18.915 and 96.574 for s = 0.5, 0.1 and 0.02, against 3, 19 and 99. The nearest point always gets weight s, and under the standard bootstrap it gets 0.632. A corollary follows: whenever the first weight exceeds one half, the bagged classifier makes exactly the same predictions as plain 1-NN, so bootstrap bagging can never change a 1-NN classifier. A Monte Carlo check on the airfoil data converges to the exact weights at the 1 over root B rate. In repeated five-fold cross-validation on three regression and four classification data sets from the UCI repository, exact bagging beats the best k-NN in all three regression problems: by 12.4% in RMSE on airfoil (bootstrap), 2.9% on the power-plant data and 7.2% on concrete. In classification the bootstrap bag reproduces 1-NN exactly on all four data sets, as the corollary requires, and subsampling helps only on the breast-cancer data (error 0.0299 against 0.0310).