A Hybrid Approach from Ant Colony Optimization and K-nearest Neighbor for Classifying Datasets Using Selected Features

Enas M.F. El Houby, Nisreen I. R. Yassin, Shaimaa Omran


This paper presents an Ant Colony Optimization (ACO) approach for feature selection. The challenge in the feature selection problem is the large search space that exists due to either redundant or irrelevant features which affects the classifier performance negatively. The proposed approach aims to minimize the subset of features used in classification and maximize the classification accuracy. The proposed approach uses several groups of ants, each group selects the candidate features using different criteria. The used ACO approach introduces the datasets to a fitness function that is composed of heuristic value component and pheromone value component. The heuristic information is represented with the Class-Separability (CS) value of the feature. The pheromone value calculation is based on the classification accuracy resulted by adding the feature. A K-Nearest Neighbor based classifier was used. The sequential forward feature selection is used, so it selects from the highest recommended features sequentially until the accuracy is enhanced. The proposed approach is applied on different medical datasets yielding promising results and findings.

Full Text:



Vieira, Susana M., Joao MC Sousa, and Thomas A. Runkler. "Multi-criteria ant feature selection using fuzzy classifiers." In Swarm Intelligence for Multi-objective Problems in Data Mining, pp. 19-36. Springer Berlin Heidelberg, 2009.

Gheyas, I.A., Smith, L.S.,“Feature subset selection in large dimensionality domains.” PatternRecognit. 43(1), 5–13 (2010).

Unler, A., Murat, A.: A discrete particle swarm optimization method for feature selection inbinary classification problems. Eur. J. Oper. Res. 206(3), 528–539 (2010).

Dash, M., Choi, K., Scheuermann, P., Liu, H.”Feature selection for clustering filter solution.” In: Proc. of Second International Conference on Data Mining, ICDM 2002, pp. 115–122 (2002).

Mitra, P., Murthy, C.A., Pal, S.K.,“Unsupervised feature selection using featuresimilarity.” IEEE Trans. Pattern Analysis and Machine Intelligence 24(3), 301–312(2002).

Miller, A.” Subset Selection in Regression.”, 2nd edn. Chapman & Hall/CRC, BocaRaton (2002).

Blum, Avrim L., and Pat Langley. "Selection of relevant features and examples in machine learning." Artificial intelligence 97, no. 1 (1997): 245-271.

Talavera, Luis. "An evaluation of filter and wrapper methods for feature selection in categorical clustering." In International Symposium on Intelligent Data Analysis, pp. 440-451. Springer Berlin Heidelberg, 2005.

Pereira, L. A. M., D. Rodrigues, T. N. S. Almeida, C. C. O. Ramos, A. N. Souza, X-S. Yang, and J. P. Papa. "A Binary Cuckoo Search and Its Application for Feature Selection." In Cuckoo Search and Firefly Algorithm, pp. 141-154. Springer International Publishing, 2014.

Fong, Simon, Suash Deb, Xin-She Yang, and Jinyan Li. "Feature selection in life science classification: metaheuristic swarm search." IT Professional 16, no. 4 (2014): 24-29.

Chen, Kun-Huang, Li-Fei Chen, and Chao-Ton Su. "A new particle swarm feature selection method for classification." Journal of Intelligent Information Systems 42, no. 3 (2014): 507-530.

Zhang, Xiangrong, Licheng Jiao, Anand Paul, Yongfu Yuan, Zhengli Wei, and Qiang Song. "Semi-supervised particle swarm optimization for classification."Mathematical Problems in Engineering 2014 (2014).

Xue, Bing, Mengjie Zhang, and Will N. Browne. "Particle swarm optimization for feature selection in classification: a multi-objective approach." IEEE transactions on cybernetics 43, no. 6 (2013): 1656-1671.

Khazaee, Ali. "Heart beat classification using particle swarm optimization."International Journal of Intelligent Systems and Applications 5, no. 6 (2013): 25.

