Apriori algorithm

Apriori is an algorithm for mining data for association rules. It was developed by Rakesh Agrawal, et al.

Apriori uses breadth-first search and a hash tree structure to count candidate item sets efficiently. It generates candidate item sets of length ${\displaystyle k}$ from item sets of length ${\displaystyle k-1}$. Then it prunes the candidates which have an infrequent sub pattern. According to the downward closure lemma, the candidate set contains all frequent ${\displaystyle k}$-length item sets. After that, it scans the transaction database to determine frequent item sets among the candidates. For determining frequent items quickly, the algorithm uses a hash tree to store candidate itemsets. 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 used in for instance p2p systems.

Apriori is designed to operate on databases containing transactions (for example, collections 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${\displaystyle (T,\varepsilon )}$ 

${\displaystyle L_{1}\gets \{}$  large 1-itemsets ${\displaystyle \}}$ 

${\displaystyle k\gets 2}$ 

while ${\displaystyle L_{k-1}\neq \varnothing }$ 

${\displaystyle C_{k}\gets }$ Generate${\displaystyle (L_{k}-1)}$ 

for transactions ${\displaystyle t\in T}$ 

${\displaystyle C_{t}\gets }$ Subset${\displaystyle (C_{k},t)}$ 

for candidates ${\displaystyle c\in C_{t}}$ 

${\displaystyle \mathrm {count} [c]\gets \mathrm {count} [c]+1}$ 

${\displaystyle L_{k}\gets \{c\in C_{k}|~\mathrm {count} [c]\geq \varepsilon \}}$ 

${\displaystyle k\gets k+1}$ 

return ${\displaystyle \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.