K-Means Clustering

K-means clustering lets you find groups in data without anyone telling you what the groups are. It is the first algorithm you meet in unsupervised learning — the branch of machine learning where there is no 'correct answer' to check against. Master this, and you unlock the rest of unsupervised learning: hierarchical clustering (where you build a tree of groups instead of picking a number in advance), DBSCAN and OPTICS (which find oddly-shaped clusters and label stray points as noise), and PCA (which compresses many features into a few). On top of that, k-means is the gateway to embeddings — the vectors that large language models use to represent words, sentences and documents. When you retrieve a passage from a knowledge base to answer a question in a RAG system, embeddings are often clustered with something like k-means to organise them. When you hear about 'semantic search' or 'similarity', that machinery often rests on ideas you will meet here.

K-means answers: given a pile of points, divide them into k groups so that points in the same group are close together, and points in different groups are far apart. Imagine you are a teacher sorting students into k study groups by ability. You might start by picking k students as 'representatives' (centroids). Then each student joins the nearest representative's group. After that, you compute the average of each group and move the representative there. You repeat: reassign every student to the nearest representative, recompute the averages, until no student changes group. That is k-means. It works when groups are roughly spherical (like blobs) and roughly equal in size. If a group is crescent-shaped, k-means will cut it in half. If one group is ten times bigger than another, k-means may split the big one and merge the small ones. It is simple, fast, and the go-to baseline for clustering — but its assumptions are often false in real data. Your library notes emphasise this: 'assumes spherical, similar-sized clusters — often false and rarely checked'. K-means is not a magic wand; it is a quick tool that works well when the blobs are blobs.

Think of a department store sorting its customers into k loyalty segments. The store knows each customer's average monthly spend and how many visits they make. They want to divide customers into k groups for targeted marketing. First, they pick k employees to be 'representative customers' — maybe one high-spender, one low-spender, one medium. Each customer is assigned to the employee most similar in spend and visits. The store then computes the average spend and visits for each group and promotes the 'average customer' of each group to be the new representative. They repeat: reassign customers to the nearest representative (now an average), compute new averages, until no one switches. The store ends up with k groups: 'bargain hunters', 'loyalists', 'occasional splurgers', etc. The analogy works because k-means is exactly this: assign to nearest, recompute prototypes, repeat. Where it breaks: real customer segments are not necessarily spherical blobs in spend-visit space. A 'bargain hunter' might visit often but spend little, or rarely but stock up on discounts — those form different shapes. K-means would force them into one or two blobs, possibly mixing distinct behaviours. Also, the store chose k in advance — but how many segments really exist? The elbow method (which we'll see) is a guess, not an answer. And the starting representatives matter: choose differently, get a different clustering — k-means++ reduces this risk but doesn't eliminate it.

K-means clustering partitions a set of points into k groups by (1) assigning each point to the nearest of k initial centroids, (2) recomputing each centroid as the average of its assigned points, and repeating until assignments stop changing.

You have not met any machine learning yet — this is your first. That is fine; k-means is the gentlest entry point. It belongs to unsupervised learning, because there is no target variable to predict; you are finding structure in unlabelled data. Your library lists hierarchical clustering, DBSCAN/OPTICS, and PCA as neighbours. Hierarchical clustering builds a tree of nested clusters, so you don't need to pick k in advance — you cut the tree afterwards. DBSCAN drops k-means' spherical assumption and labels noise points. PCA compresses many features into a few, which is often done before clustering to speed it up and reduce noise. K-means also connects to embeddings later: when you embed text into vectors, you might cluster those vectors to organise a knowledge base. So this is not an isolated trick; it is a foundation stone.