What Are the Main Clustering Methods and Which to Use?

Clustering methods fall into a handful of broad families, each built on a different idea of what makes a group a group. The main ones are centroid-based methods like K-means, density-based methods like DBSCAN, hierarchical methods that build tree-like structures of nested groups, model-based approaches like Gaussian mixture models, and graph-based techniques like spectral clustering. Which one you should reach for depends on the shape of your data, its size, how many dimensions it has, and whether you already know how many clusters to expect. There is no single best method, but there are clear situations where each one shines or falls apart.

Centroid-Based Clustering

K-means is the most widely used clustering algorithm, and for good reason: it is fast, intuitive, and works well when your clusters are roughly spherical and similar in size. The algorithm picks a set of center points (centroids), assigns every data point to the nearest centroid, recalculates each centroid as the average of its assigned points, and repeats until the assignments stop changing. Its computational cost grows in proportion to the number of data points, dimensions, clusters, and iterations, which keeps it tractable even on large datasets.¹

The well-known weakness of K-means is its sensitivity to where those initial centroids land. A bad starting configuration can trap the algorithm in a poor solution. K-means++ addresses this by spreading initial centers apart before the main loop begins, which tends to produce better final clusters and faster convergence.² Even so, picking good starting points becomes harder as the number of clusters grows. An iterative refinement called I-k-means−+ takes a different approach: after an initial K-means run, it removes the weakest cluster, splits another one, and re-clusters. In experiments, this strategy roughly doubled accuracy over standard K-means and K-means++ on some datasets while remaining reasonably fast.³

K-means also demands that you specify the number of clusters up front, and it assumes clusters are convex blobs. If your data has elongated, irregular, or overlapping groups, K-means will force them into round shapes and give you misleading results. For datasets dominated by outliers, K-medoids is worth considering: instead of computing an average centroid, it picks an actual data point as the center of each cluster. This makes K-medoids less sensitive to outliers and noise, though it runs slower on large datasets.⁴

Density-Based Clustering

Density-based methods define clusters not by their centers but by where data points crowd together. DBSCAN is the flagship here: it identifies clusters as dense regions separated by sparse areas, requires no preset number of clusters, can detect clusters of arbitrary shape, and is robust to noise.⁵ Points that sit alone in sparse regions get flagged as noise rather than forced into a cluster, which is genuinely useful when your data has junk you want to exclude.

DBSCAN’s trade-off is that you have to set two parameters: a radius that defines “nearby” and a minimum number of points that qualifies a neighborhood as dense. Getting those wrong can merge distinct clusters or shatter a real cluster into fragments. When data has spatial indexing available (tree-based lookups for neighbors), DBSCAN runs efficiently. Without it, performance can degrade sharply on large datasets as every pair of points has to be compared.¹

DBSCAN also struggles when clusters in the same dataset have very different densities. A parameter setting that works for a tight cluster will miss a looser one. HDBSCAN was designed to fix this: it builds a hierarchy of density levels and extracts clusters at varying density thresholds, eliminating the need for the difficult-to-tune distance-scale parameter while supporting variable-density clusters. Its performance is comparable to DBSCAN on uniform-density data and significantly better on mixed-density data.⁶ The underlying framework produces a complete clustering hierarchy for an infinite range of density thresholds, which also supports outlier detection and visualization in a single pass.⁷

Hierarchical Clustering

Hierarchical agglomerative clustering (HAC) starts with every data point in its own cluster and progressively merges the two closest clusters until everything is in one big group. The result is a tree-like structure called a dendrogram that you can cut at any height to get a different number of clusters. This is appealing when you genuinely do not know how many clusters to expect, because a single run lets you explore multiple granularities without re-running the algorithm.

The critical decision is the “linkage” rule that defines how distance between two clusters is measured. Single linkage uses the shortest distance between any pair of points across two clusters; complete linkage uses the longest; average linkage uses the mean; and Ward’s method minimizes the total variance within clusters at each merge. These choices produce very different results. A comparison across unimodal and bimodal datasets found that many linkage methods falsely detected two clusters in data that actually had only one group, while single linkage was more resilient to those false positives.⁸ Ward’s method tends to produce compact, evenly sized clusters and is a popular default, but it assumes roughly spherical groups, much like K-means.

