# Publishing Anonymized Set-Valued Data via Disassociation towards Analysis
## 2 Disassociation and Utility Awareness for Associations
### Utility Guided Ant-based Clustering Algorithm (Ugac)  
The utility-guided ant-based clustering (UGAC) algorithm, Algorithm 1, is presented and explained in details in [1]. This section recaps the optimization process elaborated for the preservation of the utility rules. UGAC creates for every utility rule \(ur_{i}\in UR\), an expert ant \(a_{i}\) to pick up records that are supersets of \(ur_{i}\), and drop them in the representative cluster \(C_{i}\). The choice of records for pick up is guided by the pheromone trail represented with a square matrix \(A=[u][u]\) (line 3) reflecting the support of each utility rule in every cluster. Actually, in the PickUp procedure, an ant \(a_{i}\) chooses to move a record from the cluster that has the highest density of \(ur_{i}\) (line 2) to \(C_{i}\) (line 7-9). After every move, the pheromone matrix, \(A\), is updated with the support of the utility rules in the clusters (lines 10-15). ```
0:\(\mathcal{T}\), \(UR\), \(k\), \(\delta\), \(\beta_{predefined}\), it
0:\(\mathcal{T}^{*}\)
1:\(\mathcal{T}_{|UR}=\{r\mid r\in\mathcal{T}\ and\exists\ ur\in\ UR\ and\ ur\subseteq r\}\)
2:\(u=|UR|\)
3: create \(u\) clusters, \(u\) ants and square matrix \(A[u][u]\)
4:it\(\_{count}=0\)
5:while (\(\mathcal{T}_{|UR}\
eq\emptyset\)) do
6:for each expert ant \(a_{i}\)do
7:\(C_{i}=C_{i}\cup r\mid r\in\mathcal{T}_{|UR}\ and\ ur_{i}\subseteq r\)
8:\(\mathcal{T}_{|UR}=\mathcal{T}_{|UR}\setminus r\)
9:for (\(j=0\); \(j<u\); \(j++\)) do
10:\(A[i][j]=s(ur_{i},C_{j})\)
11:endfor
12:endfor
13:endwhile
14:while (it\(\_{count}<\) it or jobless\(\_\)ants \(<u\)) do
15:\(jobless\_\)ants \(=0\)
16:for each expert ant \(a_{i}\)do
17:\(\beta_{ur_{i}}=\frac{A[i][i]}{s(ur_{i},\mathcal{T})}\)
18:if (\(\beta_{ur_{i}}<\beta_{predefined}\) or \(A[i][i]<k<s(ur_{i},\mathcal{T})\)) then
19: PickUp\((a_{i},ur_{i},0)\)
20:else
21:\(jobless\_\)ants \(++\)
22: DropLoad\((a_{i})\)
23:endif
24:endfor
25:\(it\_count++\)
26:endwhile
27:for each cluster \(C_{i}\)do
28:\(ClustersSet=ClustersSet\)\(\emptyset\)Split\((C_{i})\)
29:endfor
30:VerticalPartitioning\((ClustersSet)\)
31:Disassociation\((\mathcal{T}\setminus\mathcal{T}_{|UR})\)
```  
**Algorithm 1** Utility guided ant-based clustering algorithm (UGAC). All this pick up job is executed while \(\beta_{ur_{i}}<\beta_{predefined}\) or if there is less than \(k\) records in \(C_{i}\) (line 16-19). Yet, if \(\beta_{ur_{i}}\geq\beta_{predefined}\), the expert ant \(a_{i}\) can work for the benefit of another ant during the current iteration to converge to the optimal solution quickly (line 21-22). Function DropLoad, Algorithm 2, finds the utility rule that still needs the most iterations to achieve the \(\beta_{predefined}\) (line 2). Then, it calls the PickUp function, Algorithm 3, to find a record that can be transported to the corresponding cluster. At the end of the iterations, there exist \(u\) clusters, each representing mainly one utility rule. The resulting clusters may have sizes greater than the maximum cluster size \(\delta\) allowed. Every cluster is split into smaller clusters having respectively a size less or equal to \(\delta\) (line 28), calling Algorithm 4, when necessary. Algorithm 1 ends by vertically partitioning the resulting clusters from UGAC (line 30) and treats all the records that are not supersets of any utility rule, via the normal processes of disassociation (line 31).