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.2. Incremental Algorithm
2.2. Incremental Algorithm
In this section we describe the incremental quadratic k-means algorithm, and develop machinery for merging the batch and incremental versions of the quadratic k-means algorithms (the incremental k-means is introduced in Section 2.2.2). Although the technique of this section is custom tailored to quadratic functions it will become clear in Chapter 8 that analogous results hold for many k-means algorithms with entropy-like distances.
We begin with the following problem: Let 
= { a 1 , , a p}, 
= { b 1 , , b q} be two disjoint vector sets in R n with p and q vectors respectively. Express Q( ? ) by means of Q( ) and Q( ).
2.2.1. Quadratic functions
We return now to the quadratic function ? given by (2.1.6) for a set of scalars { a 1 , , a m}. Note that for each x one has
Furthermore for c = c({ a 1 , , a m}) and each x one has
Applications of (2.2.1) to coordinates i = 1 , 2 , , n yield:
This identity, in particular, leads to the following result.
Lemma 2.2.1. If = { a 1 , , a p} , = { b 1 , , b q} are two disjoint subsets of R n , then
where
Copyright Jacob Kogan 2007 under license agreement with Books24x7
