In supervised learning, every training example has a label. In clustering, you have data but no labels. The goal: discover natural groups (clusters) in the data.

Think of sorting a pile of laundry without anyone telling you the categories. You’d naturally group by color, fabric type, or size. Clustering algorithms do the same with data — they find groups of similar items.

Use cases: Customer segmentation (group shoppers by behavior), anomaly detection (find the one transaction that doesn’t fit any group), image compression (group similar pixels), gene expression analysis (group genes with similar activity patterns), and document organization (group similar articles).

The fundamental challenge: how do you evaluate clustering without labels? There’s no “accuracy” to compute. Instead, we use internal metrics like silhouette score and within-cluster sum of squares (WCSS).

Step 1: Initialize K cluster centers (centroids) randomly.
Step 2: Assign each data point to the nearest centroid (using Euclidean distance).
Step 3: Update each centroid to the mean of all points assigned to it.
Step 4: Repeat steps 2–3 until centroids stop moving (convergence).

Convergence is guaranteed because each step reduces the total within-cluster sum of squares (WCSS). Typically converges in 10–50 iterations.

K-Means++ improves initialization by spreading initial centroids apart. First centroid is random; each subsequent one is chosen with probability proportional to distance from existing centroids. This avoids the “all centroids start in one cluster” problem and is scikit-learn’s default (init='k-means++').

K-Means minimizes the Within-Cluster Sum of Squares (WCSS), also called inertia:

WCSS = ∑ₖ ∑ᵢ∈Cₖ ||xᵢ − μₖ||²

where μₖ is the centroid of cluster k. For each point, compute its squared distance to its cluster center, then sum over all points in all clusters.

Lower WCSS = tighter clusters. But WCSS always decreases as K increases (K = n gives WCSS = 0, with each point as its own cluster). The challenge is finding the K where adding more clusters stops helping significantly.

K-Means is an NP-hard problem in general, but the iterative algorithm finds a good local minimum. Running multiple times with different initializations (n_init=10) helps avoid bad local minima.

Elbow Method: Plot WCSS vs K. As K increases, WCSS drops. Look for the “elbow” — the point where adding more clusters stops reducing WCSS significantly. The elbow is where the curve bends from steep to flat.

Silhouette Score: For each point, compute:
s = (b − a) / max(a, b)
where a = average distance to points in the same cluster, b = average distance to points in the nearest other cluster.

s ranges from −1 to +1. s ≈ 1: well-clustered. s ≈ 0: on the boundary. s < 0: probably in the wrong cluster. The average silhouette score across all points measures overall clustering quality.

Pick the K that maximizes the average silhouette score. This is more reliable than the elbow method, which can be ambiguous.

1. Non-spherical clusters: K-Means assumes clusters are roughly spherical (equal variance in all directions). It fails on elongated, crescent-shaped, or ring-shaped clusters because it uses Euclidean distance to the centroid.

2. Unequal cluster sizes: K-Means tends to create equal-sized clusters. If one cluster has 10,000 points and another has 100, K-Means may split the large cluster and merge the small one with a neighbor.

3. Sensitivity to outliers: A single outlier far from all clusters pulls its centroid toward it, distorting the entire cluster.

4. Must specify K in advance: You need to know (or guess) the number of clusters before running. DBSCAN doesn’t have this limitation.

5. Feature scaling: K-Means uses Euclidean distance, so features on different scales dominate. Always standardize features first.

DBSCAN (Density-Based Spatial Clustering of Applications with Noise) groups points that are densely packed together and marks points in low-density regions as noise.

Two parameters: ε (eps) = neighborhood radius, min_samples = minimum points to form a dense region.

Core point: Has ≥ min_samples neighbors within ε.
Border point: Within ε of a core point but has < min_samples neighbors itself.
Noise point: Neither core nor border — an outlier.

Clusters form by connecting core points that are within ε of each other. Border points are assigned to the nearest core point’s cluster. Noise points get label −1.

Advantages: No need to specify K. Finds clusters of any shape. Automatically identifies outliers. Works well with spatial data.

Agglomerative (bottom-up) clustering starts with each point as its own cluster, then repeatedly merges the two closest clusters until only one remains.

The merge history forms a dendrogram — a tree diagram. Cut the dendrogram at any height to get a specific number of clusters. Higher cut = fewer clusters. Lower cut = more clusters.

Linkage criteria define “distance between clusters”:
• Ward: Minimizes within-cluster variance. Produces compact, equal-sized clusters. Most common.
• Complete: Maximum distance between any two points in different clusters.
• Average: Mean distance between all pairs of points.
• Single: Minimum distance. Can find elongated clusters but is sensitive to noise (chaining effect).

Complexity: O(n³) for naive, O(n² log n) optimized. Practical for up to ~10,000 points.