Clustering Algorithms Comparison

Explore the performance differences among K-means DBSCAN and agglomerative clustering algorithms. Learn their advantages disadvantages and best use cases to decide the optimal clustering approach for your specific dataset and task requirements.

We'll cover the following...

K-means
- K-means clustering comparison example
DBSCAN
- DBSCAN clustering comparison example
Agglomerative clustering
- Agglomerative clustering comparsion example
Conclusion

In previous lessons, we explored three fundamentally different unsupervised techniques: the centroid-based K-means algorithm, the density-based DBSCAN algorithm, and the hierarchical agglomerative clustering algorithm. While all aim to group similar data points into clusters, each operates under unique assumptions and performs best with different types of data structures. This lesson shifts the focus from how the algorithms work to comparing their performance, strengths, and weaknesses, helping determine the most appropriate clustering approach for a given dataset.

$K$ -means

This is a centroid-based algorithm or a distance-based algorithm, where we calculate the distances to assign a point to a cluster. $K$ -means starts by randomly selecting $k$ initial centroids and then assigns each data point to the cluster corresponding to the nearest centroid. The centroids are then updated to the mean of the points in the corresponding cluster, and the process is repeated until convergence.

Advantages of K-means clustering

Simple and easy to implement
Computationally efficient, even for large datasets
Works well when clusters are spherical and well separated
Scales effectively with the number of data points
Produces clear and interpretable cluster centers

Disadvantages of K-means clustering

Requires the number of clusters (k) to be specified in advance
Sensitive to the initial placement of centroids
Can get stuck in local optima
Performs poorly with non-spherical or unevenly sized clusters
Highly sensitive to outliers and noise

Python 3.10.4

import numpy as np
from sklearn.cluster import KMeans, DBSCAN, AgglomerativeClustering
from sklearn.metrics import pairwise_distances
import matplotlib.pyplot as plt
# Generating synthetic data
np.random.seed(42)
X = np.concatenate([np.random.normal(0, 1, size=(100, 2)),
                    np.random.normal(1, 1, size=(100, 2)),
                    np.random.normal(2, 1, size=(100, 2))])
# Defining the number of clusters for KMeans and AgglomerativeClustering
n_clusters = 3
# Initializing the KMeans model and computing its Minkowski distance
kmeans = KMeans(n_clusters=n_clusters)
kmeans_pred = kmeans.fit_predict(X)
kmeans_score = np.mean(pairwise_distances(X, kmeans.cluster_centers_, metric='minkowski'))
# Initializing the DBSCAN model and computing its Minkowski distance
dbscan = DBSCAN()
dbscan_pred = dbscan.fit_predict(X)
dbscan_score = np.mean(pairwise_distances(X, dbscan.components_, metric='minkowski'))
# Initializing the AgglomerativeClustering model and computing its Minkowski distance
agg = AgglomerativeClustering(n_clusters=n_clusters)
agg_pred = agg.fit_predict(X)
agg_score = np.mean(pairwise_distances(X, X[agg_pred==0], metric='minkowski'))
# Comparing the scores
print(f'KMeans score: {kmeans_score:.2f}')
print(f'DBSCAN score: {dbscan_score:.2f}')
print(f'AgglomerativeClustering score: {agg_score:.2f}')
# Plotting actual dataset along with the one where clusters 
# have been highlighted side by side
fig, axs = plt.subplots(1, 4, figsize = (16, 8))
axs[0].scatter(x=X[:100,0], y=X[:100,1], alpha = 0.5)
axs[0].scatter(x=X[100:200,0], y=X[100:200,1], alpha = 0.5)
axs[0].scatter(x=X[200:300,0], y=X[200:300,1], alpha = 0.5)
axs[0].set_title("Actual dataset")
titles = {1: "K-Means", 2: "DBSCAN", 3:"Agglomerative Clustering"}
for i, cpred in zip(range(1,4), [kmeans_pred, dbscan_pred, agg_pred]):
  axs[i].scatter(x=X[:, 0], y=X[:, 1],  c=cpred, alpha = 0.5)
  axs[i].set_title(titles[i])
plt.show()

In this example, we generated synthetic data with three clusters that are separated by a small distance. The data is generated using three normal distributions with different means and standard deviations.

When applied to this data, K-means is able to identify the three clusters more accurately than DBSCAN and agglomerative clustering, as shown by the lower Minkowski distance score of 1.98. This score (discussed in detail later) is a measure of how tightly clustered the points are around their centroids, and a lower value indicates superior performance for this type of data. DBSCAN struggles because the maximum distance between two points to be considered in the same cluster ( $\epsilon$ ) isn’t satisfied, and agglomerative clustering struggles to separate the clusters properly because they’re too close together.

Advantages of DBSCAN

Does not require the number of clusters to be specified in advance
Can identify arbitrarily shaped clusters
Naturally detects noise and outliers
Less sensitive to initialization compared to centroid-based methods
Works well for datasets with clear density differences

Disadvantages of DBSCAN

Sensitive to the choice of eps and min_samples parameters
Struggles when clusters have varying densities
Performance can degrade in high-dimensional data
Choosing optimal parameters can be difficult without domain knowledge
Not as efficient as K-means for very large datasets

DBSCAN clustering comparison example

One scenario where DBSCAN might perform better than $k$ -means and agglomerative clustering is when the data contains clusters of varying densities.

$K$ -means and agglomerative clustering are both sensitive to initial conditions, and can be sensitive to the shape and size of the clusters. DBSCAN, on the other hand, doesn’t require the user to specify the number of clusters or the shape of the clusters. It can identify clusters of varying densities and is less sensitive to the initial conditions.

Here is an example where DBSCAN outperforms $k$ -means and agglomerative clustering on a synthetic dataset with two clusters of varying densities:

Python 3.10.4

import matplotlib.pyplot as plt
from sklearn.datasets import make_blobs
from sklearn.cluster import DBSCAN, KMeans, AgglomerativeClustering
# Generating synthetic dataset with two clusters of varying densities
X, y = make_blobs(random_state=0, n_samples=1000, centers=[(0, 0), (5, 5)])
X[:50] += 10
X[50:100] += 5
# Fitting and predicting using DBSCAN
db = DBSCAN(eps=1, min_samples=5)
pred_db = db.fit_predict(X)
# Fitting and predicting using K-means
km = KMeans(n_clusters=2)
pred_km = km.fit_predict(X)
# Fitting and predicting using agglomerative clustering
agg = AgglomerativeClustering(n_clusters=2)
pred_agg = agg.fit_predict(X)
# Plotting the results
fig, axs = plt.subplots(1, 3, figsize=(10, 3))
for ax, title, y_pred in zip(axs, ['DBSCAN', 'K-Means', 'Agglomerative Clustering'], 
                             [pred_db, pred_km, pred_agg]):
    ax.scatter(X[:, 0], X[:, 1], c=y_pred)
    ax.set_title(title)
    ax.set_xticks([])
    ax.set_yticks([])
plt.show()

Advantages of agglomerative clustering

Produces a hierarchical structure of clusters
Can be visualized using a dendrogram
Does not rely on random initialization
Works with different distance metrics and linkage methods
Can capture complex and nonspherical cluster shapes

Disadvantages of agglomerative clustering

Computationally expensive, especially for large datasets
Requires the number of clusters or a cutoff distance to be specified
Sensitive to noise and outliers
Early merging decisions cannot be undone
Not suitable for very high-dimensional or very large datasets

Agglomerative clustering comparsion example

Imagine that we have a dataset with a large number of samples that are organized into several distinct, nonspherical clusters. In this case, $k$ -means might struggle to find the correct clusters because it’s designed to find clusters that are spherical in shape. Similarly, DBSCAN might also struggle to find the correct clusters because it’s designed to find clusters that are dense in terms of the number of samples they contain.

However, agglomerative clustering doesn’t assume that the clusters are spherical or dense. Instead, it begins by treating each sample as its own cluster and then iteratively merges the closest clusters together until a stopping condition is reached. This makes it well-suited for finding clusters that aren’t spherical or dense in shape.

You can change the hyperparameters in the following coding playground to observe the performance of each technique:

Python 3.10.4

import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import make_blobs
from sklearn.cluster import KMeans, DBSCAN, AgglomerativeClustering
# Generating a synthetic dataset with nonspherical clusters
X, y = make_blobs(n_samples=1000, centers=5, random_state=0)
# Fitting and predicting using K-means
kmeans = KMeans(n_clusters=5)
y_pred_kmeans = kmeans.fit_predict(X)
# Fitting and predicting using DBSCAN
dbscan = DBSCAN()
y_pred_dbscan = dbscan.fit_predict(X)
# Fitting and predicting using AgglomerativeClustering
agglomerative = AgglomerativeClustering(n_clusters=5)
y_pred_agglomerative = agglomerative.fit_predict(X)
# Plotting the clusters
fig, axs = plt.subplots(1, 3, figsize=(12, 4))
titles = ["Agglomerative Clustering", "KMeans", "DBSCAN"]
models = [y_pred_agglomerative, y_pred_kmeans, y_pred_dbscan]
for ax, title, model in zip(axs, titles, models):
    ax.scatter(X[:, 0], X[:, 1], c=model)
    ax.set_title(title)
plt.show()

Comparison of clustering algorithms

Feature	K-means	DBSCAN	Agglomerative Clustering
Type	Centroid-based	Density-based	Hierarchical (Linkage-based)
Input k	Required	Not required	Required (or a cutoff distance)
Cluster shape	Assumes spherical	Identifies arbitrary shapes	Flexible; depends on linkage
Outlier handling	Poor (Outliers distort centroids)	Excellent (Outliers labeled as noise)	Poor (Outliers force early merges)
Efficiency	High (Fast for large N)	Medium	Low (Computationally expensive)
Primary output	Final cluster labels	Final cluster labels + Noise labels	Dendrogram or cluster labels

Conclusion

This comparison demonstrates that no single clustering algorithm is universally superior. K-means is the go-to choice for large datasets with expected spherical clusters.

DBSCAN excels in identifying arbitrarily shaped clusters and managing noise effectively.

Agglomerative clustering is best utilized when the hierarchical relationship between data points is important. Selecting the appropriate algorithm always requires knowledge of the data’s underlying structure and the goal of the clustering task.

1.Course Overview

2.Supervised Learning

Project

3.Clustering

Mini Project

4.Generalized Linear Regression

Mini Project

5.Support Vector Machine

6.Logistic Regression

7.Ensemble Learning

Mini Project

8.Decoding Dimensions: PCA and Autoencoders

Mini Project

Mini Project

Mini Project

9.Appendix

10.Wrapping Up

Project

Clustering Algorithms Comparison

$K$ -means

Advantages of K-means clustering

Disadvantages of K-means clustering

$K$ -means clustering comparison example

DBSCAN

Advantages of DBSCAN

Disadvantages of DBSCAN

DBSCAN clustering comparison example

Agglomerative clustering

Advantages of agglomerative clustering

Disadvantages of agglomerative clustering

Agglomerative clustering comparsion example

Comparison of clustering algorithms

Conclusion

Clustering Algorithms Comparison

KKK-means

Advantages of K-means clustering

Disadvantages of K-means clustering

KKK-means clustering comparison example

DBSCAN

Advantages of DBSCAN

Disadvantages of DBSCAN

DBSCAN clustering comparison example

Agglomerative clustering

Advantages of agglomerative clustering

Disadvantages of agglomerative clustering

Agglomerative clustering comparsion example

Comparison of clustering algorithms

Conclusion

$K$ -means

$K$ -means clustering comparison example