Lloyd's algorithm: Difference between revisions

Revision as of 17:30, 6 October 2008

Revision as of 14:30, 7 December 2008

Line 1:

In [[computer graphicsscience]] and [[electrical engineering]], '''Lloyd's algorithm''', also known as '''Voronoi iteration''' or relaxation, is aan methodalgorithm for evenlygrouping distributingdata samplespoints into a given number of categories. It must be given a function to measure the similarity between two points, a function that averages two or objectsmore points together, usuallyand the number of categories into which to group the points.

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.

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

More formally:

Lloyd's algorithm starts with an initial distribution of samples or points and consists of repeatedly executing one relaxation step: