Apriori algorithm: Difference between revisions

Revision as of 15:38, 27 August 2020

Revision as of 15:00, 26 October 2020

Line 8:

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 (persistent data structure)|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.

The pseudo code for the algorithm is given below for a transaction database <math>T</math>, and a support threshold of <math>\epsilon</math>. Usual set theoretic notation is employed, though note that <math>T</math> is a [[multiset]]. <math>C_k</math> is the candidate set for level <math>k</math>. At each step, the algorithm is assumed to generate the candidate sets from the large item sets of the preceding level, heeding the downward closure lemma. <math>count[c]</math> accesses a field of the data structure that represents candidate set <math>c</math>, which is initially assumed to be zero. Many details are omitted below, usually the most important part of the implementation is the data structure used for storing the candidate sets, and counting their frequencies.