Title :
Optimized disjunctive association rules via sampling
Author :
Elble, J. ; Heeren, C. ; Pitt, L.
Author_Institution :
Dept. of Econ., Rochester Univ., NY, USA
Abstract :
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.
Keywords :
data mining; optimisation; sampling methods; very large databases; cumulative confidence threshold; data mining; optimized disjunctive association rules; performance degradation; polynomial time algorithm; sampling; sampling methods; very large databases; Association rules; Computer science; Convergence; Data mining; Databases; Degradation; History; Polynomials; Sampling methods; Time measurement;
Conference_Titel :
Data Mining, 2003. ICDM 2003. Third IEEE International Conference on
Print_ISBN :
0-7695-1978-4
DOI :
10.1109/ICDM.2003.1250901