# Enhancing Utility in Anonymized Data against the Adversary's Background Knowledge
## 2 Related Work
### Creation of the Initial QI Groups
Experiments were run on two datasets consisting of categorical and numerical attributes as follows:

(1) The adult dataset [13] is a dataset published by the US statistics center in 1994, which is widely used for anonymization experiments. This dataset contains 45,222 statistical records with 8 grouping attributes, 6 numerical attributes, and 1 attribute for showing income. To compare our algorithm with other similar studies [6; 12], three attributes of age, gender, and education were used as QI attributes, while income was used as an SA. (2) The BKseq dataset [6] was generated based on domain knowledge extracted from medical literature. It includes a history of 24 tables, each table including 4000 records. Each record in the dataset comprises three quasi-identifier (QI) attributes: gender, age, and weight, as well as a sensitive attribute that reflects the result of medical exams. The sensitive attribute includes 19 distinct values representing various stages of the disease. ### Evaluation Measure

We applied global certainty penalty (GCP) to evaluate the impact on data utility generated by anonymization (Different data utility measures are suggested for anonymization algorithms. GCP is a well-known measure and does not have limitations that other measures do [12]). GCP uses the normalized certainty penalty (\(NCP\)) measure. If table \(T\) includes D numerical QI attributes, \(A_{1}\), \(A_{2}\),..., \(A_{D}\); the generalized version of a record r = (\(x_{1}\),...,\(x_{D}\)) is \(r^{\prime}=([y_{1}-z_{1}],\ldots,[y_{D}-z_{D}])\) so that \(\forall 1\leq i\leq D,y_{i}\leq z_{i}\) (\(x_{i}\), \(y_{i}\) and \(z_{i}\) are numbers). \(NCP\) on \(A_{i}\) is calculated in Equation (2). \[NCP_{A_{i}}(r)=\frac{z_{i}-y_{i}}{|A_{i}|} \tag{2}\]where the expression \(|A_{i}|\) represents the number of unique values that attribute \(A_{i}\) takes in table \(T\). Based on this, the \(NCP(r)\) is computed as a weighted sum of its \(NCP\) values across all QI attributes, as given by Equation (3). \[NCP(r)=\sum_{i=1}^{n}(w_{i}\times NCP_{A_{i}}(r)) \tag{3}\]

GCP is calculated as the sum of \(NCP\) on all records in \(T\). The value for GCP is a number larger or equal to zero, where zero indicates a situation with no information loss and maximum data usefulness. Therefore, lower GCP values are desirable. We also evaluated our algorithms regarding record linkage (\(RL\)) [19], which measures privacy loss. It is used for disclosure risk analysis. \(RL\) is calculated using Equation (4) by the number of correct linkages between the original data and the anonymized data. \[RL=\frac{\sum_{r\in T}P_{RL}(r^{\prime})}{n} \tag{4}\]

where \(n\) is the size of \(T\), and \(P_{RL}(r^{\prime})\) is the linkage probability of the anonymized record \(r^{\prime}\). The linkage probability of \(r^{\prime}_{j}\) is calculated via Equation (5) below. \[P_{RL}(r^{\prime})=\left\{ \begin{array}{ll}\frac{1}{|E_{i}|}&:r^{\prime}\in E _{i}\\ 0&:otherwise\end{array} \right. \tag{5}\]

where \(E_{i}\) is the closest QI group to \(r\). Here, \(r^{\prime}\in E_{i}\), \(P_{RL}(r^{\prime})\) is computed as the inverse of the size of \(E_{i}\); otherwise, the probability is zero. The lower RL means the higher privacy of the record respondents. ### Effectiveness of the Proposed Algorithm

In this section, the behavior of the proposed anonymization algorithm is analyzed from three aspects: the R-U confidentiality map, the size of QI groups, and the runtime. The R-U confidentiality map is applied as a graphical description of GCP and RL. The performance of the proposed anonymization algorithm UHRA was compared with two other approaches: the BK-based algorithm [6] and \(k\)-anonymity primacy [12], shown as BKA-JS and \(k\)-primacy in the following tables and figures, respectively. BKA-JS and \(k\)-primacy are generalization-based algorithms. We ran their public versions to compare the results. We examine the impact of different privacy parameters: \(t\), \(k\), and J.