Clustering and the k-Means Algorithm

Hello students, welcome to Kwickprep. A shop has one lakh customers but no labels saying who is a bargain hunter and who is a big spender. Can a computer still find groups? Yes, it can. Today we learn clustering, watch k-Means move its centres step by step, choose the number of clusters, and see real uses.

First, a new word. Clustering means putting similar items into the same group, called a cluster. Unlike classification, nobody tells the computer the correct group for any item. Learning from data without labels is called unsupervised learning. The algorithm studies the data and discovers the groups by itself.

Board exams often ask for this difference, so let us compare. In classification, the training data has labels, but in clustering it has none. Classification is supervised learning, while clustering is unsupervised learning. In classification the groups are fixed in advance, but clustering finds groups from the data. Spam filtering is classification, while finding customer groups is clustering.

The most popular clustering algorithm is k-Means. Here, k is the number of clusters we ask for. A centroid is the centre point of one cluster. We find a centroid by taking the average, or mean, of all points in that cluster, which gives k-Means its name. Each point joins the cluster whose centroid is nearest to it.

Here is the whole algorithm as a flowchart. First, choose k starting centroids, often picked at random from the data. Next, assign every point to its nearest centroid. Then move each centroid to the mean of the points assigned to it. Now ask, did any point change its cluster? If yes, go back and assign again; if no, the clusters are final.

Let us watch k-Means work on six students' marks, with k equal to two. Asha scored twenty. Ravi scored twenty five. Meena scored thirty. Kabir scored seventy. Sana scored eighty. Dev scored ninety.

We start with two centroids placed at twenty five and thirty. The first centroid is nearest to twenty and twenty five, so those two join it. The second centroid, at thirty, is nearer to thirty, seventy, eighty and ninety, so all four join it.

Now each centroid moves to the mean of its points. The first centroid moves to twenty plus twenty five, divided by two, which is twenty two point five. The second moves to the sum two hundred seventy, divided by four, which is sixty seven point five. Watch how the second centroid jumps a long way to the right.

Now we assign every point again with the new centroids. Twenty is only two point five away from the first centroid. Twenty five is also closer to the first centroid. Pause and predict: where does thirty go now? It is seven point five from the first but thirty seven point five from the second, so Meena switches clusters. Seventy, and also eighty and ninety, stay with the second centroid.

Now we move the centroids again. The first cluster holds twenty, twenty five and thirty, so its mean is twenty five. The second holds seventy, eighty and ninety, so its mean is eighty. In round three, no point changes cluster, so the algorithm stops. We found two natural groups: students who need extra help, and high scorers.

How many clusters should we ask for? Choosing k is our job, because k-Means cannot pick it by itself. With too few clusters, very different items are forced into one group. With too many clusters, one real group gets split into tiny pieces. The elbow method helps: we run k-Means for k equal to one, two, three and more, and plot how spread out the clusters are. Finally, we ask what the business needs, like how many offers a shop can run.

Here is an elbow table for a shop's customer data, not our marks. Spread means the total squared distance of points from their centroids, so lower is tighter. With one cluster, the spread is five thousand. With two clusters, it falls sharply to twelve hundred. With three, it falls only a little, to nine hundred. With four, the drop is small again, so the bend, or elbow, is at k equal to two.

Clustering is used widely in real life. Shopping apps group customers by buying habits, and send each group suitable offers. News apps group articles about the same event together. Banks group normal transactions, so a payment that fits no group can be checked for fraud. Delivery companies group addresses to decide where to place warehouses. Photo tools group similar colours to make image files smaller.

Like every algorithm, k-Means has limits. We must decide k before we start. Different starting centroids can lead to different final clusters, so we often run it several times. An outlier, which is a value far from all others, can pull a centroid away. And it works best when clusters are roughly round and similar in size.

Let us revise what we learned today. Clustering groups data that has no labels, so it is unsupervised learning. In k-Means, each point joins its nearest centroid, and then each centroid moves to the mean. These two steps repeat until no point changes its cluster. We choose k using the elbow method and business sense. Clustering helps shops, news apps, banks and delivery companies. Try the marks example yourself with starting centroids at twenty and ninety.