2017/04/30 by Jörg Lücke, Dennis Forster · 53 citations
Computer Science · Mathematics · #Algorithm #Applied mathematics #Artificial intelligence #Bayesian Methods and Mixture Models #Computer science #Gaussian #Gaussian Processes and Bayesian Inference #Mathematical optimization #Mathematics #Mixture model #Physics #Quantum mechanics #Statistical physics #Target Tracking and Data Fusion in Sensor Networks #msc:62H30 #stat.ML
paper · pdf · doi:10.1016/j.patrec.2019.04.001
published in Pattern Recognition Letters 125, 349-356 (Elsevier BV)
openalex publication_date 2019/04/08 · arxiv created 2019/06/06 · arxiv updated 2019/06/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
We show that k-means (Lloyd's algorithm) is obtained as a special case when truncated variational EM approximations are applied to Gaussian Mixture Models (GMM) with isotropic Gaussians. In contrast to the standard way to relate k-means and GMMs, the provided derivation shows that it is not required to consider Gaussians with small variances or the limit case of zero variances. There are a number of consequences that directly follow from our approach: (A) k-means can be shown to increase a free energy associated with truncated distributions and this free energy can directly be reformulated in terms of the k-means objective; (B) k-means generalizations can directly be derived by considering the 2nd closest, 3rd closest etc. cluster in addition to just the closest one; and (C) the embedding of k-means into a free energy framework allows for theoretical interpretations of other k-means generalizations in the literature. In general, truncated variational EM provides a natural and rigorous quantitative link between k-means-like clustering and GMM clustering algorithms which may be very relevant for future theoretical and empirical studies.