Apriori Algorithm

The Apriori Algorithm works in two steps:

1. Generate all frequent itemsets.

2.Generate all confident association rules from the frequent itemsets

1. 在创建frequent itemsets时：

Downward Closure Property:   If an itemset has minimum support, then every non-empty subset of this itemset also has minimum support.

Iterative Algorithm(level-wise-search):  It generates all frequent itemsets by making multiple passes over data.

Candidate - gen function: The Candidate generate function is given below. It consists of two steps, the join step and the pruning step:

Note that, this is an exponential algorithm. Let # of items in I be m. The space of all itemsets is O(2^m). Because each item may or may not be in an itemset.

2. Association Rule Generation:

To generate rules for all frequent itemset f, we use all non-empty subsets of f. For each subset alpha, we output a rule of the form:

where f.count is the support count of f, (f - alpha).count is the support count of (f - alpha)

The support of the rule is f.count/n, where n is the transaction number.