Optimized disjunctive association rules via sampling

J. Elble, C. Heeren, L. Pitt

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


The problem of finding optimized support association rules for a single numerical attribute, where the optimized region is a union of k disjoint intervals from the range of the attribute, is investigated. The first polynomial time algorithm for the problem of finding such a region maximizing support and meeting a minimum cumulative confidence threshold is given. Because the algorithm is not practical, an ostensibly easier, more constrained version of the problem is considered. Experiments demonstrate that the best extant algorithm for the constrained version has significant performance degradation on both a synthetic model of patterned data and on real world data sets. Running the algorithm on a small random sample is proposed as a means of obtaining near optimal results with high probability. Theoretical bounds on sufficient sample size to achieve a given performance level are proved, and rapid convergence on synthetic and real-world data is validated experimentally.

Original languageEnglish (US)
Title of host publicationProceedings - 3rd IEEE International Conference on Data Mining, ICDM 2003
Number of pages8
StatePublished - 2003
Event3rd IEEE International Conference on Data Mining, ICDM '03 - Melbourne, FL, United States
Duration: Nov 19 2003Nov 22 2003

Publication series

NameProceedings - IEEE International Conference on Data Mining, ICDM
ISSN (Print)1550-4786


Other3rd IEEE International Conference on Data Mining, ICDM '03
Country/TerritoryUnited States
CityMelbourne, FL

ASJC Scopus subject areas

  • Engineering(all)


Dive into the research topics of 'Optimized disjunctive association rules via sampling'. Together they form a unique fingerprint.

Cite this