Studies on Time Complexity for Computing Association Rules in Data Mining

点击翻译按钮获取中文摘要

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.