具有背景知识的高效 $k$- 中心聚类

Jan, 2024

具有背景知识的高效 $k$- 中心聚类

Efficient Constrained $k$-Center Clustering with Background Knowledge

Longkun Guo, Chaoqi Jia, Kewen Liao, Zhigang Lu, Minhui Xue

TL;DR在这项工作中，我们在广泛采用的 $k$- 中心聚类的基础上构建其输入的背景知识作为必连（ML）和禁连（CL）约束集，并通过使用一系列技术，包括反支配集、线性规划整体多面体和线性规划对偶，得出了第一个具有最佳比例 2 的约束 $k$- 中心的高效逼近算法。我们还构建了竞争性基准算法，并在各种真实数据集上对我们的逼近算法进行了实证评估。结果验证了我们的理论发现，并展示了我们的算法在聚类成本、聚类质量和运行时间方面的巨大优势。

Abstract

center-based clustering has attracted significant research interest from both theory and practice. In many practical applications, input data often contain background knowledge that can be used to improve clustering results. In this work, we build on widely adopted $k$-center clusterin

center-based clustering must-link and cannot-link constraints $k$-center approximation algorithm clustering cost

发现论文，激发创造

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

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

Feb, 2018

无需一对一约束松弛的约束聚类和多核学习

本文提出了一种新的受限聚类算法，该算法可以在考虑已有对比信息的情况下最大程度地满足约束条件，而不会将已知的链接信息转化为距离信息，以此来高效地学习核与度量，并在各种公共数据集上的表现明显优于现有方法。同时，本文还探讨了该方法如何应用于大数据处理，可以有效提高可扩展性。

Mar, 2022

利用两种背景知识的半监督聚类：融合成对约束和单调性约束

本研究提出了一种新方法来解决在存在成对约束和单调性约束时执行聚类的问题，通过定义一种特定的距离测量方法并设计目标函数实现了这一目的，并使用 EM 优化算法进行优化，该方法在多个基准数据集和一个现实世界的案例中进行了测试。

Feb, 2023

受约束的 1 - 谱聚类

本文拓展了经典的谱聚类方法，将不能链接和必须链接约束整合到了聚类中，并通过松弛优化问题获得了一种新的连续性方法，相比其他约束谱聚类方法，该方法能够保证满足所有约束条件并且可以快速处理大规模数据集。

May, 2015

深度约束聚类框架 —— 算法和新进展

这篇论文介绍了一种基于深度学习的约束聚类框架，可应用于连续数据和高层领域知识等不同类型的约束条件，相比基于传统算法的方法，效果更好。

Jan, 2019

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

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

Jun, 2021

关于约束的谱聚类及其应用

本文介绍了一种明确将 Must-Link 和 Cannot-Link 约束作为约束优化问题部分的灵活的约束光谱聚类方法，通过广义特征分解，在多个数据集上取得了较好的结果。

Jan, 2012

松弛化，无需四舍五入：聚类公式的整数性

该研究探讨了点云聚类问题的凸松弛的精确恢复条件，以 k-means 和 k-median 聚类为重点，并提供了理论分析和实验研究。

Aug, 2014

面向鲁棒聚类的统一框架的均匀集中界限

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

Oct, 2021

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

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

Sep, 2010