Mar, 2012

可扩展的 K-Means++

PDF
TL;DR本研究展示了一种通过在并行计算中显著减少所需传递次数的方法，从而获得好的初始化的 K-means|| 初始化算法，并通过实验评估证明该算法在顺序和并行设置下均优于 K-means ++。
发现论文，激发创造
  • K-Means 聚类算法高效初始化方法的比较研究

    本研究探讨了 K-means 算法及其初始化方法在聚类方面的应用，比较了 8 种常用线性时间复杂度的初始化方法，并使用各种性能指标对各种数据集进行了测试和分析， 结论表明，当前通用的初始化方法表现不佳，并且有更好的替代方案。

    Sep, 2012

  • K-Means++ 和 K-Means|| 的精确加速

    通过考虑在种子选择中执行修剪的有限机会，我们开发了专门的三角不等式修剪策略和动态优先队列，展示了 K-Means ++ 和 K-Means $\ | $ 的第一个加速，它在运行时间更快而算法上是等效的，通过对已知技术进行简单但精心选择的修改，我们能够将距离计算减少超过 500 倍。

    May, 2021

  • K-Means 算法并行化及应用于大数据聚类

    K-Means 聚类使用 LLoyd 算法是一种迭代方法，将给定数据集分成 K 个不同的簇；本文将比较并分析两种不同的方法，一种是基于 OpenMP 的平坦同步方法，另一种是基于 GPU 的并行化方法，通过比较结果测量性能改进。

    May, 2024

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

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

    Sep, 2023

  • 可扩展核聚类：近似核 k-means

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

    Feb, 2014

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

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

    Oct, 2023

  • 多交换 $k$-Means++

    通过考虑更大和更复杂的局部搜索邻域，我们的算法实现了 9 + ε 的逼近比，这是局部搜索的最佳可能性，并且在几个数据集上显著改进了 Lattanzi 和 Sohler（ICML 2019）的方法。

    Sep, 2023

  • k-variates++: k-means++ 中的更多优点

    本文提出了 k - 变量 ++ 聚类算法，它具有包括一般密度的采样和 Arthur-Vassilvitsky 近似保证的新特性，可用于分布式、流式和在线聚类，也可以应用于差分隐私。经过对多个领域和设置的实验评估，我们的算法可与现有技术相媲美。

    Feb, 2016

  • 针对大数据的 K-means 优化：一项比较研究

    本文比较分析了大数据背景下 K-means 算法的不同优化技术。通过并行化、逼近和采样方法等不同方法，探讨了克服大数据规模问题的不同途径。通过使用不同基准数据集评估了这些技术的性能，并根据 LIMA 支配准则在速度、聚类质量和可扩展性方面进行比较。结果表明，不同的技术适用于不同类型的数据集，并提供了关于 K-means 大数据聚类中速度和准确性之间权衡的见解。总体而言，本文为从业者和研究人员提供了如何优化大数据应用中的 K-means 的全面指南。

    Oct, 2023

  • 一个在线 K-Means 聚类算法

    在线聚类算法实现了与 k 均值算法相同的聚类效果，其算法复杂度显著低于 k-means++。

    Dec, 2014