Coursify

K-means Clustering: Complete Algorithm, Objective, Convergence, and Limitations

K-means Clustering: Complete Algorithm, Objective, Convergence, and Limitations

Verified Sources
Nov 1, 2026

Lloyd’s / K-means Algorithm (Complete Procedure)

  1. 1
    Step 1

    Choose data points {xi}i=1n⊂Rd\{x_i\}_{i=1}^n\subset\mathbb{R}^d and a target KK. Pick a distance measure; standard K-means uses squared Euclidean distance.

  2. 2
    Step 2

    Select initial centroid locations μ1,…,μK\mu_1,\dots,\mu_K (often random observations or a smarter seeding method such as kk-means++).

  3. 3
    Step 3

    For each xix_i, assign it to the closest centroid:   c(i)=arg⁡min⁡k∈{1,…,K}∥xi−μk∥22\;c(i)=\arg\min_{k\in\{1,\dots,K\}}\|x_i-\mu_k\|_2^2.

  4. 4
    Step 4

    For each cluster kk, recompute the centroid as the mean of points assigned to kk:   μk=1∣Ck∣∑xi∈Ckxi\;\mu_k=\frac{1}{|\mathcal{C}_k|}\sum_{x_i\in\mathcal{C}_k}x_i.

  5. 5
    Step 5

    Stop if assignments no longer change (or if the objective/centroid movement improves less than a tolerance), otherwise go back to the Assignment step.

  6. 6
    Step 6

    "Return final assignments C1,…,CK\mathcal{C}_1,\dots,\mathcal{C}_K and final centroids μ1,…,μK\mu_1,\dots,\mu_K."

    Convergence: Objective Decrease and When It Stops

    1) Why it converges (monotonic non-increase of WCSS)

    K-means/Lloyd’s algorithm alternates two operations that do not increase the objective:

    • With centroids fixed, the assignment step chooses the nearest centroid for every point (so WCSS can only decrease or stay equal).
    • With assignments fixed, the centroid update recomputes each centroid as the mean (which minimizes the within-cluster sum of squares for that cluster).

    Therefore, the WCSS sequence is non-increasing across iterations. 2 Non-increase plus a finite number of possible partitions implies the method must reach a stable state (no further improvement by reassignment), i.e., convergence. 2

    2) Practical convergence criteria (stopping rules)

    Common convergence criteria described in learning materials include:

    • Assignment-stability criterion
    • Centroid-stability criterion
    • Objective-stability criterion

    A typical rule is: stop when assignments no longer change (or equivalently when WCSS becomes stable), or when a maximum number of iterations is reached. 2

    3) What “convergence” guarantees—and what it doesn’t

    • K-means does converge in the sense that it reaches a fixed point / stable partition under the standard Lloyd updates because the objective cannot keep decreasing indefinitely.
    • K-means does not guarantee the global optimum of the K-means objective; it may converge to a local optimum depending on initialization. This limitation is explicitly emphasized in standard discussions of Lloyd’s/K-means behavior. 2

    Major Limitations (Why K-means is not universally reliable)

    Limitation A: Sensitivity to initialization (local minima / different outcomes)

    Because K-means is an iterative heuristic that can settle into a locally optimal clustering, different initial centroids can lead to different final solutions. This sensitivity to initialization and the possibility of local minima are widely noted limitations of K-means. 2

    Implications

    • You often run K-means multiple times and keep the best (lowest WCSS) solution.
    • Initialization strategies like kk-means++ are commonly used to improve seeding quality (though they don’t remove all limitations).

    Limitation B: Assumes spherical-ish clusters of comparable scale

    The K-means objective (squared Euclidean distance to centroids) effectively favors clusters that are roughly spherical and similar in variance; elongated, crescent-shaped, or otherwise non-spherical clusters are not well matched to the centroid/Euclidean geometry. Many practical guides highlight this “shape mismatch” as a fundamental issue for K-means. 2

    Limitation C: Convergence to a local optimum, not global optimum

    Even though the algorithm’s WCSS decreases monotonically, it may stop at a local minimum instead of the global minimum of the objective. Standard references explicitly distinguish “converges” from “finds the global optimum.” 2

    Limitation D: Choice of KK (model selection issue)

    K-means assumes you already know the number of clusters KK. Wrong KK can produce misleading clusters even if the algorithm converges. This “need to pre-specify KK” is repeatedly listed as a core practical limitation in K-means overviews. 2

    Limitation E: Outliers can distort centroids

    Since centroids are means, outliers can pull centroids toward themselves, changing cluster boundaries. Practical discussions of K-means limitations frequently call out outlier sensitivity. 2

    When K-means Works Well (Design/Modeling Guidelines)

    Footnotes

    1. Unsupervised learning - Describes Lloyd’s algorithm iterations and non-increasing objective; includes pseudocode and stopping when assignments stop changing. ↩ ↩2 ↩3 ↩4

    2. k-means clustering - Wikipedia - Notes WCSS monotonic decrease, convergence when assignments stabilize, and lack of global optimum guarantee. ↩ ↩2 ↩3 ↩4

    3. L15: Convergence of K-means algorithm - Explains monotonic objective decrease and finiteness of partitions leading to convergence (lecture transcript). ↩

    4. 1 Clustering 2 The k-means criterion - Discusses Lloyd’s/K-means algorithm steps, drawbacks like expensive global optimum verification and different initializations yielding different solutions. ↩ ↩2 ↩3

    5. Deep (Deep, Deep) Dive into K-Means Clustering - Explicitly discusses sensitivity to initialization and local minima; outlines common mitigation strategies. ↩

    6. K-means Clustering: Algorithm - Interactive - Highlights spherical/size assumptions and practical pitfalls including scaling. ↩ ↩2 ↩3

    7. K-means Clustering – Introduction - GeeksforGeeks - Lists common K-means operational steps and mentions stopping when centroids stabilize or max iterations reached. ↩ ↩2 ↩3

