# A Grid-Based Swarm Intelligence Algorithm for Privacy-Preserving Data Mining
## 3 Preliminary Information and Problem Statement  
Let \(I=\{i_{1},\,i_{2},\,\ldots,\,i_{m}\}\) be a finite set of \(r\) distinct items appearing in database \(D\), where \(D\) is a set of transactions consisting of \(D=\{T_{1},\,T_{2},\,\ldots,\,T_{n}\}\), and \(T_{q}\in D\). Each \(T_{q}\) is a subset of \(I\) and has a  
Figure 1: Pre-large concept for transaction deletion. unique identifier \(q\), called its _TID_. If support of the itemset is no less than the minimum support count (\(\mathit{minsup}\times|D|\), \(\mathit{minsup}\) is defined as the minimum support threshold), it is then put into the set of \(FI\). The set of confidential information is denoted as \(CI=\{c_{1},c_{2},\ldots,c_{k}\}\), which can be defined based on user preference and each \(c_{i}\in FI\). **Definition 1**. : _The maximal number of deleted transactions of all confidential information in CI is denoted as MDT, which is defined as follows:_  
\[MDT=max\{sup(c_{1}),sup(c_{2}),\ldots,sup(c_{k})\}, \tag{4}\]  
_where \(sup(c_{i})\) is defined as the support count of \(c_{i}\) in the database._  
For example, suppose the sensitive itemsets are (\(AB\):4) and (\(BC\):5), the _MDT_ of those two sensitive itemsets is calculated as \(max\{4,5\}\) (= 5). **Definition 2**. : _For each \(c_{i}\in CI\), the number of deleted transactions for hiding \(c_{i}\) is denoted as \(m\), which is defined as follows:_  
\[m=(1+\lfloor\frac{MDT-\mathit{minsup}\times|D|}{1-\mathit{minsup}}\rfloor). \tag{5}\]  
For example, support the _minsup_ is set as 35%, and _MDT_ is 5, \(m\) is then calculated as: \((1+\lfloor\frac{5-0.35\times 10}{1-0.35}\rfloor)\) (= 4). In the designed GMPSO algorithm, \(m\) is then considered as the size of a particle in the MOPSO model. To completely hide the confidential information in a database, the set of \(CI\) becomes _null_ after the sanitization process. However, this process may cause serious side effects in terms of missing and artificial costs because three side effects have a trade-off relationship. Thus, an optimization process is required to find the balance between the three side effects. Details of the three side effects are described below. **Definition 3**. : _A hiding failure indicates the amount of confidential information that fails to be hidden after the sanitization process, which is denoted as \(\alpha\), and is defined as follows:_  
\[\alpha=|CI\cap FI^{\prime}|, \tag{6}\]  
_where \(FI^{\prime}\) is the set of frequent itemsets after data sanitization._  
For example, suppose \(CI=\{(AB)\), \((BC)\}\), and \(FI^{\prime}=\{(BC)\), \((CD)\), \((ABC)\}\). Thus, \(\alpha\) is calculated as: \(|\{(AB),(BC)\}\cap\{(BC),(CD),(ABC)\}|=\{(BC)\}\) (= 1). **Definition 4**. : _The missing cost is the number of itemsets that are discovered as a large itemset before the sanitization but will be hidden after the data sanitization, which is denoted as \(\beta\), and is defined as follows:_  
\[\beta=|FI-CI-FI^{\prime}|, \tag{7}\]  
_where \(FI\) is used to keep the frequent itemsets in the original database prior to sanitization._  
For example, suppose \(FI=\{(AB)\), \((BC)\), \((ABC)\}\), and \(CI=\{(AB)\), \((BC)\}\), and \(FI^{\prime}=\{(AD)\}\), thus \(\beta\) is calculated as: \(|\{(AB),(BC),(ABC)\}-\{(AB),(BC)\}-\{(AD)\}|=|\{(ABC)\}|=1\). **Definition 5**. : _The artificial cost is the number of arisen itemsets that were not discovered as large itemsets before sanitization but will appear as frequent itemsets after the sanitization process, which is denoted as \(\gamma\), and is defined as follows:_  
\[\gamma=|FI^{\prime}-FI|. \tag{8}\]For example, suppose \(FI=\{(AB),\)\((BC),\)\((ABC)\}\) and \(FI^{\prime}=\{(AD)\}\), and the \(\gamma\) is calculated as: \(|\{(AD)\}-\{(AB),(BC),(ABC)\}|=|\{(AD)\}|=1\).