Inline Algorithm - Association Rule Hiding for Data Mining - page 67

maximize å u nm 2U u nm

( å T n 2D I Õ i m 2I u nm < msup;8I 2S min
å T n 2D I Õ i m 2I u nm msup;8I 2V
where V =fI 2Bd + (F 0 D ) : I\I S min 6=?g

subject to

Fig. 14.2: The CSP formulation as an optimization process.

Replace

å T n 2D z Y i S msup;Y i = Õ i m 2 z u nm = u n z 1 : : :u n z j z j

with

8
<
:

Y i u n z 1
Y i u n z 2
.
Y i u n z j z j
Y i u n z 1 +u n z 2 +: : :+u n z j z j jzj+1
and
å i Y i S msup

8i

where Y i 2f0; 1g

Fig. 14.3: The Constraints Degree Reduction approach.

a-priori unknown, and can be as large as the number of items M in the given dataset.
This fact prohibits the solution of the CSP in the exact same format that is presented
in Figure 14.2. Fortunately though, due to the binary nature of the variables involved
in the CSP, one can replace inequalities that contain products of two or more u nm
variables with a set of inequalities that each contains no product of binary variables.
In addition, this can be accomplished in a way that when all the new inequalities
are solved, the solution that is attained is the same as the one of solving the ini-
tial inequality. The side-effect of this methodology is that it increases the number
of constraints that participate to the system of inequalities. On the other hand, the
resulting inequalities are very simple and allow for fast solutions, thus adhere for
an efficient solution of the CSP. To generate this transition, a number of temporary
binary values Y i need to be introduced, as shown in Figure 14.3. After applying
the Constraints Degree Reduction (CDR) approach, all constraints become linear
with no coefficients. A linear optimization solver can then be applied to provide the
optimal solution L C of the CSP.
The final case that needs to be examined is what happens if the optimization
problem yields no solution, i.e. the produced CSP is unsolvable. To handle such
problems where an exact solution cannot be attained, the inline algorithm relies on
the properties of the produced CSP. As one can observe, the integer programming
problem that contains only the constraints imposed by the sensitive itemsets in S min