Content deleted Content added
No edit summary |
No edit summary |
||
Line 2:
{{cleanup-context}}
'''Apriori''' is an algorithm for [[data mining|mining data]] for [[association rule]]s. It was developed by Rakesh Agrawal, et al. Apriori is designed to operate on [[database]]s 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 <i>itemsets</i> (for instance, sets of retail transactions each containing individual items purchased), the algorithm attempts to find subsets which are common to at least a minimum number C (the cutoff) of the itemsets. Apriori uses a "bottom up" approach, where frequent subsets are extended one item at a time (a step known as <i>candidate generation</i>, and 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 <math>k</math> from item sets of length <math>k-1</math>. Then it prunes the candidates which have an infrequent sub pattern. According to the [[downward closure lemma]], the candidate set contains all frequent <math>k</math>-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 table]]s at internal nodes (Zaki, 99). Note that this is not the same kind of [[hash tree]] used in for instance p2p systems.▼
▲Apriori uses [[breadth-first search]] and a [[hash tree]] structure to count candidate item sets efficiently. It generates candidate item sets of length <math>k</math> from item sets of length <math>k-1</math>. Then it prunes the candidates which have an infrequent sub pattern. According to the [[downward closure lemma]], the candidate set contains all frequent <math>k</math>-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 table]]s 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. Candidate generation generates large numbers of subsets which do not exist in the data. Bottom-up subset exploration finds maximal subsets after all of their subsets.
== Algorithm ==
| |||