Threshold-free Pattern Mining Meets Multi-Objective Optimization: Application to Association Rules

Charles Vernerey, Samir Loudni, Noureddine Aribi, Yahia LebbahIJCAI 2022 · DOI

TL;DR

This paper introduces a novel Constraint Programming (CP) approach for discovering "Pareto optimal" patterns (skypatterns) without relying on arbitrary thresholds. By framing pattern mining as a multi-objective optimization problem and introducing a new global constraint, they enable the efficient extraction of high-quality, non-redundant association rules, demonstrating significant performance improvements on benchmark datasets and a real-world gene expression analysis.

What Problem Does This Paper Address?

Traditional pattern mining, especially for association rules, often requires users to specify thresholds for measures like "support" (how often a pattern appears) and "confidence" (how often a rule holds true). Choosing these thresholds is notoriously difficult and can lead to either too many uninteresting patterns or missing valuable insights. Existing methods for dealing with multiple quality measures or finding "condensed" representations (like closed itemsets) still struggle with the sheer volume of results or the complexity of setting parameters. This paper tackles the challenge of mining meaningful patterns and association rules in a threshold-free manner, allowing for the discovery of high-quality insights without user pre-specification of arbitrary cutoffs.

Methods

The core contribution is a new Constraint Programming (CP) model called CLOSEDSKY for efficiently mining Pareto optimal patterns (skypatterns). This model frames the problem as a multi-objective optimization task where multiple "interestingness" measures (like support, area, and all-confidence) are optimized simultaneously.

Key novelties include:

  • Multi-Objective Optimization (MOO) for Pattern Mining: Instead of optimizing a single combined objective, the model seeks solutions that are not dominated by any other solution across multiple objectives. This means a pattern is considered "good" if no other pattern can improve one measure without worsening another.
  • Global Constraint ADEQUATECLOSURE: This new constraint is crucial for ensuring "closedness" of patterns across a set of measures. It efficiently prunes the search space by enforcing that no item can be added to a pattern without changing its value for at least one of the objective measures. This helps in finding condensed representations.
  • Threshold-Free Association Rule Mining: The paper proposes a two-step process. First, CLOSEDSKY mines skypatterns using a set of measures (support, area, all-confidence). Second, these skypatterns are used to generate Minimal Non-Redundant Rules (MNRs) using a dedicated CP model. This second step is also threshold-free, leveraging the properties of skypatterns to ensure rules meet quality criteria implicitly.

Datasets

The paper evaluates its approach on:

  • Six datasets from the FIMI repository: These are standard benchmark datasets for frequent itemset mining.
  • A gene expression dataset: This dataset involves gene expression profiles and various biological annotations (GO IDs, KEGG pathways, etc.) for Yeast genes. This is a real-world application demonstrating the method's utility beyond transactional data.

Key Insights and Ideas

  • Pareto Optimality as a Quality Measure: Framing pattern mining in terms of Pareto optimality provides a principled way to handle multiple, potentially conflicting, quality measures without requiring users to define complex trade-offs.
  • ADEQUATECLOSURE Enables Efficiency: The new global constraint significantly reduces the search space by enforcing a form of "maximal" closedness across multiple measures, leading to more efficient mining of condensed pattern representations.
  • Skypatterns as a Bridge to High-Quality Rules: Skypatterns, by definition, represent patterns that are optimal across multiple dimensions. This property makes them excellent candidates for generating high-quality association rules that are likely to be interesting and non-redundant, even without explicit threshold settings.
  • Threshold-Free Mining is Achievable and Effective: The proposed two-step approach successfully generates meaningful association rules without requiring users to specify support or confidence thresholds, overcoming a major hurdle in traditional association rule mining.

Key Results

  • Skypattern Mining Performance: The CLOSEDSKY model (and its variant CLOSEDSKY-WC) significantly outperforms existing CP-based (CP+SKY) and specialized algorithms (AETHERIS) in terms of runtime on UCI datasets, often by orders of magnitude. It also successfully handles the large gene expression dataset where other methods timed out or ran out of memory.
  • MNR Mining Performance: The SKY4MNR approach (using CLOSEDSKY-WC) generates a drastically reduced number of MNRs compared to traditional methods like CP4MNR and ECLAT-Z, while achieving comparable or better performance in terms of runtime. For instance, on the Mushroom dataset, it reduced the number of MNRs from 105 to 24 in under 2 seconds.
  • Qualitative Analysis of MNRs: The generated MNRs exhibit high confidence (often >90%) and a good balance between support and confidence, suggesting they capture genuinely interesting relationships. The gene expression analysis revealed biologically plausible links between gene annotations and expression patterns.

Limitations and Future Work

  • Automatic Selection of Measure Sets (M'): While the paper mentions that the set of measures M' for the ADEQUATECLOSURE constraint is automatically computed to ensure maximal skylineability, the details of this process are beyond the scope of the paper. Future work could explore this further.
  • Heuristics in CP: The paper mentions using a heuristic for selecting free items in the CP solver. While effective, exploring different heuristics or more advanced CP techniques could further improve performance.
  • Scalability for Extremely Large Datasets: While the approach shows excellent performance, extremely large datasets might still pose challenges, and further optimizations or distributed computing approaches could be explored.
  • Exploration of Different Measures: The paper uses a specific set of measures. Investigating the impact of other or domain-specific measures on skypattern and rule discovery would be a valuable future direction.

Summary updated

BibTeX
@inproceedings{vernerey2022threshold,
  author = {Charles Vernerey and Samir Loudni and Noureddine Aribi and Yahia Lebbah},
  title = {{Threshold-free Pattern Mining Meets Multi-Objective Optimization: Application to Association Rules}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.24963/ijcai.2022/261},
}
Figure