Constraint-Based Search of Straddling Biclusters and Discriminative Patterns

  • Israel Guerra Universidade Federal de Minas Gerais
  • Loïc Cerf Universidade Federal de Minas Gerais
  • João Foscarini Universidade Federal de Minas Gerais
  • Michel Boaventura Universidade Federal de Minas Gerais
  • Wagner Meira Jr. Universidade Federal de Minas Gerais
Keywords: closed patterns, data mining, discriminative patterns, straddling biclusters

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.

Author Biography

Loïc Cerf, Universidade Federal de Minas Gerais

Computer Science Department

Assistant Professor

Published
2013-08-29