Mining Best Closed Itemsets for Projection-antimonotonic Constraints in
  Polynomial Time
  The exponential explosion of the set of patterns is one of the main
challenges in pattern mining. This challenge is approached by introducing a
constraint for pattern selection. One of the first constraints proposed in
pattern mining is support (frequency) of a pattern in a dataset. Frequency is
an anti-monotonic function, i.e., given an infrequent pattern, all its
superpatterns are not frequent. However, many other constraints for pattern
selection are neither monotonic nor anti-monotonic, which makes it difficult to
generate patterns satisfying these constraints.
  In order to deal with nonmonotonic constraints we introduce the notion of
"projection antimonotonicity" and SOFIA algorithm that allow generating best
patterns for a class of nonmonotonic constraints. Cosine interest, robustness,
stability of closed itemsets, and the associated delta-measure are among these
constraints. SOFIA starts from light descriptions of transactions in dataset (a
small set of items in the case of itemset description) and then iteratively
adds more information to these descriptions (more items with indication of
tidsets they describe).
