Fuzzy Clustering with Similarity Queries
  The fuzzy or soft $k$-means objective is a popular generalization of the
well-known $k$-means problem, extending the clustering capability of the
$k$-means to datasets that are uncertain, vague, and otherwise hard to cluster.
In this paper, we propose a semi-supervised active clustering framework, where
the learner is allowed to interact with an oracle (domain expert), asking for
the similarity between a certain set of chosen items. We study the query and
computational complexities of clustering in this framework. We prove that
having a few of such similarity queries enables one to get a polynomial-time
approximation algorithm to an otherwise conjecturally NP-hard problem. In
particular, we provide algorithms for fuzzy clustering in this setting that
asks $O(\mathsf{poly}(k)\log n)$ similarity queries and run with
polynomial-time-complexity, where $n$ is the number of items. The fuzzy
$k$-means objective is nonconvex, with $k$-means as a special case, and is
equivalent to some other generic nonconvex problem such as non-negative matrix
factorization. The ubiquitous Lloyd-type algorithms (or alternating
minimization algorithms) can get stuck at a local minimum. Our results show
that by making a few similarity queries, the problem becomes easier to solve.
Finally, we test our algorithms over real-world datasets, showing their
effectiveness in real-world applications.
