Abstract | ||
---|---|---|
Differential privacy is widely used in data analysis. State-of-the-art k-means clustering algorithms with differential privacy typically add an equal amount of noise to centroids for each iterative computation. In this paper, we propose a novel differentially private k-means clustering algorithm, DP-KCCM, that significantly improves the utility of clustering by adding adaptive noise and merging clusters. Specifically, to obtain k clusters with differential privacy, the algorithm first generates n x k initial centroids, adds adaptive noise for each iteration to get n x k clusters, and finally merges these clusters into k ones. We theoretically prove the differential privacy of the proposed algorithm. Surprisingly, extensive experimental results show that: 1) cluster merging with equal amounts of noise improves the utility somewhat; 2) while adding adaptive noise only does not improve the utility, combining both cluster merging and adaptive noise further improves the utility significantly. (C) 2020 Elsevier B.V. All rights reserved. |
Year | DOI | Venue |
---|---|---|
2021 | 10.1016/j.neucom.2020.10.051 | NEUROCOMPUTING |
Keywords | DocType | Volume |
K-means, Cluster, Differential privacy | Journal | 424 |
ISSN | Citations | PageRank |
0925-2312 | 2 | 0.37 |
References | Authors | |
0 | 5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Tianjiao Ni | 1 | 2 | 0.37 |
Minghao Qiao | 2 | 2 | 0.37 |
zhili chen | 3 | 44 | 5.88 |
Shun Zhang | 4 | 7 | 2.16 |
Hong Zhong | 5 | 208 | 33.15 |