Paper Info
Title
Approximation of Optimal Two-Dimensional Association Rules for Categorical Attributes Using Semidefinite Programming
Abstract
We consider the problem of finding two-dimensional association rules for categorical attributes. Suppose we have two conditional attributes A and B both of whose domains are categorical, and one binary target attribute whose domain is {"positive", "negative"}. We want to split the Cartesian product of domains of A and B into two subsets so that a certain objective function is optimized, i.e., we want to find a good segmentation of the domains of A and B. We consider in this paper the objective function that maximizes the confidence under the constraint of the upper bound of the support size. We first prove that the problem is NP-hard, and then propose an approximation algorithm based on semidefinite programming. In order to evaluate the effectiveness and efficiency of the proposed algorithm, we carry out computational experiments for problem instances generated by real sales data consisting of attributes whose domain size is a few hundreds at maximum. Approximation ratios of the solutions obtained measured by comparing solutions for semidefinite programming relaxation range from 76% to 95%. It is observed that the performance of generated association rules are significantly superior to that of one-dimensional rules.
Year
Venue
Keywords
1999
Discovery Science
categorical attribute,approximation ratio,problem instance,optimal two-dimensional association rules,certain objective function,semidefinite programming,objective function,association rule,approximation algorithm,proposed algorithm,domain size,data consistency,upper bound
DocType
Volume
ISSN
Conference
1721
0302-9743
ISBN
Citations 
PageRank 
3-540-66713-X
4
0.74
References 
Authors
14
5
Name
Order
Citations
PageRank
Katsuki Fujisawa124828.63
Yukinobu Hamuro2437.76
naoki katoh31101187.43
Takeshi Tokuyama41179417.31
Katsutoshi Yada513133.27