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

This talk will follow up on last week’s SILO talk by Prof. Ellenberg. In particular, this will be a discussion about the “EDSN” algorithm for robust and efficient hierarchical clustering.

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. In this talk we will discuss a method to perform hierarchical clustering of N items using 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 3NlogN similarities. We demonstrate this order of magnitude saving in the number of pairwise similarities requires sequentially selecting which similarities to obtain in an adaptive fashion, rather than picking them at random. We then propose an active clustering method that is robust to a limited fraction of anomalous similarities, and show how even in the presence of these “noisy” similarity values we can resolve the hierarchical clustering using only O(N log2 N) pairwise similarities. This is joint work with: Brian Eriksson, Aarti Singh and Rob Nowak