We analyze several problems of optimizing disjunctive association rules.The problems have important applications in data mining,allowing users to focus at interesting rules extractedfrom databases.We consider association urles of the form #LAMBDA#_j=1~n(A_i_j=v_j)->C_2,where {A_i_1,A_i_2,...,A_i_n} is a subset of the categorical attributes of the underlying relation R_1and 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 looding for one optimiazed 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 space complexity of the designed algorithms and shwo how they can by improved by alowing for approximate solutions.
展开▼
