We propose a framework for Semi-Supervised Active Clustering framework
(SSAC), where the learner is allowed to interact with a domain expert, asking
whether two given instances belong to the same cluster or not. We study the
query and computational complexity of clustering in this framework. We consider
a setting where the expert conforms to a center-based clustering with a notion
of margin. We show that there is a trade off between computational complexity
and query complexity; We prove that for the case of $k$-means clustering (i.e.,
when the expert conforms to a solution of $k$-means), having access to
relatively few such queries allows efficient solutions to otherwise NP hard
problems.
In particular, we provide a probabilistic polynomial-time (BPP) algorithm for
clustering in this setting that asks $O\big(k^2\log k + k\log n)$ same-cluster
queries and runs with time complexity $O\big(kn\log n)$ (where $k$ is the
number of clusters and $n$ is the number of instances). The algorithm succeeds
with high probability for data satisfying margin conditions under which,
without queries, we show that the problem is NP hard. We also prove a lower
bound on the number of queries needed to have a computationally efficient
clustering algorithm in this setting.

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