Efficient active algorithms for hierarchical clustering

Akshay Krishnamurthy, Sivaraman Balakrishnan, Min Xu, Aarti Singh

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

28 Citations (Scopus)

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
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

Fingerprint

Clustering algorithms
Set theory
Explosions
Internet
performance measurement
Processing
guarantee
performance
time

All Science Journal Classification (ASJC) codes

  • Human-Computer Interaction
  • Education

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).
Krishnamurthy, Akshay ; Balakrishnan, Sivaraman ; Xu, Min ; Singh, Aarti. / Efficient active algorithms for hierarchical clustering. Proceedings of the 29th International Conference on Machine Learning, ICML 2012. 2012. pp. 887-894 (Proceedings of the 29th International Conference on Machine Learning, ICML 2012).
@inproceedings{bb73dded10024127ab136021f28dd8b1,
title = "Efficient active algorithms for hierarchical clustering",
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.",
author = "Akshay Krishnamurthy and Sivaraman Balakrishnan and Min Xu and Aarti Singh",
year = "2012",
month = "10",
day = "10",
language = "English (US)",
isbn = "9781450312851",
series = "Proceedings of the 29th International Conference on Machine Learning, ICML 2012",
pages = "887--894",
booktitle = "Proceedings of the 29th International Conference on Machine Learning, ICML 2012",

}

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. Proceedings of the 29th International Conference on Machine Learning, ICML 2012, vol. 1, pp. 887-894, 29th International Conference on Machine Learning, ICML 2012, Edinburgh, United Kingdom, 6/26/12.

Efficient active algorithms for hierarchical clustering. / Krishnamurthy, Akshay; Balakrishnan, Sivaraman; Xu, Min; Singh, Aarti.

Proceedings of the 29th International Conference on Machine Learning, ICML 2012. 2012. p. 887-894 (Proceedings of the 29th International Conference on Machine Learning, ICML 2012; Vol. 1).

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

TY - GEN

T1 - Efficient active algorithms for hierarchical clustering

AU - Krishnamurthy, Akshay

AU - Balakrishnan, Sivaraman

AU - Xu, Min

AU - Singh, Aarti

PY - 2012/10/10

Y1 - 2012/10/10

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84867133838&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84867133838&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84867133838

SN - 9781450312851

T3 - Proceedings of the 29th International Conference on Machine Learning, ICML 2012

SP - 887

EP - 894

BT - Proceedings of the 29th International Conference on Machine Learning, ICML 2012

ER -

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