Constraint-based rule mining in large, dense databases

Roberto J. Bayardo, R. K. Agrawal, Dimitrios Gunopulos

1999 · 361 citations · 25 references

Concepts

TL;DR

Constraint‑based rule mining seeks all rules satisfying user‑specified thresholds such as minimum support and confidence, but traditional algorithms like Apriori that rely only on support fail on dense datasets due to combinatorial explosion. We aim to introduce an algorithm that directly exploits all user‑specified constraints, including a new predictive‑advantage constraint that ensures each mined rule outperforms any of its simplifications. The algorithm achieves this by efficiently handling low‑support rules in dense or relational datasets while simultaneously enforcing the predictive‑advantage constraint.

Abstract

Constraint-based rule miners find all rules in a given dataset meeting user-specified constraints such as minimum support and confidence. We describe a new algorithm that directly exploits all user-specified constraints including minimum support, minimum confidence, and a new constraint that ensures every mined rule offers a predictive advantage over any of its simplifications. Our algorithm maintains efficiency even at low supports on data that is dense (e.g. relational data). Previous approaches such as Apriori and its variants exploit only the minimum support constraint, and as a result are ineffective on dense data date to a combinatorial explosion of "frequent itemsets".

References

25