@inproceedings{6d9f5188b2bc4cffa8528a9472e5bb99,
title = "Spectral relaxation for k-rneans clustering",
abstract = "The popular K-rneans clustering partitions a data set by minimizing a surn-of-squares cost function. A coordinate descend method is then used to find local minima. In this paper we show that the minimization can be reformulated as a trace maximization problem associated with the Gram matrix of the data vectors. Furthermore, we show that a relaxed version of the trace maximization problem possesses global optimal solutions which can be obtained by computing a partial eigendecomposition of the Gram matrix, and the cluster assignment for each data vectors can be found by computing a pivoted QR decomposition of the eigenvector matrix. As a by-product we also derive a lower bound for the minimum of the surn-of-squares cost function.",
author = "Hongyuan Zha and Xiaofeng He and Chris Ding and Horst Simon and Ming Gu",
year = "2002",
language = "英语",
isbn = "0262042088",
series = "Advances in Neural Information Processing Systems",
publisher = "Neural information processing systems foundation",
booktitle = "Advances in Neural Information Processing Systems 14 - Proceedings of the 2001 Conference, NIPS 2001",
address = "美国",
note = "15th Annual Neural Information Processing Systems Conference, NIPS 2001 ; Conference date: 03-12-2001 Through 08-12-2001",
}