Efficient active algorithms for hierarchical clustering

Akshay Krishnamurthy, Sivaraman Balakrishnan, Min Xu, Aarti Singh

Research output: Chapter in Book/Report/Conference proceedingConference contribution

28 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings of the 29th International Conference on Machine Learning, ICML 2012
Pages887-894
Number of pages8
StatePublished - Oct 10 2012
Externally publishedYes
Event29th International Conference on Machine Learning, ICML 2012 - Edinburgh, United Kingdom
Duration: Jun 26 2012Jul 1 2012

Publication series

NameProceedings of the 29th International Conference on Machine Learning, ICML 2012
Volume1

Other

Other29th International Conference on Machine Learning, ICML 2012
CountryUnited Kingdom
CityEdinburgh
Period6/26/127/1/12

All Science Journal Classification (ASJC) codes

  • Human-Computer Interaction
  • Education

Fingerprint Dive into the research topics of 'Efficient active algorithms for hierarchical clustering'. Together they form a unique fingerprint.

  • Cite this

    Krishnamurthy, A., Balakrishnan, S., Xu, M., & Singh, A. (2012). Efficient active algorithms for hierarchical clustering. In Proceedings of the 29th International Conference on Machine Learning, ICML 2012 (pp. 887-894). (Proceedings of the 29th International Conference on Machine Learning, ICML 2012; Vol. 1).