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 6: Information Theoretic Clustering
This chapter discusses an information theoretic framework for k-means clustering. Let
(when it does not lead to ambiguity, we shall drop the subscript 1 and the superscript n ? 1 and denote the set just by 
+). Although each vector a ? + can be interpreted as a probability distribution in an attempt to keep the exposition of the material as simple as possible we shall turn to probabilistic arguments only when the deterministic approach fails to lead to desired results.
The chapter focuses on k-means clustering of a data set 
= { a 1 , , a m} ? + with the Kullback Leibler divergence.
6.1. Kullback Leibler Divergence
The section provides an additional example of a distance-like function and lists a number of its basic properties.
Definition 6.1.1. The relative entropy, or Kullback Leibler divergence between two probability distributions a and b ? + is defined as 
(when a > 0 and b > 0 , motivated by continuity arguments, we use the convention a log 
and 0 log 
).
We first show that when a ? + is fixed the range of KL( a , x), x ? + is [0 , ?]. Since 
we shall consider the function 
. Note that:
-
f ( x) ? 0.
-
Since a[ j] > 0 for at least one j = 1 , ,...
Copyright Jacob Kogan 2007 under license agreement with Books24x7
