TY - GEN
T1 - A convergent differentially private k-means clustering algorithm
AU - Lu, Zhigang
AU - Shen, Hong
N1 - Publisher Copyright:
© Springer Nature Switzerland AG 2019.
PY - 2019
Y1 - 2019
N2 - 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 Lloyd’s algorithm in at most twice the iterations of Lloyd’s 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.
AB - 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 Lloyd’s algorithm in at most twice the iterations of Lloyd’s 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.
KW - Adversarial machine learning
KW - Differential privacy
KW - k-means clustering
UR - http://www.scopus.com/inward/record.url?scp=85064929836&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-16148-4_47
DO - 10.1007/978-3-030-16148-4_47
M3 - Conference contribution
AN - SCOPUS:85064929836
SN - 9783030161477
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 612
EP - 624
BT - Advances in Knowledge Discovery and Data Mining - 23rd Pacific-Asia Conference, PAKDD 2019, Proceedings
A2 - Zhou, Zhi-Hua
A2 - Huang, Sheng-Jun
A2 - Zhang, Min-Ling
A2 - Gong, Zhiguo
A2 - Yang, Qiang
PB - Springer Verlag
T2 - 23rd Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD 2019
Y2 - 14 April 2019 through 17 April 2019
ER -