Clustering Algorithms

Clustering finds groups of similar items in unlabelled data. The algorithms make different assumptions about what "groups" look like; picking the wrong one produces strange results. This page is the working set, with the assumptions and failure modes of each.

K-means

The classic. Pick K; iteratively assign points to the nearest centroid; recompute centroids.

```

init centroids randomly

repeat:

assign each point to nearest centroid

update each centroid to mean of its points

until convergence

```

Assumes:

- Spherical clusters of roughly equal size.

- Clusters defined by Euclidean distance from a centroid.

- You know K in advance.

Strengths: fast (O(NKI)); simple; understood; widely-implemented.

Weaknesses:

- Bad on non-spherical clusters (elongated, U-shaped, nested).

- Bad on clusters of very different sizes.

- Sensitive to outliers (centroids shift toward them).

- K-means++ initialisation is critical; random init produces local minima.

Use K-means when: clusters are roughly spherical and you have a reasonable K.

Don't use when: clusters have variable density, shape, or size; outliers matter; you can't choose K.

K-medoids (PAM)

Like K-means but cluster centres are actual data points (medoids), not centroids. More robust to outliers.

Slower than K-means. Useful when your distance metric isn't Euclidean (you can use any distance) or when outliers are a problem.

Hierarchical clustering (agglomerative)

Start with each point as its own cluster; iteratively merge nearest clusters. Produces a dendrogram (tree).

```

each point is a cluster

repeat:

find the two nearest clusters

merge them

until one cluster

```

The "nearest" depends on linkage:

- **Single** — minimum distance between clusters. Produces stringy clusters.

- **Complete** — maximum distance. Compact clusters.

- **Average** — mean distance. Compromise.

- **Ward** — minimises within-cluster variance. Often produces best clusters; computationally similar to K-means.

Strengths: no need to choose K up front (cut the dendrogram at any level); produces a hierarchy that's interpretable.

Weaknesses: O(N²) memory; O(N³) time naively. Doesn't scale beyond ~10k-100k points.

Use when: you want hierarchy; data isn't huge.

DBSCAN

Density-based. A cluster is a region where points have many neighbours within distance `eps`. Points in low-density regions are noise.

Two parameters: `eps` (distance threshold) and `min_samples` (minimum density).

Strengths:

- Finds non-spherical clusters.

- Handles noise / outliers explicitly.

- No need to choose K.

Weaknesses:

- Sensitive to `eps`. Wrong choice produces all-noise or one-huge-cluster.

- Can't handle clusters of very different densities.

- O(N²) without indexing; with kd-tree / ball tree, O(N log N).

Use when: clusters have similar density; you don't know K; outliers are real.

HDBSCAN

Hierarchical DBSCAN. Builds a hierarchy then extracts clusters at varying density. Solves DBSCAN's "single eps" problem.

Strengths:

- Handles variable density.

- Doesn't need `eps`.

- Robust noise detection.

- Stable across hyperparameter ranges.

Weaknesses:

- More complex than DBSCAN.

- Slower than K-means but much smarter on real data.

Use when: real-world clustering, especially on embeddings. The default for document clustering, customer segmentation, anomaly detection. See [DocumentClusteringApproaches]().

Gaussian Mixture Models (GMM)

Assume data is generated from K Gaussian distributions with different means and covariances; learn the parameters.

Strengths:

- Soft clustering — each point has probabilities for each cluster.

- Handles elliptical clusters (not just spherical).

- Probabilistic framing — useful for uncertainty quantification.

Weaknesses:

- Need to choose K.

- Slower than K-means.

- Failure on non-Gaussian data (clusters with funny shapes).

Use when: clusters are roughly elliptical; soft assignment matters; you can choose K with cross-validation or BIC.

Spectral clustering

Build a similarity graph; compute eigenvectors of its Laplacian; cluster in eigenvector space.

Strengths:

