本文提出了一种半监督主动聚类框架 (SSAC)，通过进行少量的相同聚类查询，可以在多项式时间内解决 K-means 聚类问题，而且算法不需要边界假设。

Apr, 2017

提出了一个半监督主动聚类框架 (SSAC)，其中学习器允许与领域专家交互，询问给定实例是否属于同一群集。研究了在这个框架下聚类问题的查询和计算复杂性，并考虑了专家遵守具有边缘概念的中心聚类的情况。在 k-means 聚类的情况下，证明具有相对较少的查询即可提供有效的解决方案，提供一个概率多项式时间（BPP）算法，该算法需要 $O (k^2log k+klog n)$ 个相同集群查询，并具有时间复杂度 $O (knlog n)$。算法成功的概率很高，只要数据满足边缘条件，在没有查询的情况下，该问题是 NP 难的，还证明了在这种情况下需要具有计算效率的聚类算法所需的查询数量的下限。

Jun, 2016

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

Apr, 2005

本文主要研究了查询效率，使用类似于计算距离的相似度度量，通过提出新的算法实现了更加高效的相关聚类，能够在给定预算内使用不同的查询方式获得与最优解相差不大的结果，并且针对算法进行了实验研究。

Feb, 2020

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

Aug, 2021

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

Aug, 2021

本研究提出了一种新的 min-max 图割算法 ——Min Max s-t Cut，同时探讨了基于局部目标的方法，针对最大不同数，给出了最大总权重的最小化问题的一个 O (√n) 近似算法，局部无序最小化问题的一个简单的 7 - 近似算法，以及最小总权重的最大化问题的一个更好的 1/(2+ε) 近似算法。

Apr, 2017

本研究讨论了半监督聚类中 “同簇” 查询的弱监督方法，并提出了一种处理不确定响应的有效算法。实验显示，我们的方法在克服监督不确定性和产生高质量聚类方面非常有效。

Nov, 2017

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

Feb, 2024

研究交互聚类的查询复杂度和相似度矩阵的信息理论下界及上界，证明相似度矩阵可以显著降低查询复杂度，在不知道 $k,f_+ 和 f_-$ 的前提下，算法高效且参数免费，并揭示其与常见社区检测模型的关联。

Jun, 2017