Information Technology Reference
In-Depth Information
12.4 CFP-Tree Algorithm
In FP-growth algorithm there are 6 fields in a FP-tree node, containing
item-name, count, parent-link, child-link, sibling-link and next-link (a pointer to
next node that has same item-name). However, child-link and sibling-link are
only used in the FP-tree constructing process, parent-link and next-link are only
used in the mining process. So we can reduce the number of fields by joining
child-link with parent-link as cp-link which is first pointing to its child-node and
after construction pointing to its parent node, and joining sibling-link with
next-link as sn-link which is first pointing to its sibling-node and finally pointing
to next node(Qin,2004).
The compact FP-tree (CFP-tree) has similar structure as FP-tree, but several
differences btween them:
(1) Each node in CFP-tree has 4 fields, item-no (which is the sequential number
of an item in frequent 1-itemsets according frequency descending order), count,
cp-link and sn-link. Therefore, CFP-tree requires only 2/3 memory spaces of
FP-tree.
(2) FP-tree is bi-directional, but CFP-tree is single directional. After the
construction, CFP-tree only exists paths from leaves to the root.
The CFP-tree is constructed by Algorithm 12.4.
Algorithm 12.4
CFP-tree construction.
Input: DB, a database of transactions;
minsup, the minimum support count threshold.
Output: CFP-tree, compact frequent pattern tree..
Method:
1. Scan the transaction database DB once. Collect the set of frequent items
F
and
their supports. Sort
F
in support descending order as
L
, the list of frequent items.
2. Create the root of an FP-tree,
, and label it as “null”. For each transaction in
DB do the following. Select the frequent items and replace them with their order
in
T
L
, and sort them as
Is
. Let the sorted
Is
be [
p|P
], where
p
is the first element
and
P
is the remaining list. Call insert tree([
p|P
],
T
).
Procedure
: insert_tree([
p
|
P
],
T
).
1. If T has no child or can not find a child which its item-no=
p
, then create a new
node
N
.
N
.item-no=
p
,
N
.count=1,
N
.cp-link=
T
; Insert
N
before the first node
which item-no is greater than
p
.
