Differentially Private K-Means Clustering and a Hybrid Approach to Private Optimization
Authors:
Open Access
- 26 October 2017
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Privacy and Security
- Vol. 20 (4) , 1-33
Abstract
k -means clustering is a widely used clustering analysis technique in machine learning. In this article, we study the problem of differentially private k -means clustering. Several state-of-the-art methods follow the single-workload approach, which adapts an existing machine-learning algorithm by making each step private. However, most of them do not have satisfactory empirical performance. In this work, we develop techniques to analyze the empirical error behaviors of one of the state-of-the-art single-workload approaches, DPLloyd, which is a differentially private version of the Lloyd algorithm for k >-means clustering. Based on the analysis, we propose an improvement of DPLloyd. We also propose a new algorithm for k -means clustering from the perspective of the noninteractive approach, which publishes a synopsis of the input dataset and then runs k -means on synthetic data generated from the synopsis. We denote this approach by EUGkM. After analyzing the empirical error behaviors of EUGkM, we further propose a hybrid approach that combines our DPLloyd improvement and EUGkM. Results from extensive and systematic experiments support our analysis and demonstrate the effectiveness of the DPLloyd improvement, EUGkM, and the hybrid approach.Keywords
Funding Information
- United States National Science Foundation (CNS-1116991,CNS-1640374)
This publication has 28 references indexed in Scilit:
- Towards Accurate Histogram Publication under Differential Privacy2014
- Functional mechanismProceedings of the VLDB Endowment, 2012
- 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
- 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