本文研究的是隐私保护聚类算法,提出了一个依据难易程度来组合本来不带保护性质的聚类算法和隐私保护结果的框架,并在高斯混合数据和 $k$-means 算法中实现了样本复杂度较小的聚类效果进行了实证评估。
Dec, 2021
本论文研究了不同 ially private clustering 任务,为 Euclidean DensestBall、1-Cluster、k-means 和 k-median 等基本聚类问题提供了有效的差分隐私算法,同时只产生小的附加误差,从而实现了与任何非私有算法可以获得的近似比例基本相同的近似比例。这改进了现有的仅实现某些大常数逼近因子的有效算法。我们的结果还暗示了改进的 Sample and Aggregate 隐私框架算法。此外,我们展示了在适度的维数下,可以利用我们的 1-Cluster 算法中使用的工具来获得更快的 ClosestPair 量子算法。
Aug, 2020
20 年前的算法经过轻微修改,适用于各种隐私模型,匹配几乎所有已知结果,改进了一些结果并扩展到新的隐私模型,即连续观测环境。
Jun, 2024
使用差分隐私的新算法定位少数点的集群,并可用于私人数据探索、聚类和去除异常值,同时大大放宽了样本和聚合技术的需求,可将非私有的分析编译为保护差分隐私的分析。
Apr, 2016
本研究比较交互式和非交互式方法在差分隐私数据分析中的权衡,并提出了一种混合方法。通过 $k$-means 聚类作为一个例子,该方法首先使用非交互式机制发布数据集的摘要,然后使用标准 $k$-means 聚类算法学习聚类中心,最后使用交互式方法来进一步改进这些聚类中心。我们分析了交互式和非交互式方法的误差行为,并使用这种分析来决定如何分配隐私预算,大量实验结果支持我们的分析,并证明我们方法的有效性。
Apr, 2015
在水平联邦环境中,我们研究了隐私保护的 k-means 聚类问题,并通过综合差分隐私和安全计算的方法提出了一个更快速、更加隐私安全和更准确的设计。
May, 2024
本文提出了一种针对图中任意形状节点簇的差分隐私聚类算法,该算法仅使用在权重差分隐私约束下释放的近似最小生成树作为输入,并通过最优剪切方法从中成功恢复底层的非凸聚类分区。与现有方法不同,我们的算法在理论上得到了很好的支持,并且实验证实了我们的理论发现。
Mar, 2018
论文提出了不同隐私性水平的 k-means 和 k-median 流式聚类算法,采用核心集算法作为黑盒子并使用多项式空间达到恒定乘性错误和多项式加性错误。
Jul, 2023
本文研究在实际应用中,哪些加性扰动稳定性的实例可以设计有效算法,并证明它们能找到最优聚类。我们提出了一种稳定性定义,并设计了算法以证明稳定实例的最优聚类。当实例具有一定的分离性时,我们显示出一种具有证明保证的鲁棒算法,也能容忍异常值。通过研究真实数据集的稳定性,我们补充了这些结果,并展示了我们的算法在这些基准数据集上的表现。
Dec, 2017
我们考虑在 $ R^d $ 中进行隐私数据集聚类的问题