Email this article 
Open Access
Subscription or Fee Access
TARPIN: Discovering Temporal Association Rules Using P-Tree Based Incremental Algorithm
Abstract
Association rule mining is one of very popular data mining method and number of organizations uses this technique to find the frequent item-sets of products to improve the benefits of organizations. There are number of available algorithms for association rule mining which takes multiple scans of database. The complexities of association rule algorithms primarily depends on number of database scan, so by reducing the number of database scans one can improve the time complexity of these algorithms. The purpose of this proposed algorithm is to reduce the number of database scans for discovering the temporal association rules by applying P-Tree algorithm for temporal association rules which takes just one scan of database to find out the association rules.
A new pattern tree algorithm for mining temporal association rules in databases is introduced. This algorithm uses P-Tree (Pattern – Trees) structures for finding temporal association rules in databases. According to different time periods associated with transactions in temporal databases, it will initiate the number of P-Trees and according to time information in transactions it inserts the transactions in created appropriate trees, then using P-Tree association rule mining algorithm it finds out the frequent sets in this P-Tree and then these frequent items are merged with different time periods which will give the association rules with valid time periods. The proposed algorithm is divided in two phases in first phase all item within the transactions are inserted in different P-Trees on which the frequent item-sets are taken out and in second (merge phase) these frequent items are merged and time associates with these items are in listed which indicates that these frequent items are frequent in this time periods. Algorithm is implemented in C++ under Linux platform and evaluated results are compared with existing popular algorithm PPM (Progressive Partition Miner) for discovering temporal association rule.
Keywords
References
Chang-Hung Lee, Ming-Syan Chen, and Cheng-Ru Lin,”Progressive Partitioning Miner : An Efficient Algorithm for Mining General Temporal Association Rules”, IEEE transactions on knowledge discovery and data engineering, vol. 15, no. 4, pp 1004-1016, Aug. 2003.
Cheng-yue Chang, Ming-Syan Chen and Chang-Hung Lee, “Mining General Temporal Association Rules for Items with Different Exhibition Periods”, IEEE transactions on knowledge discovery and data engineering, IEEE, pp 58-66, 2002.
Jaun M. Ale, Gustavo H. Rossi, “An Approach to discovering Temporal Association Rules”, ACM, pp 294-300, 2000.
Francisco Guil, Alfonso Bosch, and Roque Marin, “TSET : An Algorithm for mining Frequent Temporal Patterns”, Artificial Intelligence and Knowledge discovery group, pp 51-62, 2003
Yingjiu Li, Peng Ning, X Sean Wang, Sushil Jajodia, “Discovering Calendar-based Temporal Association Rules”, IEEE, pp 111-118, 2001.
Jiawei Han, Jian Pei and Yiwen Yin, “Mining Frequent Patterns without Candidate Generation”, ACM, pp 41-50, 2000
Hao Huang, Xindong Wu, and Richard Relue, “Association Analysis with One scan of Database”, IEEE, pp 629-632, 2002
Weiqiang Lin, Mehmet A. Orgun, Graham J. Williams, “An Overview of Temporal Data Mining”, The Australian Data Mining Workshop, pp 1-8, 2003.
N.Rajkumar, M.R.Karthik, S.N. Sivanandam, “Fast Algorithm for Mining Multilevel Association Rules”, pp 680-692, IEEE, 2003.
KE Luo, Jie Wu, “A new Method to mine valid association Rules”, Proceedings of the second international conference on machine learning, pp 88-97, IEEE 2003.
Tial-rui LI, Yu-qi NIU, Jun MA, and Yang XU, “Generalized Association Rule Base Mining and Its Algorithm”, pp 919-922, National science foundation of China, 2002.
Frank Hoppner, “Discovery of Temporal Patterns, Learning rules about the qualitative behavior of time series”, pp 131-148, Springer Verlag Berlin Heidelberg 2001.
Arno Siebes and Ad Feelders , “Association Rules” , Institute of Information and Computing Science , Department of Mathematics and Computer Science , University Utrecht, pp 1-27, 2002.
Rakesh Agrawal, Ramakrishnan Srikant, “Fast Algorithm for Mining Association Rules”, IBM almalon research center, pp 1-32, 1994.
Maurice Houtsma, Arun Swami, “Set-Oriented Mining for Association Rules in Relational Databases”, IEEE, pp 25-33, 1995.
Takahiko Shintani and Masaru Kitsuregawa, “Mining Algorithm for sequential Patterns in Parallel: Hash Based Approach”, Institute of Industrial science conference, 2002.
Mohammad El-Haji, Osmar R. Zaiane, “Inverted Matrix: Efficient Discovery of Frequent Items in Large Datasets I the context of Interactive Mining”, SIGKDD, ACM, pp 107-111, 2003.
N. Jovanovic, V. Milutinovic, and Z. Obradovic, “Foundation of Predictive Data Mining”, IEEE, pp 53-58, 2002.
Yan Xue-song, Cai Zhi-hua, “Rule Discovery with PVMA Algorithm”, IEEE, pp 844-846, 2003.
Rakesh Agrawal, John C.Shafer, “Parallel Mining of Association Rules”, IEEE transaction on knowledge and data engineering, IEEE, pp 962-969, 2002.
Wei Wang, Jiong, “TAR: Temporal Association Rules on Evolving Numerical Attributes”, IBM and Richard Muntz, UCLA, 2002.
Frans Coenen, Paul Leng and Shakil Ahmed , “T-Trees , Vertical Partitioning and Distributed Association Rule Mining”, 13th international conference in Data Mining , ICDM, IEEE, pp 1-7, 2003.
Soon M. Chung and Congnan Luo, “Parallel Mining of Maximal Frequent Itemsets from Database”, 15th IEEE international conference on tool with Artificial Intelligence , ICTAI, IEEE, pp 17-27, 2003.
Mayur Datar, Shinji Fujiwara, Aristides Gionis, Rajeev Motwani, “Finding Interesting Association without Support Pruning” , International conference on knowledge discovery and data engineering, vol. 13, no. 1, IEEE, pp 64-82,2000.
Frans Coenen, Paul Leng and Shakil Ahmed, “Data Structure for Association Rule Mining : T-Trees and P-Trees”, International conference on knowledge discovery and data engineering, vol. 16, no. 6, IEEE, pp 774-782, 2004.
Iko Pramudiono, Masaru Kitsuregawa, “FP-tax: Tree Structure Based Generalized Association Rule Mining”, DMKD, ACM, pp 60-63, 2004.
Jiawei Han and Micheline Kamber, “Data Mining: Concepts and Techniques”, Morgan Kaufmann publishers, Aug. 2000, ISBN 1-55860-489-8, pp 61-170.
-
Refbacks
- There are currently no refbacks.
This work is licensed under a Creative Commons Attribution 3.0 License.