Mining Sequential Patterns Using Hybrid Evolutionary Algorithm

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.

Authors:

• Mourad Ykhlef
• Hebah ElGibreen

Keywords:

• Genetic Algorithm
• Hybrid Evolutionary Algorithm
• Particle Swarm Optimization algorithm
• Sequential Pattern mining.

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.