本文研究了带有噪声查询的聚类问题，提供了信息理论下限以及与之匹配的新算法，并介绍了在众包、社交网络和随机块模型中应用的情况。

Jun, 2017

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

Nov, 2017

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

Dec, 2017

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

Feb, 2024

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

Apr, 2017

本研究通过对树叶对之间的相似度进行主动学习，研究树的层次聚类过程。 在实现的情况下，我们提供了完全重构树切割所需的查询数量的完整特征描述。 在非实现的情况下，我们依赖于已知的重要抽样过程来获得后悔和查询复杂度界限。 我们的算法具有对统计误差的理论保证，并且更重要的是，在问题的相关参数的情况下，它们自身具有线性时间实现的可行性。 我们讨论了这样的实现，证明了它们的运行时间保证，并展示了对真实数据集的初步实验结果，表明与被动学习和简单主动学习基线相比，我们的算法具有强大的实用性能。

Jun, 2019

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

Jun, 2016

本研究的主要贡献是提出了一种使用子线性时间的谱聚类算法，该算法可以将图按照展开器分簇，并可以提高聚类的准确性，同时通过估计图中节点的随机游走的分布，实现对谱嵌入的点积访问，并使用谱嵌入进行超平面划分，从而实现聚类。

Jan, 2021

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

Jun, 2017

本论文研究了在有限先验知识下的自动协变量选择问题，通过本地分区发现算法对变量集合进行划分，识别混淆因素和其他变量类型，实现有效的调整集合确定。实验证明了该方法在调整集合的发现方面具有更好的性能。

Oct, 2023