A Convergent Differentially Private k-Means Clustering Algorithm
Preserving differential privacy(DP)for the iterative clustering algorithms has been extensively studied in the interactive and the non-interactive settings.However,existing interactive differentially private clustering algorithms suffer from a non-convergence problem,i.e.,these algorithms may not terminate without a predefined number of iterations.This problem severely impacts the clustering quality and the efficiency of the algorithm.To resolve this problem,we propose a novel iterative approach in the interactive settings which controls the orientation of the centroids movement over the iterations to ensure the convergence by injecting DP noise in a selected area.We prove that,in the expected case,our approach converges to the same centroids as Lloyds algorithm in at most twice the iterations of Lloyds algorithm.We perform experimental evaluations on real-world datasets to show that our algorithm outperforms the state-of-the-art of the interactive differentially private clustering algorithms with a guaranteed convergence and better clustering quality to meet the same DP requirement.
Differential privacy Adversarial machine learning k-means clustering
Zhigang Lu Hong Shen
School of Computer Science,The University of Adelaide,Adelaide,Australia School of Computer Science,The University of Adelaide,Adelaide,Australia;School of Data and Computer
国际会议
澳门
英文
612-624
2019-04-14（万方平台首次上网日期，不代表论文的发表时间）