Discovering episodes with compact minimal windows

DOI10.1007/S10618-013-0327-9zbMATH Open1298.68247arXiv1904.07974OpenAlexW3105717510MaRDI QIDQ468680FDOQ468680

Nikolaj Tatti

Publication date: 7 November 2014

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

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.

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)

Cites Work

• Title not available (Why is that?)
• Mining closed strict episodes
• Discovering injective episodes with general partial orders
• Discovering significant patterns
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (4)

• Efficiently mining cohesion-based patterns and rules in event sequences
• Skopus: mining top-\(k\) sequential patterns under leverage
• Title not available (Why is that?)
• Ranking episodes using a partition model

   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 👍 👎
• Title not available (Why is that?) 👍 👎

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)