Data Mining with Cubegrades

A lot of interest has been expressed in database mining using association rules (Agrawal, Imielinski, & Swami, 1993). In this chapter, we provide a different view of the association rules, referred to as cubegrades (Imielinski, Khachiyan, & Abdulghani, 2002) . An example of a typical association rule states that, say, 23% of supermarket transactions (so called market basket data) which buy bread and butter buy also cereal (that percentage is called confidence) and that 10% of all transactions buy bread and butter (this is called support). Bread and butter represent the body of the rule and cereal constitutes the consequent of the rule. This statement is typically represented as a probabilistic rule. But association rules can also be viewed as statements about how the cell representing the body of the rule is affected by specializing it by adding an extra constraint expressed by the rule’s consequent. Indeed, the confidence of an association rule can be viewed as the ratio of the support drop, when the cell corresponding to the body of a rule (in our case the cell of transactions buying bread and butter) is augmented with its consequent (in this case cereal). This interpretation gives association rules a “dynamic flavor” reflected in a hypothetical change of support affected by specializing the body cell to a cell whose description is a union of body and consequent descriptors. For example, our earlier association rule can be interpreted as saying that the count of transactions buying bread and butter drops to 23% of the original when restricted (rolled down) to the transactions buying bread, butter and cereal. In other words, this rule states how the count of transactions supporting buyers of bread and butter is affected by buying cereal as well. With such interpretation in mind, a much more general view of association rules can be taken, when support (count) can be replaced by an arbitrary measure or aggregate and the specialization operation can be substituted with a different “delta” operation. Cubegrades capture this generalization. Conceptually, this is very similar to the notion of gradients used in calculus. By definition the gradient of a function between the domain points x1 and x2 measures the ratio of the delta change in the function value over the delta change between the points. For a given point x and function f(), it can be interpreted as a statement of how a change in the value of x (?x), affects a change of value in the function (? f(x)).