Discovering the set of fundamental rule changes

ABSTRACT

The world around us changes constantly. Knowing what has changed is an important part of our lives. For businesses, recognizing changes is also crucial. It allows businesses to adapt themselves to the changing market needs. In this paper, we study changes of association rules from one time period to another. One approach is to compare the supports and/or confidences of each rule in the two time periods and report the differences. This technique, however, is too simplistic as it tends to report a huge number of rule changes, and many of them are, in fact, simply the snowball effect of a small subset of fundamental changes. Here, we present a technique to highlight the small subset of fundamental changes. A change is fundamental if it cannot be explained by some other changes. The proposed technique has been applied to a number of real-life datasets. Experiments results show that the number of rules whose changes are unexplainable is quite small (about 20% of the total number of changes discovered), and many of these unexplainable changes reflect some fundamental shifts in the application domain.

REFERENCES

• 1: Agrawal, R. and Psaila, G. "Active data mining." KDD-95.
• 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: Bayardo, R., Agrawal, R, and Gunopulos, D. "Constraintbased rule mining in large, dense databases." ICDE-99, 1999.
• 4: 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
• 5: Guozhu Dong , Jinyan Li, Efficient mining of emerging patterns: discovering trends and differences, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.43-52, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312191]
• 6: Ester, M., Frommelt, A., Kriegel, H-P., and Sander, J. "Algorithms for characterization and trend detection in spatial databases." KDD-98, 1998.
• 7: Fayyad, U. M. and Irani, K. B. "Multi-interval discretization of continuous-valued attributes for classification learning." IJCAI-93, 1993.
• 8: Venkatesh Ganti , Johannes Gehrke , Raghu Ramakrishnan, A framework for measuring changes in data characteristics, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.126-137, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.303989]
• 9: Ganti, V., Gehrke, J., and Ramakrishnan, R. "DEMON: mining and monitoring evolving data." ICDE-2000, 2000.
• 10: 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
• 11: Johnson T. and Dasu, T. "Comparing massive highdimensional data sets," KDD-98, 1998.
• 12: Kohavi, R., John, G., Long, R., Manley, D., and Pfleger, K. "MLC++: a machine learning library in C++." Tools with artificial intelligence, 740-743, 1994.
• 13: Lane, T. and Brodley, C. "Approaches to online learning and concept drift for user identification in computer security." KDD-98, 1998.
• 14: Liu, B., Hsu, W., and Chen, S. "Using general impressions to analyze discovered classification rules." KDD-97, 1997.
• 15: Liu, B., Hsu, W. and Ma, Y. Discovering the set of fundamental rule changes. NUS Technical Report, 2001.
• 16: 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]
• 17: Mann, P. Introductory statistics. John Wiley & Sons, 1998.
• 18: 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]
• 19: 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]
• 20: Gerhard Widmer , Miroslav Kubat, Learning in the presence of concept drift and hidden contexts, Machine Learning, v.23 n.1, p.69-101, April 1996 [doi>10.1023/A:1018046501280]

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

  J. Computer Applications
  J.1 ADMINISTRATIVE DATA PROCESSING
      Subjects: Business

General Terms:
Algorithms, Design, Economics

Keywords:
Change mining, data mining