# Fuzzy Clustering with Similarity Queries

arXiv: https://arxiv.org/abs/2106.02212 · HTML: https://mlsanity.com/paper/2106.02212/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 53 references that are in the map.
- First posted on arXiv 4 Jun 2021.

## Builds on (most cited first, 15 of 15)

- [Clustering with Noisy Queries](https://mlsanity.com/paper/1706.07510/) (2017)
- [Clustering with Same-Cluster Queries](https://mlsanity.com/paper/1606.02404/) (2016)
- [Query Complexity of Clustering with Side Information](https://mlsanity.com/paper/1706.07719/) (2017)
- [Correlation Clustering with Same-Cluster Queries Bounded by Optimal Cost](https://mlsanity.com/paper/1908.04976/) (2019)
- [On Mixed Memberships and Symmetric Nonnegative Matrix Factorizations](https://mlsanity.com/paper/1607.00084/) (2016)
- [Exact Recovery of Mangled Clusters with Same-Cluster Queries](https://mlsanity.com/paper/2006.04675/) (2020)
- [Same-Cluster Querying for Overlapping Clusters](https://mlsanity.com/paper/1910.12490/) (2019)
- [A Theoretical Analysis of First Heuristics of Crowdsourced Entity Resolution](https://mlsanity.com/paper/1702.01208/) (2017)
- [Exact Recovery of Clusters in Finite Metric Spaces Using Oracle Queries](https://mlsanity.com/paper/2102.00504/) (2021)
- [Query K-means Clustering and the Double Dixie Cup Problem](https://mlsanity.com/paper/1806.05938/) (2018)
- [Approximate Clustering with Same-Cluster Queries](https://mlsanity.com/paper/1704.01862/) (2017)
- [Correlation Clustering with Adaptive Similarity Queries](https://mlsanity.com/paper/1905.11902/) (2019)
- [Semisupervised Clustering by Queries and Locally Encodable Source Coding](https://mlsanity.com/paper/1904.00507/) (2019)
- [Predicting Positive and Negative Links with Noisy Queries: Theory & Practice](https://mlsanity.com/paper/1709.07308/) (2017)
- [Query complexity of heavy hitter estimation](https://mlsanity.com/paper/2005.14425/) (2020)

## Abstract (arXiv)

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(mathsfpoly(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.