Apriori algorithm: Difference between revisions

Revision as of 20:17, 6 June 2005

Revision as of 04:33, 8 July 2005

Line 1:

'''Apriori''' is an efficient [[association rule mining]] [[algorithm]], developed by Agrawal et al (Agrawal 93, Agrawal 94).

Apriori (Agrawal 94) employs [[breadth-first search]] and uses a [[hash tree]] structure to count candidate item sets efficiently. The algorithm generates candidate item sets (patterns) of length <math>k</math> from <math>k-1</math> length item sets. Then, the patterns which have an infrequent sub pattern are pruned. According to the [[downward closure lemma]], the generated candidate set contains all frequent <math>k</math> length item sets. Following that, the whole transaction database is scanned to determine frequent item sets among the candidates. For determining frequent items in a fast manner, the algorithm uses a hash tree to store candidate itemsets. Note: A hash tree has item sets at the leaves and [[hash table]]s at internal nodes (Zaki, 99).