Convergence Properties of the K-Means Algorithms

By L. Eon Bottou, Yoshua Bengio. 1994

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Optimization & Training

Citations in the corpus

Efficient Content-Based Sparse Attention with Routing Transformers (2020, background): “learned online along with the rest of the parameters, as delineated in (Bottou and Bengio, 1995).”
Quantization based Fast Inner Product Search (2015, background): “The Lloyd’s algorithm is known to converge to a local minimum (except in pathological cases where it may oscillate between equivalent solutions) [5].”
Theory and Experiments on Vector Quantized Autoencoders (2018, methodology): “A special case of the hard EM algorithm is K -means clustering [17, 2] where the likelihood is modelled by a Gaussian with identity covariance matrix.”
Online Learning and Stochastic Approximations (1998, methodology): “Experimental evidence (Bottou and Bengio, 1995) suggest that the best convergence speed is obtained by rst using the online algorithm (3.26) and then switching to a batch super-linear version of K-means.”
Graph Clustering Based on Structural/Attribute Similarities (2009, background): “Proof. Existing work has studied the convergence properties of the partitioning approach to clustering, such as K-Means [ 3 ].”
Clustering with Constraints: Feasibility Issues and the k-Means Algorithm (2005, methodology): “We acknowledge that a more complicated analysis of the algorithm exists, namely an interpretation of the algorithm as analogous to the Newton-Raphson algorithm [2].”
An Evaluation on Feature Selection for Text Clustering (2003, methodology): “Two kinds of popular measurements, entropy and precision, were used to evaluate the clustering performance.”
An Efficient k-Means Clustering Algorithm: Analysis and Implementation (2002, unknown): “See [8],[40],[47],[49]for furtherdiscussionofitsstatisticalandconvergenceproper-ties.”
Recursive Least Squares Dictionary Learning Algorithm (2010, methodology): “For the (continuous ) k-means algorithm a Search-Then-Converge scheme has been used with good results [30]–[32].”
Asynchronous parallel stochastic gradient descent: a numeric core for scalable distributed machine learning algorithms (2015, methodology): “Following the notation given in [3], K-Means is formalized as minimization problem of the quantization error E(w):”
A Survey of Clustering Data Mining Techniques (2006, background): “Scalars at satisfy certain monotone asymptotic behavior and converge to zero, coefficients w are defined through ω [32].”