Document Type : Original/Review Paper
Authors
Department of Electrical Engineering, Shahid Bahonar University of Kerman, Kerman, Iran.
Abstract
The present study aims to overcome some defects of the K-nearest neighbor (K-NN) rule. Two important data preprocessing methods to elevate the K-NN rule are prototype selection (PS) and prototype generation (PG) techniques. Often the advantage of these techniques is investigated separately. In this paper, using the gravitational search algorithm (GSA), two hybrid schemes have been proposed in which PG and PS problems have been considered together. To evaluate the classification performance of these hybrid models, we have performed a comparative experimental study including a comparison between our proposals and some approaches previously studied in the literature using several benchmark datasets. The experimental results demonstrate that our hybrid approaches outperform most of the competitive methods.
Keywords
[1] T.M. Cover and P.E. Hart, “Nearest neighbor pattern classification”, IEEE Transactions on Information Theory, vol. 13, pp. 21–27, 1967.
[2] W Li, Y Chen, and Y Song, Knowledge-Based Systems, “Boosted K-nearest neighbor classifiers based on fuzzy granules”, Knowledge-based Systems, vol. 195, pp. 1-13, 2020.
[3] R.O. Duda and P.E. Hart, Pattern Classification and Scene Analysis, Wiley Inter science, New York, 1973.
[4] J. Maillo, S. Ramírez, I. Triguero, and F. Herrera, “kNN-IS: An Iterative Spark-based design of the k-Nearest Neighbors classifier for big data”, Knowledge-based Systems, vol. 117, pp. 3-15, 2017.
[5] JJ. Valero-Mas and FJ. Castellanos, “Data Reduction in the String Space for Efficient k-NN Classification through Space Partitioning”, Applied Sciences, vol. 10, pp. 33-56, 2020.
[6] Z. Su, Q. Hu, and T. Denaeux, “A Distributed Rough Evidential K-NN Classifier: Integrating Feature Reduction and Classification”, IEEE Transactions on Fuzzy Systems, vol. 29, pp. 2322-2335, 2020.
[7] J. Hamidzadeh, N. Kashefi, and M. Moradi, “Combined weighted multi-objective optimizer for instance reduction in two-class imbalanced data problem”, Engineering Applications of Artificial Intelligence, vol. 90, pp. 103500, 2020.
[8] D. Hwang and D. Kim, “Nearest Neighbor-based prototype classification Preserving Class Regions”, Journal of Information Processing Systems, vol. 13, pp. 1345-1357, 2017.
[9] S. García, J. Derrac, JR. Cano, and F.Herrera “Prototype selection for nearest neighbor classification: Taxonomy and empirical study”, IEEE Trans. Pattern Anal. Mach. Intell, vol. 34, pp. 417–435, 2012.
[10] M. N. Ivanov, “Prototype sample selection based on minimization of the complete cross-validation functional”, Pattern Recognition and Image Analysis, vol. 20, pp. 427–437, 2010.
[11] N. Segata, E. Blanzieri, S. J. Delany, and P. Cunningham, “Noise reduction for instance-based learning with a local maximal margin approach”, Journal of Intelligent Information Systems, vol. 35, pp. 301–331, 2010.
[12] S. Ferrandiz and M. Boull´ e. “Bayesian instance selection for the nearest neighbor rule”, Machine Learning, vol. 81, pp. 229–256, 2010.
[13] M. Rubbo and LA. Silva, “Prototype Selection using Self-Organizing-Maps and Entropy for Overlapped Classes and Imbalanced Data”, International Joint Conference on Neural Networks., IJCNN, 2018, pp.1-8.
[14] P. Rosero-Montalvo and DH. Peluffo-Ordóñez, “Prototype reduction algorithms comparison in nearest neighbor classification for sensor data: Empirical study”, IEEE Second Ecuador Technical Chapters Meeting., ETCM, 2017, pp. 408–421.
[15] JR. Rico-Juan, JJ. Valero-Mas, and J. Calvo-Zaragoza, “Extensions to rank-based prototype selection in k-nearest neighbor classification”, Applied Soft Computing, vol. 85, pp. 105803, 2019.
[16] H. J. Escalante, M. Marin-Castro, A. Morales-Reyes, M. Graff, A. Rosales-Pe´rez, M. Montes-y-Go´mez, C. A. Reyes, and J. A. Gonzalez, “MOPG: a multi-objective evolutionary algorithm for prototype generation”, Pattern Analysis and Applications, vol. 20, pp. 33-47, 2017.
[17] M. Elkano, M. Galar, J. Sanz, and H. Bustince, “CHI-PG: A fast prototype generation algorithm for Big Data classification problems”, Neurocomputing, vol. 287, pp. 22-33, 2018.
[18] I. Triguero, J. Derrac, S. García, and F.Herrera, “A Taxonomy and Experimental Study on Prototype Generation for Nearest Neighbor Classification”, IEEE Transactions on Systems, Man, and Cybernetics-Part C: Applications and Reviews, vol. 42, pp. 86-100, 2012.
[19] J. Li, M.T. Manry, C. Yu, and D.R. Wilson, “Prototype classifier design with pruning”, International Journal on Artificial Intelligence Tools, vol. 14, pp. 261–280, 2005.
[20] J.S. Sa ´nchez, R. Barandela, A.I. Marque ´ s, R. Alejo, and J. Badenas, “Analysis of new techniques to obtain quality training sets”, Pattern Recognition Letters, vol. 24, pp. 1015–1022, 2003.
[21] H.A. Fayed, S.R. Hashem, and A.F. Atiya, “Self-generating prototypes for pattern classification”, Pattern Recognition, vol. 40, pp. 1498–1509, 2007.
[22] T. Raicharoen and C. Lursinsap, “A divide-and-conquer approach to the pairwise opposite class-nearest neighbor (POC-NN) algorithm”, Pattern Recognition Letters, vol. 26, pp. 1554–1567, 2005.
[23] Z. Hassani, M. Alambardar Meybodi, “Hybrid Particle Swarm Optimization with Ant-Lion Optimization: Experimental in Benchmarks and Applications”, Journal of AI and Data Mining, vol. 9, pp. 583-595, 2021.
[24] R. Storn and K.V. Price, “Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces”, Journal of Global Optimization, vol. 11, pp. 341–359, 1997.
[25] E. Rashedi, H. Nezamabadi-pour, and S. Saryazdi, “GSA: a gravitational search algorithm”, Information Sciences, vol. 179, pp. 2232–2248, 2009.
[26] L. Nanni and A. Lumini, “Particle swarm optimization for prototype reduction”, Neurocomputing, vol. 72, pp. 1092–1097, 2008.
[27] A. Cervantes, I.M. Galva ´n, and P. Isasi, “AMPSO: a new particle swarm method for nearest neighborhood classification”, IEEE Transactions on Systems, Man, and Cybernetics-Part B: Cybernetics, vol. 39, pp. 1082–1091, 2009.
[28] C. Jui-Le, T. Shih-Pang, and Y. Chu-Sing, “Using Particle Swarm Method to Optimize the Proportion of Class Label for Prototype Generation in Nearest Neighbor Classification”, Advanced Technologies, Embedded and Multimedia for Human-centric Computing, Lecture Notes in Electrical Engineering, vol. 260, pp. 239-245, 2014.
[29] I. Triguero, S. Garcı´a, and F. Herrera, “Differential evolution for optimizing the positioning of prototypes in nearest neighbor classification”, Pattern Recognition vol. 44, pp. 901–916, 2011.
[30] I. Triguero, S. Garcı´a, and F. Herrera, “IPADE: iterative prototype adjustment for nearest neighbor classification”, IEEE Transactions on Neural Networks, vol. 21, pp. 1984–1990, 2010.
[31] M. Rezaei and H. Nezamabadi-pour, “Using gravitational search algorithm in prototype generation for nearest neighbor classification”, Neurocomputing, vol. 157, pp. 256-263, 2015.
[32] H. Nezamabadi-pour, “A quantum-inspired gravitational search algorithm for binary encoded optimization problems”, Engineering Applications of Artificial Inteligence, vol. 40, pp. 62-75, 2015.
[33] S. García, J. R. Cano, and F. Herrera, “A memetic algorithm for evolutionary prototype selection: A scaling up approach”, Pattern Recognition, vol. 41, pp. 2693–2709, 2008.
[34] E. Rashedi, H. Nezamabadi-pour, and S. Saryazdi, “BGSA: binary gravitational search algorithm”, Natural Computing, vol. 9, pp. 727–745, 2010.
[35] S. Sarafrazi and H. Nezamabadi-pour, “Facing the classification of binary problems with a GSA-SVM hybrid system”, Mathematical and Computer Modelling, vol. 57, pp. 270–278, 2013.
[36] T. Kohonen, “The self-organizing map”, Proceedings of the IEEE, vol. 78, pp. 1464–1480, 1990.
[37] M. Lozano, J. M. Sotoca, J. S. S´ anchez, F. Pla, E. Pekalska, and R. P. W. Duin, “Experimental study on prototype optimization algorithms for prototype-based classification in vector spaces”, Pattern Recognition, vol. 39, pp. 1827–1838, 2006.
[38] S. W. Kim and J. Oomenn, “Enhancing prototype reduction schemes with LVQ3-type algorithms”, Pattern Recognition, vol. 36, pp. 1083–1093, 2003.
[39] J. S. Sánchez, “High training set size reduction by space partitioning and prototype abstraction”, Pattern Recognition, vol. 37, pp. 1561-1564, 2004.
[40] F. Fernández and P. Isasi, “Evolutionary design of nearest prototype classifiers”, Journal of Heuristics, vol. 10, pp. 431–454, 2004.
[41] I. Triguero, S. González, M. Moyano, S. García, J. Alcalá-Fdez, J. Luengo, A. Fernández, M. Jesús, L. Sánchez, and F. Herrera, “KEEL 3.0: an open source software for multi-stage analysis in data mining”, International Journal of Computational Intelligence Systems, vol. 10, pp. 1238-1249, 2017.
[42] A. Asuncion and D. Newman, “UCI machine learning repository”, 2007. [Online]. Available: http://www.ics.uci.edu/~mlearn/MLRepository.html.
[43] D. Sheskin, Handbook of Parametric and Non-parametric Statistical Procedures, 2nd Ed. London, U.K.: Chapman and Hall, 2006.
[44] J. Hodges and E. Lehmann, “Ranks methods for combination of independent experiments in analysis of variance”, Annals of Mathematical Statistics, vol. 33, pp. 482–497, 1962.
[45] S. Holm, “A simple sequentially rejective multiple test procedure”, Scandinavian Journal of Statistics, vol. 6, pp. 65–70, 1979.
)