Time Related Association Rules Mining with Attributes Accumulation Mechanism and its Application to Traffic Prediction
Huiyu Zhou, Wei Wei, Kaoru Shimada, Shingo Mabu, and Kotaro Hirasawa
Graduate School of Information, Production and Systems, Waseda University
Hibikino 2-7, Wakamatsu-ku, Kitakyushu, Fukuoka 808-0135, Japan,
In this paper, we propose a method of association rule mining using Genetic Network Programming (GNP) with time series processing mechanism and attributes accumulation mechanism in order to find time related sequence rules efficiently in association rule extraction systems. GNP, a kind of evolutionary computation, represents solutions using graph structures. Because of the inherent features of GNP, it works well in dynamic environments. In this paper, GNP is applied to generate candidate association rules using the database consisting of a large number of time related attributes. In order to deal with a large number of attributes, GNP individual accumulates fitter attributes gradually during rounds, and the rules of each round are stored in a Small Rule Pool using a hash method, then, the rules are finally stored in a Big Rule Pool after the check of the overlap at the end of each round. The aim of this paper is to better handle association rule extraction of the databases in a variety of time-related applications, especially in the traffic prediction problems. The algorithm which can find the important time related association rules is described and several experimental results are presented considering a traffic prediction problem.
 C. Zhang and S. Zhang, “Association Rule Mining: models and algorithms,” Springer, 2002.
 R. Agrawal and R. Srikant, “Fast Algorithms for Mining Association Rules,” in Proc. of the 20th VLDB Conf., pp. 487-499, 1994.
 S. Brin, R. Motwani, and C. Silverstein, “Beyond market baskets: generalizing association rules to correlations,” In Proc. of the 1997 ACM SIGMOD Conf., pp. 265-276, 1997.
 M. Klemettinen, H. Mannila, P. Ronkainen, H. Toivonen, and A. I. Verkamo, “Finding Interesting Rules from Large Sets of Discovered Association Rules,” Proc. Third Int. Conf. Information and Knowledge Management, pp. 401-408, Nov., 1994.
 A. Savasere, E. Omiecinski, and S. Navathe, “An Efficient Algorithm for Mining Association Rules in Large Databases,” Proc.1995 Int. Conf. Very Large Data Bases, pp. 432-443, Sept.1995.
 J. S. Park, M. S. Chen, and P. S. Yu, “An Effective Hash-Based Algorithm for Mining Association Rules,” in Proc. of the 1995 ACM SIGMOD Conf., pp. 175-186, 1995.
 X. Wu, C. Zhang, and S. Zhang, “Efficient Mining of Both Positive and Negative Association Rule,” ACM Transactions on Information Systems, Vol.22, No.3, pp. 381-405, 2004.
 R. Andrews, J. Diederich, and A. B. Tickle, “Survey and critique of techniques for extracting rules from trained artificial neural networks,” Knowlege-Based Systems, Vol.8, No.6, pp. 373-389, 1995.
 R. Andrews and J. Diederich (Eds), “Rules and Networks,” In Proc. of the Rule Extraction from Trained Artificial Neural Networks Workshop, AISB'96, Queensland University of Technology, 1996.
 J. H. Holland, “Adaptation in Natural and Artificial Systems,” Ann Arbor: University of Michigan Press, 1975.
 D. E. Goldberg, “Genetic Algorithm in search, optimization and machine learning,” Addison-Wesley, 1989.
 J. R. Koza, “Genetic Programming, on the programming of computers by means of natural selection,” Cambridge, Mass., MIT Press, 1992.
 J. R. Koza, “Genetic Programming II, Automatic Discovery of Reusable Programs,” Cambridge, Mass.: MIT Press, 1994.
 S. Mabu, K. Hirasawa, and J. Hu, “A Graph-Based Evolutionary Algorithm: Genetic Network Programming(GNP) and Its Extension Using Reinforcement Learning,” Evolutionary Computation, MIT press, Vol.15, No.3, pp. 369-398, 2007.
 T. Eguchi, K. Hirasawa, J. Hu, and N. Ota, “A study of Evolutionary Multiagent Models Based on Symbiosis,” IEEE Trans. on Syst., Man and Cybernetics - Part B -, Vol.36, No.1, pp. 179-193, 2006.
 K. Shimada, K. Hirasawa, and J. Hu, “Genetic Network Programming with Acquisition Mechanisms of Association Rules,” Journal of Advanced Computational Intelligence and Intelligent Informatics, Vol.10, No.1, pp. 102-111, 2006.
 H. Zhou, W. Wei, K. Shima, S. Mabu, and K. Hirasawa, “Time Related Association Rules mining and its Application to Traffic Control,” FAN symposium'07, pp. 97-102, Nagoya.
 C. W. Omlin and C. L. Giles, “Extraction of Rules from Discrete-time Recurrent Neural Networks,” Neural Networks, Vol.9, No.1, pp.41-52, 1996.
 A. K. H. Tung, H. Lu, J. Han, and L. Feng, “Efficient Mining of Intertransaction Association Rule,” IEEE Transactions on Knowledge and Data Engineering, Vol.15, No.1, pp. 43-56, 2003.
 S. Wu and Y. Chen, “Mining Nonambiguous Temporal Patterns for Interval-Based Events,” IEEE Transactions on Knowledge and Data Engineering, Vol.19, No.6, pp. 742-758, 2007.
 P. S. Kam and A. W. C. Fu, “Discovering Temporal Pattern for Interval-Based Events,” Proc. Second Int. Conf. Data Warehousing and Knowledge Discovery (DaWaK'00), 2000.