Sep, 2010

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

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

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

    Dec, 2011

  • 聚类中的数据稳定性：深入研究

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

    Jul, 2011

  • 度量扰动韧性

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

    Jul, 2016

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

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

    Dec, 2017

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

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

    May, 2015

  • 离散几何空间中鲁棒聚类的参数化逼近

    本文介绍了 Robust k-z 聚类和其在度量空间、算法公平性、欧几里得空间和 FPT 近似等领域的应用，提出了相应的算法，其中在特殊的欧几里得空间中得到了较好的近似结果。

    May, 2023

  • 个体偏好稳定聚类的常数逼近算法

    在一项研究中，我们引入了个体偏好稳定性（IP 稳定性），作为一种受稳定性和公平性约束启发的自然聚类目标。我们证明了对于一般度量，总存在一个 O (1)-IP 稳定的聚类算法，并且还介绍了 IP 稳定性在平均距离以及簇内和簇间最大最小距离情况下的推广。

    Sep, 2023

  • 个体公平聚类的改进近似算法

    此论文介绍了一种可行的算法，用于从簇成员与簇中心之间的距离范数角度出发解决公平聚类问题，并对相应指标（如 bicriteria）进行了优化；同时，提供了一种基于模类约束的距离范数成本设施位置 16^p - 近似算法，并将借鉴此算法，将个体公平聚类转化为更一般如群体公平聚类的解法。

    Jun, 2021

  • 图上 k - 中心问题的动态算法

    提供了首个对动态图进行边更新的 k - 中心问题的高效算法

    Jul, 2023

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

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

    Oct, 2023