Association

Apriori

$$\begin{array}{rl}& \{X_{\text{Antecedent}}\}\to \{Y_{\text{Consequent}}\}\\ & \\ & \text{Condifence}=\frac{\text{Support}(X,Y)}{\text{Support}(X)}\\ & \\ & \text{Lift Ratio}=\frac{\text{Confidence}(X,Y)}{\text{Expected Confidence}(Y)}\\ & \\ & \text{Expected Condifence}=\frac{\text{Support}(X)}{N}\end{array}$$

Lift ratio is symmetric

Properties

• If $S_1$ is large, any subset of $S_1$ is large.
• If $S_2$ is not large, any superset of $S_2$ is not large.

Steps

$$\begin{array}{rl}& L_1\\ & \\ & C_2\text{join/prune}\\ & L_2\text{count}\\ & \\ & C_3\text{join}\\ & L_3\text{count}\\ & \\ & ⋮\\ & \\ & C_n\end{array}$$

Join

Combine items with the same prefix

Prune

1. Enumerate through all $n-1$ sized itemsets in $C_n$
2. Exclude the itemset if any of its $n-1$ sized itemsets is not in $L_{n-1}$

Count

Delete itemsets if their frequency is less than the threshold frequency

$S_0,S_1,S_2$ Proof

• $S_0$ is a set of all association rule with $\text{supp}\ge \text{threshold}$ and $\text{conf}\ge \text{threshold}$
• $S_1$ is a set of all large itemsets with $\text{supp}\ge \text{threshold}$
• $S_2$ is a set of rules with $\text{conf}\ge \text{threshold}$

Claim 1

For each rule in $S_2$, it is in $S_0$

• Since $B\to C$ is in $S_2$, $conf(B\to C)\ge 50\%$
  • We know that we have to calculate $\frac{supp(B,C)}{supp(B)}$ in step (*)
• So {B, C} and {B} are in $S_1$
• Which means $supp(B,C)\ge 4$ and $supp(B)\ge 4$
• Since $supp(B\to C)=supp(B,C)$
  • $supp(B\to C)\ge 4$

Claim 2

For each rule in $S_0$, it is in $S_2$

• Since $supp(B,C)=supp(B\to C)$
  • $supp(B,C)\ge 3$
  • Thus, $B,C$ is in $S_1$
• Since $supp(B,C)\ge 3$, $supp(B)\ge 3$
  • Thus, $B$ is in $S_1$
• Since $\{B\}$ and $\{B,C\}$ are in $S_1$
  • Step 2 must consider $\{B\}$ and $\{B,C\}$ together and must generate $B\to C$ (since $\frac{supp(B,C)}{supp(B)}>threshold$)
• So, $B\to C$ is in $S_2$

FP Growth

Steps

Setup

1. Frequency table
2. Frequency table of frequent items
3. Frequent table of frequent items (descending)
4. Ordered frequent items table

Tree

1. Draw the tree according to ordered frequent items table
2. Create conditional FP-tree from the bottom
   1. Write down all conditional itemsets
   2. Draw frequency table
   3. Draw frequency table of frequent items (descending)
   4. Write down the ordered frequent items on the right of itemsets
   5. Draw the tree (ignoring the condition item)
   6. Generate large itemsets if the tree has a single path, otherwise repeat the whole process.
      1. Size-1 is the condition itself
      2. Enumerate all possible itemsets for tree nodes
      3. Append the condition to each possible itemsets