Skip to Main content Skip to Navigation
Conference papers

A Relaxation-based Approach for Mining Diverse Closed Patterns

Abstract : In recent years, pattern mining has moved from a slow-moving repeated three-step process to a much more agile iterative/user-centric mining model. A vital ingredient of this framework is the ability to quickly present a set of diverse patterns to the user. In this paper, we use constraint programming (well-suited to user-centric mining due to its rich constraint language) to efficiently mine a diverse set of closed patterns. Diversity is controlled through a threshold on the Jaccard similarity of pattern occurrences. We show that the Jaccard measure has no monotonicity property, which prevents usual pruning techniques and makes classical pattern mining unworkable. This is why we propose anti-monotonic lower and upper bound relaxations, which allow effective pruning, with an efficient branching rule, boosting the whole search process. We show experimentally that our approach significantly reduces the number of patterns and is very efficient in terms of running times, particularly on dense data sets.
Complete list of metadatas

Cited literature [22 references]  Display  Hide  Download

https://hal.archives-ouvertes.fr/hal-02935080
Contributor : Albrecht Zimmermann <>
Submitted on : Thursday, September 10, 2020 - 8:32:50 AM
Last modification on : Monday, September 21, 2020 - 2:15:48 PM

File

camera_ready_ecml_pkdd_20.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02935080, version 1

Citation

Arnold Hien, Samir Loudni, Noureddine Aribi, Yahia Lebbah, Mohammed Laghzaoui, et al.. A Relaxation-based Approach for Mining Diverse Closed Patterns. European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases 2020, Sep 2020, Gand, Belgium. ⟨hal-02935080⟩

Share

Metrics

Record views

24

Files downloads

33