Efficient mining of both positive and negative association rules

ABSTRACT

This paper presents an efficient method for mining both positive and negative association rules in databases. The method extends traditional associations to include association rules of forms A ⇒ ¬ B, ¬ A ⇒ B, and ¬ A ⇒ ¬ B, which indicate negative associations between itemsets. With a pruning strategy and an interestingness measure, our method scales to large databases. The method has been evaluated using both synthetic and real-world databases, and our experimental results demonstrate its effectiveness and efficiency.

REFERENCES

• 1: Charu C. Aggarwal , Philip S. Yu, A new framework for itemset generation, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.18-24, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275490]
• 2: R. Agrawal , T. Imielinski , A. Swami, Database Mining: A Performance Perspective, IEEE Transactions on Knowledge and Data Engineering, v.5 n.6, p.914-925, December 1993 [doi>10.1109/69.250074]
• 3: 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
• 4: Roberto J. Bayardo, Jr., Efficiently mining long patterns from databases, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.85-93, June 01-04, 1998, Seattle, Washington, United States
• 5: 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
• 6: Colin L. Carter , Howard J. Hamilton , Nick Cercone, Share Based Measures for Itemsets, Proceedings of the First European Symposium on Principles of Data Mining and Knowledge Discovery, p.14-24, June 24-27, 1997
• 7: Ming-Syan Chen , Jiawei Han , Philip S. Yu, Data Mining: An Overview from a Database Perspective, IEEE Transactions on Knowledge and Data Engineering, v.8 n.6, p.866-883, December 1996 [doi>10.1109/69.553155]
• 8: 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
• 9: Farhad Hussain , Huan Liu , Einoshin Suzuki , Hongjun Lu, Exception Rule Mining with a Relative Interestingness Measure, Proceedings of the 4th Pacific-Asia Conference on Knowledge Discovery and Data Mining, Current Issues and New Applications, p.86-97, April 18-20, 2000
• 10: San-Yih Hwang , Sun-Fa Ho , Jian Tang, Mining Exception Instances to Facilitate Workflow Exception Handling, Proceedings of the Sixth International Conference on Database Systems for Advanced Applications, p.45-52, April 19-21, 1999
• 11: Huan Liu , Hongjun Lu , Ling Feng , Farhad Hussain, Efficient Search of Reliable Exceptions, Proceedings of the Third Pacific-Asia Conference on Methodologies for Knowledge Discovery and Data Mining, p.194-203, April 26-28, 1999
• 12: Padmanabhan, B. and Tuzhilin, A. 1998. A belief-driven method for discovering unexpected patterns. In Proceedings of the Fourth International Conference on Knowledge Discovery and Data Mining (KDD-98). AAAI, Newport Beach, California, USA, 94--100.
• 13: Balaji Padmanabhan , Alexander Tuzhilin, Small is beautiful: discovering the minimal set of unexpected patterns, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.54-63, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347103]
• 14: 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]
• 15: Piatetsky-Shapiro, G. 1991. Discovery, analysis, and presentation of strong rules. In Knowledge discovery in Databases. AAAI/MIT, Menlo Park, Calif., USA, 229--248.
• 16: Ashoka Savasere , Edward Omiecinski , Shamkant B. Navathe, Mining for Strong Negative Associations in a Large Database of Customer Transactions, Proceedings of the Fourteenth International Conference on Data Engineering, p.494-502, February 23-27, 1998
• 17: Takahiko Shintani , Masaru Kitsuregawa, Parallel mining algorithms for generalized association rules with classification hierarchy, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.25-36, June 01-04, 1998, Seattle, Washington, United States
• 18: Shortliffe, E. 1976. Computer Based Medical Consultations: MYCIN. Elsevier, New York.
• 19: 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
• 20: Ramakrishnan Srikant , Rakesh Agrawal, Mining generalized association rules, Future Generation Computer Systems, v.13 n.2-3, p.161-180, Nov. 1997 [doi>10.1016/S0167-739X(97)00019-8]
• 21: Suzuki, E. 1997. Autonomous discovery of reliable exception rules. In Proceedings of the Third International Conference on Knowledge Discovery and Data Mining (KDD-97). AAAI, Newport Beach, California, USA, 259--262.
• 22: Suzuki, E. and Shimura, M. 1996. Exceptional knowledge discovery in databases based on information theory. In Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (KDD-96). AAAI, Portland, Oregon, USA, 275--278.
• 23: Pang-Ning Tan , Vipin Kumar , Jaideep Srivastava, Indirect Association: Mining Higher Order Dependencies in Data, Proceedings of the 4th European Conference on Principles of Data Mining and Knowledge Discovery, p.632-637, September 13-16, 2000
• 24: Pang-Ning Tan , Vipin Kumar, Mining Indirect Associations in Web Data, Revised Papers from the Third International Workshop on Mining Web Log Data Across All Customers Touch Points, p.145-166, August 26, 2001
• 25: 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

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Knowledge acquisition

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

General Terms:
Algorithms, Experimentation

Keywords:
Association rules, negative associations