NIPSDec, 2017

欧几里得 k-means 的稳定实例聚类

PDF
TL;DR本文研究在实际应用中，哪些加性扰动稳定性的实例可以设计有效算法，并证明它们能找到最优聚类。我们提出了一种稳定性定义，并设计了算法以证明稳定实例的最优聚类。当实例具有一定的分离性时，我们显示出一种具有证明保证的鲁棒算法，也能容忍异常值。通过研究真实数据集的稳定性，我们补充了这些结果，并展示了我们的算法在这些基准数据集上的表现。
euclidean k-meansclusteringalgorithmperturbation stabilityoutliers
发现论文，激发创造
  • 聚类中的数据稳定性：深入研究

    本文考虑了 Bilu 和 Linial（2010）提出的模型，研究了最佳聚类不发生变化的问题，我们发现即使问题是 NP 困难的，有时候也可能获得有效算法，这些算法对于特定的多项式扰动是鲁棒的。同时，我们证明了该区间内的乘法鲁棒性参数可能太强，以至于聚类问题变得微不足道，只有一个较窄的区间是有趣的。

    Jul, 2011

  • 基于稳定性扰动的中心聚类

    本文证明了当度量空间中没有 Steiner 点时，对于任何以中心为基础的聚类目标函数（例如 k - 中位数，k - 均值和 k - 中心），我们可以有效地找到最优的聚类，假设仅稳定于基础度量的 3 倍扰动，对于一般的度量，稳定性因子为 2 + 根号 3 扰动，我们还在相关条件下提出了 NP 困难性结果。

    Sep, 2010

  • 欧几里得 k - 均值问题的近似难度

    本研究采用图谱分析的方法，证明了欧几里得 k-means 问题的近似难度对于所有的 k 和 d 都是 NP 难的，同时发现当前最佳难度结果可以被推广到三角免费图中。

    Feb, 2015

  • 度量扰动韧性

    本文研究了计算机科学中由 Bilu, Linial （2010）和 Awasthi, Blum, Sheffet（2012）提出的微扰鲁棒性概念。作者考虑了一类基于中心的聚类问题，包括 k-means，k-median 和 k-center 等问题，并给出了一个用于聚类 2 - 扰动抵抗性实例的精确算法。该结果改进了 Balcan 和 Liang（2016）的结果，并且是最紧密的结果，除非 NP = RP，否则没有多项式时间算法能够解决（2-ε）- 扰动强度抵抗实例。作者还展示了该算法在满足比扰动强度抵抗更弱和自然的度量扰动强度抵抗条件的实例上的表现。

    Jul, 2016

  • 扰动鲁棒性下的聚类

    通过小乘的扰动，可在目标基础聚类问题中进行最优聚类，本文提供了几个在此框架内的结果并且基于新的关联准则提供了基于中心的和最小和聚类的算法。

    Dec, 2011

  • 交互式聚类的本地算法

    本文研究了基于稳定性假设的交互式聚类算法设计，算法开始于任意初始聚类，只进行每步的局部更改；我们证明在这种约束条件下，仍然可以设计出具有可证明高效和准确聚类能力的算法，并在真实数据上进行了实证。

    Dec, 2013

  • 具有稳定性假设的差分隐私聚类算法

    本文研究了在输入稳定性假设下的差分隐私聚类问题，提出了一种简单的算法，分析了其在 Wasserstein 距离和 k-means 代价等方面的效用，可直接应用于 “好” 的 k - 中位数实例和本地模型的差分隐私。

    Jun, 2021

  • k-means 问题的改进与简化无法近似性

    研究了 k-means 问题在 Euclidean 空间中寻找 k 个中心使得所有点到离它们最近中心的距离平方和最小，证明了该问题的近似难度是 NP-hard，并且提出了最小近似系数 1.0013。

    Sep, 2015

  • 抗扰动 $k$- 中心聚类

    该研究提供了一种在输入稳定条件下解决对称和非对称 $k$-center 问题的算法，并且这种算法在输入距离 2 - 扰动稳定时可以在最劣情况下保证聚类近似算法的最优解。

    May, 2015

  • 基于原始对偶算法的 k-Means 和欧几里得 k-Median 的更好保证

    该研究采用原始 - 对偶算法来解决 $k$-means 聚类问题，在满足集群数量限制的同时得到了 6.357 - 近似比的效果，并在欧几里得度量中解决了 $k$-median 的问题。

    Dec, 2016