Nonnegative Lagrangian Relaxation of K-Means and Spectral Clustering
Abstract
We show that K-means and spectral clustering objective functions can be written as a trace of quadratic forms. Instead of relaxation by eigenvectors, we propose a novel relaxation maintaining the nonnegativity of the cluster indicators and thus give the cluster posterior probabilities, therefore resolving cluster assignment difficulty in spectral relaxation. We derive a multiplicative updating algorithm to solve the nonnegative relaxation problem. The method is briefly extended to semi-supervised classification and semi-supervised clustering.
Cite
Text
Ding et al. "Nonnegative Lagrangian Relaxation of K-Means and Spectral Clustering." European Conference on Machine Learning, 2005. doi:10.1007/11564096_51Markdown
[Ding et al. "Nonnegative Lagrangian Relaxation of K-Means and Spectral Clustering." European Conference on Machine Learning, 2005.](https://mlanthology.org/ecmlpkdd/2005/ding2005ecml-nonnegative/) doi:10.1007/11564096_51BibTeX
@inproceedings{ding2005ecml-nonnegative,
title = {{Nonnegative Lagrangian Relaxation of K-Means and Spectral Clustering}},
author = {Ding, Chris H. Q. and He, Xiaofeng and Simon, Horst D.},
booktitle = {European Conference on Machine Learning},
year = {2005},
pages = {530-538},
doi = {10.1007/11564096_51},
url = {https://mlanthology.org/ecmlpkdd/2005/ding2005ecml-nonnegative/}
}