Yeh, Wei-Chang. "Novel swarm optimization for mining classification rules on thyroid gland data." Information Sciences 197 (2012): 65-76.

Sivagaminathan, Rahul Karthik, and Sreeram Ramakrishnan. "A hybrid approach for feature subset selection using neural networks and ant colony optimization." Expert systems with applications 33, no. 1 (2007): 49-60.

Jona, J. B., and N. Nagaveni. "Ant-cuckoo colony optimization for feature selection in digital mammogram." Pakistan Journal of Biological Sciences17, no. 2 (2014): 266.

Asad, Ahmed, Ahmad Taher Azar, Nashwa El-Bendary, and Aboul Ella Hassaanien. "Ant colony based feature selection heuristics for retinal vessel segmentation." arXiv preprint arXiv:1403.1735 (2014).

Antonio J. Tallon-Ballesteros and Jose C. Riquelme, " Tackling Ant Colony Optimization Meta-Heuristic as Search Method in Feature Subset Selection Based on Correlation or Consistency Measures ", Springer International Publishing Switzerland, pp. 386–393, 2014.

Rafael Bello, Amilkar Puris, Ann Nowe, Yailen Martínez, María M. García," Two Step Ant Colony System to Solve the Feature Selection Problem", Springer-Verlag Berlin Heidelberg 2006 pp. 588 – 596.

Coello, Carlos Coello, Satchidananda Dehuri, and Susmita Ghosh, eds. Swarm intelligence for multi-objective problems in data mining. Vol. 242. Springer, 2009.

Kanan, Hamidreza Rashidy, Karim Faez, and Sayyed Mostafa Taheri. "Feature selection using ant colony optimization (ACO): a new method and comparative study in the application of face recognition system." In Industrial Conference on Data Mining, pp. 63-76. Springer Berlin Heidelberg, 2007.

Dorigo, Marco. "Optimization, learning and natural algorithms." Ph. D. Thesis, Politecnico di Milano, Italy (1992).

Dorigo, M., Maniezzo, V., Colorni, A.: Ant system: optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics 26(1), 29–41 (1996).

Tabakhi, Sina, Parham Moradi, and Fardin Akhlaghian. "An unsupervised feature selection algorithm based on ant colony optimization." Engineering Applications of Artificial Intelligence 32 (2014): 112-123.

Dehuri, Satchidananda, Susmita Ghosh, and Carlos A. Coello Coello. "An introduction to swarm intelligence for multi-objective problems." In Swarm Intelligence for Multi-objective Problems in Data Mining, pp. 1-17. Springer Berlin Heidelberg, 2009.

S. Dudoit, J. Fridlyand and T. Speed, “Comparison of discrimination methods for the classification of tumors using gene expression data”, J. Am. Stat. Assoc. 97 (2002) 77–87.

Charu C. Aggarwal, “Data Mining: The Textbook”, Springer International Publishing Switzerland 2015.

Miroslav Kubat. An Introduction to Machine Learning, Springer International Publishing Switzerland 2015.

Dadaneh, Behrouz Zamani, Hossein Yeganeh Markid, and Ali Zakerolhosseini. "Unsupervised probabilistic feature selection using ant colony optimization." Expert Systems with Applications 53 (2016): 27-42.

Wang, Gang, HaiCheng Eric Chu, Yuxuan Zhang, Huiling Chen, Weitong Hu, Ying Li, and XuJun Peng. "Multiple parameter control for ant colony optimization applied to feature selection problem." Neural Computing and Applications 26, no. 7 (2015): 1693-1708.

Kabir, Md Monirul, Md Shahjahan, and Kazuyuki Murase. "An efficient feature selection using ant colony optimization algorithm." In International Conference on Neural Information Processing, pp. 242-252. Springer Berlin Heidelberg, 2009.

Chen, Bolun, Ling Chen, and Yixin Chen. "Efficient ant colony optimization for image feature selection." Signal processing 93, no. 6 (2013): 1566-1576.

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.