Discovering episodes with compact minimal windows

DOI10.1007/S10618-013-0327-9MaRDI QIDQ468680zbMATHOpenAlexFDO

Authors Nikolaj Tatti

Publication date 7 November 2014

Published in Data Mining and Knowledge Discovery (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1904.07974

zbMATH Keywords

independence modelstatistical testepisode miningminimal window

Mathematics Subject Classification ID

Parametric hypothesis testing (62F03) Statistical ranking and selection procedures (62F07) Formal languages and automata (68Q45) Pattern recognition, speech recognition (68T10) Algorithms on strings (68W32)

Abstract: Discovering the most interesting patterns is the key problem in the field of pattern mining. While ranking or selecting patterns is well-studied for itemsets it is surprisingly under-researched for other, more complex, pattern types. In this paper we propose a new quality measure for episodes. An episode is essentially a set of events with possible restrictions on the order of events. We say that an episode is significant if its occurrence is abnormally compact, that is, only few gap events occur between the actual episode events, when compared to the expected length according to the independence model. We can apply this measure as a post-pruning step by first discovering frequent episodes and then rank them according to this measure. In order to compute the score we will need to compute the mean and the variance according to the independence model. As a main technical contribution we introduce a technique that allows us to compute these values. Such a task is surprisingly complex and in order to solve it we develop intricate finite state machines that allow us to compute the needed statistics. We also show that asymptotically our score can be interpreted as a P-value. In our experiments we demonstrate that despite its intricacy our ranking is fast: we can rank tens of thousands episodes in seconds. Our experiments with text data demonstrate that our measure ranks interpretable episodes high.

Recommendations

• Statistical significance of episodes with general partial orders
• Ranking episodes using a partition model
• Mining closed strict episodes
• Discovering injective episodes with general partial orders
• scientific article; zbMATH DE number 2084855

Cites work

• scientific article; zbMATH DE number 1786453 (Why is no real title available?)
• scientific article; zbMATH DE number 2084855 (Why is no real title available?)
• scientific article; zbMATH DE number 765034 (Why is no real title available?)
• Discovering injective episodes with general partial orders
• Discovering significant patterns
• Mining closed strict episodes

Cited in

(7)

• scientific article; zbMATH DE number 2084855 (Why is no real title available?)
• Ranking episodes using a partition model
• Statistical significance of episodes with general partial orders
• Discovering injective episodes with general partial orders
• Mining closed strict episodes
• Skopus: mining top-\(k\) sequential patterns under leverage
• Efficiently mining cohesion-based patterns and rules in event sequences

This page was built for publication: Discovering episodes with compact minimal windows

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q468680)