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
Chapter 4: Spherical k-means Algorithm
This chapter describes a clustering algorithm designed to handle l 2 unit norm vectors. The algorithm is reminiscent to the quadratic k-means algorithm (Algorithm 2.1.1), however the distance between two unit vectors x and y is measured by d( x , y) = x T y (so that the two unit vectors x and y are equal if and only if d( x , y) = 1). We define the set 
housing centroids as a union of the unit n ? 1-dimensional l 2 sphere
centered at the origin and the origin (when it does not lead to ambiguity we shall denote the sphere just by 
).
The chapter is structured similar to Chapter 2. First, we introduce the batch spherical k-means algorithm, then the incremental version of the algorithm is described. Finally, the batch and incremental iterations are combined to generate the spherical k-means algorithm. We conclude the chapter with a short discussion that relates quadratic and spherical k-means algorithms.
4.1. Spherical Batch k-means Algorithm
To introduce centroids one has to modify formula (2.1.1). For a set of vectors 
= { a 1 , , a m} ? R n, and the distance-like function d( x , a) = a T x define centroid c = c ( ) of the set as a solution of the maximization problem
Copyright Jacob Kogan 2007 under license agreement with Books24x7
