Mining Sequential Patterns Using Hybrid Evolutionary Algorithm

Authors: Mourad Ykhlef, Hebah ElGibreen

Abstract:

Mining Sequential Patterns in large databases has become an important data mining task with broad applications. It is an important task in data mining field, which describes potential sequenced relationships among items in a database. There are many different algorithms introduced for this task. Conventional algorithms can find the exact optimal Sequential Pattern rule but it takes a long time, particularly when they are applied on large databases. Nowadays, some evolutionary algorithms, such as Particle Swarm Optimization and Genetic Algorithm, were proposed and have been applied to solve this problem. This paper will introduce a new kind of hybrid evolutionary algorithm that combines Genetic Algorithm (GA) with Particle Swarm Optimization (PSO) to mine Sequential Pattern, in order to improve the speed of evolutionary algorithms convergence. This algorithm is referred to as SP-GAPSO.

Keywords: Genetic Algorithm, Hybrid Evolutionary Algorithm, Particle Swarm Optimization algorithm, Sequential Pattern mining.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1330237

References:

[1] Agrawal R. and Srikant R. Mining Sequential Patterns. IBM Almaden Research Center, 650 Harry Road, San Jose, CA 95120-6099.
[2] Agrawal R. and Srikant R. 1996. Mining Sequential Patterns: Generalizations and Performance Improvements. IBM Almaden Research Center, 650 Harry Road, San Jose, CA 95120.
[3] Antunes C. and Oliveira A. Sequential Pattern Mining Algorithms: Trade-offs between Speed and Memory. Instituto Superior Tcnico / INESC-ID.
[4] Ayres J. Gehrke J. Yiu T. and Flannick J. 2002. Sequential Pattern Mining using a Bitmap Representation. SIGKDD -02 Edmonton, Alberta, Canada.
[5] Blum C. and Li X. 2008. Swarm Intelligence in Optimization. Natural Computing Series. Springer-Verlag Berlin Heidelberg, 43-85.
[6] Colombetti M. and Dorigo M. 1993. Training Agents to Perform Sequential Behavior. Italian National Research Council, TR-93-023.
[7] Fayyad U. Piatetsky-Shapiro G. and Smyth P. 1996. From Data Mining to Knowledge Discovery in Databases. American Association for Artificial Intelligence: AI Magazine, 37-54.
[8] Geng L. and Hamilton H. 2005. Interestingness Measures for Data Mining: A Survey. Computer Science, University of Regina, Regina, Saskatchewan, Canada.
[9] Goldberg D. 1989. Genetic Algorithms. Addison Wesley, ISBN: 0-201- 15767-5.
[10] Herrera F. Lozano M. and Verdegay J. 1998. Tackling Real-Coded Genetic Algorithms: Operators and tools for the Behaviour Analysis. Artificial Intelligence Review, Vol.12, 256-319.
[11] Kaya M. Alhajj R. 2004. Multi-Objective Genetic Algorithm Based Approach for Optimizing Fuzzy Sequential Patterns. 16th IEEE International Conference on Tools with Artificial Intelligence, 1082-3409/04.
[12] Montes M. 2007. Particle Swarm Optimization. IRIDIA-CoDE, Universite Libre de Bruxelles (U.L.B.).
[13] Pakhira M. and De R. 2007. Generational PipeLined Genetic Algorithm (PLGA) using Stochastic Selection. International Journal of Computer Systems Science and Engineering, Vol.4, No.1, 75 - 88.
[14] Premalatha K. and Natarajan A. 2009. Procreant PSO for fastening the convergence to optimal solution in the application of document clustering. CURRENT SCIENCE, Vol. 96, No. 1, 137- 143.
[15] Sakurai S. Kitahara Y. and Orihara R. 2008. A Sequential Pattern Mining Method based on Sequential Interestingness. International Journal of Computational Intelligence, 252-260.
[16] Shi X, Lu Y. Zhou C. Lee H. Lid W. and Liang Y. 2003. Hybrid Evolutionary Algorithms Based on PSO and GA. IEEE, 2393- 2399.
[17] Shi X, Wan L. Lee H. Yang X. Wang L. and Liang Y. (2003). An Improved Genetic Algorithm With Variable Population Size and a PSOGA Based Hybrid Evolutionary Algorithm. Proceedings of the Second International Conference on Machine Learning and Cybernetics, 1735- 1740.
[18] Spears W. Crossover or Mutation?. Navy Center for Applied Research in Artificial Intelligence, Naval Research Laboratory, Washington, D.C. 20375-5320.
[19] Spears W. and Anand V. A Study of Crossover Operators in Genetic Programming. Navy Center for Applied Research in AI, Washington, D.C 20375-5000.
[20] Tay J. and Wibowo D. 2004. An Effective Chromosome Representation for Evolving Flexible Job Shop Schedules. Intelligent Systems Lab, Nanyang Technological University, LNCS 3103, 210-221.
[21] Toracio A. Pozo A. 2007. Multiple Objective Particle Swarm for Classification-Rule Discovery. IEEE Congress on Evolutionary Computation (CEC), 684- 691.
[22] Wang H. Yeh W. Huang P. and Chang W. 2009. Using association rules and particle swarm optimization approach for part change. Expert Systems with Applications, Vol. 36, 8178-8184.
[23] Wannarumon S. Aesthetic Creation of Endless Forms: An Application in Jewelry Design. Naresuan University, Thailand, 395- 410.
[24] Wook J. and Woo S. 2005. New Encoding/Converting Methods of Binary GA/Real-Coded GA. IEICE Trans, Vol.E88-A, No.6, 1545-1564.
[25] Ykhlef M. and El-Gibreen H. 2009. Mining Sequential Patterns in Pharmacy Database Using Genetic Algorithm. 4th International Conference on Broadband Communication, Information Technology and Biomedical Applications BroadBandCom -09, Wroclaw, Poland.
[26] Zhao Q. and Bhowmick S. 2003. Sequential Pattern Mining: A Survey. CAIS, Nanyang Technological University, Singapore, No. 2003118, 1- 27.
[27] Zhanga J. Huanga D. Lokd T. Lyue M. 2006. A novel adaptive sequential niche technique for multimodal function optimization. Neurocomputing, Vol. 69, 2396-2401.
[28] Zhou Y. 2006. Study on Genetic Algorithm Improvement and Application. Master thesis.