Optimizing Disjunctive Association Rules

We analyze several problems of optimizing disjunctive association rules. The problems have important applications in data mining, allowing users to focus at interesting rules extracted from databases. We consider association rules of the form \(\bigwedge_{j=1}^{n}(A_{i_j}=v_j)\rightarrow C_2\), where \(\{A_{i_1},A_{i_2},\ldots,A_{i_n}\}\) is a subset of the categorical attributes of the underlying relation R, and C 2 is any fixed condition defined over the attributes of the relation R. An instantiation of the rule binds the variables v j ’s to values from the corresponding attribute domains. We study several problems, in which we seek a collection of instantiations of a given rule that satisfy certain optimality constraints. Each of the problems can re-interpreted as looking for one optimized disjunctive association rule. We exhibit efficient algorithms for solving the optimized support and optimized confidence problems, the weighted support/confidence problem, and the shortest rule problem. We discuss time and splace complexity of the designed algorithms and show how they can be improved by allowing for approximate solutions.