Clustering in Data Mining: Types, Algorithms, Applications

Take 5,000 points scattered uniformly at random inside a four-dimensional cube. There is no structure in them at all: no groups, no dense regions, nothing but noise. Run k-means on them and it returns k tidy clusters anyway, with a silhouette score of 0.187 at k=2 that climbs steadily to 0.223 at k=8. Nothing in the output warns you. The centroids look reasonable, the labels are balanced, and if you plot the first two dimensions you will see boundaries that your eye happily accepts.

That is the fact to keep hold of through everything below. Clustering groups records so that items in one group resemble each other more than they resemble items in any other group, and nobody supplies the groups in advance. The algorithm proposes them. That makes clustering unsupervised, and it also means clustering cannot fail loudly: there is no accuracy to drop, no error to raise. It returns a partition of whatever you hand it. Your job is deciding whether the partition means anything.

This guide covers what cluster analysis computes, the main types of clustering in data mining, the core algorithms, how distance and quality are measured, choosing the number of clusters without the elbow method, what breaks when the data gets big, and where the whole approach stops applying. Every version number, price and project status below was read from the project's or vendor's own documentation on 10 August 2026. The timings are ours, run on the machine described where they appear.

No clustering method is neutral

Jon Kleinberg proved the awkward part in a 2002 NIPS paper, An Impossibility Theorem for Clustering. He set out three properties any sensible clustering function ought to have. Scale-invariance: multiply every distance by the same constant and the answer should not change. Richness: every possible partition of the points should be reachable from some distance function. Consistency: shrink the distances inside clusters and stretch the distances between them, and the answer should stay put. The theorem states that no clustering function satisfies all three. You can have any two.

This is not a curiosity for theorists. It is the reason there is no default algorithm and no correct number of clusters, and the reason two competent analysts hand the same table to two competent tools and get two different, equally defensible answers. The method you pick encodes a definition of what a cluster is, and the output is at least as much a property of that definition as of your data.

Run the noise experiment against a density-based method and the difference is immediate. On the same 5,000 uniform points, HDBSCAN labeled 87.7% of them as noise and returned two small clusters instead of a clean partition. k-means could not tell you the data was structureless because k-means has no vocabulary for saying so. HDBSCAN does, and used it.

Two practical rules follow. Choose the family whose definition of a cluster matches the question you are asking, before you tune anything. And before you interpret a result, check that clustering the same data with a different definition does not produce something unrecognizable.

What cluster analysis actually computes

Picture every record as a point in a multi-dimensional space, one axis per feature. A shop's customers might sit on axes like visits per month, average order value and days since last purchase. Points close together behave alike. Cluster analysis finds the dense neighborhoods automatically and tags each point with the group it landed in.

A cluster is then summarized by a representative:

• In numeric (Euclidean) space, the natural summary is the centroid, the coordinate-wise average of the cluster's points, plus a spread measure such as the average distance from that center. The centroid usually is not a real record, and does not have to be.
• Where averaging is meaningless, you nominate an actual member instead: the medoid, the point with the smallest total distance to the rest of the cluster. You cannot average two document titles or two sets of purchased SKUs, so you pick the most central one. The looser term clustroid covers the same idea with other choices of which total to minimize.

Because a cluster reduces to one representative plus a spread, clustering doubles as data compression and summarization. Millions of rows become a handful of profiles you can hold in your head, argue about in a meeting and act on.

Clustering is one of the pillars of the field alongside classification and association rules. For the wider picture, see data mining techniques and what is data mining.

Clustering vs classification

Classification is supervised. You already hold labeled examples, spam and not-spam, and you train a model to reproduce those labels on data it has not seen. Clustering is unsupervised. There are no labels. The algorithm proposes groups and you decide what, if anything, they mean.

The consequence that trips people up is evaluation. A classifier has an accuracy, a precision and a recall, all computed against known truth. A clustering has none of those, because there is nothing to compare to. Every number in the "evaluating clusters" section below is either a measure of geometric tidiness, which is not the same as correctness, or a comparison against labels you happened to have, in which case you had labels and could have classified.

Use classification when you can name the categories. Use clustering when you suspect structure exists and cannot name it yet. Do not use a cluster label as a class label without checking that it survives being recomputed.

Types of clustering in data mining

Different methods encode different assumptions about what a cluster is. Five families cover nearly everything in production.

1. Partitioning (centroid-based)

Split the data into a fixed number k of non-overlapping groups, each built around a center. k-means and k-medoids (PAM) are the classic examples. Fast and simple, and biased in a specific direction: you choose k up front, and the method leans hard toward round clusters of similar size.

2. Hierarchical

Build a tree (dendrogram) of nested clusters instead of one flat partition. Agglomerative methods start with every point as its own cluster and repeatedly merge the closest pair; divisive methods start with one cluster and split. You pick the number of clusters afterward by cutting the tree at a chosen height, which is a genuine advantage when you want to see structure at several scales at once.

3. Density-based

Define clusters as dense regions separated by sparse ones. DBSCAN, OPTICS and HDBSCAN find clusters of any shape and, importantly, refuse to place sparse points anywhere, labeling them noise. No k to set.

This family behaves differently from the other four in a way worth stating plainly: it is the only one that can return the answer "there is nothing here". Everything else partitions whatever it is given. That single property is why density methods are the right default for exploratory work on data you do not already understand, and why they double as anomaly detectors at no extra cost. The price is a different pair of parameters to think about, and a runtime that grows much faster than k-means, which the measurements below make concrete.

4. Distribution / model-based

Assume the data came from a mixture of probability distributions and fit them. A Gaussian Mixture Model (GMM) gives each point a probability of belonging to each cluster, a soft assignment rather than the hard one-cluster-only assignment of k-means. It also gives you a likelihood, which means model-selection criteria such as BIC apply, and that is a firmer footing for choosing the number of components than anything available to k-means.

5. Grid-based

Quantize the space into a grid of cells and cluster the cells (STING, CLIQUE). Work depends on the number of cells rather than the number of points, so it scales beautifully with rows. It scales terribly with columns: cell count grows exponentially with dimension, so ten features at ten bins each is already 10 billion cells. Low-dimensional, very large data only.

Cutting across all five is the hard versus soft (fuzzy) distinction. Hard clustering puts each point in exactly one cluster; fuzzy c-means and GMMs let a point belong partially to several, which matters when the boundaries are genuinely blurry and when you would rather see the ambiguity than have it rounded away.

Clustering algorithms in data mining

k-means clustering in data mining

k-means clustering in data mining is the algorithm most people meet first, because it is fast, short to explain, and short to implement:

1. Choose k and initialize k centroids, using k-means++ rather than pure randomness.
2. Assign every point to its nearest centroid.
3. Update each centroid to the mean of the points now assigned to it.
4. Repeat steps 2 and 3 until assignments stop changing.

That assign-and-update loop is Lloyd's algorithm, and it is worth being precise about what it does and does not give you. It minimizes within-cluster variance (inertia) and converges to a local minimum. Finding the global optimum of that objective is NP-hard, so no number of restarts turns Lloyd's algorithm into an exact method. Restarts only reduce how badly you lose. scikit-learn's own notes put the average complexity at O(k n T) for T iterations, which is why it runs comfortably on millions of rows.

A default changed underneath a lot of published code. In scikit-learn 1.2 the n_init parameter gained an 'auto' option, and in 1.4 'auto' became the default. The documentation spells out what it means: "10 if using init='random' or init is a callable; 1 if using init='k-means++' or init is an array-like." Since k-means++ is itself the default initializer, code that used to get ten restarts now gets one. We measured the cost across 40 seeds on 3,000 points, 10 features, 25 true clusters: the median difference in inertia between a single restart and ten was exactly zero, and the worst case was 64% higher inertia, with the adjusted Rand index against the true labels falling from 1.000 to 0.950. That is the shape of the problem. Nothing fails, most runs are identical, and once in a while the result is quietly much worse. Set n_init explicitly and the question disappears.

