Jul, 2011

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

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

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

    Dec, 2011

  • 度量扰动韧性

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

    Jul, 2016

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

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

    Sep, 2010

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

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

    Dec, 2017

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

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

    May, 2015

  • 本地隐私 k-Means 聚类

    该研究设计了一种新的算法，用于处理欧几里得 k - 均值问题的差分隐私，通过本地模型，可以大幅降低加性误差，同时保持乘性误差不变。

    Jul, 2019

  • 论基本公平聚类的代价

    本文提出了针对多个保护类的公平聚类方法，并且提出了一种松散的公平概念，在这种概念下，可以对所有经典聚类目标进行双标准常数因子近似，这是通过将任意现有不公平的（整数）解和公平的（分数）线性规划解结合起来实现的。

    Nov, 2018

  • 带有恒定乘性误差的差分隐私 k 均值算法

    本研究针对欧几里得 k 均值问题，设计了新的差分隐私算法，其在中心模型和本地模型中均获得了显著提高的误差保证，并且还能计算私有 corsets 来处理 k 均值聚类问题。

    Apr, 2018

  • 利用 1-Center 和 1-Mean 聚类法处理带有离群值的分布式学习的近最优鲁棒聚合规则

    该研究论文讨论了拜占庭机器学习中安全抵御拜占庭机器的关键问题，并提出了一种基于异常值鲁棒聚类的近似聚集器，该方法在度量标准上表现出优越性，为均匀和异构情况提供了近乎最优的聚集器。基于研究结果，提出了一个两阶段的安全聚集框架，并通过图像分类实验验证了该框架的有效性。

    Dec, 2023

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

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

    Jun, 2021