Oct, 2023

一维投影聚类的简单、可扩展和有效方法

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

    该论文研究了使用降维技术来提高 $k$-means 聚类算法的效率和精度，通过使用随机矩阵对多维数据进行投影，并经过大量实验验证了该方法的准确性。

    Nov, 2010

  • k-Means 聚类和低秩逼近的降维

    研究采用缩略图替代数据矩阵来加速 k - 均值聚类和约束 k - 秩近似问题的精确、近似或启发式算法，并提供降维和草图技术及近似算法来解决这些普遍问题。

    Oct, 2014

  • 你知道什么是 q-means 吗？

    改进版的 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-means

    本文提出了一种基于随机化的近似核 K-means 簇算法，其利用采样点与数据集中所有点之间的核相似性来近似聚类中心，实现了与传统低秩核近似聚类方案相比更好的聚类性能、更短的运行时间和更小的内存需求，最后利用集成聚类技术进一步提高算法性能。

    Feb, 2014

  • 改进的异常值鲁棒的 k 均值种子

    对 $k$-means 算法进行改进，使其对异常值更加鲁棒，同时具备 $O (1)$ 的近似保证，且可在线性时间内输出精确的 $k$ 个聚类中心。

    Sep, 2023

  • 关于投影聚类的泛化界限

    给定一组点，聚类是找到一个点集合的分区，使分配给一个点的中心尽可能接近。对于中心为点的目标，我们显示了一个收敛速度为 O (sqrt (k/n)) 的收敛界限。对于中心为 j 维子空间的子空间聚类，我们显示了一个收敛速度为 O (sqrt ((kj^2)/n)) 的收敛界限。对于广义 $k$-means 的投影聚类特例，我们证明了一个收敛速度为 Omega (sqrt ((kj)/n)) 的必要界限。

    Oct, 2023

  • k-means 在平面上甚至需要指数次迭代

    证明了 k-means 算法存在关于维数的指数下界，并以平面上的简单构造为例给出了指数下界的证明。

    Dec, 2008

  • Johnson-Lindenstrauss 变换在 k-Means 和 k-Medians 聚类中的表现

    通过投影到随机的 O (log (k/ ε) / ε²) 维子空间上，可以近似保持欧几里得 k-means 或 k-medians 聚类的最优解成本，并且适用于任何满足温和的子高斯尾条件的维度缩减映射，其维数几乎是最优的。此外，该结果适用于所有权重的欧几里得 k - 聚类。

    Nov, 2018

  • 高维情况下近似最优的可解释 k 均值算法

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

    Jun, 2021

  • 带谱范数和 k-means 算法的聚类

    该论文证明了一个简单的聚类算法可以在不假设任何生成模型的情况下运作，只需要假定一种叫做 “接近条件” 的规律。该算法依赖于著名的 k-means 算法，能够产生大多数现有生成模型的结果，同时提出了一种新的技术来提高间距与标准差之比。

    Apr, 2010