Extending Set-based Dualization: Application to Pattern Mining

摘要

Dualization problems have been intensively studied in combinatorics, AI and pattern mining for years. Roughly speaking, for a partial order (P, ≤) and some monotonic predicate Q over P, the dualization consists in identifying all maximal elements of P verifying Q from all minimal elements of P not verifying Q, and vice versa. The dualization is equivalent to the enumeration of minimal transversal of hypergraphs whenever (P, ≤) is a boolean lattice. In the setting of interesting pattern mining in databases, P represents a set of patterns and whenever P is isomorphic to a boolean lattice, the pattern mining problem is said to be representable as sets. The class of such problems is denoted by RAS. In this paper, we introduce a weak representation as sets for pattern mining problems which extends the RAS class to a wider and significantly larger class of problems, called WRAS. We also identify εWRAS, an efficient subclass of WRAS for which the dualization problem is still quasi-polynomial. Finally, we point out that one representative pattern mining problem known not to be in RAS, namely frequent rigid sequences with wildcard, belongs to εWRAS. These new classes might prove to have large impact in unifying existing pattern mining approaches.