## 3 Proposal: Applying \(k\)-Anonymity to a (Random) Decision Tree
### Experiments on \(k\)-AnonToRdt  
The efficiency of the proposal was verified using the Nursery dataset [18], the Adult dataset [19], the Mushroom dataset [20], and the Loan dataset [21]. The characteristics of each dataset are as follows. * The Nursery dataset contains 12,960 records with eight features, with a maximum of five values for each feature;
* The Adult dataset contains 48,842 records with 14 features. Here, each feature has more possible values and more records than in the Nursery datasets; \begin{table}
\begin{tabular}{c c c c c c c c c} \hline \hline \multirow{2}{*}{\(N_{t}\epsilon\setminus\beta\)} & \multicolumn{3}{c}{\(k=5\)} & \multicolumn{3}{c}{\(k=10\)} & \multicolumn{3}{c}{\(k=20\)} \\ \cline{2-10}  & **0.01** & **0.1** & **0.4** & **0.01** & **0.1** & **0.4** & **0.01** & **0.1** & **0.4** \\ \hline
1.0 & 0.001 & - & - & \(4.66\times 10^{-7}\) & 0.355 & - & \(1.20\times 10^{-13}\) & 0.045 & - \\
2.0 & \(5.52\times 10^{-5}\) & 0.352 & - & \(1.08\times 10^{-9}\) & 0.034 & - & \(7.00\times 10^{-19}\) & 0.000 & - \\
3.0 & \(7.68\times 10^{-6}\) & 0.127 & - & \(2.72\times 10^{-11}\) & 0.005 & - & \(4.75\times 10^{-22}\) & \(7.82\times 10^{-6}\) & 0.426 \\
4.0 & \(1.86\times 10^{-6}\) & 0.043 & - & \(1.68\times 10^{-12}\) & 0.001 & 0.583 & \(1.92\times 10^{-24}\) & \(2.37\times 10^{-7}\) & 0.134 \\
5.0 & \(7.47\times 10^{-7}\) & 0.028 & 0.994 & \(2.85\times 10^{-13}\) & 0.000 & 0.348 & \(3.54\times 10^{-26}\) & \(1.61\times 10^{-8}\) & 0.051 \\
6.0 & \(2.417\times 10^{-7}\) & 0.009 & 0.963 & \(3.19\times 10^{-14}\) & \(3.93\times 10^{-5}\) & 0.191 & \(7.71\times 10^{-28}\) & \(1.03\times 10^{-9}\) & 0.016 \\
7.0 & \(1.22\times 10^{-7}\) & 0.009 & 0.963 & \(8.51\times 10^{-15}\) & \(2.05\times 10^{-5}\) & 0.175 & \(5.75\times 10^{-29}\) & \(1.48\times 10^{-10}\) & 0.008 \\
8.0 & \(1.22\times 10^{-7}\) & 0.004 & 0.498 & \(4.07\times 10^{-15}\) & \(4.53\times 10^{-6}\) & 0.093 & \(6.27\times 10^{-30}\) & \(1.56\times 10^{-11}\) & 0.003 \\
9.0 & \(5.47\times 10^{-8}\) & 0.002 & 0.410 & \(7.58\times 10^{-16}\) & \(1.87\times 10^{-6}\) & 0.078 & \(5.06\times 10^{-31}\) & \(2.82\times 10^{-12}\) & 0.001 \\ \hline \hline \end{tabular}
\end{table} 
Table 5: Approximate value of \(N_{t}\delta\) for \(k=5,10,20\) and \(N_{t}=10\). * The Mushroom dataset contains 8124 records with 22 features. Compared to the above two datasets, there are more features, but the number of records is small. In general, applying \(k\)-anonymity to this kind of dataset is challenging. * The Loan dataset [21] contains 9578 records with 13 features. We used the \"not.fully.paid\" feature to label classes. There are four binary attributes and seven numerical attributes in this dataset. Appendix A contains the evaluation of the basic decision tree with each dataset. Firstly, \(\delta,N_{t},k\) were set to \(\delta=0.4\), \(N_{t}\in\{8,\ldots,11\}\), and \(k\in\{5,10\}\). The results from the Nursery dataset obtained via \(k\)-AnonToRdt with these parameters are as follows:  
* The accuracy of the original decision tree was 0.933, as shown in Table A1. * As shown in Table 6 (a), for a tree depth equal to four, the accuracy obtained was 0.84, which was inferior to that of the original decision tree. * As shown in Table 6 (a), for a tree depth equal to five, the accuracy decreased drastically as \(k\) increased. The results from the Adult dataset obtained via \(k\)-AnonToRdt with the same \(\delta,N_{t},k\) were as follows: (there were numerical values in this dataset; to handle this, a threshold \(t\) was chosen randomly from its domain, and two children for \(\leq\)\(t\) and \(>\)\(t\) were produced by the tree)