Differentially Private K-Means Clustering

By Dong Su, Jianneng Cao, Ninghui Li, Elisa Bertino, Hongxia Jin. 2015

169 citations recorded by the source corpus.

There are two broad approaches for differentially private data analysis. The interactive approach aims at developing customized differentially private algorithms for various data mining tasks. The non-interactive approach aims at developing differentially private algorithms that can output a synopsis of the input dataset, which can then be used to support various data mining tasks. In this paper we study the effectiveness of the two approaches on differentially private k-means clustering. We develop techniques to analyze the empirical error behaviors of the existing interactive and non-interactive approaches. Based on the analysis, we propose an improvement of DPLloyd which is a differentially private version of the Lloyd algorithm. We also propose a non-interactive approach EUGkM which publishes a differentially private synopsis for k-means clustering. Results from extensive and systematic experiments support our analysis and demonstrate the effectiveness of our improvement on DPLloyd and the proposed EUGkM algorithm.

Subfields: Artificial Intelligence

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

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.”
Differentially private subspace clustering (2015, background): “However, empirical evidence shows that sample-aggregate based private clustering suffers from poor utility in practice [26].”
How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacy (2023, methodology): “(Su et al., 2016)’s experiments show that the synopsis approach outperforms DP-Lloyd on datasets with 2 or 3 dimensions, but performs worse on datasets with larger dimensions.”
Differentially Private Mixture of Generative Neural Networks (2017, background): “on the training data and create multiple generative models that produce higher-quality synthetic samples compared to a single model. Differentially Private k-means has also been studied in prior work [44], however, aiming to ﬁnd linearly separable clusters and add noise which is proportional to the ”
Differentially Private Releasing via Deep Generative Model (2018, methodology): “The existing work can be roughly categorized into supervised settings, such as logistic regression [5] and support vectormachine (SVM) [5, 31], and unsupervised settings, such as publishing histograms [37], releasing contingency tables [38], hypothesis testing [13], collaborative recommendation [42]”
Locally Private k-Means Clustering (2019, background): “There has been a significant amount of work aimed at constructing differentially private kmeans algorithms that work in the trusted-curator model [9, 22, 12, 20, 14, 21, 29, 25, 26, 24, 13, 5, 23, 16, 18].”
Differentially Private Clustering in High-Dimensional Euclidean Spaces (2017, methodology): “Among all private methods, the griding algorithm in (Su et al., 2016) achieves the lowest objective value in this setting, while our algorithm and SuLQ both achieved reasonably good performance.”
Locally Private k-Means in One Round (2021, background): “…2005; Nissim et al., 2007; Feldman et al., 2009; Gupta et al., 2010; Mohan et al., 2012; Wang et al., 2015; Nissim et al., 2016; Nock et al., 2016; Su et al., 2016; Feldman et al., 2017; Balcan et al., 2017; Nissim and Stemmer, 2018; Huang and Liu, 2018; Nock et al., 2016; Nissim and Stemmer,…”