# Publishing Anonymized Set-Valued Data via Disassociation towards Analysis
## 2 Disassociation and Utility Awareness for Associations
### Framework of the Algorithm  
We are motivated by the need to preserve some items associated together to increase their utility value despite disassociation and the ambiguity that it raises. We refer to those associations as utility rules. Accordingly, we transform normal horizontal partitioning for the set of records, which are supersets of at least one utility rule, into a clustering optimization problem. Before describing the algorithm, it is important to identify the challenges of the clustering problem in our context:  
* A record might enclose multiple utility rules and with partitional clustering, this record should belong to exactly one cluster satisfying one utility rule. * The common items, belonging or not to a utility rule, between the records affect the distance metrics. * The maximum cluster size constant, \(\delta\), limits the number of records allowed in a cluster. The proposed algorithm benefits from the studied behaviors of natural ant. Table 2 describes the environment of our clustering problem in the ant colony system terminology. Let \(\mathcal{T}_{|UR}\) be the set of records from \(\mathcal{T}\) that are supersets of any utility rule \(ur\in UR\):  
\[\mathcal{T}_{|UR}=\{r\in\mathcal{T}\mid\exists\;ur\in UR\;and\;ur\subseteq r\}. \tag{3}\]  
Cluster initialization: Every utility rule, \(ur\), has a representative cluster and an expert ant that transports records. The algorithm starts by sending the expert ants in search for records from \(\mathcal{T}_{|UR}\) containing their representative utility rules; recursively until \(\mathcal{T}_{|UR}\) is empty. Pheromone Trail: Square matrix \(A=[u][u]\) represents the pheromone trail of the working ants, with \(u\) being the number of predefined utility rules, \(u=|UR|\). It is the collective adaptive memory of the expert ants and is initialized by the value of the support of each utility rule \(ur_{i}\) in each cluster \(C_{j}\), such that:  
\[A[i][j]=s(ur_{i},C_{j}). \tag{4}\]  
We denote by \(\beta_{ur_{i}}\) the ratio of the records representing \(ur_{i}\) in cluster \(C_{i}\):  
\[\beta_{ur_{i}}=\frac{A[i][i]}{s(ur_{i},\mathcal{T})}. \tag{5}\]  
Individual and cooperative work of expert ants:During the clustering process, every ant \(a_{i}\) works for its utility rule \(ur_{i}\) to reach a support threshold \(\beta_{predefined}\in[0,1]\) in its representative cluster \(C_{i}\), such that:  
\[\beta_{ur_{i}}\geq\beta_{predefined} \tag{6}\]  
\(\bullet\) If \(\beta_{ur_{i}}<\beta_{predefined}\):  
Let \(d(ur_{i},C_{j})\) be the density of a utility rule \(ur_{i}\) in \(C_{j}\):  
\[d(ur_{i},C_{j})=\frac{A[i][j]}{|C_{j}|}. \tag{7}\]  
Each ant \(a_{i}\) chooses the cluster whose density of \(ur_{i}\) is the highest. A record \(r\) from this one is then moved to cluster \(C_{i}\), with \(ur_{i}\subseteq r\). This process is known as the pick up job. \(\bullet\) If \(\beta_{ur_{i}}\geq\beta_{predefined}\):  
To speed up the convergence of the solution and prevent the ants from moving aimlessly, for the current iteration, ant \(a_{i}\) works for the benefit of another ant \(a_{j}\) that needs the most help to increase its \(\beta_{ur_{j}}\). This process is known as the drop job. We consider that ant \(a_{j}\) is in need for the most help when reaching \(\beta_{ur_{j}}\) for its utility rule \(ur_{j}\) demands the highest number of iterations:  
\[ur_{j}=\operatorname*{arg\,max}_{j\in[1,\ldots,u]-i}\big{(}s(ur_{j},\mathcal{ T})*(\beta_{predefined}-\beta_{ur_{j}})\big{)}. \tag{8}\]  
The next section describes and comments the algorithm implementing the ant-based clustering methodology.