Knowledge-Based Sequence Mining with ASP

Martin Gebser, Thomas Guyet, René Quiniou, Javier Romero, Torsten SchaubIJCAI 2016

Introduction

Sequential pattern mining is a cornerstone of data analysis, yet it frequently suffers from the "pattern explosion" problem. While modern algorithms are optimized for speed, they often generate an overwhelming volume of redundant or irrelevant results. Furthermore, these "black-box" tools are difficult to customize with domain-specific constraints. This paper presents a declarative framework using Answer Set Programming (ASP) to bridge this customization gap, allowing experts to prioritize relevance and quality over raw processing volume.

Declarative Mining Framework

The core of the proposed approach is the use of ASP, a logic programming paradigm that allows users to describe what a valid pattern is rather than how to find it. By defining basic logic rules for subsequence relations and frequency counting, the framework becomes inherently modular. Users can easily append "plug-and-play" modules to enforce specific constraints, such as regular expressions or gap limits, without modifying the underlying solver.

Beyond simple constraints, the framework integrates preference handling via the asprin tool. This enables the extraction of "skypatterns"—results that are Pareto-optimal across multiple conflicting measures like length and frequency.

Pruning the Pattern Explosion

A significant advantage of the ASP-based approach is its ability to effectively filter the search space. Traditional miners often return every frequent sequence, leading to massive redundancy. By implementing logic for condensed patterns (maximal or closed patterns) and qualitative preferences, the framework drastically reduces the output size.

Comparison of pattern counts across different strategies.

As shown in the experimental results, the use of preferences can reduce thousands of potential patterns to a handful of high-quality insights, making the data much more manageable for human experts.

Performance and Scalability

The authors evaluated the framework against CPSM, a state-of-the-art Constraint Programming miner. For short to medium-length sequences, the ASP approach remains competitive. However, a fundamental trade-off exists regarding scalability.

Runtime performance vs. sequence length.

The "grounding bottleneck" is the primary limitation: as sequences grow longer, the process of translating logic into a propositional format becomes computationally expensive. While ASP excels at navigating complex constraints in mid-sized datasets, dedicated CP solvers with specialized propagators maintain an edge for very long sequences.

Conclusion

The ASP-based framework for sequence mining offers a powerful alternative to traditional optimized miners when domain knowledge is paramount. By trading off some scalability for extreme flexibility and high-quality results, it empowers experts to extract truly meaningful patterns from complex datasets. Future work aims to incorporate specialized propagators within ASP solvers to mitigate grounding overhead and further improve performance on longer sequences.

Summary updated

BibTeX
@inproceedings{gebser2016knowledge,
  author = {Martin Gebser and Thomas Guyet and René Quiniou and Javier Romero and Torsten Schaub},
  title = {{Knowledge-Based Sequence Mining with ASP}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure