Spectral Relaxation for K-means Clustering

Published 3 January 2001

Hongyuan Zha, Xiaofeng He, Chris Ding, Ming Gu, Horst D. Simon

Citations561

TL;DR

It is shown 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 ofThe eigenvector matrix.

Abstract

The popular K-means clustering partitions a data set by minimiz-ing a sum-of-squares cost function. A coordinate descend method is then used to nd 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 com-puting a partial eigendecomposition of the Gram matrix, and the cluster assignment for each data vectors can be found by comput-ing a pivoted QR decomposition of the eigenvector matrix. As a by-product we also derive a lower bound for the minimum of the sum-of-squares cost function. 1

Keywords

Computer ScienceEngineering

Neural ComputationNonlinear Component Analysis as a Kernel Eigenvalue Problem

8,078 Citations1998Bernhard Schölkopf, Alexander J. Smola +1 more

A new method for performing a nonlinear form of principal component analysis by the use of integral operator kernel functions is proposed and experimental results on polynomial feature extraction for pattern recognition are presented.

Mathematics and Computers in SimulationMatrix perturbation theory

2,518 Citations1991

Refining Initial Points for K-Means Clustering

999 Citations1998Paul S. Bradley, Usama M. Fayyad

A procedure for computing a refined starting condition from a given initial one that is based on an efficient technique for estimating the modes of a distribution that allows the iterative algorithm to converge to a “better” local minimum.

IEEE Transactions on Neural NetworksMercer kernel-based clustering in feature space

895 Citations2002Mark Girolami

It is shown that the eigenvectors of a kernel matrix which defines the implicit mapping provides a means to estimate the number of clusters inherent within the data and a computationally simple iterative procedure is presented for the subsequent feature space partitioning of the data.

Document clustering using word clusters via the information bottleneck method

476 Citations2000Noam Slonim, Naftali Tishby

A novel implementation of the recently introduced information bottleneck method for unsupervised document clustering that first finds word-clusters that capture most of the mutual information about to set of documents, and then finds document clusters that preserve the information about the word clusters.

View PDF

Constrained K-Means Clustering

346 Citations2000Kristin P. Bennett, Patricia Bradley +1 more

Preliminary numerical tests on real datasets indicate the constrained approach is less prone to poor local solutions, producing a better summary of the underlying data.