Mar, 2024

个体偏好稳定聚类的可扩展算法

PDF
TL;DR本文研究了个体偏好稳定性（IP Stability），该概念捕捉了聚类中的个体公平性和稳定性。在这个设置中，如果每个数据点到其簇的平均距离不超过其到其他簇的平均距离的 α 倍，那么聚类就是 α-IP 稳定的。本文研究了个体偏好稳定聚类的自然局部搜索算法，我们的分析证实了该算法具有 O (log n)-IP 稳定性保证，其中 n 是输入中点的数量。此外，通过改进局部搜索方法，我们展示了该算法运行时间几乎是线性的，即约为 O (nk)。
发现论文，激发创造
  • 个体偏好稳定聚类的常数逼近算法

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

    Sep, 2023

  • 聚类的个人偏好稳定性

    本文提出了一种基于个体偏好稳定性思想的聚类方法，通过设计多种算法和在不同度量空间的实验验证，实现了具有较高效率和稳定性的聚类。

    Jul, 2022

  • 一个可扩展的算法用于个体公平的 K-means 聚类

    我们提出了一种可扩展的算法来解决由 Jung et al. 和 Mahabadi et al. 引入的个体公平（$p$, $k$）- 聚类问题。我们设计了首个快速局部搜索算法，具有～$O (nk^2)$ 的运行时间，并获得了（O (1), 6）的二对象近似解，然后我们通过实验证明了我们的算法不仅比以前的工作快得多，而且产生了更低成本的解决方案。

    Feb, 2024

  • 交互式聚类的本地算法

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

    Dec, 2013

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

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

    Sep, 2010

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

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

    Dec, 2017

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

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

    Jun, 2021

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

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

    Jun, 2021

  • 更好的面向个体公平的 $k$- 聚类算法

    运用线性规划和局部搜索算法解决在数据聚类问题中，$\ell_p$-range 目标下的个体公平问题。通过修改 LP 理论和结合局部搜索算法实践，实现更优算法，并在实验中展现了出众的表现。

    Jun, 2021

  • K - 聚类的个体公平性

    本文提出了一种基于局部搜索的算法，用于实现 $k$-median 和 $k$-means（以及任何使用 $\ell_p$ 范数的 $k$- 聚类），并从个体公平性的角度来考虑。我们的算法提供了一个逼近可行的 $k$- 聚类，其 $k$-median ($k$-means) 的成本与最优的 $k$- 聚类成本相比呈常数比例，并且我们的解决方案大约满足公平条件 (也在常数因子之内)。此外，我们还通过实证评估来补充我们的理论界限。

    Feb, 2020