Unsupervised Clustering: K-Means & DBSCAN

Group unlabelled data points by Euclidean centroid convergence and density connectivity.

1. K-Means Lloyd's Algorithm

Given \(k\) clusters, K-Means minimizes the Within-Cluster Sum of Squares (WCSS):

\[ \text{WCSS} = \sum_{i=1}^k \sum_{\mathbf{x} \in S_i} \|\mathbf{x} - \mathbf{\mu}_i\|^2 \]

Iterates between **Assignment Step** (assign points to nearest centroid \(\mu_i\)) and **Update Step** (recompute \(\mu_i\) as the mean of assigned points).

2. DBSCAN (Density-Based Spatial Clustering of Applications with Noise)

Overcomes K-Means spherical assumptions by discovering arbitrary non-linear cluster geometries based on point density (\(\epsilon\)-neighborhood and \(\text{MinPts}\)).

🎯 Module Mastery Certification Quiz

+100 XP

What is a major limitation of standard K-Means clustering compared to DBSCAN?

K-Means assumes clusters are spherical and of similar size, and struggles with irregular non-convex shapes and arbitrary noise outliers.

K-Means cannot run on numeric numbers.

K-Means requires a GPU.

K-Means always finds only 1 cluster.