Abstract
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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Breiman, L.: Bagging Predictors. Machine Learning 24, 123–140 (1996)
Duda, R.O., Hart, P.E.: Pattern Classification and Scene Analysis. John Wiley, New York (1973)
Freund, Y., Schapire, R.E.: Experiments with a New Boosting Algorithm. In: Proc. 13th Int. Conf. Mach. Learn., pp. 146–148. Morgan Kaufmann, San Francisco (1996)
Freund, Y., Schapire, R.E.: A Decision-theoretic Generalization of Online Learning and an Application to Boosting. J. Comput. Syst. Sci. 1, 119–139 (1997)
Quinlan, J.R.: Bagging, Boosting, and C4.5. In: Proc. 13th Nat. Conf. on AI, pp. 725–730. AAAI Press/MIT Press (1996)
Dietterich, T.G.: Ensemble methods in machine learning. In: Multiple Classifier Systems, pp. 1–15. Springer, Heidelberg (2000)
Buhlmann, P., Yu, B.: Analyzing Bagging. Annals of Statistics 30, 927–961 (2002)
Jiang, W.: Process Consistency for AdaBoost. Technical report, Dept. of Statistics, Northwestern University (2000)
Caprile, B., Merler, S., Furlanello, C.: Exact Bagging with k-Nearest Neighbour Classifiers. Technical report, IRST, 0106-03 (2001)
Efron, B., Tibshirani, R.J.: An Introduction to the Bootstrap. Chapman & Hall, New York (1993)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Caprile, B., Merler, S., Furlanello, C., Jurman, G. (2004). Exact Bagging with k-Nearest Neighbour Classifiers. In: Roli, F., Kittler, J., Windeatt, T. (eds) Multiple Classifier Systems. MCS 2004. Lecture Notes in Computer Science, vol 3077. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-25966-4_7
Download citation
DOI: https://doi.org/10.1007/978-3-540-25966-4_7
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-22144-9
Online ISBN: 978-3-540-25966-4
eBook Packages: Springer Book Archive