PE-means: Improved Differentially Private $k$-means Clustering through Private Evolution
Provides a more accurate differentially private clustering method for data analysts needing privacy guarantees.
PE-means introduces a differentially private k-means clustering algorithm using private evolution, achieving an average 20% improvement in clustering loss over state-of-the-art baselines.
We study the problem of differentially private (DP) $k$-means clustering in Euclidean space. Previous solutions rely on summing the private data directly, which induces a sensitivity proportional to the domain. We introduce PE-means, an extension of the private evolution (PE) algorithm (an increasingly popular method for synthetic data generation), to the problem of $k$-means clustering. The key advantage of PE is that it only computes a private histogram with constant sensitivity to guide the evolution. Our adaptation of PE includes new evolutionary operators for clustering, as well as other algorithmic improvements of independent interest. Overall, PE-means achieves an average improvement of 20% in clustering loss over state-of-the-art baselines.