Apriori Algorithm – Generating Association Rules (ARs)

The Apriori algorithm uses a level-wise approach for generating association rules (ARs), where each level corresponds to the number of items that belong to the rule consequent. Initially, all the high-confidence rules that have only one item in the rule consequent are extracted. These rules are then used to generate new candidate rules.

For example, if {acd} → {b} and {abd} → {c} are high-confidence rules, then the candidate rule {ad} → {bc} is generated by merging the consequents of both rules.

Figure 1 shows a lattice structure for the ARs generated from the FI {a, b, c, d}. If any node in the lattice has low confidence, then according to Theorem 1 the entire subgraph spanned by the node can be pruned immediately. Suppose the confidence for {bcd} → {a} is low. All the rules containing item a in its consequent, including {cd} → {ab}, {bd} →  {ac}, {bc} →  {ad}, and {d} →  {abc} can be discarded.

Pruning of association rules using the confidence measure

Figure 1. Pruning of association rules using the confidence measure.

A pseudocode for the rule generation step is shown in Algorithms 1 and 2. Note the similarity between the ap-genrules procedure in Algorithm 2 and the FI generation procedure above. The only difference is that, in rule generation, we do not have to make additional passes over the data set to compute the confidence of the candidate rules. Instead, we determine the confidence of each rule by using the support counts computed during FI generation.

Rule generation of the Apriori algorithm

Algorithm 1. Rule generation of the Apriori algorithm.

Procedure ap-genrules

Algorithm 2. Procedure ap-genrules (fk, Hm).
Previous: Apriori algorithm – Generating Frequent Itemsets (FIs) or In general – Generating Association Rules (ARs)
Next: xx