The rest of the catches are the familiar ones. You must pick k. Results depend on initialization. The method assumes roughly spherical, similarly sized clusters. It is sensitive to outliers and to unscaled features, so standardize first. Reach for k-medoids when you need a real record as the center or a distance that is not Euclidean; the classic PAM algorithm is slow, and Erich Schubert and Peter Rousseeuw's FasterPAM published an O(k) runtime improvement over PAM, CLARA and CLARANS. It ships as python-kmedoids. The older route most tutorials still recommend, pip install scikit-learn-extra, points at a package whose last release was 0.3.0, and it is not the place to start new work.

Hierarchical clustering in data mining

Hierarchical clustering in data mining produces a dendrogram, and the tree is the point: you decide how many clusters you want after looking at the structure, not before. The key decision is the linkage, meaning how the distance between two clusters is defined:

• Single linkage: nearest pair of points. Finds elongated, chain-like shapes, and will happily chain two unrelated groups together through a bridge of a few points.
• Complete linkage: farthest pair. Produces compact, roughly equal clusters, and breaks up genuinely elongated ones.
• Average linkage: mean pairwise distance. A middle ground, and the usual choice with non-Euclidean metrics.
• Ward's method: merges the pair that increases total within-cluster variance the least. The best default for numeric data, with two conditions attached.

The first condition is that Ward means Euclidean. SciPy states it flatly: methods 'centroid', 'median' and 'ward' "are correctly defined only if Euclidean pairwise metric is used". Passing a cosine or Manhattan distance matrix to Ward produces numbers, and the numbers are meaningless.

The second is a genuine trap for anyone moving between R and Python. R's hclust offers both ward.D and ward.D2, and its own documentation says that ward.D, which was the only Ward option available in R 3.0.3 and earlier, "does not implement the clustering criterion of Ward Jr. (1963), whereas option ward.D2 implements that criterion". The distinction is whether dissimilarities are squared before the cluster update, and R documents it against Murtagh and Legendre's 2014 paper in the Journal of Classification. SciPy's and scikit-learn's ward corresponds to the correct criterion. An analysis ported from an old R script by keeping the method name will silently change what was computed.

On cost, the widely repeated "hierarchical clustering is O(n³)" is only true of the naive implementation. SciPy's linkage documentation is specific: single linkage uses a minimum spanning tree at O(n²) time, complete, average, weighted and ward use the nearest-neighbor chain algorithm, also O(n²), and only the remaining methods fall back to the naive O(n³) approach. The sentence that actually constrains you is the next one: "All algorithms use O(n²) memory." That is the real ceiling, and it arrives sooner than the runtime does.

DBSCAN and HDBSCAN (density-based)

DBSCAN takes two parameters, a neighborhood radius eps and a minimum neighbor count minPts, and grows clusters outward from dense core points. It was introduced by Ester, Kriegel, Sander and Xu at KDD 1996 and has aged better than almost anything of its vintage. It finds clusters of any shape, decides the number of clusters itself, and isolates outliers as noise, which makes it a dual-purpose anomaly detector.

Its weakness is that a single eps cannot describe clusters of different densities. HDBSCAN was built to fix exactly that, by building a hierarchy over varying density thresholds and extracting the most stable clusters from it. It arrived in scikit-learn core in version 1.3, June 2023, described in the changelog as usable "on a wide variety of data without much, if any, tuning" and adapted from Leland McInnes' original scikit-learn-contrib/hdbscan, which is still maintained separately and released 0.8.44 in June 2026. Reach for HDBSCAN first among density methods, and reserve plain DBSCAN for cases where you genuinely know the density you are looking for.

Where DBSCAN breaks is memory, not time, and the failure is abrupt. scikit-learn's documentation carries the warning in two places: the implementation "has a worst case memory complexity of O(n²), which can occur when the eps param is large and min_samples is low, while the original DBSCAN only uses linear memory", because it "bulk-computes all neighborhood queries". We hit that wall by accident while collecting the timings below. A 100,000-point, 20-feature array occupies 16 MB. DBSCAN(eps=2.0, min_samples=10) on it was killed by the kernel out-of-memory handler on a machine with 7 GB of RAM. The same array clustered fine with eps small enough to keep neighborhoods short. An eps chosen a little too generously turns a 16 MB input into a job that does not fit in memory, and there is no gradual slowdown to warn you first.

Gaussian mixture models (model-based)

A GMM fits k Gaussian components, each with its own mean, size and orientation, using Expectation-Maximization. Because components can be stretched and tilted, GMMs handle overlapping, non-spherical groups that defeat k-means, and they return membership probabilities rather than assignments. k-means is in fact the limiting case of a GMM with spherical, equal-weight components and hard assignment.

The costs are more parameters to fit, more sensitivity to initialization, and a covariance estimate that becomes unstable when a component collects fewer points than it has dimensions. In exchange you get a likelihood, and therefore AIC and BIC, and therefore a principled way to compare models with different numbers of components. Among the common methods, that is nearly unique.

Spectral and embedding-based clustering

Where similarity is more meaningful than raw coordinates, in graphs, images and text, spectral clustering works from the eigenvectors of a similarity matrix and separates shapes that centroid methods cannot. Its practical limit is the same one as hierarchical clustering: the similarity matrix is n by n.

The pattern that dominates current practice is embed, reduce, then cluster. Turn text, images or behavior into dense vectors with a neural embedding model, compress those vectors, then run k-means or HDBSCAN on the result. BERTopic is the canonical packaging of it, with a documented four-stage pipeline of sentence-transformers, UMAP, HDBSCAN and c-TF-IDF, most recently released in December 2025. Embedding is no longer the expensive part: OpenAI lists text-embedding-3-small at $0.02 per million tokens as of 10 August 2026, so embedding a million product descriptions of 50 tokens each costs about a dollar.

The reduction step deserves more skepticism than it usually gets. UMAP's own documentation on clustering warns that it "does not completely preserve density" and can "create false tears in clusters, resulting in a finer clustering than is necessarily present in the data". It recommends different settings for clustering than for pictures: n_neighbors raised from 15 to 30, min_dist at 0.0, and more than two output components. Clusters that appear only after a UMAP projection tuned for a nice-looking scatter plot are the single most common way a modern pipeline produces confident nonsense.

Distance measures: the heart of clustering

Every clustering algorithm is only as good as its notion of close. The metric is the model:

• Euclidean distance: straight-line distance, the default for continuous numeric features, and the only metric for which a centroid is properly defined.
• Manhattan distance: sum of absolute differences, less influenced by a single wild coordinate.
• Cosine similarity: angle between vectors, the standard for text and high-dimensional sparse data, where direction carries the meaning and magnitude mostly reflects length.
• Jaccard distance: for sets and binary features, shared elements over total elements.
• Gower distance: for mixed numeric-and-categorical tables, where nothing else applies cleanly.

Cosine and Euclidean are the same thing on normalized vectors, and knowing that saves work. For L2-normalized vectors, squared Euclidean distance equals twice the cosine distance. We checked it on 500 random 50-dimensional unit vectors: the largest discrepancy across all 124,750 pairs was 2.2e-15, which is floating-point noise. So running k-means on normalized embeddings gives you spherical k-means without a separate implementation, and you can use any Euclidean-only tool, Ward linkage included, on cosine-flavored data by normalizing first.

High dimensions dissolve the concept of "nearest". Kevin Beyer, Jonathan Goldstein, Raghu Ramakrishnan and Uri Shaft published this at ICDT 1999 under the title "When Is 'Nearest Neighbor' Meaningful?", and reported the effect showing up in as few as 10 to 15 dimensions. It is easy to reproduce. Draw 1,000 uniform points in a unit cube and look at the spread of pairwise distances as dimension rises:

Measured with SciPy 1.17.1 on a single seed, uniform points in the unit hypercube. Your exact numbers will differ; the shape will not.

By 1,000 dimensions the farthest point is only 20% farther away than the nearest one. Every point is roughly equidistant from every other, "nearest neighbor" stops being a meaningful category, and any algorithm built on distance ranking degrades toward arbitrary. This is why raw 1,536-dimensional embeddings usually get reduced before clustering, and why cosine distance, which throws away magnitude, holds up better than Euclidean in text spaces.

The Euclidean versus non-Euclidean split has one more practical consequence. In Euclidean space you can summarize a cluster by its centroid. In a non-Euclidean space, clustering documents by shared rare words or grouping moviegoers by overlapping tastes, there is no meaningful average, so each cluster has to be represented by an actual member.

Finally, scale or normalize features before computing distances, or the largest-range column silently dominates everything; see data normalization. The counterweight, which most write-ups omit, is that standardizing is itself an assumption. Dividing every column by its standard deviation asserts that all features deserve equal weight. When one feature's spread is the signal, order value across a customer base, say, z-scoring can flatten the very structure you came to find. Scale by default, then check what changes if you do not.

Choosing k, and why the elbow method should go

Erich Schubert's 2023 paper in SIGKDD Explorations is called, without hedging, "Stop using the elbow criterion for k-means and how to choose the number of clusters instead". Its argument is that the elbow is easy to read into any curve, that better methods have been available for decades, and that reviewers should stop accepting conclusions based on it.

The demonstration takes a minute. Cluster 5,000 uniform random points, no structure whatever, at k from 1 to 15, and watch the per-step drop in inertia: 19%, 15%, 13%, 12%, 10%, 9%, 10%, 6%, 6%, 7%, 6%, 5%, 5%, 4%. Plotted, that is a smooth decaying curve, and a smooth decaying curve is exactly what people point at and call an elbow around k=4 or k=5. Run the same procedure on data with twelve real clusters and the drops go 33%, 26%, 26%, 21%, 31%, 30%, 39%, 26%, 21%, 18%, 19%, then 2%, 2%, 2%. The bend is real there, and it is unmissable, because it is a cliff rather than a curve. The elbow method does not distinguish between the two situations. It always finds a bend, and reading a bend off a smooth curve is a Rorschach test.

What to use instead, in rough order of how much they ask of you:

Silhouette, which measures how much closer each point is to its own cluster than to the next nearest one, on a scale from -1 to 1. It is the most useful single number for comparing candidate values of k. Note what it did to our noise: it kept rising with k, from 0.187 to 0.223, so a peak in silhouette is evidence of relative tidiness, not of structure existing.

The gap statistic (Tibshirani, Walther and Hastie, 2001) compares your inertia curve to the curve you would get from uniform data over the same range. That comparison is the piece the elbow lacks, and it is why the gap statistic can return k=1, meaning "no clusters here", which no elbow reading ever will.

BIC on a Gaussian mixture, when a mixture model is defensible. This is the only option on the list with a real model-selection theory behind it rather than a heuristic.

Not asking. DBSCAN, HDBSCAN and OPTICS infer the count from the data. If you have no principled value of k and no strong reason to expect spherical clusters, this is usually the shortest path to an honest answer.

Stability. Cluster ten bootstrap resamples of your data and compare the partitions with the adjusted Rand index. A structure that survives resampling is worth interpreting. One that does not survive is a description of this particular sample, and you should say so before anyone builds a campaign on it.

An earlier version of this article recommended the elbow method first and called these techniques "guides, not oracles". The guidance was too soft. The elbow is not a weaker version of the others, it is a method that returns a confident answer on data containing nothing.

A worked example in Python

scikit-learn is the standard toolkit. The code below was run against Python 3.11.15, scikit-learn 1.8.0 and NumPy 2.4.4. The current release is 1.9.0, from June 2026; its clustering changes were confined to AgglomerativeClustering accepting metric="l2" with Ward, a MiniBatchKMeans sample-weight fix and a BisectingKMeans init fix, none of which touch this snippet.

import numpy as np
from sklearn.preprocessing import StandardScaler
from sklearn.cluster import KMeans, HDBSCAN
from sklearn.metrics import silhouette_score

# X: rows = customers, columns = [visits, avg_order_value, recency_days]
X = np.array([
    [22, 18.0,  3], [25, 21.5,  5], [ 2, 120.0, 40],
    [ 3, 140.0, 55], [30, 15.0,  2], [ 1, 200.0, 70],
])

X_scaled = StandardScaler().fit_transform(X)          # never skip this

best_k, best_score = None, -1
for k in range(2, 5):
    labels = KMeans(n_clusters=k, n_init=10, random_state=42).fit_predict(X_scaled)
    score = silhouette_score(X_scaled, labels)
    print(f"k={k}  silhouette={score:.3f}")
    if score > best_score:
        best_k, best_score = k, score

model = KMeans(n_clusters=best_k, n_init=10, random_state=42).fit(X_scaled)
print("chosen k:", best_k, "labels:", model.labels_)

# the method that needs no k, and that is allowed to say "nothing here"
hdb = HDBSCAN(min_cluster_size=2).fit(X_scaled)
print("hdbscan:", hdb.labels_)                        # -1 means noise

Actual output:

k=2  silhouette=0.770
k=3  silhouette=0.589
k=4  silhouette=0.332
chosen k: 2 labels: [1 1 0 0 1 0]
hdbscan: [0 0 1 1 0 1]

Two details in that snippet are the article rather than the code. n_init=10 is written out because the default no longer means ten. And HDBSCAN is run alongside k-means rather than instead of it, because agreement between a method that must produce clusters and a method that may decline is the cheapest sanity check available. Here they agree, which is what you want from six points that separate this obviously.

Swapping methods is a one-line change: AgglomerativeClustering(n_clusters=best_k, linkage="ward"), DBSCAN(eps=0.6, min_samples=3), or GaussianMixture(n_components=best_k). On large data, MiniBatchKMeans updates centroids from small random batches and trades a little accuracy for a large speed gain.

Evaluating clusters

With no labels available, judgment comes from two directions.

Internal metrics describe geometry and nothing else. Silhouette runs from -1 to 1, higher being better. Davies-Bouldin is lower-is-better. Inertia is the within-cluster sum of squares. All three reward compact, well-separated, roughly spherical clusters, which means all three quietly prefer whatever k-means produces, and all three return respectable-looking values on pure noise.

External metrics compare against labels you already have. Prefer the Adjusted Rand Index and, in the mutual-information family, Adjusted rather than Normalized Mutual Information. scikit-learn's documentation is direct about why: "NMI and MI are not adjusted against chance", and NMI "will tend to increase as the number of different labels (clusters) increases, regardless of the actual amount of 'mutual information' between the label assignments". An earlier version of this article listed NMI without that caveat. Comparing two clusterings with different numbers of clusters using NMI is a comparison you will win by adding clusters.

Two checks are worth more than any of the metrics. The first is stability: recompute on resampled data and see whether the partition survives. The second is the one no library provides. Show the clusters to somebody who knows the domain, without telling them what the algorithm found, and see whether they recognize the groups and can say what they would do differently for each. A clustering nobody can act on differently is a clustering with one cluster in it.

What breaks when the data gets big

The following are our own timings, on a 2-core Intel Xeon at 2.10 GHz with 7 GB of RAM, scikit-learn 1.8.0 under Python 3.11.15. The data is make_blobs with 20 features and 12 well-separated clusters, standardized. Every method recovered the true clusters exactly (adjusted Rand index 1.000), so the only thing varying here is cost.

Measured on a single machine, one run per cell, on synthetic data that is kinder than yours. Your numbers will differ; the ratios are the point.

Read the columns rather than the cells. Between 5,000 and 20,000 points, a fourfold increase, k-means costs 12 times more and Ward linkage costs 47 times more. Between 20,000 and 100,000, k-means costs 4 times more and HDBSCAN costs 29 times more. The methods that scale linearly and the methods that scale quadratically are indistinguishable at small n and separated by two orders of magnitude by the time you reach a table that would fit in a spreadsheet.

The O(n²) wall is a memory wall, and it is closer than the timings suggest. A condensed float64 distance matrix needs n(n-1)/2 entries: 1.5 GiB at 20,000 points, 37 GiB at 100,000, and 3,725 GiB at a million. Anything that materializes pairwise distances, which includes hierarchical linkage, spectral clustering, plain silhouette scoring and a poorly parameterized DBSCAN, hits that number and stops. Hierarchical clustering on a million rows is not slow. It is impossible on one machine.

Three ways around it, in the order most people need them:

Sample for the metric, not for the model. silhouette_score(X, labels, sample_size=5000) cut scoring at 20,000 points from 6.13 s to 0.66 s and returned 0.666 against the exact value of 0.664. There is no reason to compute an exact silhouette on a large dataset.

Use the linear methods on the full data and the quadratic ones on a subsample. MiniBatchKMeans was the fastest thing measured at every size and lost no accuracy on this data. If a dendrogram is what you actually want, build it on 10,000 sampled rows and assign the rest by nearest representative.

Move to a GPU before moving to a cluster. cuML 26.06 provides KMeans, DBSCAN, HDBSCAN, AgglomerativeClustering and SpectralClustering on the GPU, with multi-GPU DBSCAN and KMeans through cuml.dask, and a cuml.accel mode that accelerates existing scikit-learn code without editing it. FAISS provides GPU k-means built for vector workloads, which is what you want after embedding. A single GPU covers a range of sizes that used to require a cluster, and it is a far smaller change to your code and your operations than distributing the job.

Clustering at scale: parallel computing and MapReduce

When the data genuinely outgrows one machine, the strategy has not changed in twenty years: cluster the chunks, then cluster the summaries.

• Map splits the data into chunks and gives each to a separate task, which clusters its own points and emits a compact description of each partial cluster: a centroid or medoid, a count, and spread statistics such as the sum of distances, the maximum distance and the sum of squared distances.
• Reduce collects those partial descriptions and merges the ones that belong together into a final clustering.

This works because the description of a partial cluster is tiny next to the points it describes, so the expensive pass over the data happens once, in parallel, and everything after that moves kilobytes.

The name comes from functional programming, and the earlier version of this article got a small detail wrong that is worth fixing since the article recommends checking things: in Python 3, map(square, [1, 2, 3, 4, 5]) does not return [1, 4, 9, 16, 25]. The language reference says it returns "an iterator that applies function to every item of iterable, yielding the results", and you get the list only by asking for one. reduce is no longer a built-in either; it lives in functools. The distributed version was published by Jeffrey Dean and Sanjay Ghemawat at OSDI 2004, in a paper reporting that "upwards of one thousand MapReduce jobs are executed on Google's clusters every day", and Google used it internally for web indexing, page ranking and document clustering.

Nobody hand-writes MapReduce for clustering now, and the state of the surrounding tools says why:

• Apache Spark MLlib is the usual answer for clustering that does not fit on one machine. Spark 4.2.0 shipped on 14 July 2026. Its clustering module offers exactly five algorithms: KMeans, Bisecting KMeans, Gaussian Mixture, LDA and Power Iteration Clustering. k-means uses kmeans||, a parallel variant of k-means++. There is no DBSCAN, no HDBSCAN and no general agglomerative clustering in MLlib, which is worth knowing before you plan a migration around a density-based method. Bisecting k-means is the only hierarchical option, and it is divisive rather than agglomerative.
• Apache Hadoop is still shipping, with 3.5.0 released on 2 April 2026, and MapReduce is still one of its four core modules. It is infrastructure now rather than an analytics interface.
• Apache Mahout, which was the MapReduce machine-learning library of the Hadoop era and shipped k-means, fuzzy k-means and canopy clustering, is now a quantum computing project whose current release is a Python library called Qumat. Tutorials that route you to Mahout for distributed clustering are pointing at something that no longer exists in that form.
• Dask-ML parallelizes scikit-learn-style APIs in Python, with its most recent release, 2025.1.0, dated February 2025. It works, and it is moving slowly.
• Streaming variants (streaming k-means, online mini-batch) handle data that never stops arriving, re-estimating cluster descriptions as points flow in. This is the case where centroids must be recomputed continually rather than fitted once.

