Lloyd's algorithm: Difference between revisions

Revision as of 03:56, 28 March 2012

Revision as of 04:23, 28 March 2012

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 ana [[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{{Fact|date=December 2008}}.

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).