Apriori algorithm

From Wikipedia, the free encyclopedia

This article or section may be confusing or unclear for many readers.
Please improve the article or discuss this issue on the talk page. This article has been tagged since December 2006.

In computer science and data mining, Apriori is a classic algorithm for learning association rules. 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).

As is common in association rule mining, given a set of itemsets (for instance, sets of retail transactions each listing individual items purchased), the algorithm attempts to find subsets which are common to at least a minimum number C (the cutoff, or confidence threshold) of the itemsets. Apriori uses a "bottom up" approach, where frequent subsets are extended one item at a time (a step known as candidate generation, and groups of candidates are tested against the data. The algorithm terminates when no further successful extensions are found.

Apriori uses breadth-first search and a hash tree structure to count candidate item sets efficiently. It generates candidate item sets of length $k$ from item sets of length $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 $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, while historically significant, suffers from a number of inefficiencies or trade-offs, which have spawned other algorithms. Candidate generation generates large numbers of subsets (the algorithm attempts to load up the candidate set with as many as possible before each scan). Bottom-up subset exploration (essentially a breadth-first traversal of the subset lattice) finds any maximal subset S only after all $2 | S | - 1$ of its proper subsets.

[edit] Example

This example suggests the process of selecting or generating a list of likely ordered serial candidate item sets. The techniques goal is to construct a set of $k$ node ordered serial item sets from $k - 1$ length item sets. For example, with $k = 4$ , suppose there are two such sets of length $k - 1$ ...

$A \rightarrow B \rightarrow C$ ,

and

$A \rightarrow B \rightarrow D$ ,

two candidate item sets are generated, namely

$A \rightarrow B \rightarrow C \rightarrow D$

and

$A \rightarrow B \rightarrow D \rightarrow C$ .

[edit] Algorithm

Apriori $(T,\varepsilon)$

$L_1 \gets \{$ large 1-itemsets

}

$k \gets 2$

while $L_{k-1} \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{count}[c] \gets \mathrm{count}[c]+1$

$L_k \gets \{ c \in C_k | ~ \mathrm{count}[c] \geq \varepsilon \}$

$k \gets k+1$

return $\bigcup_k L_k$

[edit] 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.