差分隐私 $k$- 均值聚类

Apr, 2015

Differentially Private $k$-Means Clustering

Dong Su, Jianneng Cao, Ninghui Li, Elisa Bertino, Hongxia Jin

TL;DR本研究比较交互式和非交互式方法在差分隐私数据分析中的权衡，并提出了一种混合方法。通过 $k$-means 聚类作为一个例子，该方法首先使用非交互式机制发布数据集的摘要，然后使用标准 $k$-means 聚类算法学习聚类中心，最后使用交互式方法来进一步改进这些聚类中心。我们分析了交互式和非交互式方法的误差行为，并使用这种分析来决定如何分配隐私预算，大量实验结果支持我们的分析，并证明我们方法的有效性。

Abstract

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 approa

differential privacy interactive approach non-interactive approach hybrid approach $k$-means clustering

发现论文，激发创造

易实例的不同 ially-Private 聚类

本文研究的是隐私保护聚类算法，提出了一个依据难易程度来组合本来不带保护性质的聚类算法和隐私保护结果的框架，并在高斯混合数据和 $k$-means 算法中实现了样本复杂度较小的聚类效果进行了实证评估。

Dec, 2021

数据流中的差分隐私聚类

论文提出了不同隐私性水平的 k-means 和 k-median 流式聚类算法，采用核心集算法作为黑盒子并使用多项式空间达到恒定乘性错误和多项式加性错误。

Jul, 2023

具有稳定性假设的差分隐私聚类算法

本文研究了在输入稳定性假设下的差分隐私聚类问题，提出了一种简单的算法，分析了其在 Wasserstein 距离和 k-means 代价等方面的效用，可直接应用于 “好” 的 k - 中位数实例和本地模型的差分隐私。

Jun, 2021

基于分层分离树的可扩展差分隐私聚类

通过利用树嵌入和标准的降维技术，我们提出了一种高效易实现的算法，能够解决 $k$- 中位数和 $k$- 均值的私有聚类问题，具有很好的时间和空间复杂度，适用于大规模分布式计算环境，并有可观的隐私保障.

Jun, 2022

FastLloyd: 基于差分隐私的联邦式、准确、安全、可调整的 $k$-Means 聚类

在水平联邦环境中，我们研究了隐私保护的 k-means 聚类问题，并通过综合差分隐私和安全计算的方法提出了一个更快速、更加隐私安全和更准确的设计。

May, 2024

本地隐私 k-Means 聚类

该研究设计了一种新的算法，用于处理欧几里得 k - 均值问题的差分隐私，通过本地模型，可以大幅降低加性误差，同时保持乘性误差不变。

Jul, 2019

具有差分隐私的对比可解释聚类

本研究提出了一种新的可解释人工智能（XAI）方法，在聚类方法中将对比解释与差分隐私相结合。通过在常见的聚类问题中（包括 k - 中值和 k - 均值），我们给出了高效的差分隐私对比解释，能够获得与非差分隐私聚类解释基本一致的解释。在每个对比场景中，我们将一个特定数据点指定为固定的质心位置，以衡量这种约束对基于差分隐私的聚类结果的影响。在各种数据集上进行的广泛实验表明我们方法在不明显损害数据隐私或聚类效果的情况下提供有意义的解释，突出了我们对隐私感知机器学习的贡献，证明了在聚类任务解释中在隐私和效用之间实现平衡的可行性。

Jun, 2024

差分隐私聚类：紧密逼近比率

本论文研究了不同 ially private clustering 任务，为 Euclidean DensestBall、1-Cluster、k-means 和 k-median 等基本聚类问题提供了有效的差分隐私算法，同时只产生小的附加误差，从而实现了与任何非私有算法可以获得的近似比例基本相同的近似比例。这改进了现有的仅实现某些大常数逼近因子的有效算法。我们的结果还暗示了改进的 Sample and Aggregate 隐私框架算法。此外，我们展示了在适度的维数下，可以利用我们的 1-Cluster 算法中使用的工具来获得更快的 ClosestPair 量子算法。

Aug, 2020

连续观察下的聚类差分隐私

我们考虑在 $ R^d $ 中进行隐私数据集聚类的问题

Jul, 2023

一轮局部隐私 k 均值

本文提出了一种算法，用于在差分隐私（DP）的一轮（也称非交互式）本地模型中进行 k 均值聚类，该算法实现的逼近比接近于最佳非私有逼近算法，改进了以前已知的仅保证大（常数）逼近比率的算法。此外，这是第一个仅需要一轮本地 DP 模型通信的 k 均值常数逼近算法，积极地解决了 Stemmer（SODA 2020）提出的一个开放性问题。我们的算法框架非常灵活；我们通过展示在（一轮）洗牌 DP 模型中也会产生类似于最优解的逼近算法来证明这一点。

Apr, 2021