The Informativeness of $k$ -Means for Learning Mixture Models
- 9 July 2019
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 65 (11) , 7460-7479
Abstract
The learning of mixture models can be viewed as a clustering problem. Indeed, given data samples independently generated from a mixture of distributions, we often would like to find the correct target clustering of the samples according to which component distribution they were generated from. For a clustering problem, practitioners often choose to use the simple k-means algorithm. k-means attempts to find an optimal clustering which minimizes the sum-of-squares distance between each point and its cluster center. In this paper, we consider fundamental (i.e., information-theoretic) limits of the solutions (clusterings) obtained by optimizing the sum-of-squares distance. In particular, we provide sufficient conditions for the closeness of any optimal clustering and the correct target clustering assuming that the data samples are generated from a mixture of spherical Gaussian distributions. We also generalize our results to logconcave distributions. Moreover, we show that under similar or even weaker conditions on the mixture model, any optimal clustering for the samples with reduced dimensionality is also close to the correct target clustering. These results provide intuition for the informativeness of k-means (with and without dimensionality reduction) as an algorithm for learning mixture models.Keywords
All Related Versions
Funding Information
- NRF Fellowship (R-263-000-D02-281)
- Ministry of Education Tier 2 (R-263-000-C83-112)
This publication has 28 references indexed in Scilit:
- Randomized Dimensionality Reduction for $k$ -Means ClusteringIEEE Transactions on Information Theory, 2014
- Deterministic Feature Selection for K-Means ClusteringIEEE Transactions on Information Theory, 2013
- Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix DecompositionsSIAM Review, 2011
- Robust PCA and Clustering in Noisy Mixtures2009
- Approximate Clustering without the Approximation2009
- The Spectral Method for General Mixture ModelsLecture Notes in Computer Science, 2005
- Clustering Large Graphs via the Singular Value DecompositionMachine Learning, 2004
- Extensions of Lipschitz mappings into a Hilbert space1984
- On the Convergence Properties of the EM AlgorithmThe Annals of Statistics, 1983
- Least squares quantization in PCMIEEE Transactions on Information Theory, 1982