Clustering

Source: Concepts adapted from Ace the Data Science Interview — Chapter 7 (“Machine Learning”) by Kevin Huo & Nick Singh. Rewritten in original wording for this course. Coding uses scikit-learn on Piston.

Clustering is the flagship unsupervised interview topic: no labels — only input features $X$. The algorithm looks for structure: customer segments, viz groupings, fraud / outlier islands. Goal: partition points into groups with high intra-cluster similarity and low inter-cluster similarity.

This lesson covers k-means, alternatives (hierarchical, DBSCAN), and Gaussian mixture models (GMM) — with slider explorers, quizzes, and coding after the core blocks.

Unsupervised setup

Supervised learning predicts a target $y$. Unsupervised learning finds patterns in $X$ alone. Clustering use cases:

• Segment users / products for marketing or personalization
• Compress structure for visualization (often after PCA)
• Flag outliers (points that refuse to join dense groups)

Ideal clusters: tight within, separated between — measured with a chosen distance (often Euclidean).

Quiz

Clustering basics

1 / 3

Clustering is unsupervised because…

Pick an answer to see if you are right.

k-means

k-means is the interview default: simple, interpretable, Euclidean.

1. Choose $k$ (user hyperparameter) and initialize $k$ centroids $\mu_1,\ldots,\mu_k$.
2. Assign each point to the nearest centroid (squared Euclidean).
3. Update each centroid to the mean of its assigned points.
4. Repeat until assignments / objective stop improving.

It minimizes within-cluster sum of squares (distortion / inertia):

$$L = \sum_{j=1}^{k}\sum_{x\in S_j}\|x-\mu_j\|^2$$

Notes: Euclidean geometry; $k$ is chosen by you (elbow, silhouette, domain); local minima → try several inits (n_init in sklearn).

Quiz

k-means

1 / 4

One k-means iteration does…

Pick an answer to see if you are right.

Compute

Compute: assign / SSE / mean

1 / 5

Story problem — figure out which numbers are the formula inputs, then compute.

k-means assign: centroids μ₀=1, μ₁=9. Point x=6. Which cluster label (0 or 1) by nearest centroid (squared Euclidean)?

Enter a number (at most 2 decimal places).

Practice: k-means mechanics & sklearn

Alternatives: hierarchical & density (DBSCAN)

Hierarchical clustering starts with each point in its own cluster and repeatedly merges the closest pair of clusters (agglomerative), until one cluster remains. The merge history is a dendrogram. Useful when $k$ is unclear or you want a multi-resolution view; distance / linkage choices matter.

Density clustering (classic: DBSCAN) does not take $k$ up front. It grows clusters from dense neighborhoods and marks sparse points as noise / outliers. Strengths: arbitrary shapes, anomaly detection. Weaknesses: parameter sensitivity (eps, min_samples), struggles with wildly varying densities.

Method	You set $k$?	Shapes	Outliers
k-means	Yes	Spherical-ish (Euclidean)	Forced into a cluster
Hierarchical	Cut the tree later	Depends on linkage	Soft — via cut height
DBSCAN	No (infers)	Arbitrary density blobs	Explicit noise label (−1)

Quiz

Hierarchical & DBSCAN

1 / 3

Hierarchical agglomerative clustering…

Pick an answer to see if you are right.

Practice: DBSCAN labels

Gaussian mixture models (GMM)

A GMM models data as a mixture of $k$ Gaussians, each with its own mean and covariance, plus mixture weights $\pi_j$. Fitting (usually EM) learns component parameters; each point gets soft responsibilities $\gamma_j(x) = P(\text{component }j \mid x)$.

vs k-means:

• k-means → hard assign; only means (equal spherical clusters in the classic view)
• GMM → soft assign; means and variances/covariances → more flexible shapes

Interview frequency: k-means ≫ GMM, but GMM shows up for ML-heavy / research loops (e.g. anomaly scoring when a point has low density under all components — think odd TikTok accounts vs typical activity Gaussians).

Quiz

GMM

1 / 3

A GMM assumes data come from…

Pick an answer to see if you are right.

Practice: GMM predict

Quick synthesis

Topic	Sound bite
Goal	High intra- / low inter-cluster similarity (unsupervised)
k-means	Assign ↔ update means; minimize SSE; choose $k$
Hierarchical	Dendrogram of merges; good when $k$ is fuzzy
DBSCAN	Density + noise labels; arbitrary shapes
GMM	Soft mixture of Gaussians; mean + variance

Prefer…	When…
k-means	Fast baseline, spherical clumps, known $k$
Hierarchical	Interpret multi-level structure
DBSCAN	Odd shapes / outlier detection
GMM	Soft membership, elliptical components, anomaly density

You now have Ace Ch.7’s unsupervised clustering toolkit alongside dimensionality reduction and the supervised model lessons. Next: Neural Networks — MLPs, backprop, CNN/RNN/LSTM.