半监督聚类的松弛预测
研究交互聚类的查询复杂度和相似度矩阵的信息理论下界及上界,证明相似度矩阵可以显著降低查询复杂度,在不知道 $k,f_+ 和 f_-$ 的前提下,算法高效且参数免费,并揭示其与常见社区检测模型的关联。
Jun, 2017
我们研究了一个通用的聚类环境,其中我们有 $n$ 个要聚类的元素,并且我们的目标是尽量少地通过一个返回两个元素之间相似度的有噪声样本的预言进行查询。我们提出了在组合多臂赌博机的纯探索范式中根源于在线学习问题的两种新颖公式:固定置信度和固定预算设置。对于这两种设置,我们设计了将采样策略与经典的相关聚类近似算法相结合的算法,并研究了它们的理论保证。我们的结果是第一个针对 NP 困难的离线优化问题情况下 PE-CMAB 的多项式时间算法的示例。
Feb, 2024
提出了一个半监督主动聚类框架 (SSAC),其中学习器允许与领域专家交互,询问给定实例是否属于同一群集。研究了在这个框架下聚类问题的查询和计算复杂性,并考虑了专家遵守具有边缘概念的中心聚类的情况。在 k-means 聚类的情况下,证明具有相对较少的查询即可提供有效的解决方案,提供一个概率多项式时间(BPP)算法,该算法需要 $O (k^2log k+klog n)$ 个相同集群查询,并具有时间复杂度 $O (knlog n)$。算法成功的概率很高,只要数据满足边缘条件,在没有查询的情况下,该问题是 NP 难的,还证明了在这种情况下需要具有计算效率的聚类算法所需的查询数量的下限。
Jun, 2016
本文通过访问同簇 oracle,在有界对手误差的情况下,着手研究仅通过主动学习来精确恢复分区的问题。我们首先强调了学习分区和相关聚类之间的新颖联系。然后,利用这种关联建立了一个 Rényi-Ulam 样式的分析框架,并证明了该问题最坏情况下查询复杂度的上下限。此外,我们还限制了相关随机算法的预期性能。最后,我们研究了该问题及相关变体的适应性和查询复杂度之间的关系。
May, 2023
本研究提出了一种基于不确定性减少的在线主动半监督谱聚类方法,通过逐步选择成对约束来提高聚类效果,该方法在三个图像数据集、多个机器学习数据集和一个基因数据集中均表现出了优异的性能。
Feb, 2014
提出一种将生成式无监督特征学习与概率上的三元组信息处理相结合的方法,将隐式的 oracle 知识转移为显式的非线性贝叶斯潜在因子模型,并证明该方法在学习表示方面优于以前的度量学习方法和没有此类副信息的生成模型。
Jun, 2015