An equivalence-class-based algorithm for the maximal number of candidate itemsets

Mining association rules is one of the most important problems in the field of data mining. To device an algorithm that can reduce the number of database scans and without taking the risk of getting a combinatorial explosion of the number of candidate itemsets, we must study what is the maximal number of candidate itemsets that can be generated. In this paper, the theory of itemset equivalence class is proposed. The property of itemset equivalence class is explored and some useful lemmas are presented. Based on the foregoing theory and a priori property, we derive some theorems about the maximal number of candidate itemsets. Based on these theorems, we device an algorithm EC for calculating the maximal number of candidate itemsets, Furthermore, the performance study shows that algorithm EC is more accurate than algorithm KK and the cost for computing the maximal number of negligible compared to the cost of the complete algorithm for association rules.