Feature Subset Selection Using Ant Colony Optimization

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.

Authors:

• Ahmed Al-Ani

Keywords:

• Ant Colony Optimization
• ant systems
• feature selection
• pattern recognition.

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/.