The main practical limitation is speed. In its basic form, HAC scales cubically with the number of data points, which makes it impractical for large datasets. Optimized implementations using priority queues can bring that down somewhat, but it still scales much less gracefully than K-means or DBSCAN.¹ For datasets with fewer than a few thousand points where you want to visually inspect the dendrogram, hierarchical clustering is excellent. For anything larger, you will likely need a different method or a sampling-based approximation.

Model-Based Clustering

Gaussian mixture models (GMMs) treat clustering as a probability problem: the data is assumed to come from a mixture of several Gaussian (bell-curve) distributions, each representing a cluster. The algorithm estimates the parameters of these distributions and assigns each data point a probability of belonging to each cluster rather than a hard assignment to just one. This “soft” membership is useful when clusters genuinely overlap, because a data point near the boundary between two groups gets partial credit for both rather than being forced into one.

GMMs are more flexible than K-means in terms of cluster shape. Because each Gaussian component has its own covariance structure, the model can capture elliptical clusters of varying size and orientation, not just round ones. The cost of that flexibility is computational: the running time depends on the number of data points, clusters, dimensions, and iterations, with a squared dependence on dimensionality that makes GMMs expensive in high-dimensional settings.¹ Like K-means, GMMs require you to specify the number of clusters in advance, though information criteria like BIC or AIC can guide that choice by balancing model fit against complexity.

Spectral and Graph-Based Clustering

Spectral clustering takes an entirely different route. Instead of working directly in the original feature space, it builds a graph where data points are nodes and edges are weighted by similarity. It then analyzes the structure of that graph using eigenvalue decomposition of a special matrix derived from it. This lets spectral clustering capture complex, non-linear relationships and detect non-convex clusters that methods like K-means would miss.⁹

The downside is cost. Constructing the similarity matrix already takes time that scales with the square of the number of data points, and the eigenvalue decomposition can scale cubically in the worst case, though sparse-matrix techniques can bring that down somewhat. Memory is also a concern because the full similarity matrix has to be stored.¹ Spectral clustering works best on moderate-sized datasets where the cluster boundaries are genuinely nonlinear and simpler methods fail. For very large datasets, approximate versions or a switch to a cheaper method is usually necessary.

How to Choose a Method

The right algorithm depends on several concrete properties of your data and your goals. Here is a practical framework for narrowing it down.

Data type: If all your features are numerical, you have the widest range of options. If some or all features are categorical, you need methods designed for that. K-modes (the categorical counterpart to K-means) and hierarchical clustering handle categorical data well when you expect a small number of groups. For more than about five expected groups in categorical or mixed data, DBSCAN or GMMs may be more appropriate.
Dataset size: For smaller datasets (under roughly a thousand points), K-means, K-medoids, and hierarchical clustering are all practical. For larger datasets, hierarchical clustering becomes too slow, and you are better off with K-means, DBSCAN, or Mini-Batch K-means.
Cluster shape: If clusters are roughly round and similar in size, K-means is hard to beat for speed and simplicity. If clusters are elongated, irregular, or vary in density, density-based methods like DBSCAN or HDBSCAN will do a better job. GMMs handle elliptical clusters well.
Known number of clusters: If you know how many groups to expect, K-means and GMMs let you specify that directly. If you have no idea, density-based methods and hierarchical clustering let the data suggest the number.
Noise and outliers: If your data has significant noise, DBSCAN and K-medoids handle it much better than K-means, which will pull centroids toward outliers.
Overlap between clusters: If groups genuinely bleed into each other and you want soft membership probabilities rather than hard assignments, GMMs are the natural choice.

