Source-linked AI summary
Differentially Private $k$-Means Clustering
Dong Su, Jianneng Cao, Ninghui Li, Elisa Bertino, Hongxia Jin
TL;DR
Differentially private analysis must balance interactive task-specific algorithms against reusable non-interactive synopses, and the paper studies this tradeoff for k-means clustering. It proposes a hybrid that uses a private synopsis to initialize interactive refinement, with error analysis guiding privacy-budget allocation. Experiments support the hybrid approach and report EUGkM as outperforming existing methods.
Problem
The paper asks whether interactive or non-interactive differential privacy provides better k-means accuracy under the same privacy budget.
Method
The hybrid first runs non-interactive EUGkM, then uses its centroids to initialize one interactive DPLloyd round, allocating privacy budget between the stages.
Results
EUGkM outperforms existing methods, and the hybrid approach is reported as the best approach to differentially private k-means clustering.
Takeaways & Limitations
Hybrid differential privacy may be useful for other analysis tasks, especially tasks requiring parameter tuning or maximizing the accuracy of one k-means clustering task.
Takeaways & Limitations
Interactive private k-means outputs centroids but cannot provide more detailed information about the shapes of points within clusters.
Abstract
from arXiv · showhide
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 tradeoff of interactive vs. non-interactive approaches and propose a hybrid approach that combines interactive and non-interactive, using $k$-means clustering as an example. In the hybrid approach to differentially private $k$-means clustering, one first uses a non-interactive mechanism to publish a synopsis of the input dataset, then applies the standard $k$-means clustering algorithm to learn $k$ cluster centroids, and finally uses an interactive approach to further improve these cluster centroids. We analyze the error behavior of both non-interactive and interactive approaches and use such analysis to decide how to allocate privacy budget between the non-interactive step and the interactive step. Results from extensive experiments support our analysis and demonstrate the effectiveness of our approach.
1. INTRODUCTION
The paper studies interactive versus non-interactive differential privacy for k-means and proposes a hybrid that combines a private synopsis with interactive refinement. Experiments and error analysis compare these approaches and guide when hybridization is beneficial.
- Interactive versus non-interactive approaches: Interactive methods customize private algorithms for one task, whereas non-interactive methods publish a reusable private synopsis for multiple analyses.Interactive access is limited by privacy-budget consumption, while a synopsis can support multiple tasks.
- Non-interactive k-means: The paper introduces non-interactive EUGkM, which applies k-means to noisy counts from cells in a d-dimensional grid.Choosing the grid size M trades spatial accuracy against noisy counts dominated by noise.
- Empirical comparisons: Across extensive evaluations on 6 external and 81 synthesized datasets, DPLloyd was the strongest of the three interactive methods.The analysis attributes poorer performance by iterative methods to privacy budget division across iterations.
- Empirical comparisons: EUGkM performed much better than DPLloyd on most datasets, while DPLloyd scaled worse with k and EUGkM scaled worse with d.The two methods performed similarly on a few datasets, and DPLloyd outperformed EUGkM on two.
- Hybrid approach: The hybrid combines EUGkM with one DPLloyd round, allocating half the privacy budget to each stage and using error analysis to decide when it can outperform EUGkM.When privacy is small, the interactive round may worsen the centroids rather than improve them.
- Broader applicability: The paper extends the hybrid idea to private parameter tuning by selecting parameters on published synopses before running interactive analysis on the dataset.This avoids dividing the limited privacy budget across many private parameter trials.
2. RELATED WORK
Related work covers interactive private data-analysis frameworks and non-interactive mechanisms for answering queries or releasing synthetic data. The paper positions its k-means methods within these two lines of research.
- Interactive approaches: Prior interactive work includes private query systems, the SuLQ model, PINQ, and the sample-and-aggregate framework applied to k-means.The GkM algorithm evaluated in this paper is implemented through the GUPT system.
- Interactive approaches: Private model-fitting work includes genetic-algorithm methods, instantiated as PGkM for differentially private k-means.PGkM is described as a general private model-fitting framework applied to clustering.
- Interactive approaches: Other interactive mechanisms have been developed for recommendations, decision trees, logistic regression, and optimization objectives.These works adapt task-specific analyses to satisfy differential privacy.
- Non-interactive approaches: Most non-interactive work targets accurate histogram or range-query answers using methods such as Laplace noise, wavelets, and hierarchical organization.These mechanisms focus on query release rather than directly performing k-means clustering.
- Non-interactive approaches: Synthetic-data mechanisms can achieve logarithmic error in the number of queries but may require super-polynomial computation in the data-universe size.Private multiplicative-weight methods are identified as subsequent work in this area.
3. BACKGROUND
The background defines differential privacy and its composable privacy budget, then describes Laplace noise and the normalized k-means objective. Lloyd’s algorithm alternates assignment and centroid updates until convergence.
- Differential privacy: Differential privacy requires neighboring datasets to produce output distributions that differ by at most an e^ε multiplicative factor.Here, neighboring datasets differ by adding or removing one tuple.
- Differential privacy: Privacy is composable: mechanisms using ε1 through εm together satisfy ε-differential privacy when ε equals their sum.For multistep analyses, the privacy budget is divided across steps so the total does not exceed ε.
- Private mechanisms: The Laplace mechanism releases a dataset function plus random noise whose scale depends on the function’s global L1 sensitivity.The paper denotes a Laplace random variable by Lap(β), with β as its scale parameter.
- k-means clustering: k-means partitions a d-dimensional dataset into k clusters while minimizing normalized intra-cluster variance.The objective sums squared distances between points and their assigned centroids, normalized by the dataset size.
- k-means clustering: Lloyd’s algorithm repeatedly assigns each point to its nearest centroid and updates each centroid to its cluster’s center.The process alternates between partitioning and centroid updates until convergence.
4. THE INTERACTIVE AND NON-INTERACTIVE APPROACHES
The paper presents interactive and non-interactive differentially private k-means methods, then combines them through approaches that manage privacy budget, initialization, and parameter choices. Interactive methods iteratively improve centroids, while non-interactive methods cluster a noisy grid synopsis.
- DPLloyd: DPLloyd adds Laplacian noise during Lloyd iterations, with the iteration count determining how privacy budget is distributed.Each iteration computes noisy cluster counts and coordinate sums; too many iterations add excessive noise, while too few may prevent convergence.
- PGkM: PGkM maintains a pool of centroid candidates and uses selection, crossover, and mutation to improve and diversify them.Its iteration count trades off convergence against the privacy budget available for selecting good candidates.
- Comparison: Interactive k-means methods limit further analyses after consuming the privacy budget, whereas a published synopsis supports repeated clustering analyses.The interactive limitation follows because additional dataset access can violate differential privacy; synopsis-based methods avoid this restriction.
- Non-interactive approaches: The non-interactive approach releases noisy counts for equal-width grid cells and runs k-means using the resulting synopsis.Cells retain bounding boxes and noisy counts, while clustering treats each cell as a whole rather than replicating rounded point counts.
- Non-interactive approaches: Choosing the number of grid cells balances noise impact against location error from representing points by cell centers.Large M lowers average cell counts and increases noise impact; small M enlarges cells and can make center-based representation inaccurate.
5. PERFORMANCE AND ANALYSIS
The evaluation compares five private k-means methods across external and synthetic datasets using NICV, examining performance as privacy budget, dimensions, and cluster count vary. Results favor DPLloyd or EUGkM depending on setting and motivate targeted modifications to weaker methods.
- Evaluation methodology: The experiments use six external datasets plus synthetic datasets varying dimensions and cluster counts, and evaluate centroid quality with average nearest-centroid squared distance, called NICV.Synthetic datasets vary d and k from 2 to 10, while external datasets include S1, Gowalla, TIGER, Image, Adult, and Lifesci.
- Comparative results: DPLloyd has the best performance among the interactive methods in most cases.PGkM exceeds DPLloyd only on S1 when ǫ is below 0.15.
- Comparative results: EUGkM outperforms DPLloyd on four low-dimensional datasets at small ǫ, while DPLloyd outperforms EUGkM on the two high-dimensional datasets across almost all tested budgets.EUGkM becomes closer to DPLloyd as ǫ increases in the low-dimensional cases.
- Scalability analysis: EUGkM is more sensitive to increasing dimension, whereas DPLloyd deteriorates more quickly as the number of clusters increases.The differing sensitivity to d and k explains why the methods perform differently across datasets.
- GkM analysis: GkM is consistently much worse than the other methods because both centroid aggregation and its added noise contribute substantial error.The analysis finds the evaluated block-size setting far from optimal because GkM error is dominated by noise.
- GkM analysis: GkM-3K becomes competitive with PGkM and sometimes significantly outperforms it, although it still underperforms DPLloyd.GkM-3K fixes each block size at 3k points.
- PGkM analysis: PGkM improves more slowly than Lloyd and receives limited privacy budget for selecting candidates across its iterations.In the Image dataset, Lloyd reaches the best baseline after three iterations, whereas Gene requires more than 10.
6. THE HYBRID APPROACH
The hybrid method combines EUGkM’s private synopsis with one DPLloyd update, applying the second stage only when error analysis predicts an improvement. Experiments show improved scalability and competitive or better NICV across settings.
- DPLloyd is the strongest interactive baseline, but EUGkM can outperform it at small privacy budgets in low-dimensional datasets.
- The hybrid method uses EUGkM to generate initial centroids, then runs one DPLloyd round with the remaining privacy budget.The analyzed design allocates half the privacy budget to EUGkM and uses its centroids to initialize DPLloyd.
- When privacy budget ǫ is small, the method falls back to EUGkM because one DPLloyd round may worsen the centroids.
- 6.1 Error Study of DPLloyd: DPLloyd’s one-round centroid MSE increases with t^2k^2d^3 and decreases with (Nǫ)^2, while convergence and initialization also affect scalability.
- 6.2 Error Study of EUGkM: EUGkM’s non-interactive error combines noisy-cell variance with discretization bias from representing points by cell centers.
- 6.4 Experimental results: The hybrid outperforms EUGkM on synthetic data as k and d increase, while on external data it is slightly better at larger ǫ and often strongest in higher dimensions.For Gowalla at ǫ = 0.7, hybrid NICV is 0.02172 versus 0.02174 for EUGkM.
- 6.4 Experimental results: EUGkM requires more runtime because it evaluates 30 initial-centroid sets and runs until convergence, whereas DPLloyd uses five iterations.
7. CONCLUSION AND DISCUSSIONS
The paper reports advances in differentially private k-means through non-interactive methods, extensive evaluation, and a hybrid approach. It concludes that EUGkM has an advantage in comparisons, while hybrid methods are promising when maximizing accuracy for one k-means task.
- The proposed EUGkM outperforms existing methods, and the hybrid approach is reported as the best approach to k-means clustering.
- Non-interactive EUGkM has a clear advantage, especially when the privacy budget ε is small, while also enabling other analyses on the dataset.
- Hybrid approaches may be the most promising solution when the goal is to improve the accuracy of one k-means clustering task as much as possible.