Using constraints to generate and explore higher order discriminative patterns

Michael Steinbach, Haoyu Yu, Gang Fang, Vipin Kumar

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Scopus citations


Discriminative pattern mining looks for association patterns that occur more frequently in one class than another and has important applications in many areas including finding biomarkers in biomedical data. However, finding such patterns is challenging because higher order combinations of variables may show high discrimination even when single variables or lower-order combinations show little or no discrimination. Thus, generating such patterns is important for evaluating discriminative pattern mining algorithms and better understanding the nature of discriminative patterns. To that end, we describe how such patterns can be defined using mathematical constraints which are then solved with widely available software that generates solutions for the resulting optimization problem. We present a basic formulation of the problem obtained from a straightforward translation of the desired pattern characteristics into mathematical constraints, and then show how the pattern generation problem can be reformulated in terms of the selection of rows from a truth table. This formulation is more efficient and provides deeper insight into the process of creating higher order patterns. It also makes it easy to define patterns other than just those based on the conjunctive logic used by traditional association and discriminant pattern analysis.

Original languageEnglish (US)
Title of host publicationAdvances in Knowledge Discovery and Data Mining - 15th Pacific-Asia Conference, PAKDD 2011, Proceedings
PublisherSpringer Verlag
Number of pages13
EditionPART 1
ISBN (Print)9783642208409
StatePublished - 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 1
Volume6634 LNAI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Bibliographical note

Funding Information:
This work was supported by NSF grant IIS-0916439. Computing resources were provided by the Minnesota Supercomputing Institute.


  • association analysis
  • discriminative pattern mining
  • frequent patterns
  • linear programming
  • synthetic data generation


Dive into the research topics of 'Using constraints to generate and explore higher order discriminative patterns'. Together they form a unique fingerprint.

Cite this