A practical decision-tree approach suggests starting with data type and size. For small numerical datasets, K-means with the elbow method is a solid baseline. For linearly separable large datasets, K-means still works. For non-linearly separable large datasets, DBSCAN, spectral clustering, or GMMs become the better options.¹ In practice, many analysts run two or three methods on the same data and compare the results rather than betting everything on one algorithm.

Evaluating Cluster Quality

Once you have clusters, you need to know whether they are any good. When you do not have ground-truth labels (which is most of the time, since clustering is typically unsupervised), you rely on internal validation metrics. The most widely used include the silhouette coefficient, the Dunn index, the Calinski-Harabasz index, and the Davies-Bouldin index.¹⁰ All of them, in different ways, try to measure two things: how tightly packed the points within a cluster are, and how well separated different clusters are from each other.

The silhouette coefficient is probably the most intuitive. For each point, it compares how close the point is to others in its own cluster versus how close it is to the nearest neighboring cluster. A score near +1 means the point fits its cluster well; near 0 means it sits on the boundary; near −1 means it was probably assigned to the wrong cluster. Averaging this across all points gives an overall clustering quality score.

These metrics are also useful for choosing the number of clusters. The elbow method plots a measure of within-cluster tightness against increasing numbers of clusters and looks for the “elbow” where adding another cluster stops improving things much. Bayesian approaches offer a more principled way to select cluster count by balancing model fit against complexity.¹¹ No single metric is perfect, and different metrics can disagree, so it is common to look at several simultaneously.

The High-Dimensional Problem

Clustering in high-dimensional spaces is a different beast. When a dataset has hundreds or thousands of features, distance measures start to break down: in very high dimensions, most points become roughly equidistant from each other, which robs distance-based algorithms of their ability to distinguish close neighbors from far ones. Many of those dimensions are also irrelevant to the cluster structure and add pure noise.

Subspace clustering tackles this by searching for clusters in different subsets of dimensions rather than using all dimensions at once. The idea is that different clusters may be defined by different subsets of features, and a cluster that is clear in three dimensions might be invisible in the full feature space.¹² Feature selection, by contrast, removes irrelevant dimensions globally by analyzing the entire dataset, which helps but misses clusters that only show up in local subspaces.¹³

A more common practical approach is to reduce dimensions before clustering. Techniques like PCA (principal component analysis), t-SNE, or UMAP project the data into a lower-dimensional space that preserves the most important structure, and then you cluster in that reduced space. This works well in many cases, but any projection loses some information, and the choice of reduction method can steer the clustering results. If you are working with data that has more than a few dozen features, some form of dimension reduction or subspace analysis is usually necessary before standard clustering algorithms will produce meaningful results.

Cluster Stability and Reproducibility

A result that changes dramatically with minor perturbations to the data is not trustworthy. Cluster stability, the degree to which the same clusters appear when you rerun the analysis on slightly different subsets of the data, is one of the most important and most overlooked aspects of clustering. Bootstrapping is a straightforward way to test this: resample the data with replacement many times, cluster each resampled dataset, and see how consistently the same groups show up.¹⁴

K-means is particularly vulnerable here because its random initialization means different runs on the same data can yield different results. The standard remedy is to run K-means many times with different random starts and keep the best solution, but even then, stability testing should follow. Hierarchical clustering, by contrast, is deterministic (given the same data and linkage rule, it always produces the same tree), though the results can still shift substantially when you add or remove a few data points. DBSCAN is also deterministic in its core assignments, but “border” points near the edge of dense regions can flip between clusters or noise status depending on the order data is processed.

Ensemble clustering, also called consensus clustering, offers another angle on the stability question. Instead of relying on a single algorithm, you generate a library of clustering solutions, possibly using different algorithms, different parameter settings, or different random seeds, and combine them into a single consensus solution. This has been shown to provide more robust results across a wide range of datasets than any individual method alone.¹⁵ If you are making a high-stakes decision based on clustering results, an ensemble approach or at minimum a stability check should be part of the workflow.

Deep Clustering and Learned Representations

Traditional clustering methods operate on the raw features you give them or on simple transformations of those features. Deep clustering flips this by using neural networks to learn a representation of the data that is specifically designed to make clusters easier to find. The network and the clustering objective are trained together, so the representation and the groupings evolve jointly.¹⁶

This matters most for data types where raw features are not very informative on their own, like images, text, or genomic sequences. A pixel-level comparison of two photos of cats will not reveal that both are cats, but a neural network trained to extract visual features can map those images to a space where “cat” images cluster naturally. Deep clustering has been applied broadly in image segmentation, natural language processing, and bioinformatics, and it is increasingly the default approach when the data is complex enough that hand-crafted features would miss important structure.

The trade-off is complexity. Deep clustering requires substantially more compute, more hyperparameter tuning, and more data than classical methods. For tabular data with well-defined numeric features, K-means or DBSCAN will usually outperform a neural network approach simply because the data does not need a learned representation. Deep clustering earns its keep when the gap between raw features and meaningful structure is wide enough that traditional methods cannot bridge it.

Common Misconceptions About Clustering

One persistent myth is that there is always a “right” number of clusters hiding in the data, and the algorithm’s job is to find it. In reality, many datasets do not have a single natural grouping. The number of clusters depends on the granularity you care about: you might split customers into three broad segments or thirty narrow ones, and neither answer is wrong. Validation metrics can guide you, but they are not oracles. Different metrics will sometimes point to different numbers of clusters, because they encode different definitions of what a “good” cluster looks like.

Another common mistake is treating the output of a clustering algorithm as ground truth. Clustering is exploratory. The algorithm is pattern-matching based on the features and distance measure you chose, and changing those inputs can dramatically change the output. Two researchers with the same dataset but different feature engineering choices can arrive at entirely different clusterings, both internally valid. This does not mean clustering is useless; it means the results are hypotheses about structure in the data, not discoveries of fixed categories.

Finally, people frequently underestimate the role of data preprocessing. Clustering algorithms that rely on distance (which is most of them) are sensitive to feature scaling. If one feature is measured in thousands and another in fractions, the first feature will dominate the distance calculations and effectively determine the clusters by itself. Standardizing features to comparable scales before clustering is almost always necessary and almost always the step that gets forgotten. The same goes for handling missing values, which most clustering algorithms cannot process natively and which, if handled poorly, can create phantom clusters or obscure real ones.

1
PubMed Central. Comprehensive analysis of clustering algorithms: exploring limitations and innovative solutions
2
Reliability: Theory & Applications. PERFORMANCE COMPARISON OF K-MEANS, PARALLEL K-MEANS AND K-MEANS++
3
Pattern Recognition. I-k-means−+: An iterative clustering algorithm based on an enhanced version of the k-means
4
Procedia Computer Science. Analysis of K-Means and K-Medoids Algorithm For Big Data
5
Proceedings of the ACM on Management of Data. Approximate DBSCAN via Density-Biased Sampling and Kernel Density Estimation
6
arXiv. Accelerated Hierarchical Density Clustering
7
ACM Transactions on Knowledge Discovery from Data. Hierarchical Density Estimates for Data Clustering, Visualization, and Outlier Detection
8
Physica A: Statistical Mechanics and its Applications. Revisiting agglomerative clustering
9
arXiv. A Comprehensive Survey on Spectral Clustering with Graph Structure Learning
10
PubMed Central. Comparative Analysis of the Clustering Quality in Self-Organizing Maps for Human Posture Classification
11
PubMed Central. Bayesian Clustering Factor Models
12
ACM SIGKDD Explorations Newsletter. Subspace clustering for high dimensional data
13
ACM Transactions on Knowledge Discovery from Data. Clustering high-dimensional data
14
PubMed. Bootstrapping cluster analysis: assessing the reliability of conclusions from microarray experiments
15
European Journal of Operational Research. Cluster ensemble selection and consensus clustering: A multi-objective optimization approach
16
IEEE Transactions on Neural Networks and Learning Systems. Deep Clustering: A Comprehensive Survey