Differentially Private K-Means Clustering
Authors:
Open Access
- 9 March 2016
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 26-37
Abstract
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.Keywords
All Related Versions
Funding Information
- National Science Foundation (NSF CNS-1116991)
This publication has 26 references indexed in Scilit:
- PrivBasisProceedings of the VLDB Endowment, 2012
- A firm foundation for private data analysisCommunications of the ACM, 2011
- Boosting the accuracy of differentially private histograms through consistencyProceedings of the VLDB Endowment, 2010
- Differential Privacy2006
- Calibrating Noise to Sensitivity in Private Data Analysis2006
- Privacy-Preserving Datamining on Vertically Partitioned Databases2004
- Estimating the Number of Clusters in a Data Set Via the Gap StatisticJournal of the Royal Statistical Society Series B: Statistical Methodology, 2001
- An empirical comparison of four initialization methods for the K-Means algorithmPattern Recognition Letters, 1999
- Genetic K-means algorithmIEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 1999
- Least squares quantization in PCMIEEE Transactions on Information Theory, 1982