No Access

MINING FREQUENT TEMPORAL PATTERNS IN INTERVAL SEQUENCES

STEFFEN KEMPE

Daimler AG, Group Research, 89081 Ulm, Germany

Search for more papers by this author

JOCHEN HIPP

Daimler AG, Group Research, 89081 Ulm, Germany

Search for more papers by this author

CARSTEN LANQUILLON

Daimler AG, Group Research, 89081 Ulm, Germany

Search for more papers by this author

, and

RUDOLF KRUSE

Dept. of Knowledge Processing and Language Engineering, Otto-von-Guericke-University of Magdeburg, 39106 Magdeburg, Germany

Search for more papers by this author

https://doi.org/10.1142/S0218488508005546Cited by:3 (Source: Crossref)

Abstract

Recently a new type of data source came into the focus of knowledge discovery from temporal data: interval sequences. In contrast to event sequences, interval sequences contain labeled events with a temporal extension. However, existing algorithms for mining patterns from interval sequences proved to be far from satisfying our needs. In brief, we missed an approach that, at the same time, defines support as the number of pattern instances, allows input data that consists of more than one sequence, implements time constraints on a pattern instance, and counts multiple instances of a pattern within one interval sequence. In this paper we propose a new support definition which incorporates these properties. We also describe FSMSet, an algorithm that employs the new support definition, and demonstrate its performance on field data from the automotive business.

Keywords:

References

R. Agrawal and R. Srikant, Mining sequential patterns, Proc. 11th Int. Conf. Data Engineering (ICDE '95) (1995) pp. 3–14. Google Scholar
J. Hanet al., Freespan: Frequent pattern-projected sequential pattern mining, Proc. 6th ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining (KDD '00) (2000) pp. 355–359. Google Scholar
H. Mannila, H. Toivonen and A. I. Verkamo, Data Mining and Knowledge Discovery 1(3), 259 (1997), DOI: 10.1023/A:1009748302351. Crossref, Web of Science, Google Scholar
N. Méger and C. Rigotti, Constraint-based mining of episode rules and optimal window sizes, 8th Europ. Conf. Principles and Practice of Knowledge Discovery in Databases (PKDD '04) (2004) pp. 313–324. Google Scholar
M. Plantevitet al., M2SP: Mining sequential patterns among several, dimensions, 9th Europ. Conf. on Principles and Practice of Knowledge Discovery in Databases (PKDD '05) (2005) pp. 205–216. Google Scholar
P.-S. Kam and A. W. Fu, Discovering Temporal Patterns for Interval-Based Events, 2nd Int. Conf. Data Warehousing and Knowledge Discovery (2000) pp. 317–326. Google Scholar
F. Höppner and F. Klawonn, Intelligent Data Analysis 6(3), 237 (2002). Crossref, Web of Science, Google Scholar
P. Papapetrou et al. , Discovering frequent arrangements of temporal intervals , 5th IEEE Int. Conf. Data Mining (ICDM '05) ( 2005 ) . Google Scholar
E. Winarko and J. F. Roddick, Discovering richer temporal association rules from interval-based data, Int. Conf. Data Warehousing and Knowledge Discovery () (2005) pp. 315–325. Google Scholar
F. Höppner, Knowledge Discovery from Sequential Data, PhD thesis, TU Braunschweig, 2003 . Google Scholar
R. Agrawalet al., Advances in Knowledge Discovery and Data Mining (AAAI/MIT Press, 1996) pp. 307–328. Google Scholar
J. Ayreset al., Sequential pattern mining using a bitmap representation, Proc. 8th ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining (KDD '02) (2002) pp. 429–435. Google Scholar
J. Peiet al., Prefixspan: Mining sequential patterns by prefix-projected growth, Proc. 17th Int. Conf. Data Engineering (ICDE '01) (2001) pp. 215–224. Google Scholar
M. J. Zaki, Machine Learning 42(1), 31 (2001), DOI: 10.1023/A:1007652502315. Crossref, Web of Science, Google Scholar
J. F. Allen, Commun. ACM 26(11), 832 (1983), DOI: 10.1145/182.358434. Crossref, Web of Science, Google Scholar
R. Agrawal, T. Imielinski and A. Swami, Mining association rules between sets of items in large databases, Proc. of the ACM SIGMOD Int. Conf. Management of Data (ACM SIGMOD '93) (1993) pp. 207–216. Google Scholar
R. Agrawal and R. Srikant, Fast algorithms for mining association rules, Proc. 20th Int. Conf. Very Large Databases (VLDB '94) (1994) pp. 487–499. Google Scholar
J. Hipp, U. Güntzer and G. Nakhaeizadeh, SIGKDD Explorations 2(1), 58 (2000), DOI: 10.1145/360402.360421. Crossref, Google Scholar
H. Mannila, H. Toivonen and I. Verkamo, Efficient algorithms for discovering association rules, AAAI Workshop on Knowledge Discovery in Databases (1994) pp. 181–192. Google Scholar