Paper Info
Title
Pareto-optimal patterns in logical analysis of data
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.
Year
DOI
Venue
2004
10.1016/j.dam.2003.08.013
Discrete Applied Mathematics
Keywords
Field
DocType
computational complexity,data mining,empirical study,boolean function,data analysis,boolean functions,machine learning,pattern analysis,polynomial time
Boolean function,Combinatorics,Data set,Pattern analysis,Logical analysis of data,Pareto optimal,Time complexity,Empirical research,Mathematics,Computational complexity theory
Journal
Volume
Issue
ISSN
144
1-2
0166-218X
Citations 
PageRank 
References 
40
2.03
24
Authors
4
Name
Order
Citations
PageRank
Peter L. Hammer11996288.93
Alexander Kogan226018.78
Bruno Simeone349654.36
Sándor Szedmák421519.09