Differential Private (Random) Decision Tree Without Adding Noise

The decision tree is a typical algorithm in machine learning and has multiple expanded variations. However, regarding privacy, few in the variations reached practical level due to many challenges on balancing privacy preservation and performance. In this paper, we propose a method of applying privacy preservation to the (random) decision tree, which is a variation of the expanded decision tree proposed by Fan et al. in 2003, to achieve the following goals: