Discovery of interesting episodes in sequence data

ABSTRACT

There is considerable body of work on sequence mining of transactional data. Most of the related work on point data (not significant intervals) makes several passes over the entire dataset in order to discover frequently occurring (sequential) patterns. But Hybrid apriori, proposed in this paper, as the name implies is an apriori-class of mining algorithm in SQL and takes a different approach. Significant intervals for each event (or device) is computed first and used for detecting frequent event patterns. The advantages of this approach are that the data set is compressed to find significant intervals thereby reducing the size of input used. Also, each event/device is processed individually allowing for parallel computation of individual events. Then the hybrid apriori algorithm works on the significant intervals using an apriori-style algorithm adapted to intervals. Our approach has significant advantages over the traditional mining algorithms in terms of its efficiency, scalability and storage requirements.

REFERENCES

• 1: Diane J. Cook , Michael Youngblood , Edwin O. Heierman, III , Karthik Gopalratnam , Sira Rao , Andrey Litvin , Farhan Khawaja, MavHome: An Agent-Based Smart Home, Proceedings of the First IEEE International Conference on Pervasive Computing and Communications, p.521, March 23-26, 2003
• 2: Mannila, H., H. Toivonen, and I. Verkamo, Discovering Frequent Episodes in Sequences, in Proc. of KDD 1995.
• 3: Ramakrishnan Srikant , Rakesh Agrawal, Mining Sequential Patterns: Generalizations and Performance Improvements, Proceedings of the 5th International Conference on Extending Database Technology: Advances in Database Technology, p.3-17, March 25-29, 1996
• 4: A. Srinivasan, S. Shrestha, and S. Chakravarthy. Discovery of Significant Intervals in Sequential Data, in Proc. of ADBIS Workshop on Data Mining and Knowledge Discovery. 2005.
• 5: Joshi, M., G. Karypis, and V. Kumar. A Universal Formulation of Sequential Patterns, in Technical Report. Dept. of Computer Science, University of Minnesota. 1999.
• 6: Rakesh Agrawal , Ramakrishnan Srikant, Mining Sequential Patterns, Proceedings of the Eleventh International Conference on Data Engineering, p.3-14, March 06-10, 1995
• 7: Mohammed J. Zaki, SPADE: an efficient algorithm for mining frequent sequences, Machine Learning, v.42 n.1/2, p.31-60, Jan. 2001 [doi>10.1023/A:1007652502315]
• 8: Mohammed J. Zaki, Sequence mining in categorical domains: incorporating constraints, Proceedings of the ninth international conference on Information and knowledge management, p.422-429, November 06-11, 2000, McLean, Virginia, United States [doi>10.1145/354756.354849]

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Interval arithmetic

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Pattern analysis

General Terms:
Algorithms, Design

Keywords:
data mining, episodes, intervals, sequential pattern mining, smart home