A Convex Optimization Framework for Bi-Clustering

Shiau Hong Lim, Yudong Chen, Huan Xu
Proceedings of the 32nd International Conference on Machine Learning, PMLR 37:1679-1688, 2015.

Abstract

We present a framework for biclustering and clustering where the observations are general labels. Our approach is based on the maximum likelihood estimator and its convex relaxation, and generalizes recent works in graph clustering to the biclustering setting. In addition to standard biclustering setting where one seeks to discover clustering structure simultaneously in two domain sets, we show that the same algorithm can be as effective when clustering structure only occurs in one domain. This allows for an alternative approach to clustering that is more natural in some scenarios. We present theoretical results that provide sufficient conditions for the recovery of the true underlying clusters under a generalized stochastic block model. These are further validated by our empirical results on both synthetic and real data.

Cite this Paper


BibTeX
@InProceedings{pmlr-v37-limb15, title = {A Convex Optimization Framework for Bi-Clustering}, author = {Lim, Shiau Hong and Chen, Yudong and Xu, Huan}, booktitle = {Proceedings of the 32nd International Conference on Machine Learning}, pages = {1679--1688}, year = {2015}, editor = {Bach, Francis and Blei, David}, volume = {37}, series = {Proceedings of Machine Learning Research}, address = {Lille, France}, month = {07--09 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v37/limb15.pdf}, url = {https://proceedings.mlr.press/v37/limb15.html}, abstract = {We present a framework for biclustering and clustering where the observations are general labels. Our approach is based on the maximum likelihood estimator and its convex relaxation, and generalizes recent works in graph clustering to the biclustering setting. In addition to standard biclustering setting where one seeks to discover clustering structure simultaneously in two domain sets, we show that the same algorithm can be as effective when clustering structure only occurs in one domain. This allows for an alternative approach to clustering that is more natural in some scenarios. We present theoretical results that provide sufficient conditions for the recovery of the true underlying clusters under a generalized stochastic block model. These are further validated by our empirical results on both synthetic and real data.} }
Endnote
%0 Conference Paper %T A Convex Optimization Framework for Bi-Clustering %A Shiau Hong Lim %A Yudong Chen %A Huan Xu %B Proceedings of the 32nd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2015 %E Francis Bach %E David Blei %F pmlr-v37-limb15 %I PMLR %P 1679--1688 %U https://proceedings.mlr.press/v37/limb15.html %V 37 %X We present a framework for biclustering and clustering where the observations are general labels. Our approach is based on the maximum likelihood estimator and its convex relaxation, and generalizes recent works in graph clustering to the biclustering setting. In addition to standard biclustering setting where one seeks to discover clustering structure simultaneously in two domain sets, we show that the same algorithm can be as effective when clustering structure only occurs in one domain. This allows for an alternative approach to clustering that is more natural in some scenarios. We present theoretical results that provide sufficient conditions for the recovery of the true underlying clusters under a generalized stochastic block model. These are further validated by our empirical results on both synthetic and real data.
RIS
TY - CPAPER TI - A Convex Optimization Framework for Bi-Clustering AU - Shiau Hong Lim AU - Yudong Chen AU - Huan Xu BT - Proceedings of the 32nd International Conference on Machine Learning DA - 2015/06/01 ED - Francis Bach ED - David Blei ID - pmlr-v37-limb15 PB - PMLR DP - Proceedings of Machine Learning Research VL - 37 SP - 1679 EP - 1688 L1 - http://proceedings.mlr.press/v37/limb15.pdf UR - https://proceedings.mlr.press/v37/limb15.html AB - We present a framework for biclustering and clustering where the observations are general labels. Our approach is based on the maximum likelihood estimator and its convex relaxation, and generalizes recent works in graph clustering to the biclustering setting. In addition to standard biclustering setting where one seeks to discover clustering structure simultaneously in two domain sets, we show that the same algorithm can be as effective when clustering structure only occurs in one domain. This allows for an alternative approach to clustering that is more natural in some scenarios. We present theoretical results that provide sufficient conditions for the recovery of the true underlying clusters under a generalized stochastic block model. These are further validated by our empirical results on both synthetic and real data. ER -
APA
Lim, S.H., Chen, Y. & Xu, H.. (2015). A Convex Optimization Framework for Bi-Clustering. Proceedings of the 32nd International Conference on Machine Learning, in Proceedings of Machine Learning Research 37:1679-1688 Available from https://proceedings.mlr.press/v37/limb15.html.

Related Material