Information Theoretical Clustering via Semidefinite Programming
Abstract
We propose techniques of convex optimization for information theoretical clustering. The clustering objective is to maximize the mutual information between data points and cluster assignments. We formulate this problem first as an instance of MAX K CUT on weighted graphs. We then apply the technique of semidefinite programming (SDP) relaxation to obtain a convex SDP problem. We show how the solution of the SDP problem can be further improved with a low-rank refinement heuristic. The low-rank solution reveals more clearly the cluster structure of the data. Empirical studies on several datasets demonstrate the effectiveness of our approach. In particular, the approach outperforms several other clustering algorithms when compared on standard evaluation metrics.
Cite
Text
Wang and Sha. "Information Theoretical Clustering via Semidefinite Programming." Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, 2011.Markdown
[Wang and Sha. "Information Theoretical Clustering via Semidefinite Programming." Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, 2011.](https://mlanthology.org/aistats/2011/wang2011aistats-information/)BibTeX
@inproceedings{wang2011aistats-information,
title = {{Information Theoretical Clustering via Semidefinite Programming}},
author = {Wang, Meihong and Sha, Fei},
booktitle = {Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics},
year = {2011},
pages = {761-769},
volume = {15},
url = {https://mlanthology.org/aistats/2011/wang2011aistats-information/}
}