CISPA
Browse

Omen: discovering sequential patterns with reliable prediction delays

Download (1.38 MB)
journal contribution
posted on 2023-11-29, 18:06 authored by Joscha Cueppers, Janis KalofoliasJanis Kalofolias, Jilles VreekenJilles Vreeken
Suppose we are given a discrete-valued time series $$X $$ X of observed events and an equally long binary sequence $$Y $$ Y that indicates whether something of interest happened at that particular point in time. We consider the problem of mining serial episodes, sequential patterns allowing for gaps, from $$X $$ X that reliably predict those interesting events. With reliable we mean patterns that not only predict that an interesting event is likely to follow, but in particular that we can also accurately tell how how long until that event will happen. In other words, we are specifically interested in patterns with a highly skewed distribution of delays between pattern occurrences and predicted events. As it is unlikely that a single pattern can explain a complex real-world progress, we are after the smallest, least redundant set of such patterns that together explain the interesting events well. We formally define this problem in terms of the Minimum Description Length principle, by which we identify the best patterns as those that describe the occurrences of interesting events $$Y $$ Y most succinctly given the data over $$X $$ X . As neither discovering the optimal explanation of $$Y $$ Y given a set of patterns, nor the discovery of optimal pattern set are problems that allow for straightforward optimization, we break the problem in two and propose effective heuristics for both. Through extensive empirical evaluation, we show that both our main method, Omen , and its fast approximation fOmen , work well in practice and both quantitatively and qualitatively beat the state of the art.

History

Preferred Citation

Joscha Cueppers, Janis Kalofolias and Jilles Vreeken. Omen: discovering sequential patterns with reliable prediction delays. In: Knowledge and Information Systems. 2022.

Primary Research Area

  • Reliable Security Guarantees

Legacy Posted Date

2022-07-15

Journal

Knowledge and Information Systems

Open Access Type

  • Gold

Sub Type

  • Article

BibTeX

@article{cispa_all_3725, title = "Omen: discovering sequential patterns with reliable prediction delays", author = "Cueppers, Joscha and Kalofolias, Janis and Vreeken, Jilles", journal="{Knowledge and Information Systems}", year="2022", }

Usage metrics

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC