Apriori algorithm

Encyclopedia : A : AP : APR : Apriori algorithm

Please [Glossary#Wwikify] (format) this article or section as suggested in the [Guide to layoutGuide to layout] and the [Manual of StyleManual of Style].
Remove this template after wikifying. This article has been tagged since May 2006.

redirect

Apriori is an efficient association rule data mining algorithm, developed by Rakesh Agrawal, et al..

Apriori 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 [k] from [k-1] 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 [k] 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: This hash tree has item sets at the leaves and hash tables at internal nodes (Zaki, 99). Note that this is not the same kind of hash tree structure used in for instance p2p systems.

Apriori is designed to operate on databases containing transactions (eg: collection of items bought by customers or details of a website frequentation). Other algorithms are designed for finding association rules in data having no transactions (Winepi and Minepi), or having no timestamps (DNA sequencing).

Algorithm

Apriori[(T,\varepsilon)]

[L_1 \gets \ ]

[k \gets 2]

: while [ L_ \neq \varnothing ]

:: [C_k \gets ]Generate[(L_k-1)]

:: for transactions [t \in T]

::: [C_t \gets ]Subset[(C_k,t)]

::: for candidates [c \in C_t]

:::: [\mathrm[c] \gets \mathrm[c]+1]

:: [L_k \gets \[c] \geq \varepsilon \}]

:: [k \gets k+1]

return [\bigcup_k L_k]

References

Agrawal R, Imielinski T, Swami AN. "Mining Association Rules between Sets of Items in Large Databases." SIGMOD. June 1993, 22(2):207-16, [pdf].
Agrawal R, Srikant R. "Fast Algorithms for Mining Association Rules", VLDB. Sep 12-15 1994, Chile, 487-99, [pdf], ISBN 1-55860-153-8.
Mannila H, Toivonen H, Verkamo AI. "Efficient algorithms for discovering association rules." AAAI Workshop on Knowledge Discovery in Databases (SIGKDD). July 1994, Seattle, 181-92, [ps].

Zaki MJ, Parthasarathy S, Ogihara M, Li W. "Parallel Algorithms for Discovery of Association Rules." Data Mining and Knowledge Discovery. Dec 1997, 1(4):343-73, [ps].

From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.