Introduction to Clustering Large and High-Dimensional Data
Focusing on a few of the most important clustering algorithms, this book provides a detailed account of these major models in an information retrieval context.
TABLE OF CONTENTS Introduction to Clustering Large and High-Dimensional Data
2.4. Spectral Relaxation
2.4. Spectral Relaxation
While k-means outperforms batch k-means it is worth exploring how far from optimal partitions generated by the clustering algorithms might be. While ? min and Q( ? min) are not available we can obtain a lower bound for Q( ? min). Let ? = { ? 1 , , ? k} be a k-cluster partition of the data set 
= { a 1 , , a m}. Rearranging the vectors in if needed we assume that the first m 1 = ? 1 vectors a 1 , , a m 1 belong to cluster ? 1, the next m 2 = ? 2 vectors belong to cluster ? 2 and so on. A straightforward computation leads to the following formula
where
To minimize Q( ?) one has to maximize trace( Y T A T AY ) over matrices Y given by (2.4.5). We note that Y T Y = I k, substitute special matrices given by (2.4.5) by orthonormal matrices, and consider a relaxed problem
Solution to this problem is given by the next statement.
Theorem 2.4.1. (Ky Fan). If H is a symmetric matrix with eigenvalues
then
This result immediately leads to a lower bound for Q( ? min):
Copyright Jacob Kogan 2007 under license agreement with Books24x7