- Handles arbitrary cluster shapes (gracefully clusters concentric circles, half-moons, etc.).

- Theoretically well-founded.

Weaknesses:

- O(N³) eigendecomposition. Doesn't scale.

- Sensitive to choice of similarity graph and number of components.

Use when: data has clear graph structure; small N; classical methods fail on the geometry.

Mean-shift

Like K-means but each point shifts toward the local density mode. Number of clusters emerges from the data.

Strengths: no K; finds modes of any shape.

Weaknesses: O(N²); bandwidth parameter is sensitive; rarely the best choice.

OPTICS

Density-based like DBSCAN; produces a reachability plot from which you can extract clusters at varying density.

Less popular than HDBSCAN now; HDBSCAN is the modern preferred choice.

BIRCH

Streaming-friendly clustering. Builds a CF tree summary; clusters from that.

Use when: data is too large to hold in memory.

Choosing an algorithm

A decision flow:

1. **Embedding-based clustering, real-world corpora?** UMAP + HDBSCAN.

2. **Spherical clusters, large data, fast result?** K-means.

3. **Want hierarchy?** Agglomerative.

4. **Want soft assignment / probabilistic?** GMM.

5. **Variable density, shape, outliers?** HDBSCAN.

6. **Strange geometric shapes (rings, half-moons)?** Spectral.

7. **Streaming data?** BIRCH or online K-means.

For most production work in 2026: K-means for fast simple cases, HDBSCAN for real data complexity. The rest are specialised.

How to choose K

For algorithms requiring K:

- **Elbow method** — plot within-cluster variance vs K; pick the "elbow." Subjective.

- **Silhouette score** — measures cluster cohesion vs separation. Pick K that maximises.

- **Gap statistic** — compares to expected variance under null reference. More principled.

- **BIC / AIC** for GMM.

For clustering you can manually inspect: try a few K, look at the clusters, pick what looks right. Often the most useful approach.

Distance / similarity matters

The choice of distance metric affects cluster shapes:

- **Euclidean (L2)** — default; sensitive to scale.

- **Cosine** — angle between vectors; standard for embeddings.

- **Manhattan (L1)** — robust to outliers in individual dimensions.

- **Hamming** — for binary vectors.

- **Custom** — whatever your domain's notion of similarity is.

For high-dimensional data (especially embeddings), cosine is usually the right pick. For low-dimensional numeric features, Euclidean.

Always normalise / standardise features for distance-based methods. Otherwise the dimension with the largest scale dominates.

Failure modes

- **Curse of dimensionality.** All distances become similar in high dimensions; clustering loses signal. Reduce dimensionality first (UMAP, PCA).

- **Wrong assumptions.** Using K-means on non-spherical data; getting weird clusters; blaming the data when the algorithm is wrong.

- **Outliers eating clusters.** K-means is famously sensitive; use HDBSCAN or pre-remove outliers.

- **Ignoring noise.** Some points genuinely don't fit anywhere; HDBSCAN labels them; don't force them.

- **Not validating.** Numerical metrics (silhouette) only go so far; manual inspection of clusters is the real test.

Evaluation

Internal validation (no labels):

- Silhouette coefficient.

- Davies-Bouldin.

- Calinski-Harabasz.

External validation (with ground-truth labels):

- Adjusted Rand Index.

- Normalised Mutual Information.

- Purity.

For production: have a small labelled set; compute external metrics; trust them more than internal ones.

A pragmatic recipe

For a new clustering task:

1. **Visualise** the data first. Plot in 2D (PCA or UMAP). Eyeball the structure.

2. **Pick algorithm based on what you see**. Spherical blobs → K-means; complex shapes → HDBSCAN.

3. **Try with default parameters**. Inspect results manually.

4. **Tune incrementally**. One parameter at a time.

5. **Validate against domain experts** or labelled samples.

Most clustering tasks don't need fancy algorithms. They need sensible preprocessing, a reasonable algorithm, and human inspection of the output.