## 3 Proposed Anonymization Method, Iterative _k_-Anonymous Clustering Method (I\(k\)-ACM)
### Information Loss Metric  
Calculating the data loss of _k_-anonymous data is needed to predict the performance of our proposed method under different _k_-anonymity parameters. In our study, we use the entropy concept of information theory to measure the information loss [10]. The difference of entropies between the _k_-anonymous data and the original data constitutes the information loss. Suppose that \(T\) is the input data set having \(r\) records and \(m\) attributes, \(B\) is the bit string representation of this data set and \(C\) is the random variable that gets the probability value of an attribute value in a _k_-anonymous data entry being the actual attribute value in the original data. Assume that all the entries of \(B\) is normalized according to the number of bits having value \"1\" in that entry (from now on we refer \"true bit\" to a bit having value \"1\") and normalized version forms data set \(\overline{B}\). A sample data set is shown in Table 1. Here, there are two records; each record has three attributes; each attribute is categorical and each has five distinct attribute values. Table 2 shows the normalized version of data. During normalization, each entry is divided by the number of true bits in the corresponding bit string entry. Information loss of a data table \(T\), \(IL(T)\), is equal to the conditional entropy, \(H(C\mid B)\). Here, conditional entropy gives the uncertainty about the prediction of the original attribute values of a record when we have the knowledge of corresponding _k_-anonymous bit strings of that record. Original data has only one true bit in each bit string because each original data entry corresponds to one attribute value. However, in _k_-anonymous data, each entry may have more than one attribute value and each attribute value is represented by an additional bit. Therefore, if an entry has only one true bit, that entry does not have information loss. In this situation, we have no doubt that this true bit is the true bit that comes from the original data. As the number of true bits increases, disorder of the data increases because it is harder \begin{table}
\begin{tabular}{|c|c|c|c|} \hline Records & \(B_{i1}\) & \(B_{i2}\) & \(B_{i3}\) \\ \hline \(T_{1}\) & \(00010\) & \(01000\) & \(10000\) \\ \(T_{2}\) & \(01100\) & \(11100\) & \(01111\) \\ \hline \end{tabular}
\end{table} 
Table 1: A sample bit string representation set. \begin{table}
\begin{tabular}{|c|c|c|c|} \hline Records & \(\overline{B_{i1}}\) & \(\overline{B_{i2}}\) & \(\overline{B_{i3}}\) \\ \hline \(T_{1}\) & \(00010\) & \(01000\) & \(10000\) \\ \(T_{2}\) & \(0\frac{1}{2}\frac{1}{2}00\) & \(\frac{1}{3}\frac{1}{3}\frac{1}{3}00\) & \(0\frac{1}{4}\frac{1}{4}\frac{1}{4}\frac{1}{4}\) \\ \hline \end{tabular}
\end{table} 
Table 2: A sample normalized version of bit string representation set. to predict which one of them is the original true bit. Prediction gets harder because information is lost due to the increase in the number of true bits. Conditional entropy, which is used in order to calculate the disorder of the data, is a well measurement tool for the information loss. Conditional entropy \(H(C\mid B)\), which is equal to information loss of table \(T\), \(IL(T)\), can be found as follows:  
\(IL(T)=H(C\mid B)=\sum_{B_{ij}\in B}p(B_{ij})H(C\mid B=B_{ij})\)  
\[IL(T)=-\sum_{B_{ij}\in B}p(B_{ij})\sum_{k\in\{1..z\}}p(C=k\mid B_{ij})\log p(C =k\mid B_{ij}) \tag{1}\]  
In Equation 1, it is assumed that each attribute is converted to bit strings having size \(z\). This means all categorical attributes have \(z\) distinct attribute values and all numerical attributes have \(z\) number of interval ranges. Also, it is assumed that all \(k\)'s, where the equalities of \(p(C=k\mid B_{ij})=0\) are true, are excluded from the summation. \(C\) random variable can take values from the set \(\{1..z\}\). Actually, \(\overline{B}\) is calculated for finding the value of this random variable.