Maximum Volume Clustering

Gang Niu, Bo Dai, Lin Shang, Masashi Sugiyama
Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, PMLR 15:561-569, 2011.

Abstract

The large volume principle proposed by Vladimir Vapnik, which advocates that hypotheses lying in an equivalence class with a larger volume are more preferable, is a useful alternative to the large margin principle. In this paper, we introduce a clustering model based on the large volume principle called maximum volume clustering (MVC), and propose two algorithms to solve it approximately: a soft-label and a hard-label MVC algorithms based on sequential quadratic programming and semi-definite programming, respectively. Our MVC model includes spectral clustering and maximum margin clustering as special cases, and is substantially more general. We also establish the finite sample stability and an error bound for the soft-label MVC method. Experiments show that the proposed MVC approach compares favorably with state-of-the-art clustering algorithms.

Cite this Paper

BibTeX
@InProceedings{pmlr-v15-niu11b, title = {Maximum Volume Clustering}, author = {Niu, Gang and Dai, Bo and Shang, Lin and Sugiyama, Masashi}, booktitle = {Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics}, pages = {561--569}, 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/niu11b/niu11b.pdf}, url = {https://proceedings.mlr.press/v15/niu11b.html}, abstract = {The large volume principle proposed by Vladimir Vapnik, which advocates that hypotheses lying in an equivalence class with a larger volume are more preferable, is a useful alternative to the large margin principle. In this paper, we introduce a clustering model based on the large volume principle called maximum volume clustering (MVC), and propose two algorithms to solve it approximately: a soft-label and a hard-label MVC algorithms based on sequential quadratic programming and semi-definite programming, respectively. Our MVC model includes spectral clustering and maximum margin clustering as special cases, and is substantially more general. We also establish the finite sample stability and an error bound for the soft-label MVC method. Experiments show that the proposed MVC approach compares favorably with state-of-the-art clustering algorithms.} }
Endnote
%0 Conference Paper %T Maximum Volume Clustering %A Gang Niu %A Bo Dai %A Lin Shang %A Masashi Sugiyama %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-niu11b %I PMLR %P 561--569 %U https://proceedings.mlr.press/v15/niu11b.html %V 15 %X The large volume principle proposed by Vladimir Vapnik, which advocates that hypotheses lying in an equivalence class with a larger volume are more preferable, is a useful alternative to the large margin principle. In this paper, we introduce a clustering model based on the large volume principle called maximum volume clustering (MVC), and propose two algorithms to solve it approximately: a soft-label and a hard-label MVC algorithms based on sequential quadratic programming and semi-definite programming, respectively. Our MVC model includes spectral clustering and maximum margin clustering as special cases, and is substantially more general. We also establish the finite sample stability and an error bound for the soft-label MVC method. Experiments show that the proposed MVC approach compares favorably with state-of-the-art clustering algorithms.
RIS
TY - CPAPER TI - Maximum Volume Clustering AU - Gang Niu AU - Bo Dai AU - Lin Shang AU - Masashi Sugiyama 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-niu11b PB - PMLR DP - Proceedings of Machine Learning Research VL - 15 SP - 561 EP - 569 L1 - http://proceedings.mlr.press/v15/niu11b/niu11b.pdf UR - https://proceedings.mlr.press/v15/niu11b.html AB - The large volume principle proposed by Vladimir Vapnik, which advocates that hypotheses lying in an equivalence class with a larger volume are more preferable, is a useful alternative to the large margin principle. In this paper, we introduce a clustering model based on the large volume principle called maximum volume clustering (MVC), and propose two algorithms to solve it approximately: a soft-label and a hard-label MVC algorithms based on sequential quadratic programming and semi-definite programming, respectively. Our MVC model includes spectral clustering and maximum margin clustering as special cases, and is substantially more general. We also establish the finite sample stability and an error bound for the soft-label MVC method. Experiments show that the proposed MVC approach compares favorably with state-of-the-art clustering algorithms. ER -
APA
Niu, G., Dai, B., Shang, L. & Sugiyama, M.. (2011). Maximum Volume Clustering. Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 15:561-569 Available from https://proceedings.mlr.press/v15/niu11b.html.

Related Material