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 improve 1-Nearest Neighbour. It also proves that, for k > 1, Bagging has a 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