Xindong Wu
Chengqi Zhang
Shichao Zhang
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.
- Aggarawal, C. and Yu, P. 1998. A new framework for itemset generation. In Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems. ACM, Seattle, Washington, 18--24.]] Google Scholar
- Agrawal, R., Imielinski, T., and Swami, A. 1993a. Database mining: A performance perspective. IEEE Trans. Knowledge and Data Eng. 5, 6 (Nov.), 914--925.]] Google Scholar
- Agrawal, R., Imielinski, T., and Swami, A. 1993b. Mining association rules between sets of items in massive databases. In Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data. ACM, Washington D.C., 207--216.]] Google Scholar
- Bayardo, B. 1998. Efficiently mining long patterns from databases. In Proceedings of the 1998 ACM SIGMOD International Conference on Management of Data. ACM, Seattle, Washington, 85--93.]] Google Scholar
- Brin, S., Motwani, R., and Silverstein, C. 1997. Beyond market baskets: Generalizing association rules to correlations. In Proceedings of the 1997 ACM SIGMOD International Conference on Management of Data. ACM, Tucson, Arizona, 265--276.]] Google Scholar
- Carter, C., Hamilton, H., and Cercone, N. 1997. Share based measures for itemsets. In Principles of Data Mining and Knowledge Discovery. Springer, Trondheim, Norway, 14--24.]] Google Scholar
- Chen, M., Han, J., and Yu, P. 1996. Data mining: An overview from a database perspective. IEEE Trans. Knowledge and Data Eng. 8, 6 (Nov.), 866--881.]] Google Scholar
- Han, J., Pei, J., and Yin, Y. 2000. Mining frequent patterns without candidate generation. In Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data. ACM, Dallas, Texas, 1--12.]] Google Scholar
- Hussain, F., Liu, H., Suzuki, E., and Lu, H. 2000. Exception rule mining with a relative interestingness measure. In Proceedings of The Third Pacific Asia Conference on Knowledge Discovery and Data Mining, PADKK 2000. Springer, Kyoto, Japan, 86--97.]] Google Scholar
- Hwang, S., Ho, S., and Tang, J. 1999. Mining exception instances to facilitate workflow exception handling. In Proceedings of the Sixth International Conference on Database Systems for Advanced Applications (DASFAA). IEEE Computer Society, Hsinchu, Taiwan, 45--52.]] Google Scholar
- Liu, H., Lu, H., Feng, L., and Hussain, F. 1999. Efficient search of reliable exceptions. In Proceedings of The Third Pacific Asia Conference on Knowledge Discovery and Data Mining, PADKK 1999. Springer, Beijing, China, 194--204.]] Google Scholar
- 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.]]Google Scholar
- Padmanabhan, B. and Tuzhilin, A. 2000. Small is beautiful: discovering the minimal set of unexpected patterns. In Proceedings of the Sixth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, Boston, MA, USA, 54--63.]] Google Scholar
- Park, J., Chen, M., and Yu, P. 1997. Using a hash-based method with transaction trimming for mining association rules. IEEE Trans. Knowl. Data Eng. 9, 5 (Sept.), 813--824.]] Google Scholar
- Piatetsky-Shapiro, G. 1991. Discovery, analysis, and presentation of strong rules. In Knowledge discovery in Databases. AAAI/MIT, Menlo Park, Calif., USA, 229--248.]]Google Scholar
- Savasere, A., Omiecinski, E., and Navathe, S. 1998. Mining for strong negative associations in a large database of customer transactions. In Proceedings of the Fourteenth International Conference on Data Engineering. IEEE Computer Society, Orlando, Florida, 494--502.]] Google Scholar
- Shintani, T. and Kitsuregawa, M. 1998. Parallel mining algorithms for generalized association rules with classification hierarchy. In Proceedings of the 1998 ACM SIGMOD International Conference on Management of Data. ACM, Seattle, Washington, 25--36.]] Google Scholar
- Shortliffe, E. 1976. Computer Based Medical Consultations: MYCIN. Elsevier, New York.]]Google Scholar
- Srikant, R. and Agrawal, R. 1996. Mining quantitative association rules in large relational tables. In Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data. ACM, Montreal, Quebec, Canada, 1--12.]] Google Scholar
- Srikant, R. and Agrawal, R. 1997. Mining generalized association rules. Future Generation Computer Systems 13, 2-3 (Nov.), 161--180.]] Google Scholar
- 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.]]Google Scholar
- 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.]]Google Scholar
- Tan, P., Kumar, V., and Srivastava, J. 2000. Indirect association: Mining higher order dependencies in data. In Principles of Data Mining and Knowledge Discovery. Springer, Lyon, France, 632--637.]] Google Scholar
- Tan, P. and Kumar, V. 2002. Mining indirect associations in web data. In WEBKDD 2001---Mining Web Log Data Across All Customers Touch Points, Third International Workshop, San Francisco, CA, USA, August 26, 2001, Revised Papers. Springer, San Francisco, CA, 145--166.]] Google Scholar
- Tsur, D., Ullman, J., Abiteboul, S., Clifton, C., Motwani, R., Nestorov, S., and Rosenthal, A. 1998. Query flocks: A generalization of association-rule mining. In Proceedings of the 1998 ACM SIGMOD International Conference on Management of Data. ACM, Seattle, Washington, USA, 1--12.]] Google Scholar
Index Terms
- Efficient mining of both positive and negative association rules
Recommendations
Efficient Mining of Intertransaction Association Rules
Most of the previous studies on mining association rules are on mining intratransaction associations, i.e., the associations among items within the same transaction where the notion of the transaction could be the items bought by the same customer, the ...
Mining Negatives Association Rules Using Constraints
Pattern discovery techniques, such as association rule discovery is one of the fundamental problem in data mining. Usually the task is limited to positive rules of the form X Y when X and Y are susbets of items. To enlarge the knowledge discovery from ...
Efficient algorithm for the extraction of association rules in data mining
ICCSA'06: Proceedings of the 2006 international conference on Computational Science and Its Applications - Volume Part IIThe problem of data mining is to discover the pattern or trend in huge volume of data. The problem is similar to knowledge discovery in artificial intelligence. Here our goal is to discover rules that reflect the pattern in the data. These rules are ...
Reviews
Ming-Yen Lin
Association rule mining is used to discover the relationships between items in a large database. The relationship, in general, shows that the occurrence of an item set would imply the occurrence of another item set. The wide applicability of association rules has motivated extensive research to improve the efficiency of the mining process, and the effectiveness of the mining results. This paper presents an efficient method for mining association rules, including negative associations between sets of items (named itemsets). Three forms of negative associations are discovered, such as A __?__ B, A __?__ B, and A __?__ B, where A and B are disjoint itemsets. While most of the papers in the literature describe the mining of either traditional associations or negative associations, the authors discover both associations at the same time. The proposed approach identifies all itemsets of interest, and then generates valid combinations of associations. The first step divides possible itemsets into frequent sets and negative sets, and prunes the uninteresting ones. The second step uses conditional-probability increment ratios to extract support-and-confidence valid rules. The main contribution of the paper is its presentation of a technique to mine both positive and negative associations concurrently. The authors define association rules of interest, and systematically shrink the search space of all combinations. A second contribution is the authors' application of conditional probability in the computation of rule generation; such a technique avoids the inefficiency of enumerating all positive and negative association rules. The paper efficiently mines associations, and helps decision making. Online Computing Reviews Service
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments