FP-Growth & Kinds of Association Rules

1Why not just use Apriori?

Apriori's candidate generate-and-test shrinks the candidate sets a lot, but it still has two non-trivial costs:

2FP-growth: the idea

Frequent-pattern growth (FP-growth) uses a divide-and-conquer strategy:

1. Compress the database of frequent items into a frequent-pattern tree (FP-tree). The tree keeps the itemset association information.
2. Divide the compressed database into conditional databases (a kind of projected database), each linked to one frequent item or "pattern fragment".
3. Mine each conditional database separately.

The three steps of building the tree 00:37

How a transaction is inserted:

• Create a root labelled null.
• Process the items of each transaction in L order (descending support).
• If the transaction shares a prefix with an existing path, increment the count of each node along the shared prefix by 1.
• Create new nodes only for the items after the shared prefix.
• Keep an item header table: each item points to its occurrences in the tree through a chain of node-links.

The problem of mining the database becomes the problem of mining the FP-tree.

3Worked example (min_sup = 3)

Supports after scan 1: f:4, c:4, a:3, b:3, m:3, p:3. Everything else (d, g, i, l, o, h, j, k, s, e, n) is below 3 and is dropped.

L order: f, c, a, b, m, p

Building the tree:

• T100 creates the path f:1 → c:1 → a:1 → m:1 → p:1.
• T200 shares the prefix f-c-a, so those become f:2, c:2, a:2, and a new branch b:1 → m:1 is added under a.
• After all five transactions, the FP-tree is:

                 null
               /      \
            f:4        c:1
           /   \         \
        c:3    b:1       b:1
         |                 \
        a:3                p:1
       /    \
     m:2    b:1
      |       \
     p:2      m:1

4Mining the FP-tree

For each frequent item, starting from the least frequent (bottom of L) as the suffix:

1. Build its conditional pattern base: the set of prefix paths in the tree that end just before the suffix, each with the suffix's count.
2. Build the conditional FP-tree from that base, keeping only items whose total count ≥ min_sup.
3. Mine it recursively. Patterns grow by concatenating the suffix with the patterns found in the conditional tree.

5Multilevel association rules

• At low (primitive) levels, data is sparse, so strong associations are hard to find.
• Strong associations at high levels may just be common sense, but what is common sense to one user may be novel to another.
• So the system should mine at multiple levels of abstraction using concept hierarchies:

                       all
        ┌───────┬──────┼───────┬─────────────┐
    computer  software printer  computer accessory
     ┌──┴──┐     …       …            …
  laptop desktop

• Rules mined at multiple levels are multilevel association rules.
• They're mined under a support-confidence framework with a top-down strategy: count frequent itemsets at level 1, then go down level by level until no more frequent itemsets are found. Any algorithm (e.g. Apriori) works at each level.

6Multidimensional association rules

Each distinct predicate in a rule is a dimension.

7Constraint-based association mining

• Mining can produce thousands of rules, most uninteresting.
• Users often know the "direction" and "form" of what they want, so they specify constraints to confine the search space. This is constraint-based mining.

8Quick revision sheet