2011/02/18 by Brian Eriksson, Eriksson, Brian, Gautam Dasarathy +5
Computer Science · Physics and Astronomy · #Advanced Clustering Algorithms Research #Complex Network Analysis Techniques #Data Management and Algorithms #FOS: Computer and information sciences #Information Theory (cs.IT) #Machine Learning (cs.LG) #Machine Learning (stat.ML)
paper · pdf · doi:10.48550/arxiv.1102.3887
openalex publication_date 2011/02/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Hierarchical clustering based on pairwise similarities is a common tool used\nin a broad range of scientific applications. However, in many problems it may\nbe expensive to obtain or compute similarities between the items to be\nclustered. This paper investigates the hierarchical clustering of N items based\non a small subset of pairwise similarities, significantly less than the\ncomplete set of N(N-1)/2 similarities. First, we show that if the intracluster\nsimilarities exceed intercluster similarities, then it is possible to correctly\ndetermine the hierarchical clustering from as few as 3N log N similarities. We\ndemonstrate this order of magnitude savings in the number of pairwise\nsimilarities necessitates sequentially selecting which similarities to obtain\nin an adaptive fashion, rather than picking them at random. We then propose an\nactive clustering method that is robust to a limited fraction of anomalous\nsimilarities, and show how even in the presence of these noisy similarity\nvalues we can resolve the hierarchical clustering using only O(N log2 N)\npairwise similarities.\n