Talk:Lloyd's algorithm

Lloyd's method is identical to the k-means algorithm. Oddly, the k-means article says the method "converges very quickly in practice", while this one says "the algorithm converges slowly". — Jeff Erickson ✍ 04:30, 6 April 2007 (UTC)

The principal difference between Lloyd's method and the k-means algorithm is that k-means applies to a finite set of prescribed discrete entities, whereas the method described on this page applies to a continuum with a prescribed density function. The 'points' referred to on this page correspond to the 'centroids' of k-means clusters, in each case iteratively optimised to model the distribution of the prescribed data.

Mathematically these are indeed equivalent. Computationally, however, they are very different - the difference between a discrete and a continuous problem. This explains the difference in performance, and the fact that of the two methods only k-means can guarantee convergence in finitely many iterations. - Robert Stanforth 14:50, 15 May 2007 (UTC)

I think the two are different enough to remove the merge tag. Weston.pace 19:50, 12 June 2007 (UTC)

LLoyd's algorithm is the most popular method to find an approximate solution to the k-means problem. --178.2.54.39 (talk) 06:26, 13 October 2011 (UTC)

Performance

Coming from the article on Smoothed analysis, I was quite surprised that Lloyd's algorithm is given as an example there, but the result cannot be found here. As I am no expert in either k-means nor smoothed analysis, I don't feel comfortable to judge whether the result is in fact worth mentioning (or still up-to-date). Maybe someone with more expertise can make this decision and throw some light on the complexity of Lloyd's algorithm? 2A02:8109:1A3F:F5B4:0:0:0:215A (talk) 09:55, 13 December 2021 (UTC)

I think the smoothed analysis reference is inaccurate and that the reference doesn't really refer to Lloyd's algorithm, as described here, but rather to the algorithm at k-means clustering#Standard algorithm (naive k-means), which is very similar and which the linked article also calls Lloyd's algorithm. The difference is that the clusters here are geometric regions and that the algorithm repeatedly replaces each center by the centroid of its region, while the clusters at the linked article and the JACM reference are sets of points and that the algorithm repeatedly replaces each center by the average of its assigned points. In the context of smoothed analysis this makes an important difference, because the smoothing part is something that can be applied to sets of points but not really directly to geometric regions. So probably the link to Lloyd's algorithm at the smoothed analysis article should be changed to point to the k-means version of Lloyd's algorithm, not to the continuous version described at this article. —David Eppstein (talk) 17:25, 13 December 2021 (UTC)