K-Means Clustering

1. Introduction

K-Means is the most widely used clustering algorithm, and often the first one people learn. It works by iteratively placing "centers" (centroids) and assigning each data point to its nearest center, gradually refining these centers until the clusters stabilize.

2. What is K-Means Clustering?

Simple definition: K-Means is a clustering algorithm that divides data into k groups by repeatedly assigning each point to its nearest cluster center, then updating each center to be the average position of its assigned points.

Technical explanation: K-Means partitions a dataset into k clusters by iteratively (1) assigning each data point to the nearest centroid (based on Euclidean distance) and (2) recalculating each centroid as the mean position of all points assigned to it, repeating until the centroids stabilize (converge) or a maximum number of iterations is reached.

3. Why is it Important?

• It's simple, fast, and scales well to large datasets, making it a common first choice for clustering tasks.
• It introduces the important concept of centroids and iterative refinement, ideas that recur throughout ML.
• It's widely used in real-world applications like customer segmentation and image compression.

4. Prerequisites

Comfort with Clustering fundamentals (Topic 1) and distance calculations (Module 4, Topic 4).

5. Core Concepts

1. Centroids (cluster centers)
2. The iterative assignment-update process
3. Choosing k (the Elbow Method)
4. Inertia / Within-Cluster Sum of Squares (WCSS)

6. Detailed Explanation

a) Centroids

A centroid is the "center point" of a cluster — specifically, the average position of all data points currently assigned to that cluster.

b) The Iterative Process

K-Means works in repeated rounds: (1) Assignment step — each data point is assigned to its nearest centroid; (2) Update step — each centroid is recalculated as the mean of all points now assigned to it. This repeats until the centroids stop moving significantly (convergence).

c) Choosing `k` (The Elbow Method)

Since k (the number of clusters) must be chosen before running K-Means, the Elbow Method helps find a reasonable value: plot the WCSS (see below) for different values of k, and look for the point where adding more clusters stops significantly reducing WCSS — this "elbow" point suggests a good balance between simplicity and fit.

d) Inertia / WCSS

Inertia (also called Within-Cluster Sum of Squares, WCSS) measures how tightly grouped the points within each cluster are — specifically, the sum of squared distances between each point and its assigned centroid. Lower inertia means tighter, more cohesive clusters.

7. How It Works

1. Choose the number of clusters, k.
2. Randomly initialize k centroids.
3. Assignment step: Assign each data point to its nearest centroid.
4. Update step: Recalculate each centroid as the mean of all points assigned to it.
5. Repeat steps 3–4 until centroids stop changing significantly (convergence) or a maximum number of iterations is reached.

8. Real-World Example

A retail company wants to group its stores into 3 categories based on average daily sales and foot traffic. K-Means would start with 3 random "center" points, assign each store to whichever center is closest, then move each center to the average position of its assigned stores, repeating this process until the 3 groups stabilize into meaningful store categories (e.g., "high-traffic urban," "moderate suburban," "low-traffic rural").

9. Mathematical Explanation

Centroid Update Formula:

centroidⱼ = (1/nⱼ) × Σ(pointsᵢ assigned to cluster j)

Where:

• centroidⱼ = the new center position for cluster j
• nⱼ = the number of points currently assigned to cluster j
• The sum is taken over all points currently assigned to cluster j

Inertia (WCSS) Formula:

WCSS = ΣΣ ||pointᵢ − centroidⱼ||²

Where:

• The outer sum is over all clusters j
• The inner sum is over all points i assigned to cluster j
• ||pointᵢ − centroidⱼ|| = the Euclidean distance between a point and its assigned centroid

Numerical Example:

Suppose Cluster 1 contains points: [2,3], [3,3], [2,4]

New centroid = ((2+3+2)/3, (3+3+4)/3) = (7/3, 10/3) ≈ (2.33, 3.33)

Interpreting the Result: The new centroid position represents the "average location" of all points currently in this cluster — in the next iteration, points will be re-checked against this updated centroid (and all other cluster centroids) to see if they should be reassigned to a different, now-closer cluster.

10. Python Example

