Ratio Rules: A New Paradigm for Fast, Quantifiable Data Mining

F. Korn, A. Labrinidis, Y. Kotidis, C. Faloutsos

In the Proceedings of the 24th International Conference on Very Large Databases (VLDB), New York City, USA, August 1998, pp. 582-593

Abstract

Association Rule Mining algorithms operate on a data matrix (eg, customers x products) to derive association rules [Agrawal93, Srikant96]. We propose a new paradigm, namely, Ratio Rules, which are quantifiable in that we can measure the "goodness" of a set of discovered rules. We propose and use the "guessing error" as a measure of the goodness, that is, the root-mean-square error of the reconstructed values of the cells of the given matrix, when we pretend that they are unknown. Another contribution is a novel method to guess missing/hidden values from the Ratio Rules that our method derives. For example, if somebody bought $10 of milk and $3 of bread, our rules can "guess" the amount spent on, say, butter. Thus, we can perform a variety of important tasks such as forecasting, answering what-if scenarios, detecting outliers, and visualizing the data. Moreover, we show that we can compute Ratio Rules in a single pass over the dataset with small memory requirements (a few small matrices), in contrast to traditional association rule mining methods that require multiple passes and/or large memory. Experiments on several real datasets (eg, basketball and baseball statistics, biological data) demonstrate that the proposed method consistently achieves a guessing error of up to 5 times less than the straightforward competitor.

The complete paper is available in pdf format


kotidis@cs.umd.edu
Last modified: Sun Nov 1 17:18:19 EST 1998