Infominer: mining surprising periodic patterns

ABSTRACT

In this paper, we focus on mining surprising periodic patterns in a sequence of events. In many applications, e.g., computational biology, an infrequent pattern is still considered very significant if its actual occurrence frequency exceeds the prior expectation by a large margin. The traditional metric, such as support, is not necessarily the ideal model to measure this kind of surprising patterns because it treats all patterns equally in the sense that every occurrence carries the same weight towards the assessment of the significance of a pattern regardless of the probability of occurrence. A more suitable measurement, information, is introduced to naturally value the degree of surprise of each occurrence of a pattern as a continuous and monotonically decreasing function of its probability of occurrence. This would allow patterns with vastly different occurrence probabilities to be handled seamlessly. As the accumulated degree of surprise of all repetitions of a pattern, the concept of information gain is proposed to measure the overall degree of surprise of the pattern within a data sequence. The bounded information gain property is identified to tackle the predicament caused by the violation of the downward closure property by the information gain measure and in turn provides an efficient solution to this problem. Empirical tests demonstrate the efficiency and the usefulness of the proposed model.

REFERENCES

• 1: G. Berger and A. Tuzhilin. Discovering unexpected patterns in temporal data using temporal logic. Temporal Databases - Research and Practice, Lecture Notes on Computer Sciences, (1399) 281-309, 1998.
• 2: Richard E. Blahut, Principles and practice of information theory, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1987
• 3: 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
• 4: Efficient Mining of Partial Periodic Patterns in Time Series Database, Proceedings of the 15th International Conference on Data Engineering, p.106, March 23-26, 1999
• 5: 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]
• 6: Bing Liu , Wynne Hsu , Yiming Ma, Mining association rules with multiple minimum supports, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.337-341, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312274]
• 7: Sheng Ma , Joseph L. Hellerstein, Mining Partially Periodic Event Patterns with Unknown Periods, Proceedings of the 17th International Conference on Data Engineering, p.205-214, April 02-06, 2001
• 8: Heikki Mannila , Dmitry Pavlov , Padhraic Smyth, Prediction with local patterns using cross-entropy, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.357-361, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312281]
• 9: Tim Oates , Matthew D. Schmill , Paul R. Cohen, Efficient Mining of Statistical Dependencies, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.794-799, July 31-August 06, 1999
• 10: 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]
• 11: 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]
• 12: Ke Wang , Yu He , Jiawei Han, Mining Frequent Itemsets Using Support Constraints, Proceedings of the 26th International Conference on Very Large Data Bases, p.43-52, September 10-14, 2000
• 13: Jiong Yang , Wei Wang , Philip S. Yu, Mining asynchronous periodic patterns in time series data, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.275-279, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347150]
• 14: J. Yang, W. Wang, and P. Yu. InfoMiner: mining surprising periodic patterns. IBM Research Report, 2001.
• 15: 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:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Classifier design and evaluation; Pattern analysis

General Terms:
Algorithms, Design, Performance