K-Means Clustering Explained: A Practical Guide with Real-World Example

📗 Chapter 2: How K-Means Works – Step-by-Step Breakdown

🎯 Objective

This chapter breaks down the inner mechanics of the K-Means algorithm. You’ll learn what happens at each iteration — from initializing centroids to forming final clusters — and how convergence is achieved through mathematical optimization.

🧩 K-Means: The Core Idea

K-Means aims to partition data into K clusters by minimizing the distance between points and their cluster centroid. The process is iterative and involves:

• Initializing centroids
• Assigning points to the nearest centroid
• Recalculating centroids
• Repeating until stabilization

This method is known as Lloyd’s algorithm.

⚙️ Step-by-Step Workflow

Let’s go step-by-step into what K-Means actually does under the hood.

🔹 Step 1: Choose the Number of Clusters (K)

Before starting, you must define K, the number of clusters. This can be based on:

• Domain knowledge
• Trial and error
• Techniques like the Elbow Method or Silhouette Score

🔹 Step 2: Initialize Centroids Randomly

• K points are chosen randomly from the dataset as initial centroids
• Alternatively, use K-Means++ to spread them out better

🔹 Step 3: Assign Each Point to the Nearest Centroid

• Calculate the Euclidean distance from each data point to each centroid
• Assign each data point to the cluster with the closest centroid

Mathematically:

🔹 Step 4: Update Centroids

• For each cluster, recalculate the centroid as the mean of all points assigned to it

🔹 Step 5: Repeat Until Convergence

• The algorithm continues repeating steps 3 and 4
• Convergence occurs when assignments no longer change, or the change in centroids is minimal

🔁 Pseudocode of K-Means

text

1. Select K initial centroids randomly

2. While centroids do not stabilize:

    a. Assign data points to nearest centroid

    b. Recalculate centroids

🧮 Key Formula – Within-Cluster Sum of Squares (WCSS)

K-Means attempts to minimize WCSS.

🧠 Example Table

🏁 How K-Means Converges

Convergence can be determined by:

• Centroids stop moving
• Assignments do not change
• Max iterations reached

K-Means generally converges fast (in a few iterations), but not necessarily to the global optimum.

📋 Choosing Initialization Strategy

🧪 Example: Iterative Clustering

Let’s say we have three clusters. On each iteration:

1. Assign data points to the closest centroid
2. Move the centroid to the mean of its assigned points
3. Check if the assignment has changed
4. Repeat until no further changes occur

This loop creates progressively tighter, more cohesive clusters.

🚧 Problems with Random Initialization

• Different runs can produce different results
• You might land in a local minimum
• Some clusters might end up empty

Solution: Use K-Means++ to initialize centroids.

🔍 Best Practices

• Always scale features
• Run K-Means multiple times with different seeds
• Use Elbow Method for selecting K
• Plot convergence of WCSS or inertia

✅ Summary Table