Mar, 2022

有效应对距离约束：基于半径上界的强韧 K 均值算法

PDF
TL;DR在探索性数据分析中，基于中心点的聚类方法如 k-means、k-medoids 和 k-centers 被广泛应用。我们提出了一种引入最大半径约束的聚类方法，通过解决半定规划问题和带二次约束的线性分配问题来达到我们的约束。通过定量和定性实验，我们证明了该方法在处理复杂的实际数据集时的鲁棒性。
centroid-based clusteringsemi-definite programminghard radius constraintimbalanced clusteringvisualization
发现论文，激发创造
  • 面向鲁棒聚类的统一框架的均匀集中界限

    提出了基于中心的聚类算法的鲁棒框架 Median-of-Means，其在形式上覆盖了多种常见的聚类变体，其强一致性和误差率的阈值能够超过文献中已知的最佳结果，同时实验证明其在真实和合成数据集上具有很好的表现，同时还得到了一致的集中度界限。

    Oct, 2021

  • 基于 K-medoids 算法的主动距离聚类

    提出了一种新的 k-medoids 聚类算法，该算法只需要一小部分数据点之间的距离，并利用三角不等式来估算未知距离的上界，并采用递归方法和主动选择数据点的方法，在真实世界和合成数据集上经验证明其能够找出合适的聚类效果。

    Dec, 2015

  • 近似聚类的最优时间界限

    本文研究了基于 k-median 目标函数的聚类问题，提出了一种称为连续采样的简单但有效的采样技术，并使用该技术开发了一个可在 O（nk）时间内运行的算法来解决 k-median 问题。

    Dec, 2012

  • 在高维空间中近似求解公平的 $k$ 最小总半径问题

    在 Euclidean 空间中，我们提出了一个在常数 k 下为公平 $k$-min-sum-radii 问题提供 PTAS 的方法，这是该问题的首个 PTAS，适用于不同的群体公平性概念。

    Sep, 2023

  • 可扩展核聚类：近似核 k-means

    本文提出了一种基于随机化的近似核 K-means 簇算法，其利用采样点与数据集中所有点之间的核相似性来近似聚类中心，实现了与传统低秩核近似聚类方案相比更好的聚类性能、更短的运行时间和更小的内存需求，最后利用集成聚类技术进一步提高算法性能。

    Feb, 2014

  • 带有约束条件的隐私保护聚类

    探讨如何将具有某些限制的聚类问题的近似算法转化为更符合隐私约束的近似算法，并结合隐私与其他约束条件。

    Feb, 2018

  • 鲁棒自动数据聚类：狄利克雷过程遇见中位数均值

    通过整合基于模型和基于质心的方法，提出了一种高效且自动的聚类技术，解决噪声对聚类质量的影响，并确保无需提前指定聚类数的优点。在模拟和真实数据集上进行了严格评估和统计保证，表明我们提出的方法优于现有先进聚类算法。

    Nov, 2023

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

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

    Feb, 2015

  • K - 聚类的个体公平性

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

    Feb, 2020

  • 公平范围聚类的近似算法

    研究公平间距聚类问题，提供 O (1) 的近似算法在最多 k+2l 个中心中选择最小化聚类成本的一组中心，并仅在每个人口统计上最多违反 2 个加法项的上限。

    Jun, 2023