Background for Association Rules and Cost Estimate of Selected Abstract Mining Algorithms

Association rules may be used to represent regular patterns in databases for the purpose of decision suppori applications. Fast algorithms for mining association rules have been proposed and studied experimentally in the literature. A key to the algorithms is to find large itemsets, i.e., sets of items that are well supported in the database. In this paper, we study association rules from a statistical viewpoint. Assuming statistical independence, we obtain the expected support of an itemset, which we regard as the background. Fluctuation of support of an itemset is noise unless it differs significantly from the background. We introduce the concept of clusters, which are the largest large itemsets. From clusters in a database, we may estimate the number of large itemsets and candidate itemsets (intermediate results), which are important to the space complexity. We consider computation costs of Aprioti, AprioriTid, AprioriHybrid, OCD, SETM and DHP algorithms and study their scalability. Our study suggeststhat the key to costs and scalability is the space complexity of large itemsets and candidate itemsets. If the size of candidate k-itemsets is less than main memory, then the above algorithms scale up well. If the size of candidate k-itemsets is larger than main memory, however, the costs increase very rapidly