Exact Bagging with k-Nearest Neighbour Classifiers

A formula is derived for the exact computation of Bagging classifiers when the base model adopted is k-Nearest Neighbour (k-NN). The formula, that holds in any dimension and does not require the extraction of bootstrap replicates, proves that Bagging cannot imrove 1-Nearest Neghbour. It also proves that, for k>1, Bagging has smoothing effect on k-NN. Convergence of empirically bagged k-NN predictors to the exact formula is also considered. Efficient approximations to the exact formula are derived, and their applicability to practical cases is illustrated