Spectral Clustering on a Budget

Ohad Shamir, Naftali Tishby
Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, PMLR 15:661-669, 2011.

Abstract

Spectral clustering is a modern and well known method for performing data clustering. However, it depends on the availability of a similarity matrix, which in many applications can be non-trivial to obtain. In this paper, we focus on the problem of performing spectral clustering under a budget constraint, where there is a limit on the number of entries which can be queried from the similarity matrix. We propose two algorithms for this problem, and study them theoretically and experimentally. These algorithms allow a tradeoff between computational efficiency and actual performance, and are also relevant for the problem of speeding up standard spectral clustering.

Cite this Paper

BibTeX
@InProceedings{pmlr-v15-shamir11a, title = {Spectral Clustering on a Budget}, author = {Shamir, Ohad and Tishby, Naftali}, booktitle = {Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics}, pages = {661--669}, 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/shamir11a/shamir11a.pdf}, url = {https://proceedings.mlr.press/v15/shamir11a.html}, abstract = {Spectral clustering is a modern and well known method for performing data clustering. However, it depends on the availability of a similarity matrix, which in many applications can be non-trivial to obtain. In this paper, we focus on the problem of performing spectral clustering under a budget constraint, where there is a limit on the number of entries which can be queried from the similarity matrix. We propose two algorithms for this problem, and study them theoretically and experimentally. These algorithms allow a tradeoff between computational efficiency and actual performance, and are also relevant for the problem of speeding up standard spectral clustering.} }
Endnote
%0 Conference Paper %T Spectral Clustering on a Budget %A Ohad Shamir %A Naftali Tishby %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-shamir11a %I PMLR %P 661--669 %U https://proceedings.mlr.press/v15/shamir11a.html %V 15 %X Spectral clustering is a modern and well known method for performing data clustering. However, it depends on the availability of a similarity matrix, which in many applications can be non-trivial to obtain. In this paper, we focus on the problem of performing spectral clustering under a budget constraint, where there is a limit on the number of entries which can be queried from the similarity matrix. We propose two algorithms for this problem, and study them theoretically and experimentally. These algorithms allow a tradeoff between computational efficiency and actual performance, and are also relevant for the problem of speeding up standard spectral clustering.
RIS
TY - CPAPER TI - Spectral Clustering on a Budget AU - Ohad Shamir AU - Naftali Tishby 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-shamir11a PB - PMLR DP - Proceedings of Machine Learning Research VL - 15 SP - 661 EP - 669 L1 - http://proceedings.mlr.press/v15/shamir11a/shamir11a.pdf UR - https://proceedings.mlr.press/v15/shamir11a.html AB - Spectral clustering is a modern and well known method for performing data clustering. However, it depends on the availability of a similarity matrix, which in many applications can be non-trivial to obtain. In this paper, we focus on the problem of performing spectral clustering under a budget constraint, where there is a limit on the number of entries which can be queried from the similarity matrix. We propose two algorithms for this problem, and study them theoretically and experimentally. These algorithms allow a tradeoff between computational efficiency and actual performance, and are also relevant for the problem of speeding up standard spectral clustering. ER -
APA
Shamir, O. & Tishby, N.. (2011). Spectral Clustering on a Budget. Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 15:661-669 Available from https://proceedings.mlr.press/v15/shamir11a.html.

Related Material