Feature Subset Selection Using Ant Colony Optimization

Authors: Ahmed Al-Ani

Abstract:

Feature selection is an important step in many pattern classification problems. It is applied to select a subset of features, from a much larger set, such that the selected subset is sufficient to perform the classification task. Due to its importance, the problem of feature selection has been investigated by many researchers. In this paper, a novel feature subset search procedure that utilizes the Ant Colony Optimization (ACO) is presented. The ACO is a metaheuristic inspired by the behavior of real ants in their search for the shortest paths to food sources. It looks for optimal solutions by considering both local heuristics and previous knowledge. When applied to two different classification problems, the proposed algorithm achieved very promising results.

Keywords: Ant Colony Optimization, ant systems, feature selection, pattern recognition.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1072066

References:

[1] A.L. Blum and P. "Langley. Selection of relevant features and examples in machine learning". Artificial Intelligence, 97:245-271, 1997.
[2] M.A. Hall. Correlation-based feature selection for machine learning. PhD thesis, The University of Waikato, 1999.
[3] R. Kohavi. Wrappers for performance enhancement and oblivious decision graphs. PhD thesis, Stanford University, 1995.
[4] P. Gallinari T. Cibas, F.F. Soulie and S. Raudys. "Variable selection with neural networks". Neurocomputing, 12:223_248, 1996.
[5] J. Kittler. "Feature set search algorithms". In C. H. Chen, editor, Pattern Recognition and Signal Processing. Sijhoff and Noordhoff, the Netherlands, 1978.
[6] P. Pudil, J. Novovicova, and J. Kittler. "Floating search methods in feature selection". Pattern Recognition Letters, 15:1119-1125, 1994.
[7] P.M. Narendra and K. Fukunaga. "A branh and bound algorithm for feature subset selection". IEEE Transactions on Computers, C-26: 917- 922, 1977.
[8] J. Yang and V. Honavar, "Feature subset selection using a genetic algorithm," IEEE Transactions on Intelligent Systems, 13: 44-49, 1998.
[9] M. Gletsos, S.G. Mougiakakou, G.K. Matsopoulos, K.S. Nikita, A.S. Nikita, and D. Kelekis. "A Computer-Aided Diagnostic System to Characterize CT Focal Liver Lesions: Design and Optimization of a Neural Network Classifier" IEEE Transactions on Information Technology in Biomedicine, 7: 153-162, 2003.
[10] I.-S. Oh, J.-S. Lee, and B.-R. Moon, "Hybrid Genetic Algorithms for Feature Selection" IEEE Transactions on Pattern Analysis and Machine Intelligence, 26: 1424-1437, 2004.
[11] M. Dorigo, V. Maniezzo, and A. Colorni. "Ant System: Optimization by a colony of cooperating agents". IEEE Transactions on Systems, Man, and Cybernetics - Part B, 26:29-41, 1996.
[12] T. St├╝tzle and M. Dorigo. "The Ant Colony Optimization Metaheuristic: Algorithms, Applications, and Advances". In F. Glover and G. Kochenberger, editors, Handbook of Metaheuristics, Kluwer Academic Publishers, Norwell, MA, 2002.
[13] G. Di Caro and M. Dorigo. "AntNet: Distributed stigmergetic control for communications networks". Journal of Artificial Intelligence Research, 9:317-365, 1998.
[14] R.S. Parpinelli; H.S. Lopes; A.A. Freitas, "Data mining with an ant colony optimization algorithm", IEEE Transactions on Evolutionary Computation, 6: 321 - 332 2002.
[15] G. Di Caro and M. Dorigo. "AntNet: Distributed stigmergetic control for communications networks". Journal of Artificial Intelligence Research, 9:317-365, 1998.
[16] R. Montemanni, L.M. Gambardella, A.E. Rizzoli and A.V. Donati. "A new algorithm for a Dynamic Vehicle Routing Problem based on Ant Colony System". Proceedings of ODYSSEUS 2003, 27-30, 2003.
[17] A. Al-Ani, M. Deriche and J. Chebil. "A new mutual information based measure for feature selection", Intelligent Data Analysis, 7: 43-57, 2003.
[18] Signal and Image Processing Institute, USC. USE-SIPI image database, 1981. http://sipi.usc.edu/services/database/.