A Comparison of Standard and Interval Association Rules

The standard formulation of association rules is suitable for describing patterns found in a given data set. A number of dif-ficulties arise when the standard rules are used to infer about novel instances not included in the original data. In previous work we proposed an alternative formulation called interval association rules which is more appropriate for the task of inference, and developed algorithms and pruning strategies for generating interval rules. In this paper we present some theoretical and experimental analyses demonstrating the dif-ferences between the two formulations, and show how each of the two approaches can be beneficial under different cir-cumstances. Standard Association Rules One of the active research areas in data mining and knowl-edge discovery deals with the construction and management of association rules. We will call the formulation typified in (Agrawal, Imielinski, & Swami 1993) the standard for-mulation. A standard association rule is a rule of the form X ⇒ Y, which says that if X is true of an instance in a database ∆, so is Y true of the same instance, with a certain level of signifi-cance as measured by two indicators, support and coverage: [support] proportion of XY s in ∆; [coverage] proportion of Y s among Xs in ∆. (Note that “coverage ” is typically called “confidence ” in the standard association rule literature. However, we will be using “confidence ” to denote the level of certainty associ-ated with an interval derived from a statistical procedure. To avoid confusion, we will refer to the above measure of rule accuracy as the coverage of the rule, and restrict the use of the word “confidence ” to terms such as “the confidence in-terval ” as are traditionally used in statistics.) The goal of standard association rule mining is to output all rules whose support and coverage are respectively above some given support and coverage thresholds. These rules ∗This work was supported by NASA NCC2-1239 and ON