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

Jul, 2023

本文提出了一种使用决策树对数据集进行聚类的算法，并探讨了该方法对 k-means 和 k-medians 目标函数的适用性。作者证明了常见的自顶向下决策树算法可能会导致成本任意大的聚类结果，但设计了一种有效的方法使用具有 k 个叶子的树生成可解释的聚类，并对于两个中心点的情况，仅需要一个阈值切割即可实现常数近似。

Feb, 2020

研究在可解释的 k - 中位数和 k - 均值问题中，提出了一种新的算法并分析了其竞争性和下界。

Jul, 2021

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

Jul, 2019

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

Aug, 2020

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

Apr, 2015

非监督学习中的聚类是一个基础问题，本研究介绍了一种简单的随机聚类算法，它在任意 k 下的期望运行时间为 O (nnz (X) + nlogn)，并在 K-means 目标函数上实现了近似比例约为 O (k^4) 的算法，通过实验证明与现有方法相比，我们的聚类算法在运行时间和聚类质量之间有一个新的权衡。

Oct, 2023

提出了一个算法，用于在 $k$-medians 目标和 $k$-means 目标下输出可解释的聚类，与最佳聚类最多相差 $O (\log^2 k)$ 和 $O (k\log^2 k)$ 的因子，算法时间为 $O (dk\log^2 k)$ 。

Jun, 2021

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

Jul, 2023

介绍了一种可解释性聚类方法，算法通过应用决策树将数据划分为轴平行超平面聚类，使得聚类边界简单，同时保证聚类代价函数的可解释性约束，聚类的代价至多是比不考虑可解释性约束的情况最小代价增加 $k^{1-2/d}$ 倍，与其他方法的代价上界取最小值可得到 $k^{1-2/d} polylog (k)$ 倍，此为 $k,d ≥ 2$ 下的最优代价上界。

Jun, 2021