FP-tree and conditional FP-tree

FP-tree

An FP-tree (Frequent Pattern tree) is a compact prefix-tree representation of a transaction database, used by the FP-growth algorithm.

• It has a root labelled "null". Every other node stores an item name, a count (number of transactions passing through the node) and a link to the parent and to the next node with the same item.
• Frequent items in each transaction are sorted by descending support, and the transaction is inserted as a path. Common prefixes are shared, so the tree is usually much smaller than the database.
• A header table lists the frequent items with their counts and a pointer to the first node of each item (node-links).

Conditional pattern base and conditional FP-tree

• The conditional pattern base of an item i is the set of prefix paths in the FP-tree that end just before the nodes of i, each with the count of the node of i.
• The conditional FP-tree of i is the FP-tree built from this pattern base, keeping only items whose total count ≥ min_sup. It is used to find the frequent patterns that end with i, and is mined recursively.

Example

Transactions (min_sup = 2): T1 {A, C, D}, T2 {B, C, E}, T3 {A, B, C, E}, T4 {B, E}, T5 {A, B, C, E}.

Frequent items sorted: B:4, C:4, E:4, A:3 (D is dropped). The FP-tree:

null
 |-- C:1 -- A:1
 |-- B:4
      |-- C:3 -- E:3 -- A:2
      |-- E:1

Header table: B → C → E → A with node-links.

For item A (A:2 under E, A:1 under C):

• Conditional pattern base: {B, C, E : 2}, {C : 1}.
• Conditional FP-tree (min_sup = 2): items B:2, C:3, E:2.

null
 |-- C:1
 |-- B:2 -- C:2 -- E:2

• Mining it gives patterns {A, C}:3, {A, B}:2, {A, E}:2, {A, B, C}:2, {A, B, E}:2, {A, C, E}:2, {A, B, C, E}:2.

For item E: pattern base {B, C : 3}, {B : 1}; conditional FP-tree has B:4, C:3 → {E, B}:4, {E, C}:3, {E, B, C}:3.