Mining relationships among interval-based events for classification

ABSTRACT

Existing temporal pattern mining assumes that events do not have any duration. However, events in many real world applications have durations, and the relationships among these events are often complex. These relationships are modeled using a hierarchical representation that extends Allen's interval algebra. However, this representation is lossy as the exact relationships among the events cannot be fully recovered. In this paper, we augment the hierarchical representation with additional information to achieve a lossless representation. An efficient algorithm called IEMiner is designed to discover frequent temporal patterns from interval-based events. The algorithm employs two optimization techniques to reduce the search space and remove non-promising candidates. From the discovered temporal patterns, we build an interval-based classifier called IEClassifier to differentiate closely related classes. Experiments on both synthetic and real world datasets indicate the efficiency and scalability of the proposed approach, as well as the improved accuracy of IEClassifier.

REFERENCES

• 1: Rakesh Agrawal , Ramakrishnan Srikant, Mining Sequential Patterns, Proceedings of the Eleventh International Conference on Data Engineering, p.3-14, March 06-10, 1995
• 2: James F. Allen, Maintaining knowledge about temporal intervals, Communications of the ACM, v.26 n.11, p.832-843, Nov. 1983 [doi>10.1145/182.358434]
• 3: C. Antunes and A. L. Oliveira. Generalization of pattern-growth methods for sequential pattern mining with gap constraints. Machine Learning and Data Mining in Pattern Recognition, 2003.
• 4: H. Cheng, X. Yan, J. Han, and C.-W. Hsu. Discriminative frequent pattern analysis for effective classification. IEEE ICDE, 2007.
• 5: Corinna Cortes , Vladimir Vapnik, Support-Vector Networks, Machine Learning, v.20 n.3, p.273-297, Sept. 1995 [doi>10.1023/A:1022627411411]
• 6: A. Hakeem, Y. Sheikh, and M. Shah. A hierarchical event representation for the analysis of videos. AAAI, 2004.
• 7: Tu Bao Ho , Trong Dung Nguyen , Saori Kawasaki , Si Quang Le , Dung Duc Nguyen , Hideto Yokoi , Katsuhiko Takabayashi, Mining hepatitis data with temporal abstraction, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956793]
• 8: Po-shan Kam , Ada Wai-Chee Fu, Discovering Temporal Patterns for Interval-Based Events, Proceedings of the Second International Conference on Data Warehousing and Knowledge Discovery, p.317-326, September 04-06, 2000
• 9: B. Liu, W. Hsu, and Y. Ma. Integrating classification and association rule mining. SIGKDD, 1998.
• 10: H. Mannila, H. Toivonen, and I. Verkamo. Discovery of frequent episodes in event sequences. SIGKDD, 1995.
• 11: Panagiotis Papapetrou , George Kollios , Stan Sclaroff , Dimitrios Gunopulos, Discovering Frequent Arrangements of Temporal Intervals, Proceedings of the Fifth IEEE International Conference on Data Mining, p.354-361, November 27-30, 2005 [doi>10.1109/ICDM.2005.50]
• 12: Jian Pei , Jiawei Han , Behzad Mortazavi-Asl , Helen Pinto , Qiming Chen , Umeshwar Dayal , Meichun Hsu, PrefixSpan: Mining Sequential Patterns by Prefix-Projected Growth, Proceedings of the 17th International Conference on Data Engineering, p.215-224, April 02-06, 2001
• 13: J. Ross Quinlan, C4.5: programs for machine learning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• 14: T. Zhao R. Nevatia and S. Hongeng. Hierarchical language-based representation of events in video streams. IEEE Workshop on Event Mining, 2003.
• 15: Shin-Yi Wu , Yen-Liang Chen, Mining Nonambiguous Temporal Patterns for Interval-Based Events, IEEE Transactions on Knowledge and Data Engineering, v.19 n.6, p.742-758, June 2007 [doi>10.1109/TKDE.2007.190613]

INDEX TERMS

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

General Terms:
Algorithms

Keywords:
classifier for interval data, interval-based event mining, temporal relation