Distributed K-Means clustering guaranteeing local differential privacy
By Chang Xia, Jingyu Hua, Wei Tong, Sheng Zhong. 2020
70 citations recorded by the source corpus.
Abstract In many cases, a service provider might require to aggregate data from end-users to perform mining tasks such as K-means clustering. Nevertheless, since such data often contain sensitive information. In this paper, we propose the first locally differentially private K-means mechanism under this distributed scenario. Differing from standard differentially private clustering mechanisms, the proposed mechanism doesn’t need any trusted third party to collect and preprocess users data. Our mechanism first perturbs users data locally to satisfy local differential privacy (LDP). Then it revises the traditional K-means algorithm to allow the service provider to obtain high-quality clustering results by collaborating with users based on the highly perturbed data. We prove that our mechanism can enable high utility clustering while guaranteeing local differential privacy for each user. We also propose an extended mechanism to improve our basic model in terms of privacy and utility. In this mechanism, we perturb both users’ sensitive data and the intermediate results of users’ clusters in each iteration. Moreover, we consider a more general setting where the users may have different privacy requirements. Extensive experiments are conducted on two real-world datasets, and the results show that our proposal can well preserve the quality of clustering results.
Subfields: Artificial Intelligence, Computer Science Applications, Sociology and Political Science
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Pasin Manurangsi
- Ravi Kumar
- Badih Ghazi
- Alisa Chang
- Yatharth Dubey
- Aleksandra Korolova
- Rasmus Pagh
- Albert Cheu
In Computer Science Applications
- Badih Ghazi
- Ravi Kumar
- Pasin Manurangsi
- Yatharth Dubey
- Aleksandra Korolova
- Jayadev Acharya
- Rasmus Pagh
- Ziteng Sun
In Sociology and Political Science
- Yatharth Dubey
- Ravi Kumar
- Badih Ghazi
- Aleksandra Korolova
- Pasin Manurangsi
- Krishnaram Kenthapadi
- Thanh T. L. Tran
Citations in the corpus
- The Power of the Hybrid Model for Mean Estimation (2018, methodology): “Other DP K-means algorithms exist in both the TCM [4, 8, 43, 46, 48, 53] and LM [47, 52, 54, 57] which improve on our two non-hybrid K-means algorithms.”
- Locally Private k-Means in One Round (2021, methodology): “Our clustering 8Very recently, (Xia et al., 2020) have reported experimental results for k-means in the local DP model.”