Fit K-means to problems with centroid-appropriate structure

Use K-means when clusters are roughly convex/spherical under squared Euclidean distance, and when outliers are limited or handled (e.g., robust scaling or preprocessing). Shape mismatch is a common failure mode for K-means. 2

Footnotes

  1. K-means Clustering: Algorithm - Interactive - Highlights spherical/size assumptions and practical pitfalls including scaling. ↩

  2. K-means Clustering – Introduction - GeeksforGeeks - Lists common K-means operational steps and mentions stopping when centroids stabilize or max iterations reached. ↩

Do not confuse monotone convergence with optimality

"K-means monotonically decreases WCSS each iteration, so it converges—but this does not guarantee the global optimum. Different initializations can land you in different local minima. 2"

Algorithm Intuition: Why the Centroid Update is the Mean

In the centroid update step, assigning points to a cluster kk fixes the set Ck\mathcal{C}_k. Choosing μk\mu_k to minimize ∑xi∈Ck∥xi−μk∥22\sum_{x_i\in \mathcal{C}_k}\|x_i-\mu_k\|_2^2 yields μk\mu_k as the arithmetic mean. This is the mathematical reason the update step recomputes the mean and why Lloyd-style iterations improve the objective. Standard instructional materials explicitly describe “update centroids by computing the mean of points assigned to each cluster.” 2

Summary Table: Objective, Convergence, and Limitations

Footnotes

  1. Unsupervised learning - Describes Lloyd’s algorithm iterations and non-increasing objective; includes pseudocode and stopping when assignments stop changing. ↩ ↩2

  2. 1 Clustering 2 The k-means criterion - Discusses Lloyd’s/K-means algorithm steps, drawbacks like expensive global optimum verification and different initializations yielding different solutions. ↩

  3. Chapter 20 K-means Clustering | Hands-On Machine Learning with R - Describes centroid recomputation as mean of assigned points and iterative repetition until assignment stability. ↩

K-means: Objective, Convergence Behavior, and Main Limitations

Qualitative mapping of how each aspect affects outcomes (higher = more impactful in practice).

Common Edge Cases & Clarifications

Convergence of K-means (Lloyd’s Algorithm) — Monotonic Objective Decrease

Knowledge Check

Question 1 of 4
Q1Single choice

What is the standard K-means objective function (for Euclidean distance)?

Explore Related Topics

1

Machine Learning: Foundations, Methods, Workflow, and Responsible Practice

Machine learning enables computers to learn predictive functions f(data,model,training)f(\text{data},\text{model},\text{training}) from data, covering supervised, unsupervised, and reinforcement paradigms, their workflows, algorithms, and responsible practices.

  • Supervised (classification, regression), unsupervised (clustering, dimensionality reduction), and reinforcement learning each use distinct training signals and evaluation metrics such as accuracy, precision, recall, F1F_1, MSE, and silhouette score.
  • A typical project follows steps: define the problem, collect/inspect data, engineer features, split into train/validation/test, train and tune models, evaluate with appropriate metrics, then deploy and monitor for drift, fairness, and reliability.
  • Understanding the bias‑variance trade‑off and using cross‑validation helps avoid overfitting and improve generalization.
  • Traditional ML relies on manual feature engineering and works well on smaller structured data, while deep learning leverages multi‑layer neural networks for large unstructured datasets but demands more compute and is harder to interpret.
  • Responsible ML requires explainability, fairness assessments, ethical risk awareness, and ongoing monitoring to ensure models do not propagate bias or cause harm.
2

What Is the Use of a K-Map? (Karnaugh Map) for Boolean Minimization in Digital Logic

3

Output of KDD: Data, Information, Queries, and Useful Information

Browse all research articles