Database Reference
In-Depth Information
in the conditional tree with such item. In this case, combining item
1
(from
node
1:2
) with the parameter of the conditional tree (in this case, item
3
), we
obtain the 2-itemset
{
1,3
}
.Thus,item
3
yields two frequent itemsets,
{
1,3
}
{
3
}
and
.
Then, we build the conditional FP-tree for item
{
2
}
. We traverse bottom-
up the tree in Fig.
9.4
b, starting from each node for
2
, and update the
counters. Now, the node
1:3
becomes
1:1
. Then, we drop all the nodes for
item
2
, in this case, the two nodes
2:1
. We obtain the tree in Fig.
9.5
b. Since
we can drop the only node in the tree because it does not have the minimum
support (the node
1:1
indicates the only path remaining for item
1
), we just
obtain the itemset
{
2
}
.
Proceeding analogously, the conditional FP-tree for item
{
1
}
is the empty
{
1
}
tree; thus, we just obtain the itemset
.
Alternatively, we could also obtain the conditional FP-trees without using
the prefix path subtrees as follows. We pick
only
the transactions that contain
i
and remove
i
from such transactions. All other transactions are discarded.
Then, we construct the conditional FP-trees as explained for regular FP-
trees. For example, for the subtree corresponding to item
3
, we pick only
transactions
1000
and
2000
(the ones that contain item
3
) and eliminate item
3
from the transactions. Transactions
3000
and
4000
are discarded. Thus, we
keep items
(from transaction
2000
).
With these items we build an FP-tree as explained above, obtaining the tree
in Fig.
9.5
a, from which we remove the infrequent nodes. From this tree,
frequent itemsets containing the item
{
1,2
}
(from transaction
1000
)and
{
1
}
{
3
}
are obtained as explained above.
We can proceed analogously to build the conditional FP-tree for item
{
2
}
.
a
b
c
root
root
root
Item
Item
Item
1
1
1:2
1:1
2
2:1
Fig. 9.5
Conditional FP-tree for items
3
(
a
),
2
(
b
), and
1
(
c
)
9.1.6 Sequential Patterns
The association rules studied above have an important characteristic: they
do not consider order. As we have seen in our examples, the order in which
Search WWH ::
Custom Search