Hubbry Logo
Lloyd's algorithmLloyd's algorithmMain
Open search
Lloyd's algorithm
Community hub
Lloyd's algorithm
logo
8 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Lloyd's algorithm
Lloyd's algorithm
Lloyd's algorithm
View on Wikipedia
from Wikipedia

In electrical engineering and computer science, Lloyd's algorithm, also known as Voronoi iteration or relaxation, is an algorithm named after Stuart P. Lloyd for finding evenly spaced sets of points in subsets of Euclidean spaces and partitions of these subsets into well-shaped and uniformly sized convex cells.[1] Like the closely related k-means clustering algorithm, it repeatedly finds the centroid of each set in the partition and then re-partitions the input according to which of these centroids is closest. In this setting, the mean operation is an integral over a region of space, and the nearest centroid operation results in Voronoi diagrams.

Although the algorithm may be applied most directly to the Euclidean plane, similar algorithms may also be applied to higher-dimensional spaces or to spaces with other non-Euclidean metrics. Lloyd's algorithm can be used to construct close approximations to centroidal Voronoi tessellations of the input,[2] which can be used for quantization, dithering, and stippling. Other applications of Lloyd's algorithm include smoothing of triangle meshes in the finite element method.

Example of Lloyd's algorithm. The Voronoi diagram of the current site positions (red) at each iteration is shown. The gray circles denote the centroids of the Voronoi cells.
Lloyd's method, iteration 1
Iteration 1
Lloyd's method, iteration 2
Iteration 2
Lloyd's method, iteration 3
Iteration 3
Lloyd's method, iteration 15
Iteration 15
In the last image, the sites are very near the centroids of the Voronoi cells. A centroidal Voronoi tessellation has been found.

History

[edit]

The algorithm was first proposed by Stuart P. Lloyd of Bell Labs in 1957 as a technique for pulse-code modulation. Lloyd's work became widely circulated but remained unpublished until 1982.[1] A similar algorithm was developed independently by Joel Max and published in 1960,[3] which is why the algorithm is sometimes referred as the Lloyd-Max algorithm.

Algorithm description

[edit]

Lloyd's algorithm starts by an initial placement of some number k of point sites in the input domain. In mesh-smoothing applications, these would be the vertices of the mesh to be smoothed; in other applications they may be placed at random or by intersecting a uniform triangular mesh of the appropriate size with the input domain.

It then repeatedly executes the following relaxation step:

  • The Voronoi diagram of the k sites is computed.
  • Each cell of the Voronoi diagram is integrated, and the centroid is computed.
  • Each site is then moved to the centroid of its Voronoi cell.

Integration and centroid computation

[edit]

Because Voronoi diagram construction algorithms can be highly non-trivial, especially for inputs of dimension higher than two, the steps of calculating this diagram and finding the exact centroids of its cells may be replaced by an approximation.

Approximation

[edit]

A common simplification is to employ a suitable discretization of space like a fine pixel-grid, e.g. the texture buffer in graphics hardware. Cells are materialized as pixels, labeled with their corresponding site-ID. A cell's new center is approximated by averaging the positions of all pixels assigned with the same label. Alternatively, Monte Carlo methods may be used, in which random sample points are generated according to some fixed underlying probability distribution, assigned to the closest site, and averaged to approximate the centroid for each site.

Exact computation

[edit]

Although embedding in other spaces is also possible, this elaboration assumes Euclidean space using the L2 norm and discusses the two most relevant scenarios, which are two, and respectively three dimensions.

Since a Voronoi cell is of convex shape and always encloses its site, there exist trivial decompositions into easy integratable simplices:

  • In two dimensions, the edges of the polygonal cell are connected with its site, creating an umbrella-shaped set of triangles.
  • In three dimensions, the cell is enclosed by several planar polygons which have to be triangulated first:
    • Compute a center for the polygon face, e.g. the average of all its vertices.
    • Connecting the vertices of a polygon face with its center gives a planar umbrella-shaped triangulation.
    • Trivially, a set of tetrahedra is obtained by connecting triangles of the cell's hull with the cell's site.

Integration of a cell and computation of its centroid (center of mass) is now given as a weighted combination of its simplices' centroids (in the following called ).

  • Two dimensions:
    • For a triangle the centroid can be easily computed, e.g. using cartesian coordinates.
    • Weighting computes as simplex-to-cell area ratios.
  • Three dimensions:
    • The centroid of a tetrahedron is found as the intersection of three bisector planes and can be expressed as a matrix-vector product.
    • Weighting computes as simplex-to-cell volume ratios.

For a 2D cell with n triangular simplices and an accumulated area (where is the area of a triangle simplex), the new cell centroid computes as:

Analogously, for a 3D cell with a volume of (where is the volume of a tetrahedron simplex), the centroid computes as:

Convergence

[edit]

Each time a relaxation step is performed, the points are left in a slightly more even distribution: closely spaced points move farther 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.[4] In higher dimensions, some slightly weaker convergence results are known.[5][6]

The algorithm converges slowly or, due to limitations in numerical precision, may not converge. Therefore, real-world applications of Lloyd's algorithm typically stop once the distribution is "good enough." One common termination criterion is to stop when the maximum distance moved by any site in an iteration falls below a preset threshold. Convergence can be accelerated by over-relaxing the points, which is done by moving each point ω times the distance to the center of mass, typically using a value slightly less than 2 for ω.[7]

Applications

[edit]

Lloyd's method was originally used for scalar quantization, but it is clear that the method extends for vector quantization as well. As such, it is extensively used in data compression techniques in information theory. 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.[8] In this application, the centroids can be weighted based on a reference image to produce stipple illustrations matching an input image.[9]

