Paper Info
Title
Maximum patterns in datasets
Abstract
Given a binary dataset of positive and negative observations, a positive (negative) pattern is a subcube having a nonempty intersection with the positive (negative) subset of the dataset, and an empty intersection with the negative (positive) subset of the dataset. Patterns are the key building blocks in Logical Analysis of Data (LAD), and are an essential tool in identifying the positive or negative nature of ''new'' observations covered by them. We develop exact and heuristic algorithms for constructing a pattern of maximum coverage which includes a given point. It is shown that the heuristically constructed patterns can achieve 81-98% of the maximum possible coverage, while requiring only a fraction of the computing time of the exact algorithm. Maximum patterns are shown to be useful for constructing highly accurate LAD classification models. In comparisons with the commonly used machine learning algorithms implemented in the publicly available Weka software package, the implementation of LAD using maximum patterns is shown to be a highly competitive classification method.
Year
DOI
Venue
2008
10.1016/j.dam.2007.06.004
Discrete Applied Mathematics
Keywords
Field
DocType
heuristic,negative nature,competitive classification method,maximum coverage,set covering,empty intersection,logical analysis of data,classification,accurate lad classification model,maximum pattern,machine learning,negative observation,maximum possible coverage,exact algorithm,binary dataset,set cover,heuristic algorithm
Data mining,Heuristic,Exact algorithm,Heuristic (computer science),Logical analysis of data,Heuristics,Software,Statistical classification,Mathematics,Binary number
Journal
Volume
Issue
ISSN
156
6
Discrete Applied Mathematics
Citations 
PageRank 
References 
13
0.92
19
Authors
3
Name
Order
Citations
PageRank
T. O. Bonates1130.92
Peter L. Hammer21996288.93
A. Kogan314212.92