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

Brian Eriksson, Gautam Dasarathy, Aarti Singh, Rob Nowak
Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, PMLR 15:260-268, 2011.

Abstract

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. This paper investigates the possibility of hierarchical clustering of $N$ items based on 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 $3N \log N$ similarities. We demonstrate this order of magnitude saving in the number of pairwise similarities necessitates sequentially selecting which similarities to obtain in an adaptive fashion, rather than picking them at random. Finally, we 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 \log^2 N)$ pairwise similarities.

Cite this Paper

BibTeX
@InProceedings{pmlr-v15-eriksson11a, title = {Active Clustering: Robust and Efficient Hierarchical Clustering using Adaptively Selected Similarities}, author = {Eriksson, Brian and Dasarathy, Gautam and Singh, Aarti and Nowak, Rob}, booktitle = {Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics}, pages = {260--268}, year = {2011}, editor = {Gordon, Geoffrey and Dunson, David and Dudík, Miroslav}, volume = {15}, series = {Proceedings of Machine Learning Research}, address = {Fort Lauderdale, FL, USA}, month = {11--13 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v15/eriksson11a/eriksson11a.pdf}, url = {https://proceedings.mlr.press/v15/eriksson11a.html}, abstract = {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. This paper investigates the possibility of hierarchical clustering of $N$ items based on 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 $3N \log N$ similarities. We demonstrate this order of magnitude saving in the number of pairwise similarities necessitates sequentially selecting which similarities to obtain in an adaptive fashion, rather than picking them at random. Finally, we 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 \log^2 N)$ pairwise similarities.} }
Endnote
%0 Conference Paper %T Active Clustering: Robust and Efficient Hierarchical Clustering using Adaptively Selected Similarities %A Brian Eriksson %A Gautam Dasarathy %A Aarti Singh %A Rob Nowak %B Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2011 %E Geoffrey Gordon %E David Dunson %E Miroslav Dudík %F pmlr-v15-eriksson11a %I PMLR %P 260--268 %U https://proceedings.mlr.press/v15/eriksson11a.html %V 15 %X 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. This paper investigates the possibility of hierarchical clustering of $N$ items based on 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 $3N \log N$ similarities. We demonstrate this order of magnitude saving in the number of pairwise similarities necessitates sequentially selecting which similarities to obtain in an adaptive fashion, rather than picking them at random. Finally, we 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 \log^2 N)$ pairwise similarities.
RIS
TY - CPAPER TI - Active Clustering: Robust and Efficient Hierarchical Clustering using Adaptively Selected Similarities AU - Brian Eriksson AU - Gautam Dasarathy AU - Aarti Singh AU - Rob Nowak BT - Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics DA - 2011/06/14 ED - Geoffrey Gordon ED - David Dunson ED - Miroslav Dudík ID - pmlr-v15-eriksson11a PB - PMLR DP - Proceedings of Machine Learning Research VL - 15 SP - 260 EP - 268 L1 - http://proceedings.mlr.press/v15/eriksson11a/eriksson11a.pdf UR - https://proceedings.mlr.press/v15/eriksson11a.html AB - 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. This paper investigates the possibility of hierarchical clustering of $N$ items based on 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 $3N \log N$ similarities. We demonstrate this order of magnitude saving in the number of pairwise similarities necessitates sequentially selecting which similarities to obtain in an adaptive fashion, rather than picking them at random. Finally, we 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 \log^2 N)$ pairwise similarities. ER -
APA
Eriksson, B., Dasarathy, G., Singh, A. & Nowak, R.. (2011). Active Clustering: Robust and Efficient Hierarchical Clustering using Adaptively Selected Similarities. Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 15:260-268 Available from https://proceedings.mlr.press/v15/eriksson11a.html.

Related Material