## 3 Proposal: Applying \(k\)-Anonymity to a (Random) Decision Tree
### Security: Strongly Safe \(k\)-Anonymization Ensures Differential Privacy  
In the field of data anonymization, in study [13], the authors demonstrated that performing \(k\)-anonymity after sampling achieved differential privacy; our proposal is a  
Figure 4: Example of conversion from decision tree (Figure 3) to anonymized data, where * in Weight and Age columns mean no partitioned for the corresponding attributes, respectively. development upon this core principle. Below, we outline the items necessary to evaluate data security. **Definition 3** (Strongly Safe \(k\)-anonymization algorithm [13]). : _Suppose that a function \(g\) has \(\mathcal{D}\rightarrow\mathcal{T}\), where \(\mathcal{D}\) and \(\mathcal{T}\) are the domain and range of \(g\), respectively. Suppose that \(g\) does not depend on \(D\subseteq\mathcal{D}\), i.e., \(g\) is constant. The strongly safe \(k\)-anonymization algorithm \(A\) with input \(D\subseteq\mathcal{D}\) is defined as follows:_  
* _Compute_ \(Y_{1}=\{g(\mathbf{x})|\mathbf{x}\in D\}\)_._
* \(Y_{2}=\{(y,|\{\mathbf{x}\in D:g(\mathbf{x})=y\}|):y\in Y_{1}\}\)_._
* _For each element in_ \(Y_{2}=\{(y,c)\}\)_, if_ \(c<k\)_, then the element is set to_ \((y,0)\)_, and the result is set to_ \(Y_{3}\)_._  
```
0: Training data \(D=\{(\mathbf{x}_{1},y_{1}),\ldots,(\mathbf{x}_{n},y_{n})\}\), the set of features \(X=\{F_{1},\ldots,F_{m}\}\), number of random decision trees to be generated \(N_{t}\)
0: Random decision trees \(T_{1},\ldots,T_{N_{t}}\)
1:for\(i\in\{1,\ldots,N_{t}\}\)do
2:\(T_{i}=\texttt{BuildTreeStructure}(\text{root},X)\)
3:endfor
4:for\(i\in\{1,\ldots,N_{t}\}\)do
5:\(D_{i}\leftarrow\emptyset\)
6: Regarding each \((\mathbf{x},y)\in D\), \(D_{i}\gets D_{i}\cup(\mathbf{x},y)\) with probability \(\beta\)
7:\(T_{i}=\texttt{UpdateStatics-}k\texttt{-anon}(T_{i},D_{i})\)
8:endfor
9:return\(T_{1},\ldots,T_{N_{t}}\)
10: UpdateStatistics-\(k\texttt{-anon}(T_{i},D_{i})\)
11: Set \(n_{i}(\texttt{leaf}^{(y)})=0\) for all leaves leaf and labels \(y\). 12:for\((\mathbf{x},y)\in D\)do
13: Find leaf corresponding to \(\mathbf{x}\), and set \(n_{i}(\texttt{leaf}^{(y)})=n_{i}(\texttt{leaf}^{(y)})+1\). 14:endfor
15:for All pairs of leaf and label \((\texttt{leaf},y)\)do
16:if\(n_{i}(\texttt{leaf}^{(y)})<k\)then
17:\(n_{i}(\texttt{leaf}^{(y)})\gets 0\) /*Removing leaves with fewer data*/
18:endif
19:endfor
```  
**Algorithm 3** Proposed training process  
Assume that \(f(j;n,\beta)\) denotes the probability mass function: the probability of succeeding \(j\) times after \(n\) attempts, where the probability of success after one attempt is \(\beta\). Furthermore, the cumulative distribution function is expressed as follows in Equation (2):  
\[f^{\prime}(j;n,\beta)=\sum_{i=0}^{j}f(i;n,\beta). \tag{2}\]  
**Theorem 1** (Theorem 5 in [13]). : _Any strongly safe \(k\)-anonymization algorithm satisfies \((\beta,\epsilon,\delta)\)-DPS for any \(0<\beta<1\), \(\epsilon\geq-\ln(1-\beta)\), and_  
\[\delta=d(k,\beta,\epsilon)=\max_{n:n\geq\lceil\frac{k}{\gamma}-1\rceil}\sum_{j >\gamma n}^{n}f(j;n,\beta), \tag{3}\]  
_where \(\gamma=\frac{\epsilon^{\prime}-1+\beta}{\epsilon^{\prime}}\)._  
Equation (3) shows the relationship between \(\beta\) and \(\delta\) in determining the value of \(\epsilon\) when \(k\) is fixed. Let us consider the case where record \((\mathbf{x},y)\in D\) is applied to a random decision tree \(T_{i}\), and the leaf reached is denoted by leaf. If a function \(g_{i}\) is defined as  
\[g_{i}((\mathbf{x},y))=(\texttt{leaf},y), \tag{4}\]  
then \(g_{i}\) in Equation (4) is apparently constant, that is, it does not depend on \(D\). Therefore, \(n_{i}(\texttt{leaf}^{(y)})\), which is generated using \(g_{i}\), can be regarded as an example of strongly safe \(k\)-anonymization; consequently, Theorem 1 can be applied. However, Theorem 1 above can be applied in its original form when there is one \(T_{i}\), i.e., when the number of trees \(N_{t}=1\). Theorem 2 can be applied when \(N_{t}>1\). **Theorem 2** (Theorem 3.16 in [17]).