ENID
Lensa ML

K-Means Clustering

Step 1 of 6: What is Clustering?

Grouping without labels

unlabeled data
Points
60
Clusters
3
Separation
4.9

Clustering finds natural groups in unlabeled data. Slide k to change how many true clusters exist, then reveal them.

Drag the number of clusters (k) slider from 2 to 5, then click Reveal Clusters to color each point by the group it was generated from. The separation card divides the average distance between cluster centers by the average spread within a cluster, so a higher value means groups that are easier to tell apart. In real problems the true groups are unknown, which makes a clustering hard to judge. Internal scores such as the silhouette coefficient compare each point's distance to its own cluster with its distance to the next nearest one.

Step 2 of 6: How K-Means Works

The algorithm step by step

k = 3 clusters to find
Phase
1/6
k
3
Reassigned
—
Inertia
—

The data is unlabeled, and the goal is to find k=3 clusters in it.

Click the six phase buttons in order, or drag the phase slider. This procedure is Lloyd's algorithm, described by Stuart Lloyd at Bell Labs in 1957 and published in 1982. Each iteration costs O(n · k · d) for n points, k centroids, and d dimensions, because every point is compared with every centroid. On this data the run settles after five updates. Random starting centroids can land badly, so the k-means++ method picks each new starting centroid with probability proportional to its squared distance from the centroids already chosen.

Step 3 of 6: Assignment Step

Color by nearest centroid

Iteration: 0
Iteration
0
Reassigned
60
Inertia
929.0
Largest
35

Each point joins its nearest centroid, which splits the plane into Voronoi regions. Press Play or drag the slider.

Press Play or drag the iteration slider and watch points change color. With the centroids held fixed, giving each point its nearest centroid is the lowest-inertia assignment possible, so this step solves its half of the problem exactly. The boundary between two clusters is the perpendicular bisector of the segment joining their centroids, which makes every region a convex polygon. Elongated or curved clusters get cut apart by these straight boundaries. Because the rule uses Euclidean distance, features on larger scales dominate, and data is usually standardized first.

Step 4 of 6: Update Step

Move centroids to their means

Iteration: 1
Iteration
1
Max disp
3.11
Inertia
287.7
% change
-69.0%

Centroids moved by up to 3.11 units, each toward the mean of its cluster.

Press Play or drag the iteration slider and follow the dashed arrows. For a fixed set of points, the mean is the location that minimizes the sum of squared distances, so this step also solves its half exactly. That is why k-means pairs means with squared Euclidean distance. Using the median with Manhattan distance gives k-medians, and requiring each center to be an actual data point gives k-medoids, which works with any distance. Mini-batch k-means updates the centroids from small random samples so it can handle millions of points.

Step 5 of 6: Convergence

When assignments stop changing

Iteration: 0
IterationInertia05101576526975
Iteration
0
Inertia
929.0
Δ inertia
—
Converged?
No

K-means stops when no point changes its assignment. Press Play and watch inertia drop.

Press Play or drag the iteration slider across the 15 iterations and watch the inertia curve. Inertia never increases, because each step is optimal for its half of the problem, and there are only finitely many ways to assign points to clusters, so the algorithm must stop. Here inertia falls from 929 to 86 within two updates. The stopping point can be a local optimum, and finding the global optimum is NP-hard in general. Libraries therefore run several random starts and keep the lowest inertia; scikit-learn's n_init parameter sets how many.

Step 6 of 6: The Elbow Method

Choosing the right k

k (clusters)Inertia12345678910elbow
k
3
Inertia
84.8
Δ inertia
306.3
Suggested k
3

The elbow: past k=3, each extra cluster cuts inertia much less. This is the usual choice.

Drag k from 1 to 10 and compare the inertia readouts. Inertia always falls as k grows and reaches zero when every point is its own cluster, so the lowest value is not the goal. Here the drop from k = 2 to k = 3 is about 306, while the drop from k = 3 to k = 4 is only about 13. That bend marks the elbow at 3, matching the 3 groups the data was generated from. Real curves often bend less clearly, and the silhouette score or the gap statistic can help choose k.

What is k-means clustering?

K-means is an unsupervised clustering algorithm that splits data into k groups, assigning each point to the cluster with the nearest center, called a centroid. It alternates two steps, assigning points to their nearest centroid and moving each centroid to the mean of its points, until the assignments stop changing. The result minimizes, at least locally, the total squared distance from points to their centroids.

K-means is used for customer segmentation, image color quantization, grouping documents, and compressing embedding vectors, as in the vector quantization inside approximate nearest-neighbor indexes. It is fast and simple, but it assumes roughly round clusters of similar size, and k has to be chosen in advance.

Key ideas

  • K-means splits data into k clusters, each represented by the mean of its points.
  • It alternates an assignment step and an update step until the assignments stop changing.
  • Both steps lower the inertia, the total squared distance from points to their centroids.
  • It always converges, but often to a local optimum that depends on the starting centroids.
  • k-means++ initialization and several random restarts make a good result much more likely.
  • The elbow of the inertia curve is a common heuristic for choosing k.

Short takes on this topic

Common questions

What is the difference between k-means and k-NN?

K-means is unsupervised clustering, and its k is the number of clusters it finds. k-nearest neighbors is supervised classification or regression, and its k is the number of labeled neighbors that vote. Both depend on distances, which is the main source of the confusion.

When does k-means fail?

It struggles when clusters are elongated, curved, nested, or very different in size or density, because it draws straight boundaries halfway between centroids. Outliers also drag centroids away from the bulk of a cluster. DBSCAN handles arbitrary shapes and noise, and Gaussian mixture models handle elliptical clusters of different sizes.

How is k-means related to Gaussian mixture models?

A Gaussian mixture fitted with expectation-maximization gives each point a soft probability of belonging to each cluster. If every component has the same small spherical variance, those soft assignments become hard nearest-centroid assignments, and the algorithm reduces to k-means.

Does k-means need feature scaling?

Usually. Squared Euclidean distance adds up differences across features, so a feature measured in large units dominates the clustering. Standardizing each feature first gives all of them a comparable influence, unless the original units are meaningful and comparable.

Related explainers

References

  1. Lloyd (1982), "Least Squares Quantization in PCM", IEEE Transactions on Information Theory
  2. James, Witten, Hastie & Tibshirani, "An Introduction to Statistical Learning", chapter 12: Unsupervised Learning

Last updated