Identifying non-actionable association rules

ABSTRACT

Building predictive models and finding useful rules are two important tasks of data mining. While building predictive models has been well studied, finding useful rules for action still presents a major problem. A main obstacle is that many data mining algorithms often produce too many rules. Existing research has shown that most of the discovered rules are actually redundant or insignificant. Pruning techniques have been developed to remove those spurious and/or insignificant rules. In this paper, we argue that being a significant rule (or a non-redundant rule), however, does not mean that it is a potentially useful rule for action. Many significant rules (unpruned rules) are in fact not actionable. This paper studies this issue and presents an efficient algorithm to identify these non-actionable rules. Experiment results on many real-life datasets show that the number of non-actionable rules is typically quite large. The proposed technique thus enables the user to focus on fewer rules and to be assured that the remaining rules are non-redundant and potentially useful for action.

REFERENCES

• 1: Gediminas Adomavicius , Alexander Tuzhilin, User profiling in personalization applications through rule discovery and validation, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.377-381, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312287]
• 2: Charu C. Aggarwal , Philip S. Yu, Online Generation of Association Rules, Proceedings of the Fourteenth International Conference on Data Engineering, p.402-411, February 23-27, 1998
• 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: Bayardo, R., Agrawal, R, and Gunopulos, D. "Constraintbased rule mining in large, dense databases." ICDE-99, 1999.
• 5: Roberto J. Bayardo, Jr. , Rakesh Agrawal, Mining the most interesting rules, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.145-154, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312219]
• 6: Everitt, B. S. The analysis of contingency tables. Chapman and Hall, 1977.
• 7: Fayyad, U. M. and Irani, K. B. "Multi-interval discretization of continuous-valued attributes for classification learning." IJCAI-93, 1993.
• 8: 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
• 9: 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]
• 10: Kohavi, R., John, G., Long, R., Manley, D., and Pfieger, K. "MLC++: a machine learning library in C++." Tools with "artificial intelligence, 740-743, 1994.
• 11: Liu, B., and Hsu, W. "Post-analysis of learned rules." AAAI- 96, 1996, pp. 828-834.
• 12: Liu, B., Hsu, W. and Ma, Y. "Integrating classification and association rule mining." KDD-98, 1998.
• 13: Bing Liu , Wynne Hsu , Yiming Ma, Pruning and summarizing the discovered associations, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.125-134, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312216]
• 14: Liu, B., Hsu, W. and Ma, Y. Identifying non-actionable association rules. NUS Technical Report, 2001.
• 15: Merz, C. J, and Murphy, P. UCI repository of machine learning databases, 1996. {http://www.cs.uci.edu/~mlearn/MLRepository.html}
• 16: 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]
• 17: Piatesky-Shapiro, G., and Matheus, C."The interestingness of deviations." KDD-94, 1994.
• 18: J. Ross Quinlan, C4.5: programs for machine learning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• 19: Sigal Sahar, Interestingness via what is not interesting, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.332-336, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312272]
• 20: Avi Silberschatz , Alexander Tuzhilin, What Makes Patterns Interesting in Knowledge Discovery Systems, IEEE Transactions on Knowledge and Data Engineering, v.8 n.6, p.970-974, December 1996 [doi>10.1109/69.553165]
• 21: Tan, P-N. & Kumar, V. "Interestingness measures for association patterns: a perspective." KDD-2000 Workshop on Post-processing in Machine Learning and Data Mining, 2000
• 22: Mohammed J. Zaki, Generating non-redundant association rules, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.34-43, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347101]

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Rule-based databases

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.5 Model Development

General Terms:
Algorithms, Performance, Theory

Keywords:
Non-actionable rules, rule interestingness