python
from sklearn.cluster import KMeans
import numpy as np
import matplotlib.pyplot as plt

# Unlabeled 2D data with two visually distinct groups
X = np.array([
    [2, 3], [3, 3], [2, 4], [3, 4],
    [8, 8], [9, 8], [8, 9], [9, 9]
])

model = KMeans(n_clusters=2, n_init=10, random_state=42)
model.fit(X)

print("Cluster assignments:", model.labels_)
print("Centroid locations:\n", model.cluster_centers_)
print("Inertia (WCSS):", model.inertia_)

# Visualizing the clusters
plt.scatter(X[:, 0], X[:, 1], c=model.labels_, cmap="viridis")
plt.scatter(model.cluster_centers_[:, 0], model.cluster_centers_[:, 1],
            color="red", marker="X", s=200, label="Centroids")
plt.title("K-Means Clustering Result")
plt.legend()
plt.show()

Expected Output (approximate):

text
Cluster assignments: [0 0 0 0 1 1 1 1]
Centroid locations:
 [[2.5 3.5]
  [8.5 8.5]]
Inertia (WCSS): 4.0

11. Code Explanation

• KMeans(n_clusters=2, ...) specifies that we want the algorithm to find exactly 2 clusters.
• model.fit(X) runs the full iterative assignment-update process until convergence.
• model.labels_ shows which cluster (0 or 1) each data point was assigned to — correctly separating the two visually distinct groups.
• model.cluster_centers_ shows the final centroid position for each cluster.
• model.inertia_ gives the final WCSS value, indicating how tightly grouped the points are within their assigned clusters.
• The plot visually confirms the clustering result, marking centroids with a distinct red "X".

12. Advantages

• Simple, fast, and scales well even to fairly large datasets.
• Easy to understand and interpret, with a clear iterative process.
• Works very well when clusters are roughly spherical and similarly sized.

13. Limitations

• Requires specifying k in advance, which isn't always obvious without experimentation (Elbow Method).
• Assumes roughly spherical, similarly-sized clusters — struggles with irregular shapes or very differently sized clusters.
• Sensitive to the initial random placement of centroids (though n_init in Scikit-learn runs the algorithm multiple times with different initializations to mitigate this).
• Sensitive to outliers, which can significantly pull centroid positions.

14. Common Mistakes

• Not scaling features before applying K-Means, distorting distance-based cluster assignments.
• Choosing k arbitrarily without using the Elbow Method or domain knowledge to guide the choice.
• Assuming K-Means will correctly handle non-spherical or very unevenly sized clusters.
• Forgetting that K-Means results can vary between runs due to random centroid initialization (mitigated by setting random_state and using n_init).

15. Best Practices

• Scale features before applying K-Means (Module 3, Topic 7).
• Use the Elbow Method to help guide your choice of k.
• Set random_state for reproducibility, and consider n_init to run multiple initializations.
• Visualize resulting clusters (where feasible) to sanity-check that they make intuitive sense.

16. Real-World Applications

• Customer segmentation based on purchasing behavior.
• Image compression (grouping similar colors/pixels together).
• Document clustering by topic similarity.

17. Interview-Oriented Points

• Be ready to explain the iterative assignment-update process step by step.
• Understand the Elbow Method and how it helps choose k.
• Be able to explain why K-Means struggles with non-spherical clusters or significant outliers.

18. Exam-Oriented Points

• K-Means iteratively assigns points to the nearest centroid, then updates centroids as the mean of assigned points.
• k must be chosen in advance; the Elbow Method helps guide this choice using WCSS/inertia.
• K-Means assumes roughly spherical, evenly-sized clusters.

19. Comparison Table — K-Means vs Hierarchical Clustering (Preview)

20. Quick Revision

• K-Means iteratively assigns points to the nearest centroid, then recalculates centroids as the mean of assigned points, until convergence.
• k must be chosen beforehand; the Elbow Method (using WCSS/inertia) helps guide this choice.
• K-Means works best with roughly spherical, evenly-sized clusters and requires feature scaling for reliable distance calculations.
• Scikit-learn's KMeans class handles the entire iterative process via .fit().