Ant colony optimization (ACO) algorithms have been successfully applied to data classification problems that aim at discovering a list of classification rules. However, on the one hand, the ACO algorithm has defects including long search times and convergence issues with non-optimal solutions. On the other hand, given bottlenecks such as memory restrictions, time complexity, or data complexity, it is too hard to solve a problem when its scale becomes too large. One solution for this issue is to design a highly parallelized learning algorithm. The MapReduce programming model has quickly emerged as the most common model for executing simple algorithmic tasks over huge volumes of data, since it is simple, highly abstract, and efficient. Therefore, MapReduce-based ACO has been researched extensively. However, due to its unidirectional communication model and the inherent lack of support for iterative execution, ACO algorithms cannot easily be implemented on MapReduce. In this paper, a novel classification rule discovery algorithm is proposed, namely MR-AntMiner, which can capitalize on the benefits of the MapReduce model. In order to construct quality rules with fewer iterations as well as less communication between different nodes to share the parameters used by each ant, our algorithm splits the training data into some subsets that are randomly mapped to different mappers; then the traditional ACO algorithm is run on each mapper to gain the local best rule set, and the global best rule list is produced in the reducer phase according to a voting mechanism. The performance of our algorithm was studied experimentally on 14 publicly available data sets and further compared to several state-of-the-art classification approaches in terms of accuracy. The experimental results show that the predictive accuracy obtained by our algorithm is statistically higher than that of the compared targets. Furthermore, experimental studies show the feasibility and the good performance of the proposed parallelized MR-AntMiner algorithm.

