## 2 Preliminaries
### Security Definitions  
Part of this work adopts _differential privacy_ to evaluate the security and efficiency of the model.  
Definition 1: A randomized algorithm \(A\) satisfies \((\epsilon,\delta)\)-DP, if for any pair of neighboring datasets, \(D\) and \(D^{\prime}\), and any \(O\subseteq\mathcal{O}\):  
\[\Pr[A(D)\in O]\leq e^{\epsilon}\cdot\Pr[A(D^{\prime})\in O]+\delta, \tag{1}\]  
\begin{table}
\begin{tabular}{c l} \hline \hline
**Notation** & **Description** \\ \hline \(k\) & Parameter for \(k\)-anonymity \\ \(\ell\) & Parameter for \(\ell\)-diversity \\ \(D\) & Dataset \(\{(\mathbf{x}_{i},y_{i})\}\), for \(i\in\{1,\ldots,n\}\) \\ \(\mathbf{X}\) & Data space with \(m\) features \(F_{1},\ldots,F_{m}\) \\ \(\mathbf{x}\) & Data \((x_{1},\ldots,x_{m})\in\mathbf{X}=(F_{1},\ldots,F_{m})\) \\ \(y\) & Label of data \(\mathbf{x}\) \\ \(Y\) & Label space \\ \(\texttt{leaf},\texttt{leaf}_{i}\) & Leaf or leaves \\ \(n(\texttt{leaf}^{(y)}_{i})\) & The number of data points classed as leaf\({}_{i}\) \\ \(n(\texttt{leaf}^{(y)}_{i})\) & with \\  & label \(y\in Y\). \\ \(n(\texttt{leaf}_{i})\) & The number of data points classed as leaf\({}_{i}\), i.e., \\  & \(n(\texttt{leaf}_{i})=\sum_{y\in Y}n(\texttt{leaf}^{(y)}_{i})\) \\ \(n_{j}(\texttt{leaf}^{(y)}_{i})\) & The number of data points with label \(y\in Y\) \\  & classed as leaf; of the \(j\)-th tree. \\  & This is used for the random decision tree. \\ \(\mathcal{H}_{u}\) & Total number of users who can be identified by a homogeneous attack \\ \(\mathcal{H}_{\texttt{leaf}}\) & Number of leaves that can be identified by a homogeneity attack \\ \(N_{t}\) & Number of random decision trees \\ ACC & Accuracy \\ \hline \hline \end{tabular}
\end{table}
Table 4: The notations used in this paper.  
where \(\mathcal{O}\) is a range of \(A\)._  
When studying differential privacy, it is assumed that the attacker knows all the elements in \(D\). However, such an assumption may not be realistic. This is taken into consideration, and the following definition is given in [13]:  
**Definition 2** (DP undersampling, \((\beta,\epsilon,\delta)\)-DPS).: _An algorithm \(A\) satisfies \((\beta,\epsilon,\delta)\)-DPS if and only if the algorithm \(A^{\beta}\) satisfies \((\epsilon,\delta)\)-DP, where \(A^{\beta}\) denotes the algorithm used to initially sample each tuple in the input dataset \(A\) with probability \(\beta\)._  
In other words, the definition describes the output of \(A\) by inputting \(D^{\prime}\), which is a result of sampling dataset \(D\). Hence, the attacker may know \(D\) but not \(D^{\prime}\).  
```
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}=\text{BuildTreeStructure}(\text{root},\mathbf{x})\)
3:endfor
4:for\(i\in\{1,\ldots,N_{t}\}\)do
5:\(T_{i}=\text{UpdateStatistics}(T_{i},D)\)
6:endfor
7:return\(T_{1},\ldots,T_{N_{t}}\)
8:
9:BuildTreeStructure\((\text{node},X)\)
10:if\((X\
eq\emptyset)\)then
11: Set the node as a leaf
12:else
13:\(F\gets X\)
14: /* Set \(F\) as the feature of the node. Also, assume \(|F|=c\) */
15:for\(i\in\{1,\ldots,c\}\)do
16:\(T=\text{BuildTreeStructure}(\text{node}_{i},X-F)\)
17:endfor
18:endif
19:
20:UpdateStatistics\((T_{i},D)\)
21: Set \(n_{i}(\text{leaf}^{(y)})=0\) for all leaves, leaf, and all labels, \(y\).
22:for\((\mathbf{x},y)\in D\)do
23: Find the leaf leaf corresponding to \(\mathbf{x}\), and set \(n_{i}(\text{leaf}^{(y)})=n_{i}(\text{leaf}^{(y)})+1\).
24:endfor
```  
**Algorithm 1** Training the random decision tree [9]