Efficient Active Algorithms for Hierarchical Clustering
This addresses the challenge of processing large datasets with limited resources, offering a practical solution for data analysis, though it is incremental as it builds on existing clustering methods.
The paper tackles the problem of clustering large datasets efficiently by proposing an active hierarchical clustering framework that uses small subsets of data, achieving recovery of clusters of size Ω(log n) with O(n log^2 n) similarities and O(n log^3 n) runtime for n objects.
Advances in sensing technologies and the growth of the internet have resulted in an explosion in the size of modern datasets, while storage and processing power continue to lag behind. This motivates the need for algorithms that are efficient, both in terms of the number of measurements needed and running time. To combat the challenges associated with large datasets, we propose a general framework for active hierarchical clustering that repeatedly runs an off-the-shelf clustering algorithm on small subsets of the data and comes with guarantees on performance, measurement complexity and runtime complexity. We instantiate this framework with a simple spectral clustering algorithm and provide concrete results on its performance, showing that, under some assumptions, this algorithm recovers all clusters of size ?(log n) using O(n log^2 n) similarities and runs in O(n log^3 n) time for a dataset of n objects. Through extensive experimentation we also demonstrate that this framework is practically alluring.