Discovering compressing serial episodes from event sequences

作者：Ibrahim A^*; Sastry Shivakumar; Sastry P S

来源：Knowledge and Information Systems, 2016, 47(2): 405-432.

DOI：10.1007/s10115-015-0854-3

• Frequent episodes
• Serial episodes
• Mining event sequences
• Discovering compressing patterns
• MDL
• Inter-event time constraints

Most pattern mining methods yield a large number of frequent patterns, and isolating a small relevant subset of patterns is a challenging problem of current interest. In this paper, we address this problem in the context of discovering frequent episodes from symbolic time-series data. Motivated by the Minimum Description Length principle, we formulate the problem of selecting relevant subset of patterns as one of searching for a subset of patterns that achieves best data compression. We present algorithms for discovering small sets of relevant non-redundant episodes that achieve good data compression. The algorithms employ a novel encoding scheme and use serial episodes with inter-event constraints as the patterns. We present extensive simulation studies with both synthetic and real data, comparing our method with the existing schemes such as GoKrimp and SQS. We also demonstrate the effectiveness of these algorithms on event sequences from a composable conveyor system; this system represents a new application area where use of frequent patterns for compressing the event sequence is likely to be important for decision support and control.

• 出版日期2016-5