1. [1] A. Colorni, M. Dorigo, and V. Maniezzo, “Distributed Optimization by Ant Colonies,” Proc. of the European Conference on Artificial Life (ECAL’91), pp. 134-142, 1991.
2. [2] R. S. Parpinelli, H. S. Lopes, and A. A. Freitas, “Data mining with an ant colony optimization algorithm,” IEEE Trans. on Evolutionary Computation, Vol.6, No.4, pp. 321-332, 2002.
3. [3] S. R. Pakize and A. Gandomi, “Comparative Study of Classification Algorithms Based on MapReduce Model,” Int. J. of Innovative Research in Advanced Engineering, Vol.1, Issue 7, pp. 251-254, 2014.
4. [4] J. Dean and S. Ghemawat, “MapReduce: simplified data processing on large clusters,” Communications of the ACM, Vol.51, Issue 1, pp. 107-113, 2008.
5. [5] T. White, “Hadoop: The Definitive Guide – Storage and Analysis at Internet Scale,” 4th Edition, O’Reilly Media, Inc., 2015.
6. [6] M. Pedemonte, S. Nesmachnow, and H. Cancela, “A survey on parallel ant colony optimization,” Applied Soft Computing, Vol.11, Issue 8, pp. 5181-5197, 2011.
7. [7] B. Liu, H. A. Abbass, and B. McKay, “Density-based heuristic for rule discovery with ant-miner,” Proc. of the 6th Australasia-Japan Joint Workshop on Intelligent and Evolutionary System, pp. 180-184, 2002.
8. [8] B. Liu, H. A. Abbass, and B. McKay, “Classification Rule Discovery with Ant Colony Optimization,” IEEE Intelligent Informatics Bulletin, Vol.3, No.1, pp. 31-35, 2004.
9. [9] D. Martens, M. De Backer, R. Haesen, J. Vanthienen, M. Snoeck, and B. Baesens, “Classification with Ant Colony Optimization,” IEEE Trans. on Evolutionary Computation, Vol.11, No.5, pp. 651-665, 2007.
10. [10] A. R. Baig, W. Shahzad, and S. Khan, “Correlation as a Heuristic for Accurate and Comprehensible Ant Colony Optimization Based Classifiers,” IEEE Trans. on Evolutionary Computation, Vol.17, No.5, pp. 686-704, 2013.
11. [11] F. E. B. Otero, A. A. Freitas, and C. G. Johnson, “cAnt-Miner: An Ant Colony Classification Algorithm to Cope with Continuous Attributes,” Proc. of the 6th Int. Conf. on Ant Colony Optimization and Swarm Intelligence (ANTS 2008), pp. 48-59, 2008.
12. [12] Z. Liang, J. Sun, Q. Lin, Z. Du, J. Chen, and Z. Ming, “A novel multiple rule sets data classification algorithm based on ant colony algorithm,” Applied Soft Computing, Vol.38, pp. 1000-1011, 2016.
13. [13] M. J. Meena, K. R. Chandran, A. Karthik, and A. V. Samuel, “An enhanced ACO algorithm to select features for text categorization and its parallelization,” Expert Systems with Applications, Vol.39, Issue 5, pp. 5861-5871, 2012.
14. [14] W. Hao, N. Zhiwei, and H. Wang, “MapReduce-based ant colony optimization,” Computer Integrated Manufacturing Systems, Vol.18, No.7, pp. 1503-1509, 2012 (in Chinese).
15. [15] N. Elanthiraiyan and C. Arumugam, “Parallelized ACO Algorithm for Regression Testing Prioritization in Hadoop Framework,” Proc. of the 2014 Int. Conf. on Advanced Communications, Control and Computing Technologies, pp. 1568-1571, 2014.
16. [16] Z. Wang, T. Li, and X. Yi, “Approach for Development of Ant Colony Optimization Based on MapReduce,” Computer Science, Vol.41, Issue 7, pp. 261-265, 2014 (in Chinese).
17. [17] H. Jin and L. Ran, “A Fair-Rank Ant Colony Algorithm in Distributed Mass Storage System,” Canadian J. of Electrical and Computer Engineering, Vol.38, No.4, pp. 338-345, 2015.
18. [18] A. Siemiński and M. Kopel, “Comparing efficiency of ACO parallel implementations,” J. of Intelligent & Fuzzy Systems, Vol.32, No.2, pp. 1377-1388, 2017.
19. [19] K. P. N. Jayasena, L. Li, and Q. Xie, “Multi-Modal Multimedia Big Data Analyzing Architecture and Resource Allocation on Cloud Platform,” Neurocomputing, Vol.253, pp. 135-143, 2017.
20. [20] W. Pan, Z. Li, S. Wu, and Q. Chen, “Evaluation Large Graph Processing in MapReduce Based on Message Passing,” Chinese J. of Computers, Vol.34, No.10, pp. 1768-1784, 2011 (in Chinese).
21. [21] UCI Machine Learning Repository, http://archive.ics.uci.edu/ml/ [accessed March 1, 2018]
22. [22] J. R. Quinlan, “C4.5: Programs for Machine Learning,” Morgan Kaufmann Publishers Inc., 1993.
23. [23] V. N. Vapnik, “The Nature of Statistical Learning Theory,” SpringerVerlag, 1995.
24. [24] V. Kolias, C. Kolias, I. Anagnostopoulos, and E. Kayafas, “RuleMR: Classification Rule Discovery with MapReduce,” Proc. of the 2014 IEEE Int. Conf. on Big Data, pp. 20-28, 2014.
25. [25] Y. Mu, X. Liu, Z. Yang, and X. Liu, “A parallel C4.5 decision tree algorithm based on MapReduce,” Concurrency and Computation: Practice and Experience, Vol.29, Issue 8, Article No.e4015, 2017.
26. [26] Weka 3: Machine Learning Software in Java, http://www.cs.waikato.ac.nz/ml/weka/ [accessed March 1, 2018].
27. [27] M. Birattari, T. Stützle, L. Paquete, and K. Varrentrapp, “A racing algorithm for configuring metaheuristics,” Proc. of the 4th Annual Conf. on Genetic and Evolutionary Computation (GECCO’02), pp. 11-18, 2002.
28. [28] D. Martens, M. De Backer, R. Haesen, J. Vanthienen, M. Snoeck, and B. Baesens, “Classification with Ant Colony Optimization,” IEEE Trans. on Evolutionary Computation, Vol.11, No.5, pp. 651-665, 2007.
29. [29] Q. He, T. Shang, F. Zhuang, and Z. Shi, “Parallel extreme learning machine for regression based on MapReduce,” Neurocomputing, Vol.102, pp. 52-58, 2013.