What Are the Different Clustering Algorithms Used?

K-means is the first clustering algorithm most people learn. It works well when your clusters are spherical and evenly sized.

But real data rarely cooperates. When your clusters are elongated, overlapping, or noisy, K-means forces square pegs into round holes. The right algorithm depends on what your data actually looks like, and picking wrong means your groups are meaningless.

What you need

• Python 3 with scikit-learn, numpy, matplotlib
• Understanding that clustering is unsupervised (no labels, no correct answer to check against)
• A dataset you want to group
• Willingness to try more than one algorithm on the same data

K-means: centroid-based clustering

K-means partitions data into k clusters by minimizing the distance between points and their cluster centroid. It iterates until centroids stabilize. The algorithm is fast and scales well, but it assumes clusters are convex and roughly equal in size.

from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs
import matplotlib.pyplot as plt

X, _ = make_blobs(n_samples=300, centers=4, random_state=42)
kmeans = KMeans(n_clusters=4, random_state=42)
labels = kmeans.fit_predict(X)
plt.scatter(X[:, 0], X[:, 1], c=labels, cmap='viridis')
plt.title('K-means on blobs')
plt.show()

K-means works when clusters are well-separated and round. It fails on crescents, rings, or when one cluster has many more points than another. The algorithm also depends on initialization — set random_state for reproducible results.

DBSCAN: density-based clustering

DBSCAN groups points that are closely packed together and marks outliers as noise. It needs two parameters: eps (neighborhood radius) and min_samples. Unlike K-means, DBSCAN finds clusters of arbitrary shape and ignores noise without being told how many clusters to expect.

from sklearn.cluster import DBSCAN
from sklearn.datasets import make_moons

X, _ = make_moons(n_samples=300, noise=0.1, random_state=42)
dbscan = DBSCAN(eps=0.2, min_samples=5)
labels = dbscan.fit_predict(X)
n_clusters = len(set(labels)) - (1 if -1 in labels else 0)
print(f'Clusters found: {n_clusters}')
print(f'Noise points: {list(labels).count(-1)}')

Output: Clusters found: 2, Noise points: 0

DBSCAN handles irregular shapes and noise. It struggles when clusters have very different densities because a single eps value cannot capture both tight and loose groupings.

Agglomerative clustering: hierarchy

Agglomerative clustering builds a tree of merges. Each point starts as its own cluster, and the closest pairs merge iteratively until the target number of clusters remains. The result is a dendrogram you can cut at any height.

from sklearn.cluster import AgglomerativeClustering
from sklearn.datasets import make_moons

X, _ = make_moons(n_samples=300, noise=0.1, random_state=42)
agg = AgglomerativeClustering(n_clusters=2)
labels = agg.fit_predict(X)
print(f'Cluster counts: {len([l for l in labels if l==0])}, {len([l for l in labels if l==1])}')

Output: Cluster counts: 202, 98

Agglomerative clustering gives you a dendrogram to choose k after the fact. It is slower than K-means for large datasets because the distance matrix grows quadratically with n. Use it when you need a hierarchy, not just flat groups.

MeanShift: find clusters without guessing k

MeanShift discovers blobs in the data density by shifting candidate centroids toward the local mean. It stops when centroids settle. The algorithm decides the number of clusters on its own, which is its main advantage over K-means.

from sklearn.cluster import MeanShift
from sklearn.datasets import make_blobs

X, _ = make_blobs(n_samples=300, centers=4, random_state=42)
ms = MeanShift()
labels = ms.fit_predict(X)
print(f'Clusters found: {len(set(labels))}')

Output: Clusters found: 4

MeanShift is slow for large datasets because each point is a candidate centroid. The bandwidth parameter controls the window size. Too small and every point becomes its own cluster.

Too large and everything merges into one blob.

Spectral clustering: when shape defeats distance

Spectral clustering uses eigenvalues of a similarity matrix to reduce dimensionality before clustering. It is designed for non-convex shapes like nested circles where K-means and DBSCAN both fail.

from sklearn.cluster import SpectralClustering
from sklearn.datasets import make_circles

X, _ = make_circles(n_samples=300, factor=0.5, noise=0.05, random_state=42)
sc = SpectralClustering(n_clusters=2, affinity='nearest_neighbors', random_state=42)
labels = sc.fit_predict(X)
print(f'Inner cluster: {len([l for l in labels if l==0])}')
print(f'Outer cluster: {len([l for l in labels if l==1])}')

Output: Inner cluster: 150, Outer cluster: 150

Spectral clustering handles nested circles and manifolds that break distance-based methods. It is expensive — O(n³) in the naive implementation — so use it on datasets under a few thousand points.

Gaussian Mixture Models: soft clustering

Gaussian Mixture Models (GMM) assume data comes from a mixture of Gaussian distributions. Each point gets a probability of belonging to every cluster instead of a hard assignment. This matters when your clusters overlap.

from sklearn.mixture import GaussianMixture
from sklearn.datasets import make_blobs
import numpy as np

X, _ = make_blobs(n_samples=300, centers=3, random_state=42)
gmm = GaussianMixture(n_components=3, random_state=42)
labels = gmm.fit_predict(X)
probs = gmm.predict_proba(X)
print(f'Max probability: {np.max(probs[0]):.3f}')
print(f'Cluster means: {len(gmm.means_)}')

Output: Max probability: 0.999, Cluster means: 3

GMM gives you uncertainty. When max probability is low, the point sits between clusters and forcing a hard call loses information. Use GMM when overlap is real, not noise.

OPTICS: DBSCAN without the eps headache

OPTICS is a density-based algorithm that produces a reachability plot instead of flat clusters. It removes DBSCAN’s sensitivity to eps by capturing the density structure across all radii. You extract clusters from the plot afterward.

from sklearn.cluster import OPTICS
from sklearn.datasets import make_moons

X, _ = make_moons(n_samples=300, noise=0.1, random_state=42)
optics = OPTICS(min_samples=5)
labels = optics.fit_predict(X)
n_clusters = len(set(labels)) - (1 if -1 in labels else 0)
print(f'Clusters found: {n_clusters}')

Output: Clusters found: 2

OPTICS is slower than DBSCAN but handles varying densities better. The reachability plot shows cluster structure visually — valleys are clusters, peaks are gaps between them.

BIRCH: clustering for large datasets

BIRCH builds a tree structure (CF-Tree) that summarizes clusters without storing every point. It processes data in a single pass and produces subclusters you can then feed into another algorithm like K-means.

from sklearn.cluster import Birch
from sklearn.datasets import make_blobs

X, _ = make_blobs(n_samples=10000, centers=5, random_state=42)
birch = Birch(threshold=0.5, n_clusters=5)
labels = birch.fit_predict(X)
print(f'Clusters found: {len(set(labels))}')
print(f'Subcluster count: {birch.subcluster_centers_.shape[0]}')

Output: Clusters found: 5, Subcluster count: 67

BIRCH reduces 10,000 points to 67 subclusters, then K-means finishes the job on those 67. Use BIRCH when you have too much data for the other algorithms to handle in memory.

Comparison

How to choose

Start with these questions in order:

• Do you know how many clusters there are? If yes, use K-means or Agglomerative. If no, use DBSCAN or MeanShift.
• Are your clusters spherical? If yes, K-means is fast and good enough. If no, use DBSCAN or Spectral.
• Do you have noise or outliers? Yes, use DBSCAN or OPTICS. No, use K-means or GMM.
• Is the dataset large (over 10k points)? Yes, use BIRCH. No, any algorithm works.
• Do clusters overlap? Yes, use GMM for soft assignment. No, stick with hard clustering.

Edge cases

• K-means: if k is wrong, results are meaningless. Use the elbow method or silhouette score to choose. Run with multiple k values and compare.
• DBSCAN: if eps is too small, everything is noise. If too large, everything is one cluster. Try values between the 3rd and 7th nearest-neighbor distances.
• Agglomerative: linkage choice (ward, complete, average) changes results. Ward works best for spherical clusters. Complete handles elongated ones.
• MeanShift: bandwidth too large merges distinct clusters. Too small splits natural groups. Use estimate_bandwidth from scikit-learn as a starting point.
• Spectral: breaks on disconnected similarity graphs. Ensure every point has at least one neighbor within the threshold.
• GMM: fails when clusters are not roughly Gaussian. Heavy tails or skewed distributions produce misleading probabilities.
• OPTICS: the reachability plot can have spurious peaks. Use the xi-cluster extraction method for more stable results.
• BIRCH: the threshold parameter controls subcluster granularity. Too fine and you get thousands of subclusters. Too coarse and distinct groups merge prematurely.

FAQ

Common questions about clustering algorithms in Python.

How do I choose k for K-means?

Run K-means for k from 2 to 10, plot inertia (sum of squared distances), and look for the elbow where adding more clusters gives diminishing returns. The silhouette score is another metric that measures how similar a point is to its own cluster versus the nearest other cluster.

When should I use DBSCAN over K-means?

Use DBSCAN when you do not know how many clusters there are, when clusters have irregular shapes, or when your data has noise and outliers. K-means forces every point into a cluster even if it does not belong anywhere. DBSCAN marks those as noise.

Is Agglomerative clustering the same as hierarchical clustering?

Agglomerative is one type of hierarchical clustering (bottom-up). Divisive hierarchical clustering starts with one cluster and splits top-down, but it is rarely used because it is computationally expensive. When people say “hierarchical clustering” they almost always mean agglomerative.

Can I use clustering for classification?

Not directly. Clustering finds groups without labels. But you can cluster first, then assign labels to each cluster based on the majority class of labeled points that fall into it.

This is called constrained clustering or semi-supervised learning.

Which algorithm is best for high-dimensional data?

Distance metrics become unreliable in high dimensions. Reduce dimensionality first with PCA or t-SNE, then apply K-means or DBSCAN. Spectral clustering can work directly on high dimensions if you use a nearest-neighbor affinity graph.

How do I evaluate clustering results?

Without ground truth labels, use silhouette score (higher is better), Davies-Bouldin index (lower is better), or Calinski-Harabasz index (higher is better). With labels, use adjusted Rand index or normalized mutual information. Never evaluate clustering by eye on the first two PCA components — you lose information that matters.

What is the curse of dimensionality for clustering?

In high dimensions, the distance between any two points converges to the same value. Euclidean distance stops discriminating. Before clustering, reduce dimensions with PCA, UMAP, or t-SNE.

Most clustering algorithms assume meaningful distances in the feature space.

Should I normalize my data before clustering?

Yes. K-means and DBSCAN use Euclidean distance. If one feature ranges from 0 to 1 and another from 0 to 10000, the second feature dominates.

Use StandardScaler or MinMaxScaler to put all features on the same scale before clustering.