Beyond intratransaction association analysis: mining multidimensional intertransaction association rules

ABSTRACT

In this paper, we extend the scope of mining association rules from traditional single-dimensional intratransaction associations, to multidimensional intertransaction associations. Intratransaction associations are the associations among items with the same transaction, where the notion of the transaction could be the items bought by the same customer, the events happened on the same day, and so on. However, an intertransaction association describes the association relationships among different transactions, such as “if(company) A's stock goes up on day 1, B's stock will go down on day 2, but go up on day 4.” In this case, whether we treat company or day as the unit of transaction, the associated items belong to different transactions. Moreover, such an intertransaction association can be extended to associate multiple contextual properties in the same rule, so that multidimensional intertransaction associations can be defined and discovered. A two-dimensional intertransaction association rule example is “After McDonald and Burger King open branches, KFC will open a branch two months later and one mile away,” which involves two dimensions: time and space. Mining intertransaction associations poses more challenges on efficient processing than mining intratransaction associations. Interestingly, intratransaction association can be treated as a special case of intertransaction association from both a conceptual and algorithmic point of view. In this study, we introduce the notion of multidimensional intertransaction association rules, study their measurements—support and confidence—and develop algorithms for mining intertransaction associations by extension of Apriori. We overview our experience using the algorithms on both real-life and synthetic data sets. Further extensions of multidimensional intertransaction association rules and potential applications are also discussed.

REFERENCES

• 1: Rakesh Agrawal , John C. Shafer, Parallel Mining of Association Rules, IEEE Transactions on Knowledge and Data Engineering, v.8 n.6, p.962-969, December 1996 [doi>10.1109/69.553164]
• 2: 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
• 3: Rakesh Agrawal , Ramakrishnan Srikant, Mining Sequential Patterns, Proceedings of the Eleventh International Conference on Data Engineering, p.3-14, March 06-10, 1995
• 4: AGGARWAL, A., KLAWE, M., MORAN, S., SHOR, P., AND WILBUR, R. 1987. Geometrics applications of a matrix-searching algorithm. Algorithmica 2, 209-233.
• 5: 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
• 6: Elena Baralis , Giuseppe Psaila, Designing Templates for Mining Association Rules, Journal of Intelligent Information Systems, v.9 n.1, p.7-32, July/Aug. 1997 [doi>10.1023/A:1008637019359]
• 7: Claudio Bettini , X. Sean Wang , Sushil Jajodia, Testing complex temporal relationships involving multiple granularities and its application to data mining (extended abstract), Proceedings of the fifteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.68-78, June 04-06, 1996, Montreal, Quebec, Canada [doi>10.1145/237661.237680]
• 8: BETTINI, C., WANG, X., AND JAJODIA, S. 1998. Mining temporal relationships with multiple granularities in time sequences. Data Engineering 21, 1 (March), 32-38.
• 9: Sergey Brin , Rajeev Motwani , Craig Silverstein, Beyond market baskets: generalizing association rules to correlations, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.265-276, May 11-15, 1997, Tucson, Arizona, United States
• 10: David Wai-Lok Cheung , Jiawei Han , Vincent Ng , C. Y. Wong, Maintenance of Discovered Association Rules in Large Databases: An Incremental Updating Technique, Proceedings of the Twelfth International Conference on Data Engineering, p.106-114, February 26-March 01, 1996
• 11: David W. Cheung , Vincent T. Ng , Ada W. Fu , Yongjian Fu, Efficient Mining of Association Rules in Distributed Databases, IEEE Transactions on Knowledge and Data Engineering, v.8 n.6, p.911-922, December 1996 [doi>10.1109/69.553158]
• 12: DAS, G., LIN, K.-I., MANNILA, H., RENGANATHAN, G., AND SMYTH, P. 1998. Rule discovery from time series. In Proc. of the second International Conference on Knowledge Discovery and Data Mining (New York, USA, August 1998), pp. 16-22.
• 13: Min Fang , Narayanan Shivakumar , Hector Garcia-Molina , Rajeev Motwani , Jeffrey D. Ullman, Computing Iceberg Queries Efficiently, Proceedings of the 24rd International Conference on Very Large Data Bases, p.299-310, August 24-27, 1998
• 14: Ling Feng , Hongjun Lu , Jeffrey Xu Yu , Jiawei Han, Mining inter-transaction associations with templates, Proceedings of the eighth international conference on Information and knowledge management, p.225-233, November 02-06, 1999, Kansas City, Missouri, United States [doi>10.1145/319950.320007]
• 15: Takeshi Fukuda , Yasuhido Morimoto , Shinichi Morishita , Takeshi Tokuyama, Mining optimized association rules for numeric attributes, Proceedings of the fifteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.182-191, June 04-06, 1996, Montreal, Quebec, Canada [doi>10.1145/237661.237708]
• 16: Takeshi Fukuda , Yasukiko Morimoto , Shinichi Morishita , Takeshi Tokuyama, Data mining using two-dimensional optimized association rules: scheme, algorithms, and visualization, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.13-23, June 04-06, 1996, Montreal, Quebec, Canada
• 17: Eui-Hong Han , George Karypis , Vipin Kumar, Scalable parallel data mining for association rules, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.277-288, May 11-15, 1997, Tucson, Arizona, United States
• 18: 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
• 19: HAN,J.AND FU, Y. 1995b. Meta-rule-guided mining of association rules in relational databases. In Proc. of the 1st Intl. Workshop on Integration of Knowledge Discovery with Deductive and Object-Oriented Databases (Singapore, December 1995), pp. 39-46.
• 20: KAMBER, M., HAN, J., AND CHIANG, J. 1997. Metarule-guided mining of multi-dimensional association rules using data cubes. In Proc. of the International Conference on Knowledge Discovery and Data Mining (California, USA, August 1997), pp. 207-210.
• 21: Mika Klemettinen , Heikki Mannila , Pirjo Ronkainen , Hannu Toivonen , A. Inkeri Verkamo, Finding interesting rules from large sets of discovered association rules, Proceedings of the third international conference on Information and knowledge management, p.401-407, November 29-December 02, 1994, Gaithersburg, Maryland, United States [doi>10.1145/191246.191314]
• 22: Brian Lent , Arun N. Swami , Jennifer Widom, Clustering Association Rules, Proceedings of the Thirteenth International Conference on Data Engineering, p.220-231, April 07-11, 1997
• 23: MANNILA,H.AND TOIVONEN, H. 1996. Discovering generalized episodes using minimal occurrences. In Proc. of the second International Conference on Knowledge Discovery and Data Mining (Portland, Oregon, August 1996), pp. 146-151.
• 24: MANNILA, H., TOIVONEN, H., AND VERKAMO, A. 1997. Discovering frequent episodes in event sequences. Technical Report Series of Publications C, Report C-1997-15 (February), Department of Computer Science, University of Helsinki.
• 25: Rosa Meo , Giuseppe Psaila , Stefano Ceri, A New SQL-like Operator for Mining Association Rules, Proceedings of the 22th International Conference on Very Large Data Bases, p.122-133, September 03-06, 1996
• 26: R. J. Miller , Y. Yang, Association rules over interval data, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.452-461, May 11-15, 1997, Tucson, Arizona, United States
• 27: 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
• 28: Banu Özden , Sridhar Ramaswamy , Abraham Silberschatz, Cyclic Association Rules, Proceedings of the Fourteenth International Conference on Data Engineering, p.412-421, February 23-27, 1998
• 29: Jong Soo Park , Ming-Syan Chen , Philip S. Yu, An effective hash-based algorithm for mining association rules, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.175-186, May 22-25, 1995, San Jose, California, United States
• 30: Data mining for path traversal patterns in a web environment, Proceedings of the 16th International Conference on Distributed Computing Systems (ICDCS '96), p.385, May 27-30, 1996
• 31: Sridhar Ramaswamy , Sameer Mahajan , Abraham Silberschatz, On the Discovery of Interesting Patterns in Association Rules, Proceedings of the 24rd International Conference on Very Large Data Bases, p.368-379, August 24-27, 1998
• 32: 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
• 33: Craig Silverstein , Sergey Brin , Rajeev Motwani , Jeffrey D. Ullman, Scalable Techniques for Mining Causal Structures, Proceedings of the 24rd International Conference on Very Large Data Bases, p.594-605, August 24-27, 1998
• 34: 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
• 35: 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
• 36: SRIKANT, R., VU, Q., AND AGRAWAL, R. 1997. Mining association rules with item constraints. In Proc. of the 3rd Intl. Conf. on Knowledge Discovery and Data Mining (Newport Beach, California, August 1997), pp. 67-73.
• 37: 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
• 38: Dick Tsur , Jeffrey D. Ullman , Serge Abiteboul , Chris Clifton , Rajeev Motwani , Svetlozar Nestorov , Arnon Rosenthal, Query flocks: a generalization of association-rule mining, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.1-12, June 01-04, 1998, Seattle, Washington, United States
• 39: ZAKI, M., PARTHASARATHY, S., OGIHARA, M., AND LI, W. 1997. New algorithms for fast discovery of association rules. In Proc. of the 3rd International Conference on Knowledge Discovery and Data Mining (Newport Beach, CA, USA, August 1997), pp. 283-286.

INDEX TERMS

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

General Terms:
Algorithms, Experimentation, Performance

Keywords:
association rules, data mining, intra/intertransaction, multidimensional context