Differential privacy preserving clustering based on Haar wavelet transform

摘要

So far, several techniques have been proposed for privacy preserving clustering (PPC). Most of the existing techniques have been designed based on heuristic notions without provable privacy guarantees. ∈-differential privacy is a strong notion of privacy, which guarantees provable privacy. However, low degree of utility is the key issue of e-differential notion. In this paper, we have proposed an e-differential based algorithm to generate a perturbed data for PPC purpose. Hence, we have used Haar wavelet transform (HWT) for two reasons: (1) for achieving the perturbed data with much lower dimension compared to the original data in order to increase the efficiency of clustering algorithms, and (2) for adding much lower noise in order to obtain the perturbed data with both appropriate level of utility and differential privacy guarantee. We have also compared the proposed algorithm with a recent algorithm based on the utility and privacy guarantees. In addition, we have presented the results of the experiments using several datasets, which show that the proposed algorithm has an appropriate level of utility.