Embedding differential privacy in decision tree algorithm with different depths

作者：Bai, Xuanyu; Yao, Jianguo^*; Yuan, Mingxuan; Deng, Ke; Xie, Xike; Guan, Haibing^*

来源：Science China Information Sciences, 2017, 60(8): 082104.

DOI：10.1007/s11432-016-0442-1

• differential privacy
• decision tree
• exponential mechanism
• exhaustive search
• MCMC

Differential privacy (DP) has become one of the most important solutions for privacy protection in recent years. Previous studies have shown that prediction accuracy usually increases as more data mining (DM) logic is considered in the DP implementation. However, although one-step DM computation for decision tree (DT) model has been investigated, existing research has not studied the scenarios when the DP is embedded in two-step DM computation, three-step DM computation until the whole model DM computation. It is very challenging to embed DP in more than two steps of DM computation since the solution space exponentially increases with the increase of computational complexity. In this work, we propose algorithms by making use of Markov Chain Monte Carlo (MCMC) method, which can efficiently search a computationally infeasible space to embed DP into DT generation algorithm. We compare the performance when embedding DP in DT with different depths, i.e., one-step DM computation (previous work), two-step, three-step and the whole model. We find that the deep combination of DP and DT does help to increase the prediction accuracy. However, when the privacy budget is very large (e.g., ? = 10), this may overwhelm the complexity of DT model, and the increasing trend is not obvious. We also find that the prediction accuracy decreases with the increase of model complexity.

• 出版日期2017-8
• 单位上海交通大学