Clustering

Clustering is an unsupervised learning task: it takes an unlabeled dataset and splits it into groups, called clusters, so that the members of any one group resemble each other more than they resemble the members of any other. Unlike classification, no one tells the algorithm what the right answer is; the only criterion is a notion of similarity —usually a distance between points— that the analyst chooses in advance.

That choice changes everything. Clustering does not neutrally uncover a structure that is «already there»: it surfaces whatever structure the similarity measure and the method allow us to see. This is why it is a tool for exploration —segmenting customers, sorting genes, flagging anomalies— rather than an oracle with a single true output.

Families of methods: partitional, hierarchical, density and model-based

The best-known method is k-means, a partitional approach whose standard procedure is Lloyd's algorithm, proposed at Bell Labs in 1957; the name «k-means» was coined by MacQueen in 1967. It divides the data into k groups by minimizing the variance within each one. It is fast and simple, but it forces you to fix k beforehand and tends to assume groups of similar size and spherical shape, so it struggles with elongated or irregular structures.

Hierarchical clustering does not require fixing k: in its agglomerative form it starts with each item as its own group and merges the closest ones until it builds a tree, the dendrogram, which is «cut» at the desired height. The density-based approach, best represented by DBSCAN (Ester, Kriegel, Sander and Xu, 1996), defines clusters as dense regions separated by sparse ones: it finds clusters of arbitrary shape, needs no preset k and, on top of that, labels isolated points as noise. Finally, model-based methods such as Gaussian mixture models (GMM) assume the data come from a blend of distributions and fit their parameters with the expectation-maximization (EM) algorithm, giving each point a probability of membership instead of a hard label.

How to choose the number of groups and how to evaluate

Except in density-based methods, choosing how many groups to look for is an open decision. Two common heuristics are the elbow method —you plot an error measure against k and look for the point where it stops improving appreciably— and the silhouette coefficient, introduced by Rousseeuw in 1987, which for each point compares its cohesion with its own group against its separation from the nearest one, on a scale from −1 to +1. Evaluating the result is even trickier: because there are no reference labels, one relies on internal indices (the silhouette among them) that measure how compact and well-separated the groups are, without ever confirming that they are the «right» ones.

Why there is no single correct answer

This is the point worth stating plainly: clustering has no single true solution. The result depends on the similarity measure, the method and its parameters, and different algorithms produce different groupings on the very same data —k-means and DBSCAN can disagree entirely—. There is no universal criterion that names «the right one»: a clustering is judged valid by how useful it is for the question you set out to answer, not by any objective correctness. Grasping that ambiguity is what separates a rigorous use of the technique from a naive reading of its output.