Top-m Clustering with a Noisy Oracle
Tuhinangshu Choudhury, Dhruti Shah, Nikhil Karamchandani · 2019
In this paper, we analyse the problem of top- m clustering with access to a noisy oracle. We consider a model where there are n nodes, belonging to k clusters. We have access to an oracle which when queried with a pair of nodes, returns a binary answer indicating whether they belong to the same cluster or not, but with a probability of error p. Our goal is to identify the top-m clusters in terms of size, using the noisy answers from the oracle. This setting was recently studied in [9], which provides an iterative algorithm for the case of complete clustering, i.e., m=k. We identify conditions (on the relative sizes of clusters) under which the first m stages of the algorithm would recover the top m clusters. We also analyze the query complexity of the algorithm and provide an upper bound which is a function of the number of recovered clusters m and the sizes of the top clusters.