k-Means Clustering

Analogy categoryAnalogies

k-Means is the most widely used clustering algorithm, and it belongs to unsupervised learning because it discovers structure in data without any labeled examples to learn from. Given a dataset and a chosen number of clusters k, the algorithm partitions the data into k groups such that points within a group are as similar as possible (measured by distance to a group centroid) and groups are as distinct as possible from each other. Unlike classification, there is no ground truth being predicted — the algorithm is simply finding structure that already exists in the feature space.

🏏

Cricket analogy: Grouping domestic players purely by their raw stat profiles — strike rate, economy, catches — without any predefined 'star' or 'role player' labels lets natural groupings emerge on their own, the way a scout might discover a cluster of all-rounders nobody had explicitly categorized before.

The Algorithm

k-Means works iteratively in two alternating steps, starting from k randomly (or smartly, via k-means++) initialized centroids. In the assignment step, every data point is assigned to the nearest centroid, forming k clusters. In the update step, each centroid is recomputed as the mean of all points currently assigned to it. These two steps repeat until assignments stop changing (convergence) or a maximum iteration count is reached. This procedure is guaranteed to converge, but it minimizes a non-convex objective (within-cluster sum of squares), so it can converge to a local rather than global minimum — which is why k-means is typically run multiple times with different random initializations and the best result (lowest inertia) is kept.

🏏

Cricket analogy: Starting from a few randomly chosen 'reference' players (centroids), every other player is grouped with whichever reference they resemble most (assignment); then each group's new reference becomes the average stat profile of its members (update), repeating until groups stop changing — but a bad initial pick can settle into a mediocre grouping, so analysts rerun this from several starting points and keep the tightest result.

Choosing k

k-Means requires the number of clusters to be specified in advance, which is often unknown. The elbow method plots inertia (within-cluster sum of squared distances) against k and looks for the point where adding more clusters yields diminishing returns — the 'elbow' of the curve. The silhouette score offers a more rigorous alternative: it measures, for each point, how similar it is to its own cluster compared to the nearest other cluster, producing a score from -1 to 1 that can be averaged across all points to compare different values of k objectively, without relying on visual judgment of an elbow that isn't always clearly visible.

🏏

Cricket analogy: Plotting how much a team's 'style diversity' score improves as you add more player categories and looking for the point where extra categories stop helping (the elbow) is one way to pick the right number of groups; a silhouette-style score comparing each player to their own category versus the next-closest one gives a more objective answer when the elbow isn't clear.

python

import numpy as np
from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import silhouette_score

X, _ = make_blobs(n_samples=500, centers=4, cluster_std=1.2, random_state=42)
X_scaled = StandardScaler().fit_transform(X)

# Evaluate several values of k using silhouette score
best_k, best_score = None, -1
for k in range(2, 8):
    km = KMeans(n_clusters=k, n_init=10, random_state=42)
    labels = km.fit_predict(X_scaled)
    score = silhouette_score(X_scaled, labels)
    print(f'k={k}: silhouette={score:.3f}, inertia={km.inertia_:.1f}')
    if score > best_score:
        best_k, best_score = k, score

print(f'Best k by silhouette score: {best_k}')

k-means++ initialization, scikit-learn's default, spreads out initial centroids probabilistically (favoring points far from already-chosen centroids) rather than picking them fully at random. This dramatically reduces the chance of poor local minima compared to naive random initialization and is why most production k-means runs converge faster and more reliably today.

k-Means assumes clusters are roughly spherical and similarly sized because it relies on Euclidean distance to a single centroid. It performs poorly on elongated, unevenly sized, or non-convex clusters — for those shapes, DBSCAN or hierarchical clustering are usually better choices. Always scale features first, since unscaled features distort Euclidean distances.

k-Means partitions data into k clusters by alternating between assigning points to the nearest centroid and recomputing centroids.
The algorithm minimizes within-cluster sum of squared distances (inertia) but can converge to a local minimum.
k-means++ initialization improves convergence quality over naive random initialization.
The elbow method and silhouette score are the two standard techniques for choosing k.
k-Means assumes roughly spherical, similarly-sized clusters and is sensitive to feature scale and outliers.
Multiple random restarts (n_init) and keeping the lowest-inertia result mitigate the local minimum problem.

Practice what you learned

1. What are the two alternating steps in the k-means algorithm?

2. Why might k-means converge to a local rather than global minimum?

3. What does the silhouette score measure?

4. What assumption does k-means implicitly make about cluster shape?

5. Why is feature scaling important before running k-means?

Was this page helpful?

Hierarchical Clustering

Topics covered

#Python#MachineLearningBasicsStudyNotes#MachineLearning#KMeansClustering#Means#Clustering#Algorithm#Choosing#StudyNotes#SkillVeris

k-Means Clustering