Active Clustering: Robust and Efficient Hierarchical Clustering using Adaptively Selected Similarities

Understand

Hierarchical clustering based on pairwise similarities is a common tool used in a broad range of scientific applications.

• However, in many problems it may be expensive to obtain or compute similarities between the items to be clustered.
• This paper investigates the hierarchical clustering of N items based on a small subset of pairwise similarities, significantly less than the complete set of N(N-1)/2 similarities.
• First, we show that if the intracluster similarities exceed intercluster similarities, then it is possible to correctly determine the hierarchical clustering from as few as 3N log N similarities.