K-means Clustering › Example

Let's work through a concrete example of K-means clustering using a simple 2D dataset with 8 data points. This step-by-step calculation will help us understand exactly how the algorithm works.

Given Data Points: We have 8 points in 2D space:

• $A(1,\,1)$, $B(1,\,2)$, $C(2,\,1)$, $D(2,\,2)$
• $E(8,\,8)$, $F(8,\,9)$, $G(9,\,8)$, $H(9,\,9)$

We want to find $k=2$ clusters. Step 1: Initialization Let's randomly initialize two centroids:

• Centroid 1: $\mu_1 = (1.5,\ 1.5)$
• Centroid 2: $\mu_2 = (8.5,\ 8.5)$

Step 2: Assignment Step (First Iteration) For each point, we calculate the distance to both centroids and assign it to the nearest one.

For point $A(1, 1)$:

• Distance to $\mu_1$: $\sqrt{(1-1.5)^2 + (1-1.5)^2} = \sqrt{0.25 + 0.25} = \sqrt{0.5} \approx 0.707$
• Distance to $\mu_2$: $\sqrt{(1-8.5)^2 + (1-8.5)^2} = \sqrt{56.25 + 56.25} = \sqrt{112.5} \approx 10.61$
• $A$ is assigned to Cluster 1 (closer to $\mu_1$)

For point $E(8, 8)$:

• Distance to $\mu_1$: $\sqrt{(8-1.5)^2 + (8-1.5)^2} = \sqrt{42.25 + 42.25} = \sqrt{84.5} \approx 9.19$
• Distance to $\mu_2$: $\sqrt{(8-8.5)^2 + (8-8.5)^2} = \sqrt{0.25 + 0.25} = \sqrt{0.5} \approx 0.707$
• $E$ is assigned to Cluster 2 (closer to $\mu_2$)

Continuing this process for all points:

• Cluster 1: $A(1,1)$, $B(1,2)$, $C(2,1)$, $D(2,2)$
• Cluster 2: $E(8,8)$, $F(8,9)$, $G(9,8)$, $H(9,9)$

Step 3: Update Step (First Iteration)
Now we recalculate the centroids as the mean of points in each cluster.

For Cluster 1:
$\mu_1 = \left( \frac{1+1+2+2}{4},\ \frac{1+2+1+2}{4} \right) = (1.5,\ 1.5)$

For Cluster 2:
$\mu_2 = \left( \frac{8+8+9+9}{4},\ \frac{8+9+8+9}{4} \right) = (8.5,\ 8.5)$

Step 4: Convergence Check
The centroids haven't changed, so the algorithm has converged!

Final Result:

• Cluster 1: $\{A, B, C, D\}$ with centroid $(1.5,\ 1.5)$
• Cluster 2: $\{E, F, G, H\}$ with centroid $(8.5,\ 8.5)$

Verification:
Let's verify that no point would change clusters if we reassigned them:

• All points in Cluster 1 are closer to $(1.5,\ 1.5)$ than to $(8.5,\ 8.5)$
• All points in Cluster 2 are closer to $(8.5,\ 8.5)$ than to $(1.5,\ 1.5)$

The algorithm has successfully identified two distinct clusters in our data.

Let's visualize this step-by-step example to see how the algorithm works:

Here you can see the complete K-means process on our simple 8-point example, showing how the algorithm successfully identifies the two natural clusters in the data.

In this example we've chosen random initial centroids that conveniently were located in the middle of the two clusters to make the example simple. In practice, we should use the k-means++ initialization method to choose the initial centroids.