Abstract
The nearest neighbor rule (NN) is one of the most powerful yet simple non parametric classification techniques. However, it is time consuming and it is very sensitive to noisy as well as outlier objects. To solve these deficiencies several prototype selection methods have been proposed by the scientific community. In this paper, we propose a new editing and condensing method. Our method combines the Rough Set theory and the Compact Sets structuralizations to obtain a reduced prototype set. Numerical experiments over repository databases show the high quality performance of our method according to classifier accuracy.
Chapter PDF
Similar content being viewed by others
References
Triguero, I., Derrac, J., García, S., Herrera, F.: A taxonomy and Experimental Study on prototype generation for Nearest Neighbor classification. IEEE Transactions on Systems, Man, and Cybernetics (2012), doi:10.1109/TSMCC.2010.2103939
Dasarathy, B.D.: Minimal consistent set (MCS) identification for optimal nearest neighbor decision systems design. IEEE Transactions on Systems, Man and Cybernetics 24, 511–517 (1994)
Chou, C.H., Kuo, B.A., Cheng, F.: The Generalized Condensed Nearest Neighbor rule as a data reduction technique. In: 18th International Conference on Pattern Recognition, pp. 556–559 (2006)
Olvera-López, J.A., Carrasco-Ochoa, J.A., Martínez-Trinidad, J.F.: Prototype Selection Via Prototype Relevance. In: Ruiz-Shulcloper, J., Kropatsch, W.G. (eds.) CIARP 2008. LNCS, vol. 5197, pp. 153–160. Springer, Heidelberg (2008)
Huang, C.-C.: A novel gray-based reduced NN classification method. Pattern Recognition 39, 1979–1986 (2006)
García-Borroto, M., Villuendas-Rey, Y., Carrasco-Ochoa, J.A., Martínez-Trinidad, J.F.: Finding Small Consistent Subset for the Nearest Neighbor Classifier Based on Support Graphs. In: Bayro-Corrochano, E., Eklundh, J.-O. (eds.) CIARP 2009. LNCS, vol. 5856, pp. 465–472. Springer, Heidelberg (2009)
Zafra, A., Gibaja, E.L., Ventura, S.: Multiple instance learning with multiple objective genetic programming for web mining. Applied Soft Computing 11, 93–102 (2011)
Nikolaidis, K., Goulemas, J.Y., Wu, Q.H.: A class boundary preserving algorithm for data condensation. Pattern Recognition 44, 704–715 (2011)
Wilson, D.L.: Asymptotic properties of nearest neighbor rules using edited data. IEEE Transactions on Systems, Man and Cybernetics SMC-2, 408–421 (1972)
Hattori, K., Takanashi, M.: A new edited k-nearest neighbor rule in the pattern classification problem. Pattern Recognition 33, 521–528 (2000)
Caballero, Y., Bello, R., Salgado, Y., García, M.M.: A method to edit training set based on rough sets. International Journal of Computational Intelligence Research 3, 219–229 (2007)
García-Borroto, M., Villuendas-Rey, Y., Carrasco-Ochoa, J.A., Martínez-Trinidad, J.F.: Using Maximum Similarity Graphs to Edit Nearest Neighbor Classifiers. In: Bayro-Corrochano, E., Eklundh, J.-O. (eds.) CIARP 2009. LNCS, vol. 5856, pp. 489–496. Springer, Heidelberg (2009)
Pawlak, Z.: Rough Sets. International Journal of Information & Computer Sciences 11, 341–356 (1982)
Ruiz-Shulcloper, J., Abidi, M.A.: Logical combinatorial pattern recognition: A Review. In: Pandalai, S.G. (ed.) Recent Research Developments in Pattern Recognition. Transword Research Networks, USA, pp. 133–176 (2002)
Hu, Q., Yu, D., Liu, J., Wu, C.: Neighborhood rough sets based heterogeneous feature selection. Information Sciences 178, 3577–3594 (2008)
Merz, C.J., Murphy, P.M.: UCI Repository of Machine Learning Databases. University of California at Irvine, Department of Information and Computer Science, Irvine (1998)
Wilson, R.D., Martinez, T.R.: Improved Heterogeneous Distance Functions. Journal of Artificial Intelligence Research 6, 1–34 (1997)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Villuendas-Rey, Y., Caballero-Mota, Y., García-Lorenzo, M.M. (2012). Using Rough Sets and Maximum Similarity Graphs for Nearest Prototype Classification. In: Alvarez, L., Mejail, M., Gomez, L., Jacobo, J. (eds) Progress in Pattern Recognition, Image Analysis, Computer Vision, and Applications. CIARP 2012. Lecture Notes in Computer Science, vol 7441. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-33275-3_37
Download citation
DOI: https://doi.org/10.1007/978-3-642-33275-3_37
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-33274-6
Online ISBN: 978-3-642-33275-3
eBook Packages: Computer ScienceComputer Science (R0)