K-Means Clustering Tool

Pseudocode

Two alternating steps, repeated until nothing moves. Assign every point to its nearest centroid, then move every centroid to the mean of its points.

KMeans(points, k):
    initialise k centroids       // see k-means++ below

    repeat until assignments stop changing:
        // Assignment step
        for each point p:
            cluster[p] = argmin over j of dist(p, centroid[j])

        // Update step
        for each cluster j:
            centroid[j] = mean of all points assigned to j

// k-means++ initialisation:
//   pick the first centroid uniformly at random, then pick
//   each next one with probability proportional to the
//   squared distance from the nearest chosen centroid

Each step can only reduce the within-cluster sum of squares, and there are finitely many possible assignments, so the algorithm must terminate. What it terminates at is a local minimum, not necessarily the global one, which is why initialisation matters so much and why k-means++ is worth the extra pass.

Worked example, step by step

Cluster four points into two groups, starting deliberately from a bad initialisation with both centroids inside the same true cluster.

Example graph: Points at (1,1), (2,1), (8,8) and (9,8). Two obvious clusters. Initial centroids placed at (1,1) and (2,1), both in the left-hand group.

1. Iteration 1, assign. Point (1,1) is exactly on the first centroid so joins cluster 0. Point (2,1) is exactly on the second so joins cluster 1. Points (8,8) and (9,8) are both nearer to (2,1) than to (1,1), so they also join cluster 1. Assignment is a lopsided one point against three.
2. Iteration 1, update. Cluster 0 has only (1,1) so its centroid stays there. Cluster 1 averages (2,1), (8,8) and (9,8) to (6.33, 5.67), a point sitting in empty space between the two real groups. The within-cluster sum of squares is 61.33.
3. Iteration 2, assign. Now (2,1) is much closer to (1,1) than to (6.33, 5.67), so it switches to cluster 0. Points (8,8) and (9,8) stay with cluster 1. The assignment is now two against two, which is correct.
4. Iteration 2, update. Centroids become (1.5, 1) and (8.5, 8), the true means of the two groups. The sum of squares collapses from 61.33 to 1.00.
5. Iteration 3, converged. Reassigning changes nothing and the centroids do not move, so the algorithm stops.

The algorithm recovers the correct clustering in two iterations despite a deliberately poor start, with the objective falling from 61.33 to 1.00. It recovered here because the true clusters are far apart. With overlapping clusters the same bad initialisation can converge to a genuinely wrong local minimum and stay there, which is the entire motivation for k-means++ and for restarting from several seeds.

Complexity, and where it comes from

Time: O(n·k·d·i) · Space: O(n + k·d)

Each iteration computes the distance from every one of n points to each of k centroids in d dimensions, giving O(n·k·d) per iteration, and the update step is a single O(n·d) pass. With i iterations the total is O(n·k·d·i). In practice i is small, usually tens rather than hundreds. The worst-case number of iterations is superpolynomial, and instances exist requiring exponentially many, but they never arise in practice. Note that this is the cost of finding a local optimum: finding the globally optimal k-means clustering is NP-hard even for k equal to 2, and even in the plane. Space is the assignment array at O(n) plus the centroids at O(k·d).

When to use K-Means Logistics Clustering, and when not to

k-means assumes spherical, similarly sized clusters and a known k. Break any of those assumptions and something else fits better.

Common pitfalls

• Using random initialisation instead of k-means++. Random seeding regularly converges to a poor local minimum, particularly when two centroids land in the same true cluster. k-means++ spreads the initial centroids by sampling proportional to squared distance and comes with an expected O(log k) approximation bound, for the cost of one extra pass.
• Not scaling the features. Euclidean distance is dominated by whichever feature has the largest numeric range. Clustering on income in dollars alongside age in years produces clusters based almost entirely on income. Standardise before clustering unless the raw scales are genuinely comparable.
• Assuming clusters are spherical and equally sized. The algorithm minimises squared distance to a mean, which implicitly assumes round clusters of similar spread. Elongated, nested or very unequally sized clusters get split or merged incorrectly no matter how good the initialisation.
• Picking k arbitrarily. The objective always improves as k grows, reaching zero when k equals n, so it cannot be used to choose k. Use the elbow method, silhouette scores, or a criterion such as BIC, and sanity-check the result against domain knowledge.
• Running it once and trusting the answer. The result depends on initialisation. Standard practice is to run it several times with different seeds and keep the clustering with the lowest within-cluster sum of squares.

Frequently asked questions

How does k-means clustering work?

It alternates two steps until convergence. First assign every point to the nearest of k centroids, then move each centroid to the mean of the points assigned to it. Both steps reduce the within-cluster sum of squares, and since there are finitely many possible assignments the process must terminate, at a local minimum.

What is the time complexity of k-means?

O(n·k·d·i) where n is the number of points, k the number of clusters, d the dimensionality and i the iteration count. Each iteration measures every point against every centroid. In practice i is small, though finding the globally optimal clustering is NP-hard even for two clusters in the plane.

How do you choose the number of clusters?

The objective always improves as k increases, so it cannot pick k for you. The elbow method plots within-cluster sum of squares against k and looks for the bend where returns diminish. Silhouette scores measure how well each point fits its cluster relative to the next nearest. Both should be checked against what the clusters mean in context.

What is k-means++ and why does it matter?

It is an initialisation scheme that chooses the first centroid uniformly at random and then each subsequent one with probability proportional to the squared distance from the nearest already-chosen centroid. That spreads the starting centroids apart, avoiding the common failure where two land in the same true cluster, and it gives an expected approximation ratio of O(log k).

When should I not use k-means?

When clusters are non-spherical, of very different sizes or densities, or when the data has significant outliers, since the mean is not robust to them. Also when k is genuinely unknown and no good criterion exists. DBSCAN handles arbitrary shapes and noise, Gaussian mixtures handle elliptical overlapping clusters, and k-medoids handles outliers and non-Euclidean distances.