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.
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.For example,to get square-grid tiles other than hexagons, manhattan metric can be used. (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).
Lloyd's algorithm starts with an initial distribution of samples or points and consists of repeatedly executing one relaxation step:
- The Voronoi diagram of all the points is computed.
- Each cell of the Voronoi diagram is integrated and the centroid is computed.
- Each point is then moved to the centroid of its Voronoi cell.
Each time a relaxation step is performed, the points are left in a slightly more even distribution: closely spaced points move further apart, and widely spaced points move closer together. In one dimension, this algorithm has been shown to converge to a centroidal Voronoi diagram, also named a centroidal Voronoi tessellation (Du, Emelianenko & Ju 2006). In higher dimensions, some slightly weaker convergence results are known (Sabin 1986), (Emelianenko, Ju & Rand 2009).
Since the algorithm converges slowly, and, due to limitations in numerical precision the algorithm will often not converge, real-world applications of Lloyd's algorithm stop once the distribution is "good enough." One common termination criterion is when the maximum distance a point moves in one iteration is below some set limit.
Lloyd's method is used in computer graphics because the resulting distribution has blue noise characteristics (see also Colors of noise), meaning there are few low-frequency components that could be interpreted as artifacts. It is particularly well-suited to picking sample positions for dithering.
Lloyd's algorithm is also used to generate dot drawings in the style of stippling (Deussen et al. 2000). In this application, the centroids can be weighted based on a reference image (Secord 2002) to produce stipple illustrations matching an input image.
- Deussen, Oliver; Hiller, Stefan; van Overveld, Cornelius; Strothotte, Thomas (2000), "Floating points: a method for computing stipple drawings", Computer Graphics Forum 19 (3): 41–50, doi:10.1111/1467-8659.00396, Proceedings of Eurographics.
- Du, Qiang; Emelianenko, Maria; Ju, Lili (2006), "Convergence of the Lloyd algorithm for computing centroidal Voronoi tessellations", SIAM Journal on Numerical Analysis 44: 102–119, doi:10.1137/040617364.
- Du, Qiang; Faber, Vance; Gunzburger, Max (1999), "Centroidal Voronoi tessellations: applications and algorithms", SIAM Review 41 (4): 637–676, doi:10.1137/S0036144599352836.
- Emelianenko, Maria; Ju, Lili; Rand, Alexander (2009), "Nondegeneracy and Weak Global Convergence of the Lloyd Algorithm in $R^d$", SIAM Journal on Numerical Analysis 46: 1423–1441.
- Lloyd, Stuart P. (1982), "Least squares quantization in PCM", IEEE Transactions on Information Theory 28 (2): 129–137, doi:10.1109/TIT.1982.1056489.
- Sabin, M. J.; Gray, R. M. (1986), "Global convergence and empirical consistency of the generalized Lloyd algorithm", IEEE Transactions on Information Theory 32 (2): 148–155, doi:10.1109/TIT.1986.1057168.
- Secord, Adrian (2002), "Weighted Voronoi stippling", Proceedings of the Symposium on Non-Photorealistic Animation and Rendering (NPAR), ACM SIGGRAPH, pp. 37–43, doi:10.1145/508530.508537.
- Hausner, Alejo (2001), "Simulating decorative mosaics", Proceedings of the 28th annual conference on Computer graphics and interactive techniques, ACM SIGGRAPH, pp. 573–580, doi:10.1145/383259.383327.