NIPSJun, 2016

使用同类群查询的聚类

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

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

    Apr, 2017

  • 使用同簇查询的近似相关聚类

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

    Dec, 2017

  • 带侧信息的聚类查询复杂度

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

    Jun, 2017

  • 半监督聚类的松弛预测

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

    Nov, 2017

  • 使用比较查询进行主动分类

    研究一种扩展主动学习的方法，其中学习算法可以要求注释者比较两个示例与其标签类边界的距离，并使用半空间的框架展示这种方法的优越性。

    Apr, 2017

  • 查询 K 均值聚类和双 Dixie 杯问题

    本研究提出了基于同类簇查询与有噪音答案的方法，解决了离群点存在情况下的近似 K-means 聚类优化问题，证明了在一定条件下可以以大概率获得最优潜在解的 (1+ε）近似解，并且比目前已知的方法减少了同类簇查询数量。这种方法也推广到了控制噪音、离群点的场景中，同时在人造数据集和真实数据集上进行了测试。

    Jun, 2018

  • 基于模型不确定性降低的主动聚类

    本研究提出了一种基于不确定性减少的在线主动半监督谱聚类方法，通过逐步选择成对约束来提高聚类效果，该方法在三个图像数据集、多个机器学习数据集和一个基因数据集中均表现出了优异的性能。

    Feb, 2014

  • 具有嘈杂歧义回答的高效查询相关聚类

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

    Feb, 2024

  • 优化 k 最近邻图以实现计算上有效的谱聚类

    本文提出了一种在精简边界的 $k$-nearest neighbor graph 中基于局部统计的数据代表子集的近似谱聚类算法的方法，以提高其计算效率，且在人工合成的测试数据集和真实数据集中实验表明与常规方法相比较，该方法具有性能一致性和较少边界数量的特点。

    Feb, 2023

  • 定数个簇的相关聚类

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

    Apr, 2005