A Constraint-based Approach for Enumerating Gradual Itemsets

Gradual itemsets model complex attributes covariations of the form the more or less is A, the more or less is B. Recently, such kind of itemsets has received great attention over the last years, and several proposals have been introduced to automatically extract these patterns from numerical databases. Unfortunately, discovering such itemsets remains challenging because of the exponential combinatorial search space. In this paper, we first formalize the problem of mining gradual itemsets as a constraint-based problem. Then, we use SAT solvers for solving the corresponding propositional satisfiability problem. Extensive experiments on real-world datasets confirm that our proposal is competitive with GRITE, one of the most efficient state-of-the-art algorithm for discovering frequent gradual itemsets. Lastly, we show the flexibility of our SAT-based approach by its ability to modeling additional user constraints without revising the solving process.