A priori algorithm
Apriori is an efficient association rule mining algorithm, developed by Agrawal et al (Agrawal 93, Agrawal 94)
Apriori (Agrawal 94) employs BFS 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 hash tables at internal nodes (Zaki, 99).
Algorithm
Apriori<math>(T,\varepsilon)<math>
<math>L_1 \gets \{ <math> large 1-itemsets <math> \} <math>
<math>k \gets 2<math>
while <math> L_{k-1} \neq \varnothing <math>
<math>C_k \gets <math>Generate<math>(L_k-1)<math>
for transactions <math>t \in T<math>
<math>C_t \gets <math>Subset<math>(C_k,t)<math>
for candidates <math>c \in C_t<math>
<math>\mathrm{count}[c] \gets \mathrm{count}[c]+1<math>
<math>L_k \gets \{ c \in C_k | ~ \mathrm{count}[c] \geq \varepsilon \}<math>
<math>k \gets k+1<math>
return <math>\bigcup_k L_k<math>
References
Rakesh Agrawal and Tomasz Imielinski and Arun N. Swami, Mining Association Rules between Sets of Items in Large Databases, Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data.
Rakesh Agrawal and Ramakrishnan Srikant, Fast Algorithms for Mining Association Rules, Proc. 20th Int. Conf. Very Large Data Bases (VLDB), 1994.
Heikki Mannila and Hannu Toivonen and A. Inkeri Verkamo, Efficient algorithms for discovering association rules, AAAI Workshop on Knowledge Discovery in Databases (KDD-94), 1994.
Mohammed Javeed Zaki and Srinivasan Parthasarathy and Mitsunori Ogihara and Wei Li, Parallel Algorithms for Discovery of Association Rules, Data Mining and Knowledge Discovery, 1997.
