Information Technology Reference
In-Depth Information
and its node-link be linked to the nodes with the same item-name via the
node-link structure.
3. If
P
is nonempty, call Insert_tree(
P, N
) recursively.
Table 12.1 Transaction Database (Han et al, 2000)
TID
Items Bought
(Ordered) Frequent Items
100
f, a, c, d, g, i, m,p
f, c, a, m, p
200
a, b, c, f, l, m, o
f, c, a, b,m
300
b, f, h, j, o
f, b
400
b, c, k, s, p
c, b, p
500
a, f, c, e, l, p, m, n
f, c, a, m, p
Table 12.1 lists a transaction database. We can use Algorithm 12.2 to
construct a FP-Tree shown in Figure 12.2. First, a scan of DB derives a list of
frequent items, {(f:4), (c:4), (a:3), (b:3), (m:3), (p:3)}, in which items ordered in
frequency descending order. This ordering is important since each path of a tree
will follow this order. Second, one may create the root of a tree, labeled with
“null”. Scan the DB the second time. The scan of the first transaction leads to the
construction of the first branch of the tree: {(
f
:1), (
c
:1), (
a
:1), (
m
:1), (
p
:1)}. For
the second transaction, since its (ordered) frequent item list {
f, c, a, b,m
} shares a
common prefix {
}, the count of each
node along the prefix is incremented by 1, and one new node {
f, c, a
} with the existing path {
f, c, a, m, p
b
:1} is created and
linked as a child of {
a
:2} and another new node {
m
:1} is created and linked as
the child of {
b
:1}. For the third transaction, since its frequent item list {
f, b
}
shares only the node {
f
} with the f-prefix subtree,
f
's count is incremented by 1,
and a new node {
:3}. The scan of the
fourth transaction leads to the construction of the second branch of the tree,
{(
b
:1} is created and linked as a child of {
f
c
:1), (
b
:1), (
p
:1)}. For the last transaction, since its frequent item list {
f, c, a, m,
p
} is identical to the first one, the path is shared with the count of each node
along the path incremented by 1. To facilitate tree traversal, an item header table
is built in which each item points to its occurrence in the tree via a head of
node-link. Nodes with the same item-name are linked in sequence via such
node-links. After scanning all the transactions, the tree with the associated
node-links is built and shown in Figure 12.2.
