Apr, 2016

隐私定位小的聚类簇

PDF
TL;DR使用差分隐私的新算法定位少数点的集群，并可用于私人数据探索、聚类和去除异常值，同时大大放宽了样本和聚合技术的需求，可将非私有的分析编译为保护差分隐私的分析。
发现论文，激发创造
  • 使旧事焕新：差分隐私聚类的统一算法

    20 年前的算法经过轻微修改，适用于各种隐私模型，匹配几乎所有已知结果，改进了一些结果并扩展到新的隐私模型，即连续观测环境。

    Jun, 2024

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

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

    Aug, 2020

  • 易实例的不同 ially-Private 聚类

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

    Dec, 2021

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

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

    Jul, 2023

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

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

    Jun, 2021

  • 集中式和本地式模型的聚类算法

    该研究提出了关于最小囊括圆问题的差分隐私算法，达到了在中心模型和本地模型下不错的精度，并演示了如何在这两个模型中使用该算法来近似 $k$-means。

    Jul, 2017

  • 差分隐私主成分的近似最优算法

    本文探讨了不同 ially private PCA 方法的理论和实证性能，并提出了一种明确优化输出效用的新方法。我们发现其样本复杂度与现有程序的不同之处在于其与数据维度的缩放，而且在实际数据中，该方法与现有方法相比具有较大的性能差距。

    Jul, 2012

  • DPM：通过分离对敏感数据进行聚类

    通过优化数据集的分割器，以差分隐私方式搜索准确的数据点分隔符的差分隐私聚类算法 DPM 在聚类度量不变性方面取得了显著的改善。

    Jul, 2023

  • 具有差分隐私的因果推断（聚类）结果

    基于随机实验估计因果效应只有在参与者同意透露潜在敏感回应的情况下才可行。我们提出了一种新的差分隐私机制 “Cluster-DP”，通过利用数据的任何给定的聚类结构来实现更强的隐私保证和更低的方差损失，同时仍然允许因果效应的估计。

    Aug, 2023

  • 一轮局部隐私 k 均值

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

    Apr, 2021