PE-means：通过私有进化改进的差分隐私k-means聚类

# 通过私有进化改进的差分隐私k-means聚类
来源：https://arxiv.org/html/2606.00342
###### 摘要

我们研究了欧几里得空间中差分隐私 \(DP\) \k\-均值聚类问题。以往的解法则依赖于直接对私有数据求和，这会导致敏感度与数据域成比例。我们引入 PE-means，将私有进化 \(PE\) 算法（一种日益流行的合成数据生成方法）扩展到 \k\-均值聚类问题。PE 的关键优势在于它只计算一个敏感度恒定的私有直方图来指导进化过程。我们对 PE 的适配包括用于聚类的新型进化算子，以及其他具有独立意义的算法改进。总体而言，PE-means 在聚类损失上比最先进的基线平均改善了 20%。

## I. 引言

\k\-均值聚类算法是数据科学中的基础工具，在推荐系统和医疗健康数据分析等许多有影响力的应用中发挥着重要作用 [25 (https://arxiv.org/html/2606.00342#bib.bib20),16 (https://arxiv.org/html/2606.00342#bib.bib32)]。其目标是将数据划分为 \k 组具有相似特征的群组，从而使实践者能够理解复杂数据集。挑战在于，将标准 \k\-均值算法应用于敏感数据会危及数据集中参与者的隐私。在最坏的情况下，\k\-均值算法会发布数据集中离群个体的精确数据记录。为了解决这个问题，大量研究工作考虑了差分隐私 \k\-均值问题 [31 (https://arxiv.org/html/2606.00342#bib.bib5),5 (https://arxiv.org/html/2606.00342#bib.bib9),4 (https://arxiv.org/html/2606.00342#bib.bib6),3 (https://arxiv.org/html/2606.00342#bib.bib19),1 (https://arxiv.org/html/2606.00342#bib.bib7),30 (https://arxiv.org/html/2606.00342#bib.bib27),25 (https://arxiv.org/html/2606.00342#bib.bib20),12 (https://arxiv.org/html/2606.00342#bib.bib24),15 (https://arxiv.org/html/2606.00342#bib.bib28)]。差分隐私 \(DP\) 是一种流行的隐私定义，它确保单个用户输入的变化不会对机制的输出产生显著影响 [9 (https://arxiv.org/html/2606.00342#bib.bib13)]。通过在聚类过程中加入校准的随机化，现有方法在提供正式隐私保障的同时，保留了 \k\-均值聚类的好处。

DP 的挑战在于平衡隐私与效用之间的固有权衡。现有的最先进 DP \k\-均值方法依赖于在某个过程中直接对私有数据求和 [4 (https://arxiv.org/html/2606.00342#bib.bib6),31 (https://arxiv.org/html/2606.00342#bib.bib5),1 (https://arxiv.org/html/2606.00342#bib.bib7)]。求和查询的敏感度（即任何单个用户能产生的最大影响）是添加（或移除）某个位于域边界上的点。这意味着，为了满足 DP，必须添加与整个域成比例的噪声，这会严重降低聚类质量。在最近的工作中，一种名为 FastLloyd 的方法通过相对聚类更新，成功将这种敏感度从整个域降低到每个聚类周围的较小半径 [5 (https://arxiv.org/html/2606.00342#bib.bib9)]。然而，该半径仍然与数据维度成比例，且 FastLloyd 由于相对更新而引入了额外的误差项。

私有进化 \(PE\) 是一种日益流行的技术，用于生成各种模态的合成数据 [22 (https://arxiv.org/html/2606.00342#bib.bib2),32 (https://arxiv.org/html/2606.00342#bib.bib3),21 (https://arxiv.org/html/2606.00342#bib.bib4)]。PE 仅通过对基础模型进行推理 API 调用来进化合成数据种群，这些模型在进化算法中生成并扰动数据。PE 成功的一个关键组成部分是，它仅在最近邻投票方案中使用私有数据，以选择迄今为止生成的最佳样本。具体来说，每个私有数据点在每次迭代中仅贡献一票。因此，添加或移除任何私有数据点只会对输出产生 1 的恒定敏感度，无论数据域如何。这使 PE 相对于基于梯度的技术具有显著优势，后者必须添加与梯度域成比例的噪声。真正令人印象深刻的是，尽管 PE 从私有数据中获得的信号要少得多，但它通过利用进化的鲁棒优化特性，仍然能有效地遍历大型复杂的数据域。

在这项工作中，我们将 PE 框架扩展至 \k\-均值聚类问题，提出了 PE-means。在此应用中，PE 的种群包含随机生成的质心，这些质心通过迭代进化逐渐逼近私有数据的质心。我们的设计用轻量级聚类初始化方法和基于莱维飞行的变异算子替换了 PE 对基础模型的 API 调用。除了将 PE 适配到聚类问题外，我们还对算法进行了几项具有独立意义的改进。具体来说，我们解决了 PE 选择技术中的一个关键问题：当投票分散在最佳候选者之间时，可能导致特定区域没有代表被选中。我们还通过更好地后处理投票直方图，以及在隐私成本不变的情况下提供自适应调整信噪比的机制，来减少 DP 噪声的影响。我们的实验评估表明，PE-means 在多个真实和合成数据集上优于最先进的基线。此外，我们提出了 HDPE-means，这是 PE-means 的一个变体，采用了与 Balcan 等人 [1 (https://arxiv.org/html/2606.00342#bib.bib7)] 类似的降维方法，使 PE-means 能够扩展到更高维度。总体而言，我们在聚类损失上观察到比最先进方法高达 91% 的提升，在所有评估的数据集上平均提升了 20%。

## II. 背景

### II-A \k\-均值聚类

给定一个大小为 \(N\)、维度为 \(d\) 的数据集 \(D\)，\k\-均值问题的目标是将数据集划分为 \(k\) 个组（聚类）\(C = \{C_1, \dots, C_k\}\)，每个 \(C_i \subset D\)，使得以下目标函数最小化：

\[
\arg\min_{C} \sum_{i=1}^k \sum_{x \in C_i} \|x - \mu_i\|^2 \tag{1}
\]

其中 \(\mu_i\) 是聚类 \(i\) 的质心（\(\mu_i = \frac{1}{|C_i|} \sum_{x \in C_i} x\)）。在这项工作中，我们假设数据集的大小和维度是公开信息，但要求从数据集中发布的任何其他信息都满足差分隐私。

### II-B 差分隐私

差分隐私 \(DP\)[9 (https://arxiv.org/html/2606.00342#bib.bib13)] 通过向聚合统计量计算中添加随机性来保护个体的隐私。DP 保证，无论是否有任何用户参与，算法的输出都大致相同。更正式地，差分隐私可以定义如下。

###### 定义 II.1（差分隐私）
一个随机化算法 \(\mathcal{M} : \mathcal{D} \mapsto \mathbb{R}\) 是 \((\epsilon, \delta)\)-DP 的，如果对于任意一对相邻数据集 \(D, D' \in \mathcal{D}\) 以及任意 \(S \subseteq \mathbb{R}\)，有
\[
\Pr[\mathcal{M}(D) \in S] \leq e^{\epsilon} \Pr[\mathcal{M}(D') \in S] + \delta. \tag{2}
\]

隐私参数 \(\epsilon\) 定义了输出分布必须有多相似，而 \(\delta\) 允许定义中存在很小的失败概率。我们使用无界相邻定义，其中数据集相邻当且仅当 \(|D \backslash D' \cup D' \backslash D| = 1\)（即允许添加或移除单个数据点）。由于后处理引理[10 (https://arxiv.org/html/2606.00342#bib.bib14)]，对 DP 机制的输出执行任意计算不会影响隐私。最后，DP 可以自然地与机制的多次运行进行组合。如果我们顺序应用差分隐私机制，隐私参数可以通过求和或更高级的方法组合 [10 (https://arxiv.org/html/2606.00342#bib.bib14)]。

###### 定义 II.2（敏感度）
设 \(f: \mathcal{D} \mapsto \mathbb{R}^k\)。如果 \(\mathbb{D}\) 是 \(\mathbb{R}^k\) 元素间的一种距离度量，那么 \(f\) 的 \(\mathbb{D}\)-敏感度为
\[
\Delta^{(f)} = \max_{(D, D')} \, \mathbb{D}(f(D), f(D')), \tag{3}
\]
其中 \((D, D')\) 是相邻数据集对。

我们主要使用 \(\ell_2\) 范数作为距离度量 \(\mathbb{D}\)。为了满足 DP，我们在工作中使用高斯噪声，并使用高斯差分隐私 \(GDP\)[6 (https://arxiv.org/html/2606.00342#bib.bib17)] 进行分析。

###### 定义 II.3（GDP [6 (https://arxiv.org/html/2606.00342#bib.bib17)]）
一个机制 \(\mathcal{M}\) 被称为满足 \(\theta\)-高斯差分隐私 (\(\theta\)-GDP)，如果它是 \(G_\theta\)-DP 的。即，对于所有相邻数据集 \(D\) 和 \(D'\)，
\[
\mathcal{T}\big(\mathcal{M}(D), \mathcal{M}(D')\big) \geq G_\theta,
\]
其中 \(\mathcal{T}\) 是一个权衡函数，用来衡量攻击者识别单个数据点存在的难度，而 \(G_\theta = \mathcal{T}\big(\mathcal{N}(0,1), \mathcal{N}(\theta,1)\big)\)（关于定义的具体内容，参见 Dong 等人 [6 (https://arxiv.org/html/2606.00342#bib.bib17)]）。

自然地，高斯机制满足 GDP。

###### 定理 II.1
（高斯机制 GDP [6 (https://arxiv.org/html/2606.00342#bib.bib17)]）定义作用于统计量 \(f\) 的高斯机制为 \(\mathcal{M}(D) = f(D) + \eta\)，其中 \(\eta \sim \mathcal{N}(0, \Delta^{(f)} / \theta)\)。那么，\(\mathcal{M}\) 是 \(\theta\)-GDP 的。

我们考虑 GDP 在机制多次运行下的组合。

###### 定理 II.2（GDP 组合 [6 (https://arxiv.org/html/2606.00342#bib.bib17)]）
\(n\) 个 \(\theta_i\)-GDP 机制的重叠组合是 \(\sqrt{\theta_1^2 + \cdots + \theta_n^2}\)-GDP 的。

我们还有一种在 GDP 和 DP 之间进行转换的方法。

###### 定理 II.3（GDP 到 DP [6 (https://arxiv.org/html/2606.00342#bib.bib17),2 (https://arxiv.org/html/2606.00342#bib.bib18)]）
一个机制是 \(\theta\)-GDP 的当且仅当对于所有 \(\epsilon \geq 0\)，它是 \((\epsilon, \delta(\epsilon))\)-DP 的，其中
\[
\delta(\epsilon) = \Phi\Big(-\frac{\epsilon}{\theta} + \frac{\theta}{2}\Big) - e^{\epsilon} \Phi\Big(-\frac{\epsilon}{\theta} - \frac{\theta}{2}\Big).
\]

在实践中，我们使用 Balle 和 Wang 推导的算法来求解该函数以得到 \(\theta\) [2 (https://arxiv.org/html/2606.00342#bib.bib18), 算法 1]。

## III. 方法论

算法 1 PE-means：基于私有进化 \(PE\)[22 (https://arxiv.org/html/2606.00342#bib.bib2)]
1: **输入**: 私有样本: \(D = \{x_i\}_{i=1}^N \subset \mathbb{R}^d\); 迭代次数: \(T\); 生成样本数: \(N_{\mathrm{syn}} = k\); 变异数: \(L\); DP 最近邻直方图的噪声乘数: \(\sigma\)
2: **输出**: DP 聚类中心 \(S'_T = \{\mu_1, \dots, \mu_k\} \subset \mathbb{R}^d\)
3:
4: \(S_0 \leftarrow\) RANDOM_API(\(N_{\mathrm{syn}} * L\))
5: **for** \(t = 1, \dots, T\) **do**
6:     \(hist_t \leftarrow\) DP_NN_HISTOGRAM(\(D, S_{t-1}, \sigma\))  ▷ 参见算法 2 (https://arxiv.org/html/2606.00342#alg2)
7:     \(P_t \leftarrow hist_t / \mathrm{sum}(hist_t)\)  ▷ \(P_t\) 是 \(S_{t-1}\) 上的分布
8:     \(S'_t \leftarrow\) 根据 \(P_t\) 对样本排序，并从 \(S_{t-1}\) 中抽取 \(N_{\mathrm{syn}}\) 个样本
9:     \(S'_t \leftarrow\) WEIGHTED_K_MEANS(\(S_{t-1}, k = N_{\mathrm{syn}},\) 权重 = \(hist_t\))  ▷ 返回质心
10:    \(S_t \leftarrow S'_t\)  ▷ 保存最佳样本
11:    **如果** \(\mathrm{sum}(hist_t^2) / (N \sigma^2) < 1.0\) **则**
12:        \(L \leftarrow L / 2\)
13:    **结束如果**
14:    **对于** \(i = 1, \dots, L\) **执行**
15:        \(S_t \leftarrow S_t \cup\) VARIATION_API(\(S'_t\))
16:    **结束对**
17: **结束对**
18: **返回** \(S'_T\)

私有进化 \(PE\) 是一种新兴的私有合成数据生成技术，它仅通过对大型机器学习模型进行推理 API 调用来进化一组合成样本 [22 (https://arxiv.org/html/2606.00342#bib.bib2),32 (https://arxiv.org/html/2606.00342#bib.bib3),21 (https://arxiv.org/html/2606.00342#bib.bib4)]。在高层面上，PE 从随机生成的合成数据（使用 RANDOM_API）开始，通过创建新的变体（使用 VARIATION_API）并对最接近私有数据的合成数据进行排名，迭代地进化到高质量的合成数据。我们建立在 PE 的文本变体 Aug-PE [32 (https://arxiv.org/html/2606.00342#bib.bib3)] 的基础上。在算法 1 (https://arxiv.org/html/2606.00342#alg1) 中，我们概述了 PE 的基线版本。算法 1 (https://arxiv.org/html/2606.00342#alg1) 也展示了我们的方法 PE-means，突出显示了我们为改进 PE 并将其适配到解决 \k\-均值聚类问题所做的修改。

### III-A 随机 API

PE 的第一步是独立于私有数据，使用 RANDOM_API 生成初始种群（算法 1 (https://arxiv.org/html/2606.00342#alg1) 第 4 行）。在 PE 的先前变体中，这是通过查询预训练的基础模型（使用标签等信息，通常假定为公开）来完成的。为了解决聚类问题，我们不创建合成数据样本的种群，而是创建一组要进化的质心。我们假设可用于生成初始种群的唯一上下文是数据域的形状。为简单起见，我们假设域是一个超球面，并使用与其他方法对其半径 \(R\) 施加相同 \(\ell_2\) 边界的方式来约束敏感度 [31 (https://arxiv.org/html/2606.00342#bib.bib5),4 (https://arxiv.org/html/2606.00342#bib.bib6),1 (https://arxiv.org/html/2606.00342#bib.bib7),5 (https://arxiv.org/html/2606.00342#bib.bib9)]。然而，在我们的情况下，边界过紧或过松最多只会影响收敛速度，而不会影响添加噪声的量。一个简单的用于聚类的 RANDOM_API 会在超球面内生成均匀随机数据。但是，随机点可能聚集在一起，这会减少我们对域的覆盖。因此，我们转而采用 Su 等人 [31 (https://arxiv.org/html/2606.00342#bib.bib5)] 的方法，使用球面填充法。Su 等人的方法从一个给定的半径 \(a\)（通常是域半径的一半）开始，然后迭代地添加随机样本，这些样本距离边界至少为 \(a\)，并且距离已添加的样本至少为 \(2a\)。如果在固定次数的重试后，无法找到满足这些条件的随机样本，则 \(a\) 减半，算法继续，直到找到 \(k\) 个样本。我们调整 Su 等人的算法，考虑 \(\ell_2\) 有界的超球面，而不是 \(\ell_\infty\) 有界的超立方体。