易实例的不同 ially-Private 聚类

ICMLDec, 2021

Differentially-Private Clustering of Easy Instances

Edith Cohen, Haim Kaplan, Yishay Mansour, Uri Stemmer, Eliad Tsfadia

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

Abstract

Clustering is a fundamental problem in data analysis. In differentially private clustering, the goal is to identify $k$ cluster centers without disclosing information on individual data points. Despite significant research progress, the problem had so far resisted practical solutions. In this work we aim at providing simple implementable →

differentially private clustering $k$-means sample complexity bounds gaussian mixtures empirical evaluation

发现论文，激发创造

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

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

Aug, 2020

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

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

Apr, 2015

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

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

Jun, 2021

通过动态处理提高差分隐私聚类效用

通过使用 Morse 理论，构建子高斯簇将复杂簇分布与不同隐私保护保持一定的性能平衡，由于差分隐私子簇是通过现有方法进行获得的，所以所提出的方法几乎不存在额外的隐私损失。实验结果表明，在相同的隐私级别下，我们的方法能够实现更好的聚类性能。

Apr, 2023

隐私定位小的聚类簇

使用差分隐私的新算法定位少数点的集群，并可用于私人数据探索、聚类和去除异常值，同时大大放宽了样本和聚合技术的需求，可将非私有的分析编译为保护差分隐私的分析。

Apr, 2016

使旧事焕新：差分隐私聚类的统一算法

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

Jun, 2024

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

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

Aug, 2023

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

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

Jul, 2023

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

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

Jul, 2023

数据易于 (对于 K-Means)

该论文研究了 $k$-means 算法的能力，正确地恢复互相分离的簇群。基于常见的簇群定义，考虑了簇内同质性和簇间多样性的要求，并找到了一种特殊情况的互相分离簇群，使得 $k$-means 的代价函数全局最小值与互相分离性一致。通过实验发现各种 $k$-means 品牌实际上无法发现互相分离的簇群，因此提出了一种新的算法，通过重复子抽样选择种子的方式，对 $k$-means++ 进行变体改进，并在任务中胜过 $k$-means 系列中的其他四种算法。

Aug, 2023