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

Jun, 2022

改进版的 q-means 量子算法和 dequantized 算法，分别以 O ((k^2)/(ε^2)(√k*d + log (Nd))) 和 O ((k^2)/(ε^2)(kd + log (Nd))) 的时间复杂度在近似 k-means 聚类中取得优化，其中 k 代表簇数量，ε 代表误差率，N 代表向量数量，d 代表向量维度。

Aug, 2023

针对度量空间中的经典设施定位、$k$- 中位数和 $k$- 均值问题，我们提供了近线性时间的逼近方案，并展示了针对各种变型问题的技术扩展。

Dec, 2018

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

Oct, 2023

在无监督学习的背景下，Lloyd 算法是最常用的聚类算法之一。本研究证明了在合适的初始化和小扰动的条件下，Lloyd 算法在从次高斯混合中扰动的样本上的误聚类率也在 O (log (n)) 次迭代后呈指数级下降的边界。

Sep, 2023

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

Jun, 2021

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

Jul, 2021

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

Feb, 2020

我们提出了一种新颖的加速精确 k-means 算法，在 18 个实验中比现有低维算法更优秀，速度快了最多三倍。 我们还通过更好地估计用于减少距离计算次数的距离界限，对现有最先进的加速精确 k-means 算法进行了总体改进，在 44 个实验中实现了速度提升，最高达到 1.8 倍。最后，我们提出了标准方法的简化版本，并表明它们在 59 个实验中比其全面版本更快。

Feb, 2016

本文研究了 Ward 方法在分层 k 均值问题中的应用，通过对完全链接的算法进行分析，发现当最优 k 聚类具有良好分离性时，Ward 方法可以计算出 k - 均值目标函数的 2 - 近似解，并证明了当最优聚类满足平衡条件时，Ward 方法完全恢复最优解，并且我们证明了一维数据集的 Ward 聚类可以实现 O (1) 的近似解。

Jul, 2019