Sep, 2023

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

PDF
TL;DR对 $k$-means 算法进行改进，使其对异常值更加鲁棒，同时具备 $O (1)$ 的近似保证，且可在线性时间内输出精确的 $k$ 个聚类中心。
$k$-meansoutliersapproximation guaranteeclusteringalgorithm
发现论文，激发创造
  • 关于 $k$-means 聚类中 $D^α$ 种子的分析

    研究论文通过对聚类算法和 $D^\alpha$ 种子算法的应用，证明了使用 $D^\alpha$ 种子算法在 $k$-means 目标函数方面具有更好的性能，并通过实验证实了这种优势即使在种子算法之后使用 Lloyd's 算法时依然存在。

    Oct, 2023

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

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

    Feb, 2016

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

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

    Oct, 2023

  • 非球形混合物的异常值鲁棒聚类

    本研究提出了一种新的检测离群值的高效算法，用于聚类混合的高斯模型，这种方法是鲁棒的，可以处理在数据中有少部分的失真或错误，它依赖于 TV 距离和方差有限度等假定条件，并使用极小化两种偏差的方法来修复度量误差和离群值异常。

    May, 2020

  • 分布式聚类与异常检测的实用算法

    本文提出了一种基于简要构建的数据摘要的分布式无监督学习算法，对异常点的全局识别有很好的近似保证，并在真实和人工数据上超过了所有基线算法。

    May, 2018

  • 可扩展的 K-Means++

    本研究展示了一种通过在并行计算中显著减少所需传递次数的方法，从而获得好的初始化的 K-means|| 初始化算法，并通过实验评估证明该算法在顺序和并行设置下均优于 K-means ++。

    Mar, 2012

  • 多交换 $k$-Means++

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

    Sep, 2023

  • 带有大量噪音数据的分布式 k - 聚类

    在分布式环境中，对 $k$-center/median/means 聚类与 outliers 问题 (或 $(k, z)$-center/median/means 问题) 进行研究，提出了一种改进算法，能够更好地解决 communication costs 线性依赖于 outliers 数量的问题。

    Oct, 2018

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

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

    May, 2021

  • 通过迭代取整实现 $k$- 中位数和 $k$- 均值异常值的常数近似

    本论文介绍了一个新的迭代舍入框架并用于许多聚类问题的近似算法，该算法可以大幅改善现有算法的近似比，并且通过前处理程序将几乎积分解转换为完全积分解。

    Nov, 2017