A Hybrid PSO/ACO Algorithm for Discovering  Classification Rules in Data Mining

Holden, Nicholas; Freitas, Alex A.

doi:https://doi.org/10.1155/2008/316145

Journal of Artificial Evolution and Applications

On this page

Abstract References Copyright Related Articles

Special Issue

Particle Swarms: The Second Decade

View this Special Issue

Research Article | Open Access

Volume 2008 | Article ID 316145 | https://doi.org/10.1155/2008/316145

A Hybrid PSO/ACO Algorithm for Discovering Classification Rules in Data Mining

Nicholas Holden¹and Alex A. Freitas¹

Academic Editor: Jim Kennedy

Received20 Jul 2007

Accepted06 Mar 2008

Published25 May 2008

Abstract

We have previously proposed a hybrid particle swarm optimisation/ant colony optimisation (PSO/ACO) algorithm for the discovery of classification rules. Unlike a conventional PSO algorithm, this hybrid algorithm can directly cope with nominal attributes, without converting nominal values into binary numbers in a preprocessing phase. PSO/ACO2 also directly deals with both continuous and nominal attribute values, a feature that current PSO and ACO rule induction algorithms lack. We evaluate the new version of the PSO/ACO algorithm (PSO/ACO2) in 27 public-domain, real-world data sets often used to benchmark the performance of classification algorithms. We compare the PSO/ACO2 algorithm to an industry standard algorithm PART and compare a reduced version of our PSO/ACO2 algorithm, coping only with continuous data, to our new classification algorithm for continuous data based on differential evolution. The results show that PSO/ACO2 is very competitive in terms of accuracy to PART and that PSO/ACO2 produces significantly simpler (smaller) rule sets, a desirable result in data mining—where the goal is to discover knowledge that is not only accurate but also comprehensible to the user. The results also show that the reduced PSO version for continuous attributes provides a slight increase in accuracy when compared to the differential evolution variant.

References

I. H. Witten and E. Frank, Data Mining: Practical Machine Learning Tools and Techniques, Morgan Kaufmann, San Francisco, Calif, USA, 2nd edition, 2005.
U. M. Fayyad, G. Piatetsky-Shapiro, and P. Smyth, “From data mining to knowledge discovery: an overview,” in Advances in Knowledge Discovery and Data Mining, pp. 1–34, AAAI, Menlo Park, Calif, USA, 1996.
View at: Google Scholar
J. Kennedy, R. C. Eberhart, and Y. Shi, Swarm Intelligence, Morgan Kaufmann/Academic Press, San Francisco, CA, USA, 2001.
D. Bratton and J. Kennedy, “Defining a standard for particle swarm optimization,” in Proceedings of the IEEE Swarm Intelligence Symposium (SIS '07), pp. 120–127, Honolulu, Hawaii, USA, April 2007.
View at: Publisher Site | Google Scholar
M. Dorigo and T. Stützle, Ant Colony Optimization, The MIT Press, Cambridge, Mass, USA, 2004.
N. Holden and A. A. Freitas, “A hybrid particle swarm/ant colony algorithm for the classification of hierarchical biological data,” in Proceedings of the IEEE Swarm Intelligence Symposium (SIS '05), pp. 100–107, Pasadena, Calif, USA, June 2005.
View at: Publisher Site | Google Scholar
N. Holden and A. A. Freitas, “Hierarchical classification of G-protein-coupled receptors with a PSO/ACO algorithm,” in Proceedings of the IEEE Swarm Intelligence Symposium (SIS '06), pp. 77–84, Indianapolis, Ind, USA, May 2006.
View at: Google Scholar
T. Sousa, A. Silva, and A. Neves, “Particle swarm based data mining algorithms for classification tasks,” Parallel Computing, vol. 30, no. 5-6, pp. 767–783, 2004.
View at: Publisher Site | Google Scholar
I. De Falco, A. Della Cioppa, and E. Tarantino, “Facing classification problems with particle swarm optimization,” Applied Soft Computing, vol. 7, no. 3, pp. 652–658, 2007.
View at: Publisher Site | Google Scholar
A. A. Freitas, R. S. Parpinelli, and H. S. Lopes, “Ant colony algorithms for data classification,” in Encyclopedia of Information Science and Technology, M. Khosrou-Pour, Ed., pp. 420–424, IGI Publishing, Hershey, Pa, USA, 2nd edition, 2005.
View at: Google Scholar
R. S. Parpinelli, H. S. Lopes, and A. A. Freitas, “Data mining with an ant colony optimization algorithm,” IEEE Transactions on Evolutionary Computation, vol. 6, no. 4, pp. 321–332, 2002.
View at: Publisher Site | Google Scholar
M. Dorigo and K. Socha, “An introduction to ant colony optimization,” in Handbook of Approximation Algorithms and Metaheuristics, T. F. Gonzalez, Ed., pp. 26.1–26.14, Chapman & Hall/CRC, Boca Raton, Fla, USA, 2007.
View at: Google Scholar
K. V. Price, R. M. Storn, and J. A. Lampinen, Differential Evolution: A Practical Approach to Global Optimization, Springer, Berlin, Germany, 2005.
N. Holden and A. A. Freitas, “A hybrid PSO/ACO algorithm for classification,” in Proceedings of the 9th Genetic and Evolutionary Computation Conference Workshop on Particle Swarms: The Second Decade (GECCO '07), pp. 2745–2750, ACM Press, London, UK, July 2007.
View at: Publisher Site | Google Scholar
J. R. Quinlan, C4.5: Programs for Machine Learning, Morgan Kaufmann, San Francisco, Calif, USA, 1993.
G. L. Pappa, Automatically evolving rule induction algorithms with grammar-based genetic programming [Ph.D. thesis, Computing Laboratory, University of Kent], Canterbury, UK, 2007.
J. Kennedy and R. Mendes, “Population structure and particle swarm performance,” in Proceedings of the IEEE Conference on Evolutionary Computation (CEC '02), pp. 1671–1676, Honolulu, Hawaii, USA, May 2002.
View at: Publisher Site | Google Scholar
E. Mezura-Montes, J. Velázquez-Reyes, and C. A. Coello Coello, “A comparative study of differential evolution variants for global optimization,” in Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation (GECCO '06), vol. 1, pp. 485–492, ACM Press, Seattle, Wash, USA, July 2006.
View at: Publisher Site | Google Scholar
D. J. Hand, Construction and Assessment of Classification Rules, John Wiley & Sons, New York, NY, USA, 1997.
P. Clark and R. Boswell, “Rule induction with CN2: some recent improvements,” in Proceedings of the 5th European Working Session on Learning (EWSL '91), pp. 151–163, Porto, Portugal, March 1991.
View at: Publisher Site | Google Scholar
D. J. Newman, S. Hettich, C. L. Blake, and C. J. Merz, “UCI repository of machine learning databases,” 1998, http://www.ics.uci.edu/~mlearn/MLRepository.html.
View at: Google Scholar
Differential Evolution Java Implementation, July 2007, http://www.icsi.berkeley.edu/~storn/code.html#java.

Copyright

Copyright © 2008 Nicholas Holden and Alex A. Freitas. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

PDF Download Citation

Download other formats

Order printed copies

Views

1396

Downloads

0

Citations