In the finite element method, an input domain with a complex geometry is partitioned into elements with simpler shapes; for instance, two-dimensional domains (either subsets of the Euclidean plane or surfaces in three dimensions) are often partitioned into triangles. It is important for the convergence of the finite element methods that these elements be well shaped; in the case of triangles, often elements that are nearly equilateral triangles are preferred. Lloyd's algorithm can be used to smooth a mesh generated by some other algorithm, moving its vertices and changing the connection pattern among its elements in order to produce triangles that are more closely equilateral.[10] These applications typically use a smaller number of iterations of Lloyd's algorithm, stopping it to convergence, in order to preserve other features of the mesh such as differences in element size in different parts of the mesh. In contrast to a different smoothing method, Laplacian smoothing (in which mesh vertices are moved to the average of their neighbors' positions), Lloyd's algorithm can change the topology of the mesh, leading to more nearly equilateral elements as well as avoiding the problems with tangling that can arise with Laplacian smoothing. However, Laplacian smoothing can be applied more generally to meshes with non-triangular elements.

Different distances

[edit]

Lloyd's algorithm is usually used in a Euclidean space. The Euclidean distance plays two roles in the algorithm: it is used to define the Voronoi cells, but it also corresponds to the choice of the centroid as the representative point of each cell, since the centroid is the point that minimizes the average squared Euclidean distance to the points in its cell. Alternative distances, and alternative central points than the centroid, may be used instead. For example, Hausner (2001) used a variant of the Manhattan metric (with locally varying orientations) to find a tiling of an image by approximately square tiles whose orientation aligns with features of an image, which he used to simulate the construction of tiled mosaics.[11] In this application, despite varying the metric, Hausner continued to use centroids as the representative points of their Voronoi cells. However, for metrics that differ more significantly from Euclidean, it may be appropriate to choose the minimizer of average squared distance as the representative point, in place of the centroid.[12]

See also

[edit]

References

[edit]
[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Lloyd's algorithm

View on Grokipedia
from Grokipedia
Lloyd's algorithm is an iterative for solving the problem and optimal , which involves partitioning a of points in into k disjoint subsets (clusters) to minimize the within-cluster sum of squared distances to their respective centroids. Developed by Stuart P. Lloyd in 1957 as a method for least squares quantization in (PCM) systems, it was independently proposed by Hugo Steinhaus in 1956 and formally published by Lloyd in 1982, establishing it as a cornerstone of and data compression techniques. The algorithm operates through a two-step alternation: first, each data point is assigned to the nearest based on , forming tentative clusters; second, the centroids are updated to the arithmetic means (barycenters) of the points in their assigned clusters. This process repeats until the cluster assignments stabilize or the change in the objective function falls below a threshold, ensuring monotonic decrease in the sum-of-squares and convergence to a local optimum in finite steps. While computationally efficient with a per-iteration of O(nkd)—where n is the number of points, k the number of clusters, and d the dimensionality—its performance is sensitive to initial centroid selection, potentially leading to suboptimal local minima. Despite these limitations, Lloyd's algorithm remains one of the most widely implemented clustering methods due to its simplicity, scalability to large datasets, and practical effectiveness, often yielding interpretable results in real-world applications. It underpins tools in libraries and has inspired variants, such as k-means++ for improved initialization via probabilistic seeding to approximate the global optimum more reliably. Key applications include image and signal compression, , , and , where it facilitates data reduction and theme extraction by grouping similar observations.

History and Background

Historical Development

Lloyd's algorithm originated in the field of signal processing, specifically as a method for optimal scalar quantization in pulse-code modulation (PCM) systems. In 1957, Stuart P. Lloyd, working at Bell Laboratories, developed the iterative procedure in an internal technical memorandum aimed at minimizing mean squared error in quantizing continuous amplitude signals for digital transmission, such as in audio compression. This work addressed the challenge of designing quantizers that partition the input signal range into intervals with representation levels chosen to reduce distortion, motivated by the need for efficient communication over noisy channels. Lloyd's memo remained unpublished for over two decades, circulating informally within the engineering community at Bell Labs and influencing subsequent research in quantization. Independently, in 1960, Joel Max proposed a similar iterative algorithm for minimizing distortion in non-uniform quantizers, published in the IEEE Transactions on . Max's approach solved the coupled equations for optimal decision boundaries and output levels through successive approximations, applicable to signals with known probability density functions, and discussed the entropy of the quantizer output in the context of communication efficiency. Due to these parallel developments, the method is sometimes referred to as the Lloyd-Max quantizer, particularly in the context of one-dimensional . Lloyd's original 1957 memorandum was formally published in 1982 as "Least Squares Quantization in PCM" in the IEEE Transactions on , providing a rigorous derivation and extension to . This publication solidified the algorithm's foundational role in quantization theory, bridging early communications engineering with later applications in data compression and . In the 1960s, the procedure was rediscovered and adapted for clustering problems by James MacQueen, who termed it k-means in his 1967 paper on multivariate analysis.

Mathematical Foundations and Relation to K-Means

Lloyd's algorithm addresses the problem, which seeks to partition a of nn points {x1,…,xn}\{x_1, \dots, x_n\} in Rd\mathbb{R}^d into kk clusters by minimizing the within-cluster sum of squared distances to the cluster s. The objective function is formally defined as J=∑i=1k∑x∈Ci∥x−μi∥2,J = \sum_{i=1}^k \sum_{x \in C_i} \|x - \mu_i\|^2, where CiC_i denotes the set of points assigned to the ii-th cluster and μi\mu_i is the (mean) of CiC_i. This formulation, known as the k-means objective, measures the total distortion or variance within clusters and is NP-hard to optimize globally due to its non-convex nature. Lloyd's algorithm serves as an alternating optimization procedure for approximating solutions to this objective, iteratively fixing the to assign points to clusters and then updating the based on those assignments. Each iteration performs on the joint optimization over cluster assignments and , converging to a of JJ where no further improvement is possible under this alternation. This approach guarantees a local minimum but depends on the initial placement for the quality of the result. The cluster assignments in Lloyd's algorithm naturally correspond to the Voronoi cells induced by the current in the data space, where each cell consists of all points closer to its centroid than to any other. These partitions define the optimal assignment step, ensuring that the algorithm seeks a fixed point where centroids coincide with the means of their respective Voronoi regions. Originally proposed by Stuart Lloyd in 1957 for optimal scalar quantization in , the algorithm was independently rediscovered in James MacQueen's 1967 work on classification methods, which introduced a sequential variant of k-means that processes data points one at a time. This link highlights Lloyd's deterministic batch method as the foundational iterative framework for modern k-means implementations.

Core Algorithm

Iterative Procedure

Lloyd's algorithm initiates the clustering process by selecting an initial set of kk centroids, denoted {μ1(0),…,μk(0)}\{\mu_1^{(0)}, \dots, \mu_k^{(0)}\}, typically chosen randomly from the dataset to seed the optimization. Heuristic methods, such as sampling points that are spread out across the data space, can also be employed for initialization to potentially avoid poor starting configurations. The core of the algorithm consists of an iterative loop comprising two alternating steps: assignment and centroid update. In the assignment step, each data point xjx_j is allocated to the cluster Ci(t)C_i^{(t)} associated with the nearest centroid μi(t)\mu_i^{(t)}, defined by the condition Ci(t)={xj:∥xj−μi(t)∥≤∥xj−μm(t)∥ ∀m≠i}C_i^{(t)} = \{ x_j : \|x_j - \mu_i^{(t)}\| \leq \|x_j - \mu_m^{(t)}\| \ \forall m \neq i \}, where the distance is usually the squared Euclidean norm. This step effectively partitions the data into kk clusters based on proximity to the current centroids. Following assignment, the update step recomputes each centroid as the arithmetic mean of the points in its cluster: μi(t+1)=1∣Ci(t)∣∑x∈Ci(t)x\mu_i^{(t+1)} = \frac{1}{|C_i^{(t)}|} \sum_{x \in C_i^{(t)}} x. These steps repeat, with the assignments and centroids refining progressively, until stability is achieved in the cluster memberships. The geometric interpretation of the assignment step corresponds to the Voronoi diagram induced by the current centroids, where each cell contains points closest to a particular centroid. The procedure can be represented in pseudocode as follows:

Input: Dataset {x_1, ..., x_n}, number of clusters k Output: Cluster assignments and final centroids {μ_1, ..., μ_k} 1. Initialize centroids {μ_1^{(0)}, ..., μ_k^{(0)}} randomly from the dataset 2. Set t = 0 3. Repeat: a. For each data point x_j: Assign x_j to cluster i where i = argmin_m ||x_j - μ_m^{(t)}||^2 (Form clusters C_1^{(t)}, ..., C_k^{(t)}) b. For each cluster i = 1 to k: If |C_i^{(t)}| > 0: μ_i^{(t+1)} = (1 / |C_i^{(t)}|) ∑_{x ∈ C_i^{(t)}} x Else: Reinitialize μ_i^{(t+1)} randomly (to handle empty clusters) c. t = t + 1 4. Until assignments stabilize or maximum iterations reached 5. Return clusters and {μ_1^{(t)}, ..., μ_k^{(t)}}

Input: Dataset {x_1, ..., x_n}, number of clusters k Output: Cluster assignments and final centroids {μ_1, ..., μ_k} 1. Initialize centroids {μ_1^{(0)}, ..., μ_k^{(0)}} randomly from the dataset 2. Set t = 0 3. Repeat: a. For each data point x_j: Assign x_j to cluster i where i = argmin_m ||x_j - μ_m^{(t)}||^2 (Form clusters C_1^{(t)}, ..., C_k^{(t)}) b. For each cluster i = 1 to k: If |C_i^{(t)}| > 0: μ_i^{(t+1)} = (1 / |C_i^{(t)}|) ∑_{x ∈ C_i^{(t)}} x Else: Reinitialize μ_i^{(t+1)} randomly (to handle empty clusters) c. t = t + 1 4. Until assignments stabilize or maximum iterations reached 5. Return clusters and {μ_1^{(t)}, ..., μ_k^{(t)}}

This iterative process yields a locally optimal solution with respect to the k-means objective, minimizing the within-cluster sum of squared distances, though the quality depends on the initial centroids.

Role of Voronoi Diagrams

In Lloyd's algorithm, the assignment step partitions the input space into regions based on proximity to the current set of centroids {μ1,μ2,…,μk}\{\mu_1, \mu_2, \dots, \mu_k\}, forming the of these centroids. Each Voronoi cell ViV_i is defined as the set of points xx in the space such that ∥x−μi∥≤∥x−μj∥\|x - \mu_i\| \leq \|x - \mu_j\| for all j≠ij \neq i, where ∥⋅∥\|\cdot\| denotes the . This geometric partitioning ensures that every point is assigned to the nearest centroid, creating a that divides the space without overlap except on boundaries. During each iteration of the algorithm, the is recomputed using the updated from the previous step, refining the partitioning progressively. At convergence, the resulting tessellation is a (CVT), where each coincides with the center of mass of its associated Voronoi cell. The assignments in Lloyd's algorithm directly correspond to membership in these Voronoi cells, which underpin the clustering process by grouping data points geometrically. Voronoi cells in are convex polytopes, formed as the intersection of half-spaces defined by the perpendicular bisectors between . In one , these cells simplify to contiguous intervals bounded by midpoints between adjacent . These properties ensure the partitions are well-defined and amenable to iterative refinement in the algorithm.

Centroid Computation

Approximation Methods

In cases where exact computation of requires integrating over complex Voronoi cells with respect to a continuous density function, numerical methods become essential for practical implementation of Lloyd's algorithm in centroidal Voronoi tessellations. These approximations are particularly valuable in high-al spaces or when the is irregular, as they enable scalable estimation without closed-form solutions. One prominent approach is , which estimates the μi\mu_i of the ii-th Voronoi cell by uniformly sampling NN points s1,…,sNs_1, \dots, s_N within the cell and computing μi≈1N∑s=1Ns\mu_i \approx \frac{1}{N} \sum_{s=1}^N s, weighted by the local density if applicable. This method leverages random sampling to approximate the under the cell's mass distribution, making it suitable for irregular geometries where deterministic integration is prohibitive. In probabilistic extensions of Lloyd's algorithm, such sampling is incorporated into iterative updates, where points are generated via from the density q(x)q(x) to ensure uniformity within bounds, enhancing convergence in parallel settings. Grid-based approximation offers an alternative by discretizing the ambient space into a fine lattice of pixels or voxels, then estimating the centroid as the weighted sum of grid points falling within the Voronoi cell, divided by the total weight. This technique is computationally efficient for structured domains, as it transforms the integration into a summation over discrete elements, often using the grid's inherent uniformity to bound errors. It aligns well with Lloyd's iterative relaxation, where Voronoi cells are recomputed on the grid at each step to update generator positions. Error analysis for these methods highlights a fundamental trade-off: accuracy improves with increased sample size NN in (with variance scaling as O(1/N)O(1/N)) or finer grid resolution, but at higher computational cost, particularly in high dimensions where the curse of dimensionality amplifies sampling requirements. methods excel in such settings due to their dimension-independent convergence rates for certain integrals, though they may introduce if sampling rejects too frequently; grid methods, conversely, suffer from artifacts but provide deterministic bounds. These approximations are especially practical in image processing applications, where the pixel grid naturally the domain, enabling efficient for compression— for instance, approximating centroids over intensities within cells to minimize distortion without continuous integration. While exact methods suffice for low-dimensional Euclidean cases with simple densities, approximations like these ensure Lloyd's algorithm remains viable for broader, real-world scenarios.

Exact Computation in Euclidean Spaces

In low-dimensional Euclidean spaces, the exact computation of centroids for Voronoi cells in Lloyd's algorithm assumes a uniform density distribution over the cells, enabling the use of geometric formulas derived from the cell's . This approach is particularly applicable in the context of centroidal Voronoi tessellations (CVTs), where Lloyd's iterative procedure updates generators to the centroids of their associated cells. In one dimension, each Voronoi cell corresponds to a closed interval [ai,bi][a_i, b_i] on the real line, and under uniform density, the μi\mu_i is simply the of this interval, given by μi=ai+bi2\mu_i = \frac{a_i + b_i}{2}. This computation is straightforward and exact, requiring only the endpoints determined from the construction. In two dimensions, Voronoi cells are convex , and the can be computed exactly by decomposing the polygon into triangles or directly using the adapted for the center of mass. For a polygonal cell with vertices (xk,yk)(x_k, y_k) for k=1k = 1 to nn (ordered counterclockwise), the x-coordinate of the μx\mu_x is μx=16A∑k=1n(xk+xk+1)(xkyk+1−xk+1yk),\mu_x = \frac{1}{6A} \sum_{k=1}^n (x_k + x_{k+1})(x_k y_{k+1} - x_{k+1} y_k), where xn+1=x1x_{n+1} = x_1, yn+1=y1y_{n+1} = y_1, and AA is the area of the , A=12∑k=1n(xkyk+1−xk+1yk)A = \frac{1}{2} \sum_{k=1}^n (x_k y_{k+1} - x_{k+1} y_k). The y-coordinate μy\mu_y follows analogously by swapping x and y in the formula. This method yields the precise geometric for finite, bounded polygonal cells. In three dimensions, Voronoi cells form convex , and exact centroid computation involves decomposing the into relative to a chosen base point (often the origin or an interior point), then taking the volume-weighted average of the 's centroids. For a decomposed into TjT_j with volumes VjV_j and individual centroids cj=14∑m=14vj,m\mathbf{c}_j = \frac{1}{4} \sum_{m=1}^4 \mathbf{v}_{j,m} (where vj,m\mathbf{v}_{j,m} are the vertices of TjT_j), the overall μ\boldsymbol{\mu} is μ=∑jVjcj∑jVj.\boldsymbol{\mu} = \frac{\sum_j V_j \mathbf{c}_j}{\sum_j V_j}. The volume of each is Vj=16∣det⁡(vj,2−vj,1,vj,3−vj,1,vj,4−vj,1)∣V_j = \frac{1}{6} |\det(\mathbf{v}_{j,2} - \mathbf{v}_{j,1}, \mathbf{v}_{j,3} - \mathbf{v}_{j,1}, \mathbf{v}_{j,4} - \mathbf{v}_{j,1})|. This tetrahedral decomposition ensures an exact result for bounded polyhedral cells under uniform density. These methods rely on the assumption of uniform density within each cell, where the coincides with the geometric . For non-uniform densities ρ(x)\rho(\mathbf{x}), the generalizes to the μ=∫Vxρ(x) dx∫Vρ(x) dx\boldsymbol{\mu} = \frac{\int_V \mathbf{x} \rho(\mathbf{x}) \, d\mathbf{x}}{\int_V \rho(\mathbf{x}) \, d\mathbf{x}}, computable via over the cell for low dimensions, though this increases complexity beyond the uniform case. In higher dimensions, exact polyhedral decompositions become prohibitive due to , often necessitating approximations.

Convergence Properties

Theoretical Analysis

Lloyd's algorithm minimizes a quantization energy function J(μ)=∑i=1k∫Vi(μ)∥x−μi∥2 dP(x)J(\mu) = \sum_{i=1}^k \int_{V_i(\mu)} \|x - \mu_i\|^2 \, dP(x), where μ={μi}i=1k\mu = \{\mu_i\}_{i=1}^k denotes the set of centroids, Vi(μ)V_i(\mu) are the associated Voronoi cells, and PP is the underlying . In the assignment step, data points are allocated to the nearest , which minimizes JJ for fixed μ(t)\mu^{(t)} by defining the Voronoi partition. The subsequent update step computes μi(t+1)\mu_i^{(t+1)} as the over Vi(μ(t))V_i(\mu^{(t)}), minimizing JJ for the fixed partition. This alternating optimization ensures that each iteration produces a non-increasing objective value, satisfying J(μ(t+1))≤J(μ(t))J(\mu^{(t+1)}) \leq J(\mu^{(t)}), with equality holding only at stationary points. The sequence of iterates converges to a fixed point of the Lloyd iteration map, where the centroids coincide with the mass centroids (generators) of their Voronoi cells, forming a critical point of JJ. Under mild conditions, such as finite fixed points sharing the same distortion value, the algorithm achieves global convergence to this stationary configuration. In one dimension, for any positive and smooth density function, Lloyd's algorithm converges globally to the unique optimum. In higher dimensions, convergence is typically to a local minimum, as the non-convex nature of JJ allows multiple stationary points. Recent analyses have established sequential convergence of the iterates to a single for variants of Lloyd's method under analyticity assumptions on the target measure's density. Furthermore, the algorithm demonstrates consistency under data perturbations, with misclustering rates on sub-Gaussian mixtures exponentially bounded after O(log⁡n)O(\log n) iterations, provided suitable initialization and separation conditions hold.

Practical Implementation Considerations

In practical implementations of Lloyd's algorithm, appropriate stopping criteria are essential to balance computational efficiency and convergence reliability. A common approach is to monitor the change in the objective function JJ, defined as the sum of squared distances from points to their assigned centroids, and halt iterations when ∣J(t+1)−J(t)∣<ϵ|J^{(t+1)} - J^{(t)}| < \epsilon for a small tolerance ϵ\epsilon, such as 10−610^{-6}. Another standard criterion is to stop when cluster assignments remain unchanged between consecutive iterations, indicating that the algorithm has reached a stable partitioning. To accelerate convergence while maintaining stability, over-relaxation can be incorporated into the update step. Specifically, the new μi(t+1)\mu_i^{(t+1)} for cluster ii is computed as a of the previous and the μˉi\bar{\mu}_i of the points assigned to it: μi(t+1)=(1−ω)μi(t)+ωμˉi,\mu_i^{(t+1)} = (1 - \omega) \mu_i^{(t)} + \omega \bar{\mu}_i, where the relaxation parameter ω\omega is chosen between 1 and 2; values closer to 2 often yield faster progress but risk overshooting in ill-conditioned data. This technique, rooted in methods, reduces the number of iterations required compared to standard updates, particularly in applications like centroidal Voronoi tessellations. Initialization of centroids significantly impacts the algorithm's performance, as poor starting points can lead to suboptimal local minima. The Forgy method selects kk initial uniformly at random from the data points, offering and low overhead but potentially yielding uneven spreads. In contrast, the k-means++ initialization improves upon this by choosing the first randomly and subsequent ones with probability proportional to the squared distance from the nearest existing , promoting better separation and typically requiring fewer iterations—often 2–3 times faster in practice—while achieving solutions within O(log⁡k)O(\log k) of the optimum in expectation. To mitigate risks in degenerate scenarios, such as persistent empty clusters or stalled progress, implementations impose a maximum limit, commonly set to 300, beyond which the algorithm terminates even if convergence criteria are unmet. This safeguard prevents infinite loops without compromising the nature of the process, as shows most practical runs converge within 20–50 iterations.

Variants and Extensions

Non-Euclidean Distance Metrics

Lloyd's algorithm, originally formulated for Euclidean spaces, can be adapted to non-Euclidean distance metrics by modifying the assignment and update steps to use the chosen metric for nearest-neighbor assignment while adjusting the representative computation accordingly. One prominent adaptation employs the (L1) distance, where the objective is to minimize the sum of absolute deviations rather than squared Euclidean distances. In this case, known as k-s clustering, the cluster representative is updated to the coordinate-wise of the points assigned to the cluster, rather than the , as the minimizes the L1 objective in each dimension. This adjustment makes the algorithm more robust to outliers compared to the standard Euclidean version. Additionally, the Voronoi cells under the metric in two dimensions form diamond shapes bounded by lines tilted at 45 degrees to the coordinate axes, altering the geometry of the partitioning compared to the perpendicular bisectors in . Other metrics, such as the , extend the algorithm to handle correlated data by incorporating a structure into the , which scales the space to account for variable correlations and spreads. The is defined as d(x,μ)=(x−μ)TS−1(x−μ)d(\mathbf{x}, \boldsymbol{\mu}) = \sqrt{(\mathbf{x} - \boldsymbol{\mu})^T \mathbf{S}^{-1} (\mathbf{x} - \boldsymbol{\mu})}
Add your contribution
Related Hubs
User Avatar
No comments yet.