Journal
MACHINE LEARNING
Volume 56, Issue 1-3, Pages 9-33Publisher
SPRINGER
DOI: 10.1023/B:MACH.0000033113.59016.96
Keywords
Singular Value Decomposition; randomized algorithms; k-means clustering
Categories
Ask authors/readers for more resources
We consider the problem of partitioning a set of m points in the n-dimensional Euclidean space into k clusters ( usually m and n are variable, while k is fixed), so as to minimize the sum of squared distances between each point and its cluster center. This formulation is usually the objective of the k-means clustering algorithm (Kanungo et al. ( 2000)). We prove that this problem in NP-hard even for k = 2, and we consider a continuous relaxation of this discrete problem: find the k-dimensional subspace V that minimizes the sum of squared distances to V of the m points. This relaxation can be solved by computing the Singular Value Decomposition (SVD) of the m x n matrix A that represents the m points; this solution can be used to get a 2-approximation algorithm for the original problem. We then argue that in fact the relaxation provides a generalized clustering which is useful in its own right. Finally, we show that the SVD of a random submatrix-chosen according to a suitable probability distribution of a given matrix provides an approximation to the SVD of the whole matrix, thus yielding a very fast randomized algorithm. We expect this algorithm to be the main contribution of this paper, since it can be applied to problems of very large size which typically arise in modern applications.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available