用私有演化算法改进隐私保护k均值聚类，误差降低26%。
PE-means: Improved Differentially Private $k$-means Clustering through Private Evolution
- 基于私有演化生成聚类中心，仅依赖常数敏感度的私有直方图
- 在多个数据集上聚类损失平均降低26%，优于主流基线方法
- 适合需要高精度隐私保护聚类的场景，如医疗数据分析
我们研究欧氏空间中的差分隐私(k-均值)聚类问题。以往方法直接对私有数据求和，导致敏感度与数据域大小成正比。本文提出PE-means，将私有演化(PE)算法扩展至聚类任务。其核心优势在于仅需计算敏感度恒定的私有直方图来引导演化过程。本工作引入新的聚类演化算子及其他算法改进，具有独立应用价值。整体上，PE-means在多个基准数据集上相较Google的基于局部敏感哈希的算法及DP-Lloyd变体，平均降低26%的聚类损失。
原文摘要 · Abstract (English)
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 26% in clustering loss over state-of-the-art baselines such as Google's LSH-based algorithm and DP-Lloyd variants.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。