Max–Min Algorithms - Association Rule Hiding for Data Mining - page 50

affecting the support of any max-min itemset. If this is possible, then the authors
in [50, 51] prove that no other itemset from the minimum support itemsets will be
affected. Reducing the support of a sensitive itemset without affecting the support
of the max-min itemsets from Bd + j j can be accomplished only if (i) the max-min
itemsets are not subsets of the sensitive itemset, and (ii) there exist transactions in
the database which support the sensitive itemset without, however, supporting the
max-min itemsets. In order to get this information, Max-Min 2 computes for every
sensitive itemset and for every max-min itemset the transactions of the original
database that support them. Assuming that L I and L U are the two lists, then their
difference L I L U denotes the set of transactions from D O that support the sensitive
itemset I without supporting the max-min itemset U . If the size of this set is at least
equal to sup(I) msup 1, then there exists a sufficient number of transactions for
hiding I, without reducing the support of the max-min itemset.
The second case scenario involves the existence of more than one max-min item-
sets that correspond to different tentative victim items. In this case scenario, Max-
Min 2 iterates over the sets of tentative victim itemsets Bd + j j (for the different
items j) that contain a max-min itemset, and examines whether the support of the
sensitive itemset can be reduced through j, without affecting the support of any of
the corresponding tentative victim itemsets that belong in Bd + j j . If this is possi-
ble, then the authors of [50, 51] prove that the support of no other itemset in Bd + j i
(i 6= j) will be affected as a result of this process. To examine whether the support
of the sensitive itemset can be reduced through j without affecting the support of
its corresponding tentative itemsets in Bd + j j , the authors identify the transactions
in the database that support the sensitive itemset without supporting any max-min
itemset in Bd + j j . Deleting item j from such transactions leads to a reduction in the
support of the sensitive itemset, without affecting the support of any nonsensitive
itemset. Provided that a sufficient number of transactions exist with this property,
the hiding of the sensitive itemset can be achieved with minimal distortion of the
original database.
Last, when the second case scenario is inapplicable, Max-Min 2 iterates over all
possible pairs of the Bd + j j sets, to identify transactions that support the minimum
support itemsets of the first list and are affected by the corresponding victim item,
while not supporting any of the max-min itemsets that belong to the second list.
If such transactions exist, then the corresponding victim item is deleted from them.
Otherwise, the victim item is deleted from transactions that support the minimum
support itemsets of the first list. Algorithm 11.2 presents the details pertaining to the
operation of the Max-Min 2 algorithm.