Constraint-Based Search of Straddling Biclusters and Discriminative Patterns

Abstract

The state-of-the-art Data-Peeler algorithm extracts closed patterns in n-ary relations. Because it refines a lower bound and an upper bound of the pattern space, Data-Peeler can, in some circumstances, guarantee that a region of the pattern space does not contain any closed n-set satisfying some relevance constraint, allowing the algorithm to not perform any further pattern search in that region. If it is so, this region is left unexplored and some time is saved. Not all constraints enable such a pruning of the pattern space but both the monotone and the anti-monotone constraints do. This article shows that a minimal (resp. maximal) cover of some arbitrary groups of elements is anti-monotone (resp. monotone). As a consequence, Data-Peeler may prune the search space with those constraints and efficiently discover many different patterns. For instance, it can list the so-called straddling biclusters, which cover at least some given portions of every group. It can also discover closed n-sets that discriminate a group from the others, what has potential applications to supervised classification.