Studies on Time Complexity for Computing Association Rules in Data Mining

1.菜篮子数据库的关联规则计算是数据挖掘中最基本的问题之一。关联规则是X⇒Y形式的陈述，其直观含义是，如果客户购买了X中的所有项目，那么他也可能购买Y中的所有项目。为了使关联规则有意义，必须(A)项目集X∪Y大，(B)规则是自信的，(C)左侧Y包含足够的项目。关联规则的计算算法由两部分组成：首先计算一个大的项集Z，然后将其划分为X和Y，使得X⇒Y具有意义。我们引入了一个稀有项集，它是大型项集的对偶概念，并证明了判定是否存在小于给定大项集的大型项集是NP完全的。通过将上面的稀有项集问题转化为从给定的大型项集中是否可以获得有意义的关联规则的问题，证明了计算有意义的关联规则的问题是NP完全的。得到了在多项式时间内计算稀有项集的一个充分条件。利用上述充分条件，我们得到了一个可以在多项式时间内计算出有意义关联规则的数据库子类。

1. Computing association rules for market basket database is one of the most fundamental problems in data mining. An association rule is a statement of the form X⇒Y, whose intuitive meaning is that if a customer buys all the items in X, then he is also likely to buy all the items in Y. In order that the association rule is meaningful, it is necessary that (a) the itemset X∪Y is large, (b) the rule is confident, and (c) the left side Y contains enough items. The algorithm for computing association rules consists of the two parts: first, computing a large itemset Z, and then dividing the set Z into X and Y such that X⇒Y is meaningful.2. We introduced a rare itemset that is a dual concept for a large itemset, and proved that it is NP-complete to decide if there is a large itemset whose size is smaller than a given size.3. By transforming the rare itemset problem above into a problem for deciding if a meaningful association rule can be obtained from a given large itemset, we proved that the problem for computing a meaningful association rule is NP-complete.4. We obtained a sufficient condition to compute a rare itemset in polynomial time.5. Using the sufficient condition above, we obtained a subclass of databases in which a meaningful association rule can be computed in polynomial time.