Lloyd's algorithm: Difference between revisions

Revision as of 21:18, 25 May 2013

Revision as of 23:30, 25 May 2013

Line 29:

In [[computer science]] and [[electrical engineering]], '''Lloyd's algorithm''', also known as '''Voronoi iteration''' or relaxation, is an algorithm for grouping data points into a given number of categories, used for [[k-means clustering|''k''-means clustering]].

Lloyd's algorithm is usually used in a [[Euclidean space]], so the distance function serves as a measure of similarity between points, and averaging of each dimension for the averaging, but this need not be the case.{{Clarify|date=May 2013}} For example,to get square-grid tiles other than hexagons, [[manhattan metric]] can be used. {{harv|Hausner|2001}}

Lloyd's algorithm starts by partitioning the input points into k initial sets, either at random or using some [[heuristic]]. It then calculates the average point, or [[centroid]], of each set via some metric (usually averaging dimensions in [[Euclidean space]]). It constructs a new partition by associating each point with the closest centroid, usually using the [[Euclidean distance]] function. Then the centroids are recalculated for the new clusters, and algorithm repeated by alternate application of these two steps until convergence, which is obtained when the points no longer switch clusters (or alternatively centroids are no longer changed).