Database Reference
In-Depth Information
algorithm we move top-down in the lattice to identify infrequent itemsets whose all
proper subsets are frequent in F
0
D
. First, we examine all 1-itemsets (i.e., items).
If any of these itemsets is infrequent, it should be included in the revised negative
border. Then, we examine all 2-itemsets by properly joining (symbol ./ denotes a
join) the frequent 1-itemsets. Again, if the produced 2-itemset does not exist in F
0
D
we include it in Bd
(F
0
D
). To examine k-itemsets (where k > 3), we first construct
them by properly joining frequent (k-1)-itemsets (as in Apriori) and then check to
see if the produced itemset is frequent inF
0
D
. If the itemset is reported as infrequent,
we then examine all its (k-1) proper subsets. If none of these is infrequent, then the
itemset belongs to the revised negative border, so we include it in Bd
(F
0
D
).
Algorithm 9.4 Hiding of all the sensitive itemsets and their supersets.
1: procedure H
IDE
SS(F
D
O
, S
max
)
2:
for each s 2S
max
do
. for all sensitive itemsets
3:
for each f 2F
D
O
do
. for all large itemsets
4:
if s f then
. the large itemset is sensitive
5:
F
D
O
F
D
O
f
. remove itemset f
6: end if
7: end for
8: end for
9: Return: F
0
D
F
D
O
10: end procedure
Last, Algorithm 9.4 presents the hiding process in which we identify F
0
D
by
removing from F
D
O
all the sensitive itemsets and their supersets. To do so, we
iterate over all the sensitive itemsets and their supersets (i.e., set S
max
), and the large
itemsets in F
D
O
, and we identify all those large itemsets that are supersets of the
sensitive. Then, we remove these itemsets from the list of frequent itemsets, thus
construct a new set F
0
D
with the remaining large itemsets in F
D
O
.