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 11: Solutions to Selected Problems
Problem 2.1.6. True or False? If 
is the optimal partition, then x l ? c ( 
) ? x l + 1.
Solution to Problem 2.1.6
Consider a four scalar set = {0, 1/9, 4/9, 1}. While the arithmetic mean of the set is 7/18 the optimal 2 cluster partition is 
, where 
and 
. In this case the mean fails to separate the optimal clusters.
Problem 2.2.2. Show that the k-means clustering algorithm does not necessarily lead to the optimal partition.
Solution to Problem 2.2.2
Consider the one dimensional data set = {0, 1, 1 + ?, 3}. Since the optimal partition should be convex (see Lemma 2.1.1 and Theorem 2.3.1) the three candidates for an optimal 2 cluster partition are
-
? (0) = {{0, 1, 1 + ?}, {3}} with
. -
? (1) = {{0, 1}, {1 + ?, 3}} with
. -
? (2) = {{0}, {1, 1 + ?, 3}} with
.
Hence, when ? is a small positive number (for example 0 < ? < 0.05), one has
An application of a batch k-means iteration to ? (0) does not change the partition. The first variation of ? (0) is ? (0) itself. An application of k-means to ? (0) does not change the partition, and the algorithm misses the optimal partition ? (2).
Problem 2.2.3. Assume that the...
Copyright Jacob Kogan 2007 under license agreement with Books24x7