The lesson survives the tooling churn intact: cluster the chunks in parallel, then cluster the summaries.

Where clustering stops working

Four situations where the honest answer is that this is the wrong tool.

When you cannot say what a cluster would mean. Clustering is a hypothesis generator. If no decision changes depending on which group a record falls into, the clusters are decoration, and they will be recomputed differently next quarter with different membership and the same absence of consequence.

When the features are mostly categorical. Distance between "Denmark" and "Portugal" is not a quantity. Gower distance and k-modes exist and work, but the result depends heavily on how you weighted the categorical part, and a well-chosen cross-tabulation often answers the question with less machinery and fewer assumptions.

When the dimensionality is high and unreduced. See the distance table above. Above a few dozen effective dimensions, every distance-based method is operating on differences that are close to uniform. Reduce first, and check that clusters found after reduction still make sense in the original space.

When you need the same answer twice. k-means depends on its seed. HDBSCAN depends on min_cluster_size. UMAP depends on its random state unless pinned. A customer segmentation that reshuffles every time the pipeline runs is worse than no segmentation, because the downstream systems will treat it as stable. Pin every seed, version the model artifact, and measure drift between runs deliberately instead of discovering it through a support ticket.

Real-world applications of clustering

• Customer segmentation groups buyers by behavior, usually on RFM axes of recency, frequency and monetary value, to target marketing and pricing. This is the most common commercial use and the one most exposed to the stability problem above: segments that reshuffle between quarterly runs cannot carry a strategy.
• Document and topic clustering organizes articles, support tickets or reviews by theme, now almost always by embedding the text and clustering the vectors. The BERTopic pipeline described earlier is the default shape.
• Anomaly and fraud detection treats points that fit no cluster as the finding. DBSCAN and HDBSCAN noise labels are the mechanism, which is why a method that can decline to assign is worth more here than a method that cannot.
• Image segmentation groups pixels into regions for computer vision and medical imaging.
• Recommendation clusters users or items to power "customers like you" suggestions.
• Web and marketing analytics clusters traffic sources or landing pages. The original motivation for this article was grouping referral channels by visits and pages-per-visit to see which behaved alike.
• Bioinformatics groups genes or patients by expression profile, and is where several of the evaluation methods above were developed.

Every one of these depends on a clean, well-structured dataset existing in the first place, usually assembled by web scraping and then deduplicated and normalized. Duplicates deserve particular attention before clustering, because a record that appears five times pulls a centroid toward itself five times and can manufacture a cluster out of a data-collection artifact. Where assembling and maintaining that pipeline is not the work you want to be doing, Scraping.Pro delivers datasets already scraped, cleaned and structured to a schema, and can run AI processing such as classification and entity extraction in the same pass.

The bottom line

Clustering turns an unlabeled pile of records into groups you can name and act on, and it will do the same to a pile of noise without changing its tone of voice. Three things carry most of the weight. Pick the family whose definition of a cluster matches your data and your question, remembering that the density family is the only one that can tell you there is nothing there. Pick a distance that reflects real similarity, and check what your scaling decision did to it. Validate with resampling and with a person who knows the domain, not with a single internal metric that rewards the geometry your algorithm was built to produce.

Then watch the size of the thing. Everything is fast at 5,000 rows. At 100,000 the quadratic methods have already stopped, and knowing which of your steps are quadratic is worth more than any tuning. When the input data is the bottleneck rather than the algorithm, we can deliver it ready to cluster.