该研究介绍了一种半监督聚类框架及其在相关性聚类问题中的应用，提出了一种有效的近似算法，并给出了同类查询数量的上下界。

Dec, 2017

我们研究了一个通用的聚类环境，其中我们有 $n$ 个要聚类的元素，并且我们的目标是尽量少地通过一个返回两个元素之间相似度的有噪声样本的预言进行查询。我们提出了在组合多臂赌博机的纯探索范式中根源于在线学习问题的两种新颖公式：固定置信度和固定预算设置。对于这两种设置，我们设计了将采样策略与经典的相关聚类近似算法相结合的算法，并研究了它们的理论保证。我们的结果是第一个针对 NP 困难的离线优化问题情况下 PE-CMAB 的多项式时间算法的示例。

Feb, 2024

研究聚类分析中的一种新方法 —— 相关聚类或定性信息聚类，探讨了最大化协议的问题和最小化分歧的问题，重点研究了聚类数为常数 k 的情况，发现该问题具有多项式时间近似解，为解决最小化分歧问题做了大量的技术工作。

Apr, 2005

本研究提出了更快的近似算法，避免了其最佳逼近算法所依赖的不切实际的线性规划放宽，为两个经过充分研究的特殊情况 —— 聚簇编辑和聚簇删除提供了更快、更实用、更高效的线性规划算法及极具可扩展性的组合技术，包括聚簇删除的第一个组合逼近算法，实际应用中，我们的算法产生了近乎与质量最佳算法相匹配的近似解，同时适用于数量级更大的问题。

Nov, 2021

本文研究了相关聚类问题在每个相似边和不相似边权重符合一定假设下的近似算法，并给出了此问题渐近匹配的线性规划完整性间隙。

Aug, 2021

研究了具有加权图的相关聚类问题，在此问题下，通过加权边标记为相似或不相似，通过最小化不同意向量的 l_p 规范的目标函数，提供了一个近似算法。

Aug, 2021

我们在这篇论文中建立了多层相关聚类，这是对相关聚类（Bansal 等人，FOCS'02）在多层设置中的一种新的概括。我们首先设计了一个基于知名区域生长技术的 O (Llogn) 逼近算法（其中 L 是层数），然后研究了带有概率约束的一个重要特殊情况。我们进一步设计了一个 4 逼近算法，该算法改进了一般概率约束情况下的逼近比例。使用真实数据集的计算实验证明了我们所提出算法的有效性。

Apr, 2024

本文聚焦于 Correlation Clustering functional，它结合了数据点之间的正面和负面亲和性。文章的贡献包括两个方面，一是提供了该函数的理论分析；二是提出了新的优化算法，能够处理无法使用现有方法解决的大规模问题（>100K 变量）。通过对该函数的理论分析，发现该函数具备概率生成解释的能力，并且合理地解释了其内在的 “模型选择” 能力。此外，文章还探索了该函数和 well-known Potts 能量最小化之间的类比，这为我们提出了几种新的优化算法，这些算法利用函数的内在 “模型选择” 能力，可以自动恢复基础聚类数。与此同时，文章还介绍了两种新的应用领域：无监督人脸识别和通过粗略边界描绘实现的交互式多对象分割。

Dec, 2011

本文研究动态数据流模型下相关聚类问题，结合线性草图和凸规划与抽样技术提出 O (n・polylog n)-space 近似算法，解决了自然问题。

Dec, 2018

本文研究了用于相关聚类问题的并行算法，其中每个不同实体的每对实体都标记为相似或不相似，旨在将实体分成簇以最小化与标签的不一致性，提出了首个多项式对数深度并行算法，并使用比 3 更好的逼近比计算 (2.4 +ϵ) 逼近解，可以将其转换为 (m1.5) 时间顺序算法和带有 (m1.5) 总内存的多项式对数轮次亚线性内存计算算法。

Jul, 2023