## 3 Proposed Anonymization Method, Iterative _k_-Anonymous Clustering Method (I\(k\)-ACM)
### Bottom-Up Hierarchical Clustering Process  
I\(k\)-ACM is based on forming clusters of input vectors iteratively. Input data to I\(k\)-ACM is represented as \(T\) and \(i^{th}\) input vector is \(T_{i}\). Each cluster is numerated as \(L_{j}^{h}\) in each iteration, \(h\), where \(j\) is the index number of cluster. Input vector set of cluster \(L_{j}^{h}\) is represented by \(V_{j}^{h}\), the number of input vectors belonging to that cluster is \(|V_{j}^{h}|\), and representative vector is \(R_{j}^{h}\). Suppose that \(k^{th}\) data item of representative vector is denoted as \(R_{j}^{h}[k]\). Representative vector is actually the anonymized output of input vectors belonging to that cluster which is formed by generalization and encryption operations  
Figure 5: Steps of iterative anonymization. of some data parts of vectors. Assume that \(D^{h}\) is distance matrix of iteration \(h\). It contains distances between each cluster pairs. Algorithm of I\(k\)-ACM is given in Algorithm 1. Hierarchical clustering process starts with the initialization phase given in second step of main function. In this phase each input vector constitutes separate cluster and that vector is also representative vector of the cluster. As given in the fourth phase of algorithm, iterations are divided into anonymization steps. Iterations continue until \(n^{th}\)-anonymization step. In each iteration, by using the information loss metric described in Section 3.2, distances between each cluster are calculated. Distance between any two clusters is actually equal to the information loss that may occur if both clusters are merged. Two clusters having smallest distance, assume that clusters, \(L_{s}^{h}\) and \(L_{t}^{h}\), are chosen for merging. New bigger cluster, \(L_{u}^{h+1}\) which contains the vector items of both clusters is formed and old two clusters are deleted. \(|V_{u}^{h+1}|\) is equal to the sum of \(|V_{s}^{h}|\) and \(|V_{t}^{h}|\). For the first step of cluster operations (\(k1\)-anonymization stage), anonymity operation is generalization. In these generalization operations, \(R_{u}^{h+1}[k]\), is equal to the XOR of \(R_{s}^{h}[k]\) and \(R_{t}^{h}[k]\). Encryption is used as an anonymity operation in all anonymization steps except \(k1\)-anonymization. Assume that two clusters, \(L_{h}^{s}\), \(L_{h}^{t}\) are chosen as the closest cluster pair at \(h\)th iteration of I\(k\)-ACM and this iteration corresponds to \((i+1)^{th}\)-anonymization step. The newly created cluster is labelled as \(L_{h}^{st}\) and \(E_{e_{i-1}}(x)\) represents the encrypted output of input \(x\) with key \(e_{i-1}\). Formation of representative vector for newly created cluster, \(R_{h}^{st}\), is given in Algorithm 2. A sample cluster combination by encryption operation is shown in Figure 6. Assume that represented vectors of two closest clusters, \(L_{t}^{h}\) and \(L_{s}^{h}\) are '0011 0010 1000' and '0100 0010 1000', respectively. The values of vectors indicate that data records have three attributes each having four distinct attribute values. First bit strings of vectors, '0011' and '0100' are compared. Since they are not identical, concatenation of values are encrypted. This encryption result forms the first bit string of representative vector of newly created cluster, \(L_{ts}^{h+1}\). Second bit strings of clusters, '0010' and '0100', are identical. Therefore, second bit string of new cluster is also '0100'. By using the same method, third bit string is found as '1000'. Clustering process occurs in each iteration of anonymization model described in Section 3.3. In that model, each iteration takes \(k_{i}\)-anonymized output, clustering operations are completed until data is \(k_{i+1}\)-anonymized. In the first iteration raw data is \(k_{1}\)-anonymized by generalization operations. In the second one and the rest of all iterations data is anonymized to a higher level by encryption operations where different key is used in each iteration.