K-Means Clustering with Local Distance Privacy
Authors:
- 1 December 2023
- journal article
- research article
- Published by Tsinghua University Press in Big Data Mining and Analytics
- Vol. 6 (4) , 433-442
Abstract
With the development of information technology, a mass of data are generated every day. Collecting and analysing these data help service providers improve their services and gain an advantage in the fierce market competition. K-means clustering has been widely used for cluster analysis in real life. However, these analyses are based on users' data, which disclose users' privacy. Local differential privacy has attracted lots of attention recently due to its strong privacy guarantee and has been applied for clustering analysis. However, existing $K$ -means clustering methods with local differential privacy protection cannot get an ideal clustering result due to the large amount of noise introduced to the whole dataset to ensure the privacy guarantee. To solve this problem, we propose a novel method that provides local distance privacy for users who participate in the clustering analysis. Instead of making the users' records in-distinguish from each other in high-dimensional space, we map the user's record into a one-dimensional distance space and make the records in such a distance space not be distinguished from each other. To be specific, we generate a noisy distance first and then synthesize the high-dimensional data record. We propose a Bounded Laplace Method (BLM) and a Cluster Indistinguishable Method (CIM) to sample such a noisy distance, which satisfies the local differential privacy guarantee and local d E -privacy guarantee, respectively. Furthermore, we introduce a way to generate synthetic data records in high-dimensional space. Our experimental evaluation results show that our methods outperform the traditional methods significantly.
Keywords
This publication has 20 references indexed in Scilit:
- A Convergent Differentially Private k-Means Clustering Algorithm2019
- Minimax Optimal Procedures for Locally Private EstimationJournal of the American Statistical Association, 2018
- Differentially Private K-Means Clustering and a Hybrid Approach to Private OptimizationACM Transactions on Privacy and Security, 2017
- RAPPOR2014
- The Algorithmic Foundations of Differential PrivacyFoundations and Trends® in Theoretical Computer Science, 2014
- PrivGene2013
- Geo-indistinguishability2013
- Privacy-preserving statistical estimation with optimal convergence rates2011
- What Can We Learn Privately?SIAM Journal on Computing, 2011
- Practical privacy2005