Talk:Lloyd's algorithm

This is the talk page for discussing improvements to the Lloyd's algorithm article.
This is not a forum for general discussion of the article's subject.

Put new text under old text. Click here to start a new topic.
New to Wikipedia? Welcome! Learn to edit; get help.

Article policies

Find sources: Google (books · news · scholar · free images · WP refs) · FENS · JSTOR · TWL

This article has not yet been rated on Wikipedia's content assessment scale.
It is of interest to the following WikiProjects:

Please add the quality rating to the {{WikiProject banner shell}} template instead of this project banner. See WP:PIQA for details.

Statistics Start‑class Low‑importance

	This article is within the scope of WikiProject Statistics, a collaborative effort to improve the coverage of statistics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.StatisticsWikipedia:WikiProject StatisticsTemplate:WikiProject StatisticsStatistics
Start	This article has been rated as Start-class on Wikipedia's content assessment scale.
Low	This article has been rated as Low-importance on the importance scale.

Please add the quality rating to the {{WikiProject banner shell}} template instead of this project banner. See WP:PIQA for details.

Computer science Start‑class Mid‑importance

This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.Computer scienceWikipedia:WikiProject Computer scienceTemplate:WikiProject Computer scienceComputer science

Start

This article has been rated as Start-class on Wikipedia's content assessment scale.

Mid

This article has been rated as Mid-importance on the project's importance scale.

Things you can help WikiProject Computer science with:

Here are some tasks awaiting attention:

Article requests :
- Requested articles/Applied arts and sciences/Computer science, computing, and Internet
Cleanup :
- Computer science articles needing attention
- Computer science articles needing expert attention
Copyedit :
- Computing
Expand :
- Computer science
Infobox :
- Computer science articles without infoboxes
Maintain :
- Timeline of computing 2020–present
Photo :
- Find pictures for the biographies of computer scientists (see List of computer scientists)
- Computing articles needing images
Stubs :
- Computer science stubs
Unreferenced :
- WikiProject Computer science/Unreferenced BLPs
Project-related :
- Tag all relevant articles in Category:Computer science and sub-categories with {{WikiProject Computer science}}

Databases (inactive)

This article is within the scope of WikiProject Databases, a project which is currently considered to be inactive.DatabasesWikipedia:WikiProject DatabasesTemplate:WikiProject DatabasesDatabases

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". — Jeﬀ Erickson ✍ 04:30, 6 April 2007 (UTC)[reply]

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)[reply]

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

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)[reply]

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)[reply]