Abstract
In this paper, we would like to propose a new method for constructing decision trees based on Ant Colony Optimization (ACO). The ACO is a metaheuristic inspired by the behavior of real ants, where they search for optimal solutions by considering both local heuristic and previous knowledge, observed by pheromone changes. Good results of the ant colony algorithms for solving combinatorial optimization problems suggest an appropriate effectiveness of the approach also in the task of constructing decision trees. In order to improve the accuracy of decision trees we propose an Ant Colony algorithm for constructing Decision Trees (ACDT). A heuristic function used in a new algorithm is based on the splitting rule of the CART algorithm (Classification and Regression Trees). The proposed algorithm is evaluated on a number of well-known benchmark data sets from the UCI Machine Learning repository. What deserves particular attention is the fact that empirical results clearly show that ACDT performs very good while comparing to other techniques.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Breiman, L., Friedman, J.H., Olshen, R.A., Stone, C.J.: Classification and Regression Trees. Chapman & Hall, New York (1984)
Clark, P., Niblett, T.: The CN2 rule induction algorithm. Machine Learning 3(4), 261–283 (1989)
Corne, D., Dorigo, M., Glover, F.: New Ideas in Optimization. Mc Graw–Hill, Cambridge (1999)
Doerner, K.F., Merkle, D., Stützle, T.: Special issue on ant colony optimization. Swarm Intelligence 3(1), 1–2 (2009)
Dorigo, M., Caro, G.D.: New Ideas in Optimization. McGraw–Hill, London (1999)
Dorigo, M., Caro, G.D., Gambardella, L.: Ant algorithms for distributed discrete optimization. Artif. Life 5(2), 137–172 (1999)
Dorigo, M., Gambardella, L.M.: Ant Colony System: A cooperative learning approach to the Traveling Salesman Problem. IEEE Trans. Evol. Comp. 1, 53–66 (1997)
Dorigo, M., Stützle, T.: Ant Colony Optimization. MIT Press, Cambridge (2004)
Ant Colony Optimization and Swarm Intelligence. In: Dorigo, M., et al. (eds.) ANTS 2008. LNCS, vol. 5217, Springer, Heidelberg (2008)
Dorigo, M., Birattari, M., Stützle, T., Libre, U., Bruxelles, D., Roosevelt, A.F.D.: Ant colony optimization – artificial ants as a computational intelligence technique. IEEE Comput. Intell. Mag. 1, 28–39 (2006)
Galea, M.: Applying swarm intelligence to rule induction. Master’s thesis, University of Edingbourgh (2002)
Grasse, P.P.: Termitologia, vol. II. Paris, Masson (1984)
Hyafil, L., Rivest, R.: Constructing optimal binary decision trees is NP–complete. Inf. Process. Lett. 5(1), 15–17 (1976)
Murphy, O., McCraw, R.: Designing Storage Efficient Decision Trees. IEEE Transactions on Computers 40, 315–320 (1991)
Parpinelli, R.S., Lopes, H.S., Freitas, A.A.: An ant colony algorithm for classification rule discovery. In: Abbas, H., Sarker, R., Newton, C. (eds.) Data Mining: a Heuristic Approach, Idea Group Publishing, London (2002)
Parpinelli, R.S., Lopes, H.S., Freitas, A.A.: Data mining with an ant colony optimization algorithm. IEEE Transactions on Evolutionary Computation, Special issue on Ant Colony Algorithms, 321–332 (2004)
Quinlan, J.R.: C4.5: Programs for Machine Learning. Morgan Kaufmann, San Francisco (1993)
Rokach, L., Maimon, O.: Data Mining With Decision Trees: Theory And Applications. World Scientific Publishing, Singapore (2008)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Boryczka, U., Kozak, J. (2010). Ant Colony Decision Trees – A New Method for Constructing Decision Trees Based on Ant Colony Optimization. In: Pan, JS., Chen, SM., Nguyen, N.T. (eds) Computational Collective Intelligence. Technologies and Applications. ICCCI 2010. Lecture Notes in Computer Science(), vol 6421. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-16693-8_39
Download citation
DOI: https://doi.org/10.1007/978-3-642-16693-8_39
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-16692-1
Online ISBN: 978-3-642-16693-8
eBook Packages: Computer ScienceComputer Science (R0)