Agglomerative Clustering and DBSCAN

After learning k-means, it is natural to assume it works like the other decomposition methods you have seen. PCA and NMF both describe each data point as a combination of learned building blocks, so it seems reasonable that k-means does the same thing with its cluster centers. This section tests that assumption. The same test set of face images is reconstructed by all three methods, and the differences in what each method keeps are what the comparison is designed to reveal.

Keep this prediction in mind. The sections that follow show that the answer is not a matter of opinion: it follows directly from the steps each method performs when it reconstructs a face.

The source fits all three models on the same training split, using 100 components for PCA and NMF and 100 cluster centers for k-means. The test faces are then reconstructed by each model. The training data shapes the three models, and the test data is only passed through them. Each model's reconstruction is therefore a statement about what that model learned from the training faces.

The comparison has two parts: the components each method extracts, and the reconstructions each method produces. For components, k-means yields cluster centers, which are typical faces of the groups it found. PCA and NMF yield components that are reused across many faces. For reconstructions, PCA and NMF build a face from several components at once, while k-means returns the single closest center.

The diagram shows the two logics side by side. The k-means column has a single chosen center at the end of the path, while the PCA and NMF column has several components feeding into one sum. The plotting code in the source places the same test faces next to each method's output, which is how these differences become visible on screen.

The correction to the misconception is best seen as a path of steps. A test face is first assigned to its nearest training-set cluster, which yields an integer index. That index selects one stored center. The selected center becomes the reconstruction. No blending happens at any stage.

In this notation, x is a test face, c_k is the k-th cluster center learned on the training set, and k* is the index of the closest center to x. The formula restates the description in the source: the reconstruction is the closest cluster center found on the training set. Because the output can only be one of the centers learned from the training data, k-means reconstructions look like typical faces from the training set, not like the particular test face.

The source points out a second, less obvious use of k-means. Clustering can also encode data, a technique called vector quantization. Here the goal is no longer a faithful reconstruction. Instead, each point is replaced by its cluster assignment, and that assignment becomes a feature. The source notes that many more clusters than input dimensions can be used this way, which PCA and NMF cannot do in the same sense.

The source's example is the two_moons dataset, which lives in only two dimensions. Reducing it to one dimension with PCA or NMF would destroy its structure. Using k-means with more cluster centers gives a more expressive representation, and the source fits 10 cluster centers to show it.

Read the diagram as a feature vector with one position per cluster. The point's assignment selects position 3, which receives the value 1. Every other position holds 0. This is the sea of 0s with a single 1 that the source describes. The representation says only which cluster the point belongs to.

The source adds that an even richer representation is possible by using the distances to each cluster center as features, which is obtained through the transform method of the fitted k-means model. Those distances keep more information than a single 1, because they record how far the point is from every center.

A final point from the source explains a drawback that the comparison makes visible. The result of k-means depends on a random initialization, so the outcome depends on a random seed. A different seed can give different cluster centers, and therefore different reconstructions. The random_state=0 argument in the code fixes the seed, so the result is repeatable in that example.

scikit-learn reduces this dependence by running several initializations and keeping the best result. Rather than trusting one random starting point, the model tries multiple starts and selects the run that gives the better outcome. This reduces the risk of settling on a poor set of centers, but it does not remove the randomness from the method.

The source also lists the strengths that make k-means popular: it is relatively easy to understand and implement, it runs relatively quickly, and it scales easily to large datasets. scikit-learn includes MiniBatchKMeans for very large datasets. The same source lists the drawbacks: the reliance on random initialization, relatively restrictive assumptions about the shape of clusters, and the requirement to specify the number of clusters, which may not be known in a real-world application.

Suppose you have a pile of unlabeled data points and no idea how many natural groups they form. Clustering methods answer this kind of question by grouping points that resemble each other. Agglomerative clustering is one family of these methods, and its strategy is unusual: instead of splitting one big group into smaller ones, it begins at the opposite extreme and builds larger groups up from the bottom.

Agglomerative clustering is a collection of algorithms that share one underlying principle. Every algorithm in the family starts in the same place: each data point is treated as a cluster containing only itself. From that starting arrangement, the algorithm repeatedly looks for the two clusters that are most similar to each other and merges them into one. After each merge there is one fewer cluster, and the process continues.

It helps to notice what the procedure never does. It does not start with one big cluster and cut it apart, and it does not need a guess about the final groups before it begins. The final grouping emerges from the sequence of merges themselves. This is why the word agglomerative, meaning gathering together, fits the method well.

Each step of agglomerative clustering takes the two most similar current clusters and merges them. Because each merge reduces the cluster count by one, the sequence of merges is a record of how the groups were built. The example below uses five points labeled A through E. The merge order is illustrative, chosen only to show the mechanism.

Read the tree from the bottom up, which mirrors the build-up process. The leaves are the original singleton points. Each internal node records one merge, and the stopping point is the horizontal line that cuts the tree where two clusters remain. The example merges happen to be fixed here, but in the algorithm they are chosen by a similarity measure, which the linkage criterion defines.

Merging cannot go on forever, so the algorithm needs a rule for when to halt. That rule is called the stopping criterion. The source describes the general idea as merging the most similar pair of clusters until some stopping criterion is satisfied, which means the criterion is what ends the loop.

In scikit-learn, the implementation discussed here uses the number of clusters as its stopping criterion. You tell the algorithm how many clusters you want to end up with, and it keeps merging the most similar clusters until only that number is left. The number is therefore an input you supply, not something the algorithm discovers on its own.

Because each merge reduces the cluster count by one, reaching a target count requires a predictable number of merges. Starting from n singleton points and aiming for k clusters takes exactly n minus k merges. The stopping criterion therefore fixes both the endpoint and how much merging happens along the way.

Choosing the two most similar clusters requires a way to score similarity, and this is where linkage criteria come in. A linkage criterion defines how most similar is measured between two existing clusters. The source stresses that there are several linkage criteria, and that the exact meaning of most similar depends on which one you select.

An important detail is that a linkage criterion always compares two clusters that already exist. It is not a rule for comparing a single point to a single point in isolation at the moment of merging. Early in the process, clusters may still be single points, but the linkage rule still operates on pairs of current clusters. Each time a merge happens, the set of clusters changes, and the comparisons are made again on the new set.

scikit-learn lets you select the linkage criterion as a setting when you configure the model. The options differ in how they define similarity between clusters, so the same data can produce different merge sequences depending on the one you pick. The source does not spell out the formal definition of each option in this material, so when you choose one, check its documentation for the exact rule.