Multiple pheromone types and other extensions to the Ant-Miner classification rule discovery algorithm
Tóm tắt
Ant-Miner is an ant-based algorithm for the discovery of classification rules. This paper proposes five extensions to Ant-Miner: (1) we utilize multiple types of pheromone, one for each permitted rule class, i.e. an ant first selects the rule class and then deposits the corresponding type of pheromone; (2) we use a quality contrast intensifier to magnify the reward of high-quality rules and to penalize low-quality rules in terms of pheromone update; (3) we allow the use of a logical negation operator in the antecedents of constructed rules; (4) we incorporate stubborn ants, an ACO variation in which an ant is allowed to take into consideration its own personal past history; (5) we use an ant colony behavior in which each ant is allowed to have its own values of the α and β parameters (in a sense, to have its own personality). Empirical results on 23 datasets show improvements in the algorithm’s performance in terms of predictive accuracy and simplicity of the generated rule set.
Tài liệu tham khảo
Abdelbar, A. M. (2008). Stubborn ants. In Proceedings IEEE swarm intelligence symposium (SIS’08) (pp. 1–5). New York: IEEE Press.
Asuncion, A., & Newman, D. (2007). UCI machine learning repository. http://www.ics.uci.edu/mlearn/MLRepository.html. Retrieved July 2009.
Chan, A., & Freitas, A. (2005). A new classification-rule pruning procedure for an ant colony algorithm. In Lecture notes in computer science: Vol. 3871. Artificial evolution (Proc. EA’05) (pp. 25–36). Heidelberg: Springer.
Cohen, W. W. (1995). Fast effective rule induction. In Proceedings of 12th international conference on machine learning (pp. 115–123). San Francisco: Morgan Kaufmann.
Deb, K. (2009). Multiobjective optimization using evolutionary algorithms. New York: Wiley.
Demšar, J. (2006). Statistical comparisons of classifiers over multiple data sets. Journal of Machine Learning Research, 7, 1–30.
Dorigo, M., & Stützle, T. (2004). Ant colony optimization. Cambridge: MIT Press.
Dorigo, M., & Stützle, T. (2010). Ant colony optimization: overview and recent advances. In M. Gendreau & J. Y. Potvin (Eds.), Handbook of metaheuristics (pp. 227–263). New York: Springer.
Frank, E., & Witten, I. H. (1998). Generating accurate rule sets without global optimization. In Proceedings of the fifteenth international conference on machine (pp. 144–151). San Francisco: Morgan Kaufmann.
Galea, M., & Shen, Q. (2006). Simultaneous ant colony optimization algorithms for learning linguistic fuzzy rules. In A. Agraham, C. Grosan, & V. Ramos (Eds.), Swarm intelligence in data mining (pp. 75–99). Berlin: Springer.
Jaiwei, H., & Kamber, M. (2006). Data mining: concepts and techniques. San Francisco: Morgan Kaufmann.
Kohavi, R., & Sahami, M. (1996). Error-based and entropy-based discretization of continuous features. In Proceedings of the second international conference on knowledge discovery and data mining (pp. 114–119). Menlo Park: AAAI Press.
Liu, B., Abbass, H. A., & McKay, B. (2002). Density-based heuristic for rule discovery with ant-miner. In Proceedings of the 6th Australasia–Japan joint workshop on intelligent and evolutionary systems (AJWIS2002), Canberra, Australia (pp. 180–184).
Liu, B., Abbass, H. A., & McKay, B. (2003). Classification rule discovery with ant colony optimization. In Proceedings IEEE/WIC international conference on intelligent agent technology (pp. 83–88). IEEE Comput. Soc.: Los Alamitos.
Martens, D., Backer, M. D., Haesen, R., Vanthienen, J., Snoeck, M., & Baesens, B. (2007). Classification with ant colony optimization. IEEE Transactions on Evolutionary Computation, 11, 651–665.
Martens, D., Baesens, B., & Fawcett, T. (2011). Editorial survey: swarm intelligence for data mining. Machine Learning, 82(1), 1–42.
Otero, F., Freitas, A., & Johnson, C. G. (2008). cAnt-Miner: an ant colony classification algorithm to cope with continuous attributes. In Lecture notes in computer science: Vol. 5217. Ant colony optimization and swarm intelligence (Proc. ANTS’08) (pp. 48–59). Heidelberg: Springer.
Otero, F., Freitas, A., & Johnson, C. G. (2009). Handling continuous attributes in ant colony classification algorithms. In Proceedings IEEE symposium on computational intelligence and data mining (CIDM’09) (pp. 225–231). New York: IEEE Press.
Parpinelli, R. S., Lopes, H. S., & Freitas, A. (2002). Data mining with an ant colony optimization algorithm. IEEE Transactions on Evolutionary Computation, 6, 321–332.
Quinlan, J. R. (1993). C4.5: programs for machine learning. San Francisco: Morgan Kaufmann.
Salama, K. M., & Abdelbar, A. M. (2010). Extensions to the Ant-Miner classification rule discovery algorithm. In Proceedings seventh international conference on swarm intelligence (ANTS’10) (pp. 43–50). Berlin: Springer.
Smaldon, J., & Freitas, A. (2006). A new version of the Ant-Miner algorithm discovering unordered rule sets. In Proceedings genetic and evolutionary computation conference (GECCO-2006) (pp. 43–50). San Francisco: Morgan Kaufmann.
Stützle, T., Lòpez-Ibàñez, M., Pellegrini, P., Maur, M., Montes de Oca, M., Birattari, M., & Dorigo, M. (2010). Parameter adaptation in ant colony optimization. In Y. Hamadi, E. Monfroy, & F. Saubion (Eds.), Autonomous search. Heidelberg: Springer (in press).
Stützle, T., & Hoos, H. (2000). \(\mathcal{MAX}\)-\(\mathcal{MIN}\) ant system. Future Generation Computer Systems, 16(8), 889–914.
Swaminathan, S. (2006). Rule induction using ant colony optimization for mixed variable attributes. Master’s Thesis, Texas Tech. University, Lubbock, Texas.
Wang, Z., & Feng, B. (2004). Classification rule mining with an improved ant colony algorithm. In G. I. Webb & X. Yu (Eds.), Lecture notes in computer science: Vol. 3339. Advances in artificial intelligence (Proc. AI’04) (pp. 357–367). Heidelberg: Springer.
Witten, H., & Frank, E. (2005). Data mining: practical machine learning tools and techniques. San Francisco: Morgan Kaufmann.