摘要
ost proposed algorithms for mining association rules follow the conventional level wise approach. The dynamic candidate generation idea introduced in the dynamic itemset counting (DIC) algorithm broke away from the level wise limitation which could find the large itemsets using fewer passes over the database than level wise algorithms. However, the dynamic approach is very sensitive to the data distribution of the database and it requires a proper interval size. In this paper an optimization technique named adaptive interval configuration (AIC) has been developed to enhance the dynamic approach. The AIC optimization has the following two functions. The first is that a homogeneous distribution of large itemsets over intervals can be achieved so that less unnecessary candidates could be generated and less database scanning passes are guaranteed. The second is that the near optimal interval size could be determined adaptively to produce the best response time. We also developed a candidate pruning technique named virtual partition pruning to reduce the size 2 candidate set and incorporated it into the AIC optimization. Based on the optimization technique, we proposed the efficient AIC algorithm for mining association rules. The algorithms of AIC, DIC and the classic Apriori were implemented on a Sun Ultra Enterprise 4000 for performance comparison. The results show that the AIC performed much better than both DIC and Apriori, and showed a strong robustness.
ost proposed algorithms for mining association rules follow the conventional level wise approach. The dynamic candidate generation idea introduced in the dynamic itemset counting (DIC) algorithm broke away from the level wise limitation which could find the large itemsets using fewer passes over the database than level wise algorithms. However, the dynamic approach is very sensitive to the data distribution of the database and it requires a proper interval size. In this paper an optimization technique named adaptive interval configuration (AIC) has been developed to enhance the dynamic approach. The AIC optimization has the following two functions. The first is that a homogeneous distribution of large itemsets over intervals can be achieved so that less unnecessary candidates could be generated and less database scanning passes are guaranteed. The second is that the near optimal interval size could be determined adaptively to produce the best response time. We also developed a candidate pruning technique named virtual partition pruning to reduce the size 2 candidate set and incorporated it into the AIC optimization. Based on the optimization technique, we proposed the efficient AIC algorithm for mining association rules. The algorithms of AIC, DIC and the classic Apriori were implemented on a Sun Ultra Enterprise 4000 for performance comparison. The results show that the AIC performed much better than both DIC and Apriori, and showed a strong robustness.
