Pareto-optimal patterns in logical analysis of data

Peter L. Hammer, Alexander Kogan, Bruno Simeone, Sándor Szedmák

Research output: Contribution to journalArticlepeer-review

59 Scopus citations

Abstract

Patterns are the key building blocks in the logical analysis of data (LAD). It has been observed in empirical studies and practical applications that some patterns are more "suitable" than others for use in LAD. In this paper, we model various such suitability criteria as partial preorders defined on the set of patterns. We introduce three such preferences, and describe patterns which are Pareto-optimal with respect to any one of them, or to certain combinations of them. We develop polynomial time algorithms for recognizing Pareto-optimal patterns, as well as for transforming an arbitrary pattern to a better Pareto-optimal one with respect to any one of the considered criteria, or their combinations. We obtain analytical representations characterizing some of the sets of Pareto-optimal patterns, and investigate the computational complexity of generating all Pareto-optimal patterns. The empirical evaluation of the relative merits of various types of Pareto-optimality is carried out by comparing the classification accuracy of Pareto-optimal theories on several real life data sets. This evaluation indicates the advantages of "strong patterns", i.e. those patterns which are Pareto-optimal with respect to the "evidential preference" introduced in this paper.

Original languageEnglish (US)
Pages (from-to)79-102
Number of pages24
JournalDiscrete Applied Mathematics
Volume144
Issue number1-2
DOIs
StatePublished - Nov 30 2004

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Keywords

  • Boolean functions
  • Classification accuracy
  • Extremal patterns, Data mining
  • Machine learning

Fingerprint

Dive into the research topics of 'Pareto-optimal patterns in logical analysis of data'. Together they form a unique fingerprint.

Cite this