K-means clustering explained: worked examples for exam revision

K-means clustering is an unsupervised machine learning algorithm that groups unlabelled data into a pre-defined number of distinct clusters, represented by the variable K. It achieves this by iteratively assigning each data point to the nearest cluster centre and then recalculating those centres until the groupings stop changing. This process minimises the variance within each cluster, effectively grouping similar data points together based on their mathematical features.

As a university student revising for your machine learning exams, you need to understand both the mechanics of this algorithm and the mathematical assumptions behind it. K-means is a staple of introductory modules because it is mathematically straightforward and computationally efficient. It is one of the most widely taught algorithms in university computer science and statistics departments because it offers a foundational understanding of how machines can find hidden patterns without human guidance.

However, examiners frequently test your knowledge of its limitations, specifically its strict reliance on distance metrics and its sensitivity to initial conditions. Let us break down exactly how the algorithm works, look at a numerical example you can replicate on paper, and review how to demonstrate your critical understanding to an examiner.

The core algorithm step by step

To apply K-means clustering, you must first define your dataset and choose your target value for K. The algorithm then follows a strict, repeatable sequence of operations.

Step 1: Initialisation. The algorithm selects K random points from the dataset to act as the initial cluster centres. These centres are known as centroids.

Step 2: Assignment. The algorithm calculates the physical distance between every single data point and each of the K centroids. The most common measurement used here is Euclidean distance. Each data point is then assigned to the cluster of its nearest centroid.

Step 3: Update. Once all data points are assigned to a cluster, the algorithm calculates the new mean position of all the points within each specific cluster. This newly calculated mean coordinate becomes the updated centroid for that group.

Step 4: Convergence. Steps 2 and 3 repeat in a loop. The algorithm stops when the centroids no longer move, when the assignments stop changing, or when a pre-determined maximum number of iterations is reached. At this stage, the algorithm has converged.

A concrete worked example in two dimensions

Let us look at a miniature dataset. Imagine you have four data points representing the age and income of four individuals, scaled down to small integers for the sake of simplicity.

Point A is at coordinates (1, 1). Point B is at (2, 1). Point C is at (4, 3). Point D is at (5, 4).

You are asked to cluster this data into two groups (K=2) and show your working for one full iteration.

First, we initialise our centroids. We will randomly select Point A (1, 1) as Centroid 1 and Point C (4, 3) as Centroid 2.

Now we enter the assignment step. We must calculate the Euclidean distance from each point to both centroids. The formula for squared Euclidean distance between two points (x1, y1) and (x2, y2) is the sum of the squared differences of their coordinates. We use squared distances here because calculating the square root is entirely unnecessary for simply comparing which distance is smaller, saving you valuable time in an exam setting.

The distance from Point A (1, 1) to Centroid 1 (1, 1) is 0. The distance to Centroid 2 (4, 3) is 9 plus 4, which equals 13. Because 0 is smaller than 13, Point A belongs to Cluster 1.

The distance from Point B (2, 1) to Centroid 1 is 1 plus 0, which equals 1. The distance to Centroid 2 is 4 plus 4, which equals 8. Because 1 is smaller than 8, Point B belongs to Cluster 1.

The distance from Point C (4, 3) to Centroid 1 is 9 plus 4, which equals 13. The distance to Centroid 2 is 0. Point C belongs to Cluster 2.

The distance from Point D (5, 4) to Centroid 1 is 16 plus 9, which equals 25. The distance to Centroid 2 is 1 plus 1, which equals 2. Point D belongs to Cluster 2.

Next, we perform the update step. We calculate the new centroids by finding the mean coordinates of the assigned points in each cluster.

Cluster 1 currently contains Point A (1, 1) and Point B (2, 1). The mean of the x coordinates (1 and 2) is 1.5. The mean of the y coordinates (1 and 1) is 1. Therefore, the new Centroid 1 moves to (1.5, 1).

Cluster 2 contains Point C (4, 3) and Point D (5, 4). The mean of the x coordinates (4 and 5) is 4.5. The mean of the y coordinates (3 and 4) is 3.5. Therefore, the new Centroid 2 moves to (4.5, 3.5).

If you repeat the assignment step using these new centroids, the assignments for Points A, B, C, and D will remain identical. Because the cluster assignments have not changed, the algorithm has successfully converged.

Choosing the right value for K

In an exam scenario, you will often be asked how to determine the optimal number of clusters when the correct answer is not known in advance. The standard technique expected by examiners is the elbow method.

To use the elbow method, you run the K-means algorithm multiple times, starting with K=1 and increasing the value by one for each subsequent run. For each run, you calculate the within-cluster sum of squares. This metric represents the sum of the squared distances between each individual data point and its assigned centroid.

When K=1, the within-cluster sum of squares is at its absolute highest because all data points in the entire dataset are measured against a single centre. As you increase the value of K, the sum of squares naturally decreases. If K equals the total number of data points, the sum of squares drops to zero because every point becomes its own independent centroid.

If you plot the sum of squares against the value of K on a line graph, the line will curve downwards. You are looking for the exact point on the graph where the rate of decrease sharply slows down, creating an angle that looks like a bent elbow. This inflection point represents a mathematical sweet spot where you have achieved good clustering performance without overfitting the model with too many unnecessary groups.

Key limitations you must know

Exam questions frequently present a visual dataset and ask you to identify why standard K-means might fail to cluster it effectively. There are three major limitations you should commit to memory.

First, the algorithm assumes that clusters are spherical and roughly equal in size. Because it relies purely on radial distance from a central point, it struggles with elongated shapes, nested circles, or intersecting lines. If an exam question shows two crescent-shaped clusters wrapped around one another, you must state that K-means will fail and suggest a density-based algorithm like DBSCAN instead.

Second, the algorithm is highly sensitive to outliers. A single extreme data point will drag a centroid far away from the true centre of a dense cluster. This happens because the algorithm uses mean values and squared distances, which mathematically over-penalise large deviations.

Third, the final clusters depend heavily on the initial random placement of the centroids. If the initial centroids are placed poorly, the algorithm can converge on a local minimum rather than the true global optimum. This is why data scientists typically run the algorithm multiple times with different random seeds and select the single run that produces the lowest within-cluster sum of squares.

How to answer this in an exam

Examiners do not just want to see that you can perform the basic arithmetic. They want to test your practical judgement as a data scientist. When writing your answers, keep the following mark scheme requirements in mind.

Always mention standardisation. If a question asks you to prepare a dataset for K-means, state clearly that all features must be scaled or standardised to have a mean of zero and a standard deviation of one. If you fail to do this, a feature measured in thousands (like an annual salary) will completely dominate a feature measured in single digits (like years of experience) simply because the mathematical distance values are much larger.

Be precise with your terminology. Do not write that the algorithm “finds groups”. Write that it “minimises within-cluster variance”. Use correct technical terms like “local optimum”, “centroid”, and “Euclidean distance”.

If asked about time complexity, state that standard K-means is O(nki), where n is the number of data points, k is the number of clusters, and i is the number of iterations. Because k and i are usually small constants, you can note that the algorithm scales linearly with the number of data points, making it highly efficient for large datasets.

You can find more examples of how to secure full marks on these specific questions in the Full Marks Press Data Science and Data Mining guide, which covers this algorithm extensively with worked exam questions and annotated student answers.

FAQ

What happens if K-means does not converge? In theory, the algorithm is guaranteed to converge in a finite number of steps because there is a finite number of possible cluster assignments. However, for massive datasets, reaching absolute convergence can take too long. In practice, you set a maximum iteration limit to force the algorithm to stop computing if the centroids are only making microscopic, insignificant adjustments.

Why must we standardise data before applying K-means? The algorithm groups points based on physical distance in a mathematical space. If one variable is measured in kilometres and another in millimetres, the larger numbers will disproportionately influence the distance calculation. Standardising forces all variables to contribute equally to the final clusters.

How does K-means++ differ from standard K-means? Standard K-means selects initial centroids entirely at random, which can lead to poor clustering if the initial points are too close together. K-means++ adds a probabilistic step to the initialisation phase, ensuring the starting centroids are spread as far apart from each other as possible. This speeds up convergence and helps avoid local minima.

Can K-means handle categorical data? No. The algorithm relies on calculating a mathematical mean to update the centroid positions. You cannot calculate the mean of categorical variables like “red”, “blue”, or “green”. For datasets with categorical variables, you must use an alternative algorithm such as K-modes.

To master algorithms like this and practice your exam technique, get a free copy of our revision fundamentals at fullmarkspress.com/free.