How Clustering Finds Hidden Groups

A biologist studying gene expression data has no labels telling her which of 20,000 genes belong to which functional pathway. A retailer has purchase histories for millions of customers but no predefined "customer type" tags stamped on any of them. Clustering algorithms solve exactly this problem: finding natural groupings in raw data when nobody has told the algorithm in advance what the groups should be, or even how many there are.

That single constraint, no labels, is what separates clustering from almost everything else people mean when they say "machine learning." This article walks through how the major clustering algorithms actually work mechanically, why the number of clusters is such a persistent headache, how the field measures whether a clustering is any good without ground truth to check against, and where clustering shows up in research and industry today.

Why clustering is called "unsupervised" and why that matters

Unsupervised learning — a category of machine learning where the algorithm receives no labeled examples and must find structure in data on its own. Contrast this with supervised learning, where a spam filter is trained on thousands of emails a human has already tagged "spam" or "not spam," and the algorithm's whole job is to reproduce that labeling on new, unseen emails. Clustering never gets that answer key. It only ever sees the raw feature values, numbers describing each data point, and it groups points based purely on how those numbers relate to each other in space.

This distinction changes the math and it changes what "correct" even means. A supervised classifier has an objective, measurable target: did it predict the label a human assigned, yes or no. Accuracy, precision, and recall all depend on comparing the model's output to a known right answer. Clustering has no such right answer sitting in the dataset waiting to be checked against. The "right" grouping of a set of customers depends entirely on what question you are trying to answer, and two defensible, differently structured groupings of the identical dataset can both be legitimate.

Take a concrete example. A telecom company clustering customers by usage pattern might get one clustering that groups people by how much data they consume, and a completely different clustering that groups the same people by which hours of the day they are active. Neither clustering is "wrong." They answer different business questions, and the algorithm has no way of knowing which question the analyst actually cares about, because nobody told it. This is why clustering projects tend to start with a business question rather than a "let's see what the algorithm finds" mindset, even though the algorithm's job is technically to find structure the analyst didn't specify.

Because there is no ground truth, evaluating a clustering is inherently more subjective and more contested than evaluating a classifier's error rate. Statisticians developed internal metrics, like the silhouette score, which measures how much closer a point is to its own cluster than to the nearest neighboring cluster, precisely because there is no external label to compare against. These metrics are useful diagnostics, but none of them can tell an analyst whether the resulting clusters are meaningful to the actual problem at hand. That judgment call remains human.

How k-means finds groups by minimizing distance

K-means is the oldest and still the most widely deployed clustering algorithm in practice, and its lineage traces to a 1957 Bell Telephone Laboratories technical report by Stuart Lloyd on signal quantization, work that was not formally published until 1982 in IEEE Transactions on Information Theory as "Least Squares Quantization in PCM" (Lloyd, 1982). The iterative procedure Lloyd described for compressing pulse-code modulation signals turned out to be structurally identical to what became known as k-means clustering, and the underlying two-step loop, assign then update, is still called Lloyd's algorithm in technical literature.

The mechanism is straightforward once you see it laid out. The analyst first picks k, the number of clusters, and the algorithm places k "centroids," representative points that act as the current best guess for the center of each cluster, usually at random or semi-random starting positions within the data. Every data point then gets assigned to whichever centroid it is closest to, using a distance measure, almost always ordinary straight-line (Euclidean) distance. Once every point has an assignment, each centroid moves to the average position, the mean, of all points currently assigned to it. Then the whole process repeats: reassign every point to the nearest (now-moved) centroid, recompute the means, reassign again, until assignments stop changing between iterations.

Centroid — the mean position of every data point currently assigned to a given cluster, recalculated after each iteration and used as that cluster's current representative center. It is worth being precise here: a centroid is not necessarily an actual data point in the dataset. It is a computed average position, which is one reason k-means clusters tend to look like round blobs centered on that average rather than following any specific data point's shape.

A useful mental picture is dropping several magnets onto a table scattered with iron filings, then letting the filings snap to whichever magnet pulls hardest on them, and then physically moving each magnet to the center of mass of the filings currently clustered around it. Do that repeatedly and eventually nothing shifts: every filing is closer to its current magnet than to any other, and every magnet sits at the exact center of its filings. That fixed point, where reassignment produces no more movement, is what k-means converges to. It usually takes only a handful of iterations to reach that stable state on real data, which is part of why the algorithm remains popular even though it dates to the 1950s: it is computationally cheap and scales well to large datasets.

K-means minimizes a specific quantity called within-cluster sum of squares: the total squared distance between every point and its assigned centroid, summed across all clusters. This is important because it explains a limitation covered below, that k-means implicitly assumes clusters are roughly spherical, since minimizing squared distance to a single center point naturally favors round shapes over elongated or irregular ones.

Stuart Lloyd developed the algorithm now called k-means in 1957 while working on pulse-code modulation signal compression at Bell Labs, not for data analysis. The work went unpublished for 25 years until IEEE Transactions on Information Theory printed it in 1982 (Lloyd, 1982), by which point other researchers had already independently arrived at similar clustering procedures.

Why you have to choose the number of groups in advance

K-means requires the analyst to specify k, the number of clusters, before the algorithm runs a single iteration. This is a genuinely awkward practical requirement, because the entire premise of unsupervised clustering is that nobody knows the underlying structure of the data in advance, and yet the most popular clustering algorithm demands the analyst guess one of the most important structural facts about that data before starting.

In practice, analysts lean on a handful of heuristics rather than a definitive answer. The most common is the elbow method: run k-means repeatedly with increasing values of k, from say 2 through 15, and plot the within-cluster sum of squares (the error metric described above) against each value of k. Error always decreases as k increases, since more clusters mean points are, on average, closer to their nearest centroid. But the rate of improvement typically slows sharply at some point, producing a bend, or "elbow," in the plot. Analysts pick the k at that elbow as a reasonable balance between explaining the data well and not overfitting to noise by creating too many tiny clusters.

The elbow method is a heuristic, not a proof. Real data frequently produces plots with no obvious elbow, a smooth curve that keeps improving gradually with no clear bend, which leaves the choice of k a matter of domain judgment rather than a computed answer. A second common approach, the silhouette score mentioned earlier, computes a score between negative one and one for each point based on how much closer it is to its own cluster than to the next nearest one, then averages across all points for a given k; analysts often try several values of k and pick whichever produces the highest average silhouette score. Neither method removes the underlying uncertainty. They narrow the search rather than eliminate the guesswork.

Method	Requires k in advance?	Handles non-spherical clusters?	Sensitive to outliers?	Typical dataset scale
K-means	Yes	Poorly	Yes, high	Very large (millions of points)
Hierarchical clustering	No (produces a tree, or dendrogram)	Somewhat, depends on linkage method	Moderately	Small to medium (thousands of points)
DBSCAN	No	Yes, well	No, treats them as noise rather than distorting clusters	Medium to large

K-means trades flexibility for speed and simplicity; DBSCAN trades a fixed cluster count for the ability to find irregular shapes and to identify outliers explicitly rather than forcing them into a group.

How the elbow method actually looks on a plot

Plotting k on the x-axis against within-cluster sum of squares on the y-axis for a well-separated dataset typically produces a curve that drops steeply from k=1 to k=3 or k=4, then flattens into a much shallower slope afterward. The "elbow" is the k value where that transition from steep to shallow happens, and analysts read that point as the k value where adding more clusters stops meaningfully reducing error relative to the added complexity.

How hierarchical clustering builds a tree instead of fixed groups

Hierarchical clustering takes a different approach entirely: instead of producing one flat set of k clusters, it builds a nested tree structure called a dendrogram, showing how individual points merge into progressively larger groups. The most common variant, agglomerative hierarchical clustering, starts by treating every single data point as its own cluster, then repeatedly merges the two closest clusters into one, continuing until every point belongs to a single all-encompassing cluster at the top of the tree.

The key design decision in hierarchical clustering is the linkage method, the rule for measuring "closeness" between two clusters that each already contain multiple points, not just single points. Single linkage measures the distance between the two closest points in each cluster; complete linkage measures the distance between the two farthest points; average linkage measures the average distance across all pairs. Each choice produces meaningfully different tree structures from the identical starting data, another reminder that "the" clustering result of a dataset is rarely a single objective fact.

The practical advantage of the dendrogram is that an analyst can choose the number of clusters after seeing the full tree, by drawing a horizontal cut line at whatever height produces a useful number of groups, rather than committing to k before running anything. The tradeoff is computational cost: naive implementations scale poorly, since computing distances between every possible pair of clusters at every merge step becomes expensive quickly as the dataset grows, which is part of why hierarchical clustering tends to be used on datasets in the thousands or low tens of thousands of points rather than the millions k-means can handle.

How DBSCAN finds clusters shaped like anything

DBSCAN, short for Density-Based Spatial Clustering of Applications with Noise, was introduced by Martin Ester, Hans-Peter Kriegel, Jörg Sander, and Xiaowei Xu at the 1996 KDD conference in a paper titled "A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise" (Ester et al., 1996). It takes a genuinely different approach from both k-means and hierarchical clustering: instead of assuming clusters are round blobs organized around a center point, or building them as a strict nested tree, DBSCAN groups together points that are densely packed relative to their neighbors and explicitly marks sparse, isolated points as noise rather than forcing every point into some cluster.

Density-based clustering — a clustering approach where a group is defined as a region where points are packed closely together, separated by regions of lower point density, rather than by proximity to a computed center point. DBSCAN operationalizes this with two parameters: eps, the radius defining a point's neighborhood, and minPts, the minimum number of points required within that radius for a point to count as a "core point" capable of forming or extending a cluster.

The mechanical process starts by picking any unvisited point and checking how many other points fall within eps distance of it. If that count meets or exceeds minPts, the point becomes a core point and a new cluster forms, which then expands by recursively checking every point reachable through a chain of other core points within eps of each other. Points that fall within eps of a core point but do not themselves have enough neighbors to be core points are still included in the cluster as border points. Any point that never qualifies as core or border, meaning it sits too far from any sufficiently dense region, gets labeled noise and excluded from every cluster.

This mechanism lets DBSCAN correctly identify clusters shaped like crescents, spirals, concentric rings, or other irregular forms that k-means, which assumes roughly spherical groups because it minimizes distance to a single center, would badly misclassify by cutting straight through the middle of a curved cluster. It also means DBSCAN does not require specifying the number of clusters in advance the way k-means does; the number of clusters emerges naturally from how many separate dense regions the algorithm finds. The tradeoff is that DBSCAN performs poorly when clusters in the same dataset have very different densities, since a single global eps and minPts setting can be too loose for a sparse cluster and too tight for a dense one simultaneously.

What happens to outliers under each method

K-means forces every point into one of the k clusters no matter how far it sits from any centroid, meaning a single extreme outlier can visibly drag a centroid toward it and distort the cluster's shape. DBSCAN instead labels genuinely isolated points as noise and excludes them entirely, which is often more honest about what the data actually contains, though it means DBSCAN's cluster count depends on the density thresholds chosen.

What "similarity" actually means mathematically

Every clustering algorithm needs a formal, numeric way to measure how alike two data points are, since "similar" is not something a computer understands intuitively. That measure is almost always calculated as a distance in a mathematical space where each feature of the data, income, age, purchase frequency, gene expression level, becomes one coordinate axis, and each data point becomes a location in that multi-dimensional space.

Euclidean distance, the ordinary straight-line distance formula familiar from basic geometry (the square root of the sum of squared differences across every dimension), is the default choice for most clustering work, and it is what k-means uses internally. It works well when features are on comparable numeric scales and the raw magnitude of differences matters. But Euclidean distance behaves poorly in high-dimensional spaces, a phenomenon sometimes called the "curse of dimensionality," where as the number of features grows, distances between all pairs of points tend to become similarly large, making it harder for any distance-based method to distinguish "close" from "far."

Cosine similarity, which measures the angle between two data vectors rather than the straight-line gap between their endpoints, works better for text data and other high-dimensional, sparse representations where the direction a vector points matters more than its raw length. Two documents about the same topic might use similar words in wildly different total quantities, one long and one short, and cosine similarity correctly identifies them as similar because it ignores overall magnitude and focuses only on the relative proportions, the direction, of the word-frequency vectors involved.

The choice of distance measure is not a minor technical detail; it fundamentally changes what "similar" means to the algorithm, and different choices on the identical dataset can produce entirely different clusters. An analyst clustering customer purchase data with Euclidean distance on raw dollar amounts will treat a customer spending $10,000 across ten categories very differently from one spending $1,000 across the same ten categories in identical proportions, even though their spending patterns, the proportions, are structurally identical. Normalizing or standardizing features before clustering, and choosing a distance measure that matches the actual question, matters as much as choosing the algorithm itself.

Where clustering actually gets used

Clustering is not a purely academic exercise; it underlies a substantial share of applied data analysis across industries that never touch anything resembling a supervised classifier.

Customer segmentation in marketing is probably the most commercially visible application: companies group buyers by purchase behavior, browsing pattern, or engagement frequency to target campaigns without needing predefined categories decided in advance by a marketing team. A retailer running k-means on transaction histories might discover a cluster of infrequent-but-high-value shoppers that nobody on the marketing team had explicitly defined as a segment, revealing a group worth a dedicated campaign that existing category labels, like "frequent buyer" or "new customer," never captured.

In genomics, clustering gene expression profiles across experimental conditions helps researchers identify genes that behave similarly, rising and falling together across the same set of conditions, which often reveals shared biological pathways or regulatory relationships nobody had previously mapped. This is one of the older and more rigorously validated uses of clustering in science: hierarchical clustering of gene expression data has been a standard technique in molecular biology since the late 1990s, helping researchers group genes by function even when the biological mechanism connecting them is not yet understood, since the clustering only requires that the genes' expression patterns correlate, not that a biologist already knows why.

Astronomers use clustering to group stars by chemical composition and motion through the galaxy, an approach that has helped identify stellar populations, groups of stars that likely formed together from the same original gas cloud and share a common history, based purely on their present-day physical properties rather than any label assigned in advance. Image compression algorithms use a close relative of k-means, sometimes literally k-means itself, to reduce the number of distinct colors an image uses; each pixel's color gets assigned to its nearest cluster centroid, drastically cutting the palette while trying to preserve the image's overall visual appearance, an application that traces directly back to Lloyd's original 1957 signal-compression work at Bell Labs.

Anomaly and fraud detection systems also lean on clustering, though somewhat in reverse: rather than caring primarily about the clusters themselves, the system flags points that DBSCAN labels as noise, meaning they do not fit into any dense region of normal-behavior data, as candidates for further review. A financial transaction that sits far from every existing cluster of typical spending patterns is exactly the kind of point DBSCAN's noise label was designed to catch.

Common misconceptions

A common misunderstanding is that clustering always finds the "true" hidden categories buried in data, as though there is one objectively correct partition waiting to be uncovered. In reality, clustering finds whatever structure is present according to the specific similarity measure and algorithm chosen, and, as the customer segmentation example earlier illustrated, different reasonable choices of features and distance measures can produce meaningfully different, equally valid groupings of the same underlying data. The clustering answers the question the analyst implicitly asked through their choice of features and distance metric, not some abstract, universal question about what categories "really" exist.

Another persistent misconception is that more clusters always mean a better result. Adding clusters can always reduce a model's internal error metric, like the within-cluster sum of squares k-means minimizes, since with enough clusters every single point could eventually get its own private group and error would drop to zero. That outcome is obviously meaningless for actual insight; a useful clustering balances error reduction against interpretability and against how well the groupings generalize to new data the analyst has not yet seen. This is structurally the same overfitting problem that shows up in why overfitting hurts machine learning, just applied to an unsupervised setting instead of a supervised one.

A third misconception, more subtle, is that clustering is a fully automated process requiring no domain judgment. In practice, the choice of features to include, whether to normalize them, which distance measure to use, and how to interpret the resulting clusters all require substantial human judgment informed by knowledge of the actual problem. This overlaps heavily with the discipline covered in what feature engineering means: the features fed into a clustering algorithm shape its output as much as, or more than, the choice of algorithm itself, since a clustering algorithm can only ever find structure that is actually present in the features it is given.

How clustering compares to other unsupervised and supervised approaches

Clustering sits alongside dimensionality reduction as one of the two major categories of unsupervised learning, but the two solve different problems. Dimensionality reduction techniques compress the number of features describing each data point while preserving as much information as possible; clustering groups the data points themselves. The two are frequently used together, running a dimensionality reduction step first to compress a high-dimensional dataset before clustering, since distance measures like Euclidean distance behave more reliably in fewer dimensions.

It is also worth being explicit about how clustering relates to supervised methods like the decision trees covered in how decision trees split data. A decision tree learns a sequence of if-then splits designed to separate labeled classes as cleanly as possible, evaluated against those known labels at every step. Clustering has no labels to split toward; it discovers groupings from the geometry of the data alone. That said, the two are sometimes combined in practice, using clustering as an unsupervised preprocessing step to generate candidate group labels, which a supervised model then learns to predict on new data once an analyst has reviewed and validated that the clusters are meaningful.

The takeaway

Clustering solves a problem labeled machine learning cannot even attempt: finding structure in data when nobody knows in advance what that structure should look like or how many groups exist. The mechanism, whether it is k-means iteratively repositioning centroids toward Lloyd's 1957 quantization logic, hierarchical clustering building a full dendrogram of nested merges, or DBSCAN following local density and marking outliers as noise, always reduces to the same underlying question: which points are more similar to each other than to everything else, and how do you draw defensible boundaries around that similarity. There is no single correct clustering of any real dataset, only clusterings that are more or less useful for the specific question an analyst is actually trying to answer.

---

Read next:

• How decision trees split data
• What feature engineering means
• Why overfitting hurts machine learning

FAQ

Q: What is the main difference between clustering and classification?

Classification is supervised, learning from labeled examples to predict categories for new data against a known right answer. Clustering is unsupervised, receiving no labels at all and instead discovering groups purely from how data points relate to each other in feature space, with no ground truth to check the result against.

Q: How does k-means clustering actually work?

K-means places a chosen number of centroids, assigns each data point to the nearest centroid using a distance measure like Euclidean distance, then moves each centroid to the average position of its assigned points. This assignment-and-update cycle, formalized by Stuart Lloyd at Bell Labs in 1957, repeats until the groupings stabilize and no points change assignment.

Q: Why do you need to choose the number of clusters before running k-means?

K-means requires the number of groups, k, as an input because its algorithm needs to know how many centroids to place before it can begin. Analysts commonly use the elbow method, plotting error against increasing values of k and looking for the point where more clusters stop meaningfully reducing that error, as a practical heuristic for choosing k.

Q: What advantage does DBSCAN have over k-means?

DBSCAN, introduced by Ester, Kriegel, Sander, and Xu in 1996, groups points based on local density rather than proximity to a fixed center, letting it correctly identify irregularly shaped clusters like crescents or spirals and treat sparse, isolated points as noise. K-means, which assumes roughly spherical clusters, handles both of those situations poorly.

Q: How does hierarchical clustering differ from k-means?

Hierarchical clustering builds a nested tree, or dendrogram, by repeatedly merging the closest pairs of clusters, letting an analyst choose the number of groups after seeing the full tree rather than specifying k beforehand. It scales less efficiently than k-means to very large datasets but avoids the upfront guess k-means requires.

Q: Can clustering results be objectively wrong?

Clustering does not have a single objectively correct answer the way classification accuracy does, since there is no label to check against. A clustering can still be a poor fit for the task, however, if it fails to reflect any structure relevant to the actual question being asked, or if the chosen distance measure and features poorly capture the real relationships analysts care about in the data.

Q: What is clustering used for outside of academic research?

Documented practical applications include customer segmentation in marketing, gene expression clustering in genomics to find genes with shared biological pathways, grouping stars by chemical composition in astronomy, color-palette reduction in image compression, and flagging outlier transactions in fraud detection systems.