Optimized disjunctive association rules via sampling

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.