An Optimized Sanitization Approach for Minable Data Publication

In this section, we introduce the preprocessing strategy. Technically, the data publisher can protect an SAR by reducing its Support or Confidence to drop below the related mining thresholds^{[ 5 ]}. To this end, the data publisher can delete/add some items from/into the original dataset. Unfortunately, the mentioned methods cause the following three side-effects.

· Hiding-Failure. Some SARs still can be discovered from the original and the sanitized datasets.

· Lost-Rule. Some NARs can be discovered from the original dataset, but they are lost in the sanitized datasets.

· Fake-Rule. Some fake association rules (FARs) cannot be mined from the original dataset, but they are generated in the sanitized datasets.

These side-effects can be measured by the following three metrics.

· Hiding-Failure Rate (HFR): $\alpha ={\displaystyle \frac{|R_s\cap R_s^{\prime }|}{|R_s|}}$ ,

· Lost-Rule Rate (LRR): $\beta ={\displaystyle \frac{|\overline{R_s}\cap \overline{R_s^{\prime }}|}{|\overline{R_s}|}}$ ,

· Fake-Rule Rate (FRR): $\gamma ={\displaystyle \frac{|{\mathrm{\complement }}_{\overline{R_s^{\prime }}}\{\overline{R_s}\cap \overline{R_s^{\prime }}\}|}{|\overline{R_s}|}},$

where $R_s$ and $\overline{R_s}$ are the sets of SARs and NARs, respectively. Meanwhile, $R_s^{\prime }$ and $\overline{R_s^{\prime }}$ are the sets of SARs and NARs that obtained after sanitization process, respectively. In addition, $|\cdot |$ denotes the number of elements in the related set, and ${\mathrm{\complement }}_{A}B$ means the complement of the set $B$ relative to set $A$ .

It is worth pointing out that the Support of any FARs will not be increased if we remove the items^{[ 5 ]}. Hence, we prefer to hide SARs by removing items than randomly modifying the dataset. In addition, it will cause more serious side-effects if the data publisher changes the LHS of SARs other than the RHS of SARs. Thus, SA-MDP sanitizes the dataset by deleting some items in the RHS of SARs. Next, we give three definitions for preprocessing.

Definition 4. (Critical transaction). A transaction is a critical transaction ( $C_T$ ) if it supports one or more SARs.

Specifically, “ $t_i$ supports $X\to Y$ ” means $t_i$ contains all the items of $X\cup Y$ . Then, by Definition 4, critical transactions are composed of those SAR-related transactions, and the rest transactions are filtered out, so the solution space can be reduced.

Definition 5. (Sensitive item). An item is a sensitive item ( $S_I$ ) if it is the only item in the RHS of SAR or it has the highest frequency in the RHS of SAR and the lowest frequency in NAR.

SA-MDP tends to remove the $S_I$ to hide SARs. That is to say, only the $S_I$ -related NARs will be affected. Therefore, we present the third definition.

Definition 6. (Critical rule). A critical rule ( $C_R$ ) is the NAR which contains any $S_I$ .

According to Definition 6, SA-MDP can evaluate the LRR by evaluating the loss of $C_R$ . To sum up, the preprocessing can be summarized in three steps.

(1) SA-MDP removes useless information and leaves $C_T$ .

(2) SA-MDP computes the frequency of the RHS of SARs and finds $S_I$ .

(3) SA-MDP finds all NARs containing $S_I$ and labels them as $C_R$ .

After the preprocessing, SA-MDP can reduce the search space to improve the convergence rate.

Example. We continue to illustrate the preprocessing, step by step. We select the following two rules as SARs that need to be protected.

$$(1)B\to F\mathit{\hspace{1em}}\text{and}\mathit{\hspace{1em}}(2)C\to F$$

Then, the preprocessing is performed as follows.

First, based on Definition 4, SA-MDP removes 4 transactions, i.e., $t_2,t_3,t_6,t_{10}$ . The filtered out transactions are given in Table 4 . Then, according to Definition 5, SA-MDP determines the item $F$ is the $S_I$ for the two SARs. Next, according to Definition 6, NARs containing $F$ are identified as the $C_R$ . Thus, we have 8 $C_R$ , which are shown in Table 5 .

The data publisher can obtain that ${\displaystyle \frac{|{𝒞}_{𝒯}^{*}|}{|𝒯|}}=60\%$ and ${\displaystyle \frac{|{𝒞}_{ℛ}^{*}|}{|\overline{R_S}|}}=73\%$ . In other words, the presented preprocessing can reduce the amount of data and further reduce the search space.

In this section, we show how to design the fitness function based on the preprocessing strategy. Specifically, we design the fitness function based on the above-mentioned three side-effects, in which $\alpha$ denotes HFR and $\beta$ denotes LRR. Especially, $\alpha$ increases by 1 when one SAR in $R_s$ is failed to be protected and $\beta$ increases by 1 when one NAR in $\overline{R_s}$ is lost after the hiding process. They are two coarse-grained evaluation metrics since $\alpha$ and $\beta$ are changed by modifying multiple transactions. Therefore, to provide a fine-grained evaluation for the solution quality, we present a new evaluation metric, optimal sanitation distance (OSD) $\delta$ , which is calculated as follows:

(6) $$\delta =\frac{\underset{l=1}{\overset{R_s}{\sum }}{a}_l}{|R_s|}+\frac{\underset{u=1}{\overset{\overline{R_s}}{\sum }}{b}_u}{|\overline{R_s}|}$$

where $a_l$ is calculated as

(7) $$a_l=\max \{\min \{Con{f}_l-minC,Su{p}_l-minS\},0\}$$

$a_l$ can reflect how much at least the Confidence or the Support needs to be decreased for hiding the $l$ -th SAR. Besides, $b_u$ is calculated as

(8) $$b_u=\max \{\max \{minC-Con{f}_u,minS-Su{p}_u\},0\}$$

$b_u$ shows how much at most the Confidence or the Support needs to be increased for avoiding the loss of the $u$ -th NAR. Recall that SA-MDP hides SAR by removing its RHS, no FAR will be generated. Thus, the FRR of SA-MDP identically equals 0. Considering three side-effects, the fitness function can be represented as

(9) $$\min ℱ(p)=w_1\times \alpha +w_2\times \beta +w_3\times \delta$$

Especially, in this paper, we set $w_1=w_2=w_3=1$ . The data publisher can adjust the weights according to the practical demands. The fitness function $ℱ(p)$ provides a precise quantify of the solutions’ quality.

In this section, we introduce the initialization method, which can be divided into the following three steps.

(1) Represent the critical transaction with a binary matrix ${𝒞}_{𝒯}$ . In the preprocessing, the data publisher has filtered out the critical transaction from $𝒯$ according to Definition 4. Let ${𝒞}_{𝒯}$ denote the set of the critical transaction, which will be transformed into a $|{𝒞}_{𝒯}|\times |𝒮|$ binary matrix. In such matrix, the ( $i,j$ )-th element equals 1, which means that the item $s_j$ exists in transaction $t_i$ .

(2) Generate an initial population ${𝒫}^0$ . According to ${𝒞}_{𝒯}$ , the data publisher generates an initial particle $p_1^0=\{1,2,\mathrm{\dots },|{𝒞}_{𝒯}|\}$ . Then, to generate the initial population ${𝒫}^0=\{p_1^0,\mathrm{\dots },p_{{𝒩}_{pop}}^0\}$ , the data publisher randomly selects the elements in $p_1^0$ , and those selected elements compromise a new particle. This process will perform ${𝒩}_{pop}-1$ times, where ${𝒩}_{pop}$ is the population size and can be empirically set. ${𝒫}^0$ are constituted by the ${𝒩}_{pop}$ particles.

(3) Generate the initial best-previous position $p_{best}$ and the initial best-so-far position $g_{best}$ . SA-MDP calculates the fitness of each particle in ${𝒫}^0$ . The particle having the smallest fitness is the initial best previous position $p_{best}$ , which also is the best-so-far position $g_{best}$ .

Before the evolution is run, SA-MDP can further reduce the dimension of solution space by controlling the modifying numbers. Specifically, according to the Support and Confidence of SARs, SA-MDP can determine the upper and the lower bound of the number of transactions as ${ℳ}_{\max }$ and ${ℳ}_{\min }$ , respectively. Let $d_1$ denote the maximum Support which needs to be reduced, and $d_2$ denotes the maximum Confidence which needs to be reduced. Suppose $X\to Y$ is the SAR $R_S$ that needs to be protected, we have to remove the $Y$ -related items to hold that

(10) $$Su{p}_{R_l}\times |T|-d_1<minS\times |T|$$

or

(11) $$Con{f}_{R_l}\times Su{p}_{R_{l_X}}|T|-d_2<minC\times Su{p}_{R_{l_X}}|T|$$

To sum up, $d_1$ and $d_2$ can be calculated as follows.

(12) $$d_1=\underset{R_l\in R_s}{\max }(\lceil (Su{p}_{R_l}-minS)\times |T|\rceil )$$

(13) $$d_2=\underset{R_l\in R_s}{\max }(\lceil (Con{f}_{R_l}-minC)\times Su{p}_{R_{l_X}}|T|\rceil )$$

where $\lceil \cdot \rceil$ is the ceiling function.

Then, ${ℳ}_{\min }$ is obtained as

(14) $${ℳ}_{\min }=\min (d_1,d_2)$$

Based on ${ℳ}_{\min }$ , SA-MDP decreases the number of the modified transactions such that the data utility can be guaranteed to a certain degree. In SA-MDP, ${ℳ}_{\max }$ is set as the number of $C_T$ , i.e., ${ℳ}_{\max }=|{𝒞}_{𝒯}|$ .

Example. According to the above discussion, the initialization is achieved in the following three steps. The first step is to represent the obtained ${𝒞}_{𝒯}^{*}$ with a binary matrix. Note that $t_1$ contains 4 items (i.e., $B$ , $C$ , $D$ , and $F$ ), so $t_1$ can be represented by 011101. Besides, $t_4$ , $t_5$ , $t_7$ , $t_8$ , and $t_9$ are also denoted by a binary vector, respectively. The transformed binary matrix is obtained and is shown in Table 6 . The second step is to generate an initial population ${𝒫}^0=\{p_1^0,\mathrm{\dots },p_{{𝒩}_{pop}}^0\}$ . From the obtained matrix, we pick the $S_I$ -related columns as the data that needs to be removed. Let the transaction identifier of the removed items as the position of the particle. Thus, we can have an initial particle $p_1^0=\{\text{null}\}$ , which means not to remove any items. Then, we randomly select the transactions in ${𝒞}_{𝒯}^{*}$ to sanitize. For instance, $t_4$ and $t_9$ are selected. Then, the identifier of those transactions constitutes a new position of particle $p_2^0=\{4,9\}$ . We perform ${𝒩}_{pop}-1$ times and then obtain the initial population. The third step is to calculate the fitness of these initial particles. The particle having the smallest fitness is the initial best previous position $p_{best}$ , which also is the best-so-far position $g_{best}$ .

This section briefly introduces the evolution process of SA-MDP. The evolution includes: mother particle splitting, updating the velocity and the position, and updating the best positions. Suppose the current particle that needs to be updated is $p_i^n$ , the main steps are described as follows.

(1) Mother particle $p_i^n$ splitting. Suppose each mother particle $p_i^n$ can be split into several child particles $p_i^{n+1}$ owning to the same property with $p_i^n$ . Especially, let ${𝒮}_{\max }$ denote the maximum number of the child particles and ${𝒮}_{\min }$ denote the minimum number of the child particles. Thus, the number of the child particles of each mother particle can be computed as follows.

(15) $$s_i=\lfloor ({𝒮}_{\max }-{𝒮}_{\min })\times r_1\rfloor -{𝒮}_{\min }$$

where ${𝒮}_{\max }$ and ${𝒮}_{\min }$ are set by the data publisher, $\lfloor \cdot \rfloor$ is the floor function, and $r_1$ is a random number.

(2) Updating the velocity and the position. SA-MDP adopts two updating methods: (a) the directional learning and (b) the random splitting.

(a) The directional learning method. For the particle $p_i^n$ , $i=1,2,\mathrm{\dots },s_i$ , the specific particle updating process is performed as Eqs. ( 16 ) and ( 17 ), respectively.

(16) $$v_i^{n+1}=[p_{best}-p_i^n]\cup [g_{best}-p_i^n]$$

(17) $$p_i^{n+1}=\{p_i^n,\text{null}\}\times r_2\cup v_i^{n+1}$$

The velocity of particles is updated as Eq. ( 16 ), where $p_{best}$ is the best-previous position and $g_{best}$ is the best-so-far solution. Accordingly, the position of particles is updated as Eq. ( 17 ), where null is an empty dimension and means no transactions will be modified, and $r_2$ is a randomly generated number.

(b) The random splitting method. For the particle $p_i^n$ , $i=1,2,\mathrm{\dots },s_i$ , during the specific particle updating process, SA-MDP first calculates the modifying distance as Eq. ( 18 ).

(18) $$m_i=\lfloor \varphi \times {\displaystyle \frac{s_i}{\underset{i=1}{\overset{{𝒩}_{pop}}{\sum }}{s}_i}}\rfloor \times ({ℳ}_{\max }-{ℳ}_{\min })$$

where $\varphi$ is the total number of child particles that can be generated at most. Then, SA-MDP selects $m_i$ elements from the $C_T$ and changes them randomly.

(3) Updating the best positions ( $p_{best}$ and $g_{best}$ ). SA-MDP calculates the fitness $ℱ({𝒫}_i^{*})$ and generates the new best-previous position $p_{best}$ . Then, if $ℱ(p_{best})⩽ℱ(g_{best})$ , SA-MDP updates the best-so-far solution $g_{best}$ by $p_{best}$ . Otherwise, there is no updating during this generation, then the value of ${𝒩}_{fit}$ is incremented by 1.

If the mother particle can be split into multiple child particles, it will improve the diversity of the solution and the exploration ability of the algorithm. Therefore, there are more opportunities to escape from the local optimal solution and find the optimal particle. However, any particles certainly cannot split infinitely. Hence, SA-MDP has ${𝒮}_{\max }$ and ${𝒮}_{\min }$ , which denote the maximum and minimum number that a particle can be split into, respectively. The number of child particles $s_i$ split from the mother particle is randomly generated as Eq. ( 15 ).

In Step 2, the velocity and the position are updated. Specifically, the SA-MDP approach proposed in this paper adopts two updating methods: one is the directional learning of particles, which can improve the exploitation ability of the algorithm; the other is random splitting of particles, which can improve the exploration ability of the algorithm. Besides, in order to adapt to the evolutionary environment, the position of the particles will be randomly deflected during the splitting process. The number of deflection dimensions of the particle position will be determined according to ${ℳ}_{\max }$ and ${ℳ}_{\min }$ .

Example. Suppose $p_{best}=\{1,4,9\}$ , $g_{best}=\{4,7,$ $9\}$ and, $p_i^n=\{4,9\}$ . First, we let $5$ and $2$ be the values of ${𝒮}_{\max }$ and ${𝒮}_{\min }$ , respectively. Second, we update particle. By the directional learning method, the result of $p_{best}-p_i^n$ is $\{1\}$ and the result of $g_{best}-p_i^n$ is $\{7\}$ . Then, $v^{n+1,i}=\{1,7\}$ . On the other hand, a target set $\{p_i^n,\text{null}\}=\{4,9,\text{null}\}$ . If $r_2=0.4\times 3=1.2$ , we randomly select one dimension from the target set, i.e., $\{4\}$ . Then, we can obtain the updated position $p^{n+1,i}=\{4\}\cup \{1,7\}=\{1,4,7\}.$ Moreover, by the randomly splitting method, SA-MDP calculates the number of dimensions that need to be changed for each child particle ${ℳ}_{\max }$ and ${ℳ}_{\min }$ . The data publisher can set ${𝒮}_{\max }$ and ${𝒮}_{\min }$ . Suppose $m_i$ is 2 for $p_i^n$ , SA-MDP can obtain $p_i^{n+1}=\{4,\text{null}\}$ . Third, after the user obtains new child particles, SA-MDP calculates the relevant fitness and updates the best positions $p_{best}$ and $g_{best}$ .

The termination is determined by two parameters, i.e., ${𝒯}_{fit}$ and ${𝒯}_{gen}$ . Namely, if ${𝒩}_{fit}⩾{𝒯}_{fit}$ or ${𝒩}_{gen}⩾{𝒯}_{gen}$ , SA-MDP terminates. Specifically, ${𝒩}_{fit}$ counts the number of times the best-so-far solution $g_{best}$ has not been updated and ${𝒩}_{gen}$ denotes the number of generations. SA-MDP will repeat until at least one of these two termination conditions is satisfied.