Abstract
Filtering (or editing) is mainly effective in improving the classification accuracy of the Nearest Neighbour (NN) rule, and also in reducing its storage and computational requirements. This work reviews some well-known editing algorithms for NN classification and presents alternative approaches based on combining the NN and the Nearest Centroid Neighbourhood of a sample. Finally, an empirical analysis over real data sets is provided.
This work has partially been supported by grants TIC2000-1703-C03-03 from the Spanish CICYT, SAB2001-0004 from the Spanish MECD, and 32016-A from the Mexican CONACyT.
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
Aha, D.W., Kibler, D., Albert, M.K.: Instance-based learning algorithms, Machine Learning 6 (1991) 37–66.
Alpaydin, E.: Voting over multiple condensed nearest neighbors. Artificial Intelligence Review 11 (1997) 115–132.
Barandela, R., Gasca, E.: Decontamination of training samples for supervised pattern recognition methods, In Advances in Pattern Recognition, Lecture Notes in Computer Science 1876, Springer Verlag (2000) 621–630.
Brighton, H., Mellish, C.: Advances in instance selection for instance-based learning algorithms, Data Mining and Knowledge Discovery 6 (2002) 153–172.
Chang, C.L.: Finding prototypes for nearest neighbor classifiers, IEEE Trans. on Computers 23 (1974) 1179–1184.
Chaudhuri, B.B.: A new definition of neighborhood of a point in multi-dimensional space, Pattern Recognition Letters 17 (1996) 11–17.
Cover, T.M., Hart, P.E.: Nearest neighbor pattern classification. IEEE Trans. on Information Theory 13 (1967) 21–27.
Dasarathy, B.V.: Nearest Neighbor Norms: NN Pattern Classification techniques, IEEE Computer Society Press, Los Alamos, CA, 1991.
Dasarathy, B.V.: Minimal consistent subset (MCS) identification for optimal nearest neighbor decision systems design, IEEE Trans. on Systems, Man, and Cybernetics 24 (1994) 511–517.
Devijver, P.A., Kittler, J.: Pattern Recognition: A Statistical Approach, PrenticeHall, Englewood Cliffs, NJ, 1982.
Ferri, F.J., Sánchez, J.S., Pla, F.: Editing prototypes in the finite sample size case using alternative neighbourhoods, In: Advances in Pattern Recognition, Lecture Notes in Computer Science 1451, Springer Verlag (1998) 620–629.
Ferri, F.J., Albert, J.V., Vidal, E.: Considerations about sample-size sensitivity of a family of edited nearest-neighbor rules, IEEE Trans. on Systems, Man, and Cybernetics-Part B: Cybernetics 29 (1999) 667–672.
Fukunaga, K., Narendra, P.M.: A branch and bound algorithm for computing k- nearest neighbors, IEEE Trans. on Computers 24 (1975) 750–753.
Gates, G.W.: The reduced nearest neighbor rule. IEEE Trans. on Information Theory 18 (1972) 431–433.
Grother, P.J., Candela, G.T., Blue, J.L.: Fast implementation of nearest neighbor classifiers, Pattern Recognition 30 (1997) 459–465.
Hamamoto, Y., Uchimura, S., Tomita, S.: A bootstrap technique for nearest neighbor classifier design, IEEE Trans. on Pattern Analysis and Machine Intelligence 19 (1997) 73–79.
Hand, D.J.: Construction and Assessment of Classification Rules, John Wiley &Sons, Chichester, UK, 1997.
Hart, P.E.: The condensed nearest neighbor rule, IEEE Trans. on Information Theory 14 (1968) 515–516.
Jaromczyk, J.W., Toussaint, G.T.: Relative neighbourhood graphs and their relatives, Proc. of IEEE 80 (1992) 1502–1517.
Koplowitz, J., Brown, T.A.: On the relation of performance to editing in nearest neighbor rules, Pattern Recognition 13 (1981) 251–255.
Kuncheva, L.I.: Editing for the k-nearest neighbors rule by a genetic algorithm, Pattern Recognition Letters 16 (1995) 809–814.
Lipowezky, U.: Selection of the optimal prototype subset for 1-NN classification, Pattern Recognition Letters 19 (1998) 907–918.
Liu, H., Motoda, H.: Feature Selection for Knowledge Discovery and Data Mining, Kluwer Academic Publishers, Boston, 1998.
Merz, C.J., Murphy, P.M.: UCI Repository of Machine Learning Databases, Dept. of Information and Computer Science, University of California, Irvine, CA, 1998.
Ricci, F., Avesani, P.: Data compression and local metrics for nearest neighbor classification, IEEE Trans. on Pattern Analysis and Machine Intelligence 21 (1999) 380–384.
Ritter, G.L., Woodritz, H.B., Lowry, S.R., Isenhour, T.L.: An algorithm for selective nearest neighbor rule. IEEE Trans. on Information Theory 21 (1975) 665–669.
Sánchez, J.S., Pla, F., Ferri, F.J.: Prototype selection for the nearest neighbour rule through proximity graphs, Pattern Recognition Letters 18 (1997) 507–513.
Sánchez, J.S., Pla, F., Ferri, F.J.: On the use of neighbourhood-based non-parametric classifiers, Pattern Recognition Letters 18 (1997) 1179–1186.
Short, R.D., Fukunaga, K.: The optimal distance measure for nearest neighbor classification, IEEE Trans. on Information Theory 27 (1981) 622–627.
Tomek, I.: An experiment with the edited nearest neighbor rule, IEEE Trans. on Systems, Man and Cybernetics 6 (1976) 448–452.
Vidal, E.: An algorithm for finding nearest neighbours in (approximately) constant average time”, Pattern Recognition Letters 4 (1986) 145–147.
Wilson, D.L.: Asymptotic properties of nearest neighbor rules using edited data sets, IEEE Trans. on Systems, Man and Cybernetics 2 (1972) 408–421.
Wilson, D.R., Martinez, T.R.: Reduction techniques for instance-based learning algorithms. Machine Learning 38 (2000) 257–286.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Sánchez, J.S., Barandela, R., Ferri, F.J. (2002). On Filtering the Training Prototypes in Nearest Neighbour Classification. In: Escrig, M.T., Toledo, F., Golobardes, E. (eds) Topics in Artificial Intelligence. CCIA 2002. Lecture Notes in Computer Science(), vol 2504. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-36079-4_21
Download citation
DOI: https://doi.org/10.1007/3-540-36079-4_21
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-00011-2
Online ISBN: 978-3-540-36079-7
eBook Packages: Springer Book Archive