Clustering Explained: k-Means, Hierarchical, DBSCAN and GMM

Imagine a pile of ten thousand customer records and not a single label. Nobody tells you who is a bargain hunter, who is a loyal regular, or who is about to leave. Can an algorithm discover those groups by itself? That is the promise of clustering, and today we will build it from scratch.

• No labels given
• Structure must be discovered

Last time we studied support vector machines and kernels, which draw boundaries when the labels are known. This episode drops the labels entirely. We will cover k-means, hierarchical clustering, DBSCAN and Gaussian mixture models, and we will derive the key math for each one.

• Last episode: SVMs
• Today: four clustering families

Here is the roadmap. First the k-means objective and Lloyd's algorithm, including a proof that the mean is the right center. Then initialization and how to choose k. After that, dendrograms, density-based clustering, and mixture models with Expectation-Maximization. We finish with evaluation and honest limitations.

• k-means and its math
• Hierarchical and DBSCAN
• GMM and EM

Clustering is unsupervised learning. We have only features, a matrix of points, and we want to assign each point to a group so that points in the same group are similar and points in different groups are different. Notice the catch: similar according to what? The answer is always a choice of distance and a choice of algorithm.

• Only features, no labels
• Similar inside, different between

There is no single correct clustering. The same points can be split by color, by size, or by shape, and each split is reasonable. This is why clustering is exploratory. The output is a hypothesis about structure, and you judge it by usefulness and by stability, not by an accuracy number against ground truth.

• Many valid groupings
• Judge by usefulness

k-means makes the idea precise. You choose a number k. The algorithm places k centers, called centroids, and assigns every point to its nearest centroid. Each cluster is then summarized by its centroid, which is simply the average position of its members.

• Choose k centroids
• Assign each point to nearest

The objective is called inertia, or within-cluster sum of squares. For every point, take the squared distance to the centroid of its cluster, then add everything up. In symbols, J equals the sum over clusters k, of the sum over points x in cluster k, of the squared norm of x minus mu k. Smaller J means tighter clusters.

• Squared distance to centroid
• Sum over all points
• Smaller is tighter

Why squared distance? Squaring punishes far points heavily, which pulls centroids toward compact groups. It is also smooth, so we can differentiate it, and it leads to a beautiful closed form: the best center is the mean. Let us prove that now, because the whole algorithm rests on it.

• Punishes far points
• Smooth and differentiable

Take one cluster in one dimension with points x one through x n, and ask: which center c minimizes f of c, the sum of x i minus c, squared? Differentiate with respect to c. Each term gives minus two times x i minus c. So the derivative is minus two times the sum of x i minus c.

• f(c) = sum of (x_i - c)^2
• f'(c) = -2 sum (x_i - c)

Set the derivative to zero. The sum of x i minus n times c equals zero, so c equals one over n times the sum of x i. That is exactly the mean. The second derivative is two n, which is positive, so this is a minimum and not a maximum. In higher dimensions the same argument works coordinate by coordinate.

• c equals the mean
• Second derivative 2n is positive

Check with numbers. Take the points one, two and four. Their mean is seven thirds, about two point three three. At c equals seven thirds the cost is about one point seven seven plus zero point one one plus two point seven eight, which is four point six seven. Try c equals two instead: one plus zero plus four gives five. The mean wins.

• Mean = 7/3 ≈ 2.33
• Cost 4.67 versus 5 at c = 2

This also explains a famous weakness. The mean is sensitive to outliers, because squared error lets one far point drag the center. If you minimized absolute distance instead, the best center would be the median, giving the k-medians algorithm. Different loss, different center. Keep that connection in mind, because it returns when we discuss limitations.

• Squared loss gives the mean
• Absolute loss gives the median

Finding the best assignment and centers all at once is a hard problem; for general data it is NP-hard. Lloyd's algorithm sidesteps this with alternation. Fix the centroids and optimize the assignments. Then fix the assignments and optimize the centroids. Repeat until nothing changes.

• Fix centroids, assign points
• Fix assignments, move centroids

Each step provably cannot increase the objective. Assigning every point to its nearest centroid can only reduce or keep each point's squared distance. Replacing each centroid by its cluster mean minimizes the cost for that cluster, by our derivation. The cost never goes up, there are finitely many assignments, so the algorithm must stop.

• Each step lowers or keeps J
• Finite assignments, so it stops

Now a full example in one dimension. Our six points are one, two, four, eleven, twelve and fifteen. Start with two centroids placed at one and at four. Assignment step: one is at the first centroid, two is closer to one than to four, so it joins the first. Four goes to the second centroid, and so do eleven, twelve and fifteen.

• Centroids start at 1 and 4
• Blue: 1, 2. Orange: 4, 11, 12, 15

Update step. The blue cluster contains one and two, so its mean is one point five. The orange cluster holds four, eleven, twelve and fifteen, which add to forty two, so its mean is ten point five. The centroids glide to those new positions. Notice the orange centroid sits far from four, because it is dragged right by the others.

• Blue mean: 1.5
• Orange mean: 42 / 4 = 10.5

Iteration two. Point four is now two point five away from the blue centroid but six point five from the orange one, so it switches to blue. The clusters become one, two, four and eleven, twelve, fifteen. The new means are seven thirds, about two point three three, and thirty eight thirds, about twelve point six seven.

• Point 4 moves to blue
• Means: 2.33 and 12.67

Iteration three. Point four is one point six seven from the blue centroid and eight point six seven from the orange. Nothing changes, so we have converged. The final inertia is four point six seven for the blue cluster plus eight point six seven for the orange, a total of thirteen point three three. Each iteration took the cost down.

• No assignments changed
• Inertia 4.67 + 8.67 = 13.33

In two dimensions the picture is the same, with straight perpendicular bisectors between centroids forming a Voronoi diagram. Each iteration costs roughly n times k times d operations, with n points, k centroids and d features. That is fast, which is why k-means scales to huge datasets. But fast does not mean globally optimal.

• Straight-line boundaries
• Cost about n times k times d

Lloyd's algorithm finds a local minimum, and which one depends on the starting centroids. Put two initial centroids inside the same true group and the algorithm may split that group in half while merging two others. The result is a valid fixed point, yet clearly worse than the best solution.

• Only a local minimum
• Start decides the outcome

The simplest fix is random restarts. Run the algorithm many times with different seeds and keep the run with the lowest inertia. Scikit-learn does this by default with a parameter called n init. It is cheap insurance, but we can also choose starting points more cleverly.

• Run many seeds
• Keep the lowest inertia

That cleverer choice is k-means plus plus. Pick the first centroid uniformly at random from the data. For each later centroid, compute for every point its squared distance to the nearest centroid chosen so far, and sample the next centroid with probability proportional to that squared distance. Far points are likely picks, so the centroids spread out.

• First centroid: uniform random
• Next: probability proportional to D squared

A tiny example. Points at zero, one and ten, with the first centroid at zero. Squared distances are zero, one and one hundred. Probabilities are zero, one over one hundred one, and one hundred over one hundred one, so the far point at ten is picked about ninety nine percent of the time. This is not a heuristic only: k-means plus plus has a proven bound on the expected cost relative to the optimum.

• Squared distances: 0, 1, 100
• Far point chosen about 99%

So far k was given, but in real projects you must choose it. Inertia always decreases as k grows, and with k equal to n it hits zero, so minimizing it blindly is useless. The elbow method plots inertia against k and looks for the bend where adding clusters stops paying off.

• Inertia always falls with k
• Look for the bend

The elbow can be ambiguous, so we also use the silhouette score. For a point i, let a be its average distance to the other points in its own cluster, and b its average distance to the points in the nearest other cluster. The silhouette is b minus a, divided by the larger of a and b.

• a: mean distance within cluster
• b: mean distance to nearest other

Use our example. For the point two in the cluster one, two, four: a is the mean of one and two, which is one point five. Its distances to eleven, twelve and fifteen are nine, ten and thirteen, so b is thirty two thirds, about ten point six seven. The silhouette is ten point six seven minus one point five, over ten point six seven, about zero point eight six. A strong fit.

• a = 1.5, b = 10.67
• s ≈ 0.86

Silhouette values lie between minus one and plus one. Near one means the point sits well inside its cluster. Near zero means it lies on a border. Negative means it is probably in the wrong cluster. Average over all points for each k and choose the k with the highest mean silhouette, but treat the number as evidence, never as a verdict.

• +1 well placed, 0 border
• Negative: likely misassigned

Hierarchical clustering drops the need to pick k up front. Agglomerative clustering starts with every point as its own cluster, then repeatedly merges the two closest clusters until only one remains. The full merge history is a tree called a dendrogram, and you decide later where to cut it.

• Start: every point alone
• Merge closest pair repeatedly

What does closest mean for two clusters? That is the linkage. Single linkage uses the minimum distance between any two members. Complete linkage uses the maximum. Average linkage uses the mean of all pairwise distances. Ward linkage merges the pair that increases total within-cluster variance the least, which connects it back to k-means.

• Single: minimum distance
• Complete: maximum distance
• Ward: least variance increase

Run single linkage on our six points. One and two merge at height one, and so do eleven and twelve. Four joins one and two at height two. Fifteen joins eleven and twelve at height three. The last merge happens at height seven, the gap between four and eleven. That huge jump tells us two clusters is natural.

• Merges at 1, 1, 2, 3, then 7
• Long final jump suggests two clusters

Complete linkage on the same data gives heights one, one, three, four, and fourteen at the end, so it agrees here. But the linkages can disagree. Single linkage can chain through a thin bridge of points and merge two blobs, while complete linkage prefers compact balls. The cost is that standard hierarchical clustering needs a distance matrix, roughly quadratic memory in n.

• Single linkage chains
• Complete prefers compact balls
• Memory grows as n squared

k-means and Ward assume roughly round clusters. Two interleaving crescent moons will defeat them. DBSCAN takes a different view: a cluster is a dense region separated by sparse regions. This lets it find arbitrary shapes and, bonus, label isolated points as noise instead of forcing them into a group.

• Handles arbitrary shapes
• Marks noise explicitly

DBSCAN has two parameters. Epsilon is a radius. Min points is a count. A point is a core point if at least min points points, including itself, lie within epsilon of it. A border point is within epsilon of a core point but is not core itself. Everything else is noise.

• Epsilon: neighborhood radius
• MinPts: density threshold

The algorithm then grows clusters. Pick an unvisited core point and start a new cluster. Add every point in its epsilon neighborhood. For every new core point you add, add its neighbors too, and keep spreading like a flood. When the flood stops, that cluster is complete. Move on to another unvisited core point.

• Start from a core point
• Flood through neighboring cores

Choosing the parameters is the hard part. A common trick is to plot each point's distance to its k-th nearest neighbor, sorted from small to large, and pick epsilon near the knee of the curve. Another weakness: with one global epsilon, DBSCAN struggles when clusters have very different densities. Variants such as HDBSCAN relax this.

• Sorted k-distance plot, find knee
• One epsilon fails varying density

k-means gives hard answers: a point belongs to exactly one cluster. A Gaussian mixture model gives soft answers. It assumes the data came from a blend of K Gaussian bells, each with a mean, a covariance and a mixing weight. The density of a point is the weighted sum of those bells.

• Weights, means, covariances
• Density is a weighted sum

The covariance matrix gives each cluster its own shape: a circle, an axis-aligned ellipse, or a tilted ellipse. That is a big upgrade over k-means, which implicitly assumes equal round clusters. Think of the math from our linear algebra episodes: the eigenvectors of the covariance give the ellipse's axes, and eigenvalues give their lengths.

• Circle, ellipse, tilted ellipse
• Eigenvectors give the axes

We fit the parameters by maximum likelihood, which you met earlier. The log likelihood is the sum over points of the log of a sum over components. That log of a sum blocks a direct closed-form solution, because we do not know which component produced each point. That hidden choice is the latent variable, and Expectation-Maximization is built for exactly this situation.

• Maximum likelihood objective
• Latent component is unknown

The E step guesses the hidden labels softly. For each point it computes a responsibility: the probability that component k produced it, by Bayes' theorem. Responsibility equals pi k times the density of the point under component k, divided by the sum of that quantity over all components. Responsibilities for each point add up to one.

• Bayes' theorem per point
• Soft membership sums to one

A number example. Two components with equal weights, means zero and four, standard deviation one. For a point at x equals one, the unnormalized densities are proportional to e to the minus one half, about zero point six one, and e to the minus four and a half, about zero point zero one one. The responsibility for the first component is zero point six one over zero point six two, about ninety eight percent. At x equals two, it is exactly fifty fifty.

• At x = 1: about 98% component one
• At x = 2: exactly 50/50

The M step uses those responsibilities as fractional counts. The effective size of component k is N k, the sum of its responsibilities. The new weight is N k over n. The new mean is the responsibility-weighted average of the points. The new covariance is the weighted average of outer products of deviations. If all responsibilities were zero or one, this is exactly the k-means update.

• Weights from responsibilities
• Weighted mean and covariance

Why does this work? Each E step builds a lower bound on the log likelihood that touches it at the current parameters, using Jensen's inequality. Each M step then raises that bound. So the log likelihood never decreases across iterations. Like k-means, EM converges to a local optimum, so initialization matters, and people often start it from a k-means solution.

• E step builds a lower bound
• M step lifts it, never goes down

The relationship to k-means is worth stating clearly. If every component has the same spherical covariance, equal weights, and that shared variance shrinks toward zero, the responsibilities become hard zeros and ones. EM turns into Lloyd's algorithm. So k-means is a special, hard-assignment limit of a Gaussian mixture, and that is a satisfying piece of unification.

• Equal spherical covariance
• Variance toward zero gives hard labels

There is one more GMM issue: how many components? More components always raise the likelihood, so we penalize complexity. The Bayesian information criterion subtracts a penalty that grows with the number of parameters, and you choose the K with the lowest BIC. One danger remains: a component can collapse onto a single point, with variance near zero and likelihood exploding, so libraries add a small regularization term to covariances.

• Penalize parameter count
• Guard against collapsed components

How do we evaluate clusters? Internal metrics use only the data: inertia, silhouette, or the Davies-Bouldin index. External metrics compare to known labels, if you happen to have them, using the adjusted Rand index or normalized mutual information. Adjusted Rand corrects for chance, so random labelings score near zero.

• Internal: silhouette, inertia
• External: adjusted Rand, NMI

Beware a subtle mistake: internal metrics prefer the shape their algorithm assumes. Silhouette and inertia favor compact round clusters, so they will rate k-means highly and may score a correct DBSCAN crescent solution poorly. Always pair numbers with a plot and with domain knowledge about whether the groups mean anything.

• Silhouette favors round clusters
• Always plot and sanity check

Now the practical pitfalls. Distance-based methods need feature scaling: income in dollars will drown out age in years unless you standardize. In many dimensions distances concentrate and lose meaning, so reduce dimensions first, which is next episode's topic. And check stability by clustering bootstrap samples and seeing whether the groups persist.

• Standardize features first
• High dimensions blur distances

So which method should you choose? Use k-means as a fast baseline for round, similar-sized groups and large data. Use hierarchical clustering when you want a tree or have a small dataset. Use DBSCAN for odd shapes and noise. Use a Gaussian mixture when you need probabilities and elliptical clusters. And remember that every algorithm will return clusters even when none exist.

• k-means: fast baseline
• DBSCAN: shapes and noise
• GMM: soft, elliptical clusters

One last honest point. Clustering finds structure, not truth. A good clustering earns its value by being useful: customer segments that suggest different marketing, image colors compressed into a palette, or anomalies flagged as noise. Always ask what decision the clusters will support before reaching for an algorithm.

• Algorithms always return clusters
• Judge by usefulness

Let us recap. k-means minimizes within-cluster squared distance, and the mean is optimal because the derivative of the squared cost vanishes there. Lloyd's algorithm alternates assignment and update, never increasing the cost, but only to a local minimum, so use k-means plus plus and restarts. Choose k using the elbow, silhouette and domain knowledge.

• Mean minimizes squared cost
• Lloyd's: assign, update, repeat
• Pick k with elbow and silhouette

Hierarchical clustering builds a dendrogram you can cut at any height, with linkage deciding what close means. DBSCAN grows clusters from dense core points and flags noise. Gaussian mixtures give soft assignments, fit by Expectation-Maximization: responsibilities in the E step, weighted parameter updates in the M step. And evaluation always needs both metrics and judgment.

• Dendrogram: cut anywhere
• DBSCAN: density and noise
• GMM: soft labels via EM

Next episode we tackle dimensionality reduction: principal component analysis, singular value decomposition, t-SNE and UMAP, the tools that help you see and simplify high-dimensional data.

• PCA, SVD, t-SNE, UMAP
• Subscribe for episode 23