Twain: Two-end association miner with precise frequent exhibition periods

ABSTRACT

We investigate the general model of mining associations in a temporal database, where the exhibition periods of items are allowed to be different from one to another. The database is divided into partitions according to the time granularity imposed. Such temporal association rules allow us to observe short-term but interesting patterns that are absent when the whole range of the database is evaluated altogether. Prior work may omit some temporal association rules and thus have limited practicability. To remedy this and to give more precise frequent exhibition periods of frequent temporal itemsets, we devise an efficient algorithm Twain (standing for TWo end AssocIation miNer.) Twain not only generates frequent patterns with more precise frequent exhibition periods, but also discovers more interesting frequent patterns. Twain employs Start time and End time of each item to provide precise frequent exhibition period while progressively handling itemsets from one partition to another. Along with one scan of the database, Twain can generate frequent 2-itemsets directly according to the cumulative filtering threshold. Then, Twain adopts the scan reduction technique to generate all frequent k-itemsets (k > 2) from the generated frequent 2-itemsets. Theoretical properties of Twain are derived as well in this article. The experimental results show that Twain outperforms the prior works in the quality of frequent patterns, execution time, I/O cost, CPU overhead and scalability.

REFERENCES

• 1: Ramesh C. Agarwal , Charu C. Aggarwal , V. V. V. Prasad, A tree projection algorithm for generation of frequent item sets, Journal of Parallel and Distributed Computing, v.61 n.3, p.350-371, March 1, 2001 [doi>10.1006/jpdc.2000.1693]
• 2: Rakesh Agrawal , Tomasz Imieliński , Arun Swami, Mining association rules between sets of items in large databases, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.207-216, May 25-28, 1993, Washington, D.C., United States
• 3: Rakesh Agrawal , Ramakrishnan Srikant, Fast Algorithms for Mining Association Rules in Large Databases, Proceedings of the 20th International Conference on Very Large Data Bases, p.487-499, September 12-15, 1994
• 4: Juan M. Ale , Gustavo H. Rossi, An approach to discovering temporal association rules, Proceedings of the 2000 ACM symposium on Applied computing, p.294-300, March 2000, Como, Italy [doi>10.1145/335603.335770]
• 5: Ayad, A. M., El-Makky, N. M., and Taha, Y. 2001. Incremental mining of constrained association rules. In Proceedings of the 1st ACM-SIAM Conference on Data Mining. ACM, New York.
• 6: Christopher Besemann , Anne Denton, Integration of profile hidden Markov model output into association rule mining, Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081933]
• 7: Bettini, C., Wang, X., and Jajodia, S. 1998. Mining temporal relationships with multiple granularities in time sequences. Bulle. IEEE Comput. Soc. Tech. Comm. Data Eng.
• 8: Julien Blanchard , Fabrice Guillet , Regis Gras , Henri Briand, Using Information-Theoretic Measures to Assess Association Rule Interestingness, Proceedings of the Fifth IEEE International Conference on Data Mining, p.66-73, November 27-30, 2005 [doi>10.1109/ICDM.2005.149]
• 9: Cheng-Yue Chang , Ming-Syan Chen , Chang-Hung Lee, Mining General Temporal Association Rules for Items with Different Exhibition Periods, Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM'02), p.59, December 09-12, 2002
• 10: Chen, J., He, H., Williams, G., and Jin, H. 2004. Temporal sequence associations for rare events. In Proceedings of the 8th Pacific Asia Conference on Knowledge Discovery and Data Mining.
• 11: Discovering Temporal Association Rules: Algorithms, Language and System, Proceedings of the 16th International Conference on Data Engineering, p.306, February 28-March 03, 2000
• 12: Chen, X., Petrounias, I., and Heathfield, H. 1998. Discovery of association rules in temporal databases. In Proceedings of the Issues and Applications of Database Technology.
• 13: Edith Cohen , Mayur Datar , Shinji Fujiwara , Aristides Gionis , Piotr Indyk , Rajeev Motwani , Jeffrey D. Ullman , Cheng Yang, Finding Interesting Associations without Support Pruning, IEEE Transactions on Knowledge and Data Engineering, v.13 n.1, p.64-78, January 2001 [doi>10.1109/69.908981]
• 14: Jiawei Han , Yongjian Fu, Discovery of Multiple-Level Association Rules from Large Databases, Proceedings of the 21th International Conference on Very Large Data Bases, p.420-431, September 11-15, 1995
• 15: Jiawei Han , Micheline Kamber, Data mining: concepts and techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2000
• 16: Jiawei Han , Jian Pei, Mining frequent patterns by pattern-growth: methodology and implications, ACM SIGKDD Explorations Newsletter, v.2 n.2, p.14-20, Dec. 2000 [doi>10.1145/380995.381002]
• 17: Jiawei Han , Jian Pei , Behzad Mortazavi-Asl , Qiming Chen , Umeshwar Dayal , Mei-Chun Hsu, FreeSpan: frequent pattern-projected sequential pattern mining, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.355-359, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347167]
• 18: Jiawei Han , Jian Pei , Yiwen Yin, Mining frequent patterns without candidate generation, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.1-12, May 15-18, 2000, Dallas, Texas, United States
• 19: Sherri K. Harms , Jitender S. Deogun, Sequential Association Rule Mining with Time Lags, Journal of Intelligent Information Systems, v.22 n.1, p.7-22, January 2004 [doi>10.1023/A:1025824629047]
• 20: Jiang, N. and Gruenwald, L. 2006. An efficient algorithm to mine online data streams. In Proceedings of the 2006 KDD TDM Workshop.
• 21: Yiping Ke , James Cheng , Wilfred Ng, MIC Framework: An Information-Theoretic Approach to Quantitative Association Rule Mining, Proceedings of the 22nd International Conference on Data Engineering, p.112, April 03-07, 2006 [doi>10.1109/ICDE.2006.94]
• 22: Cristian Bucila , Johannes Gehrke , Daniel Kifer , Walker White, DualMiner: a dual-pruning algorithm for itemsets with constraints, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775054]
• 23: Raymond T. Ng , Laks V. S. Lakshmanan , Jiawei Han , Alex Pang, Exploratory mining and pruning optimizations of constrained associations rules, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.13-24, June 01-04, 1998, Seattle, Washington, United States
• 24: Laks V. S. Lakshmanan , Raymond Ng , Jiawei Han , Alex Pang, Optimization of constrained frequent set queries with 2-variable constraints, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.157-168, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 25: Lee, C.-H., Chen, M.-S., and Lin, C.-R. 2003. Progressive partition miner: An efficient algorithm for mining general temporal association rules. IEEE Trans. Knowl. Data Eng. 15, 4 (Aug.), 1004--1017.
• 26: Chang-Hung Lee , Cheng-Ri Lin , Ming-Syan Chen, On Mining General Temporal Association Rules in a Publication Database, Proceedings of the 2001 IEEE International Conference on Data Mining, p.337-344, November 29-December 02, 2001
• 27: Chang-Hung Lee , Cheng-Ru Lin , Ming-Syan Chen, Sliding-window filtering: an efficient algorithm for incremental mining, Proceedings of the tenth international conference on Information and knowledge management, October 05-10, 2001, Atlanta, Georgia, USA [doi>10.1145/502585.502630]
• 28: Jun-Lin Lin , Margaret H. Dunham, Mining Association Rules: Anti-Skew Algorithms, Proceedings of the Fourteenth International Conference on Data Engineering, p.486-493, February 23-27, 1998
• 29: Bing Liu , Wynne Hsu , Yiming Ma, Mining association rules with multiple minimum supports, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.337-341, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312274]
• 30: Andreas Mueller, Fast sequential and parallel algorithms for association rule mining: a comparison, University of Maryland at College Park, College Park, MD, 1995
• 31: Muhonen, B. G. J. and Toivonen, H. 2005. Mining non-derivable association rules. In Proceedings of the 5th ACM SIAM Conference on Data Mining. ACM, New York.
• 32: Raymond T. Ng , Jiawei Han, Efficient and Effective Clustering Methods for Spatial Data Mining, Proceedings of the 20th International Conference on Very Large Data Bases, p.144-155, September 12-15, 1994
• 33: Jong Soo Park , Ming-Syan Chen , Philip S. Yu, Using a Hash-Based Method with Transaction Trimming for Mining Association Rules, IEEE Transactions on Knowledge and Data Engineering, v.9 n.5, p.813-825, September 1997 [doi>10.1109/69.634757]
• 34: Jian Pei , Jiawei Han, Can we push more constraints into frequent pattern mining?, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.350-354, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347166]
• 35: Jian Pei , Jiawei Han , Behzad Mortazavi-Asl , Helen Pinto , Qiming Chen , Umeshwar Dayal , Meichun Hsu, PrefixSpan: Mining Sequential Patterns by Prefix-Projected Growth, Proceedings of the 17th International Conference on Data Engineering, p.215-224, April 02-06, 2001
• 36: Ashoka Savasere , Edward Omiecinski , Shamkant B. Navathe, An Efficient Algorithm for Mining Association Rules in Large Databases, Proceedings of the 21th International Conference on Very Large Data Bases, p.432-444, September 11-15, 1995
• 37: Ramakrishnan Srikant , Rakesh Agrawal, Mining Generalized Association Rules, Proceedings of the 21th International Conference on Very Large Data Bases, p.407-419, September 11-15, 1995
• 38: Ramakrishnan Srikant , Rakesh Agrawal, Mining quantitative association rules in large relational tables, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.1-12, June 04-06, 1996, Montreal, Quebec, Canada
• 39: Michael Steinbach , Pang-Ning Tan , Vipin Kumar, Support envelopes: a technique for exploring the structure of association patterns, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014086]
• 40: Szymon Jaroszewicz, Polynomial association rules with applications to logistic regression, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150472]
• 41: Tansel, A. and Ayan, N. 1998. Discovery of association rules in temporal databases. In Proceedings of the AAAI on Knowledge Discovery in Databases.
• 42: Hannu Toivonen, Sampling Large Databases for Association Rules, Proceedings of the 22th International Conference on Very Large Data Bases, p.134-145, September 03-06, 1996
• 43: Ke Wang , Yu He , Jiawei Han, Mining Frequent Itemsets Using Support Constraints, Proceedings of the 26th International Conference on Very Large Data Bases, p.43-52, September 10-14, 2000
• 44: Xuan-Hieu Phan , Le-Minh Nguyen , Tu-Bao Ho , Susumu Horiguchi, Improving discriminative sequential learning with rare--but--important associations, Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081906]
• 45: Cheng Yang , Usama Fayyad , Paul S. Bradley, Efficient discovery of error-tolerant frequent itemsets in high dimensions, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.194-203, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502539]
• 46: Zijian Zheng , Ron Kohavi , Llew Mason, Real world performance of association rule algorithms, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.401-406, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502572]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms

Keywords:
Association, temporal