Linkage-Based Clustering Algorithms

A Boundary Before the Algorithm

The supplied material supports a clear account of clustering and linkage-based algorithms, but it does not define PCA, variance maximization, principal components, or dimensionality reduction. That boundary matters: clustering and PCA should not be treated as two names for the same task. This article therefore focuses on the supported topic: grouping data points according to similarity and distance, then repeatedly merging groups according to a chosen linkage rule.

From Data Points to Groups

Clustering is an unsupervised grouping task. A clustering model receives data points together with a way to judge distance between points. Its output is a grouping of those points into clusters. Because the result depends on similarity and distance choices, changing those choices can produce different clusterings.

The Starting State

Linkage-based clustering begins in a maximally fragmented state: every data point is its own single-point cluster. The algorithm does not begin with several large groups. Instead, it constructs larger clusters by repeatedly selecting two existing clusters and merging them.

The Repeated Merge Cycle

Each round follows the same basic cycle. First, inspect the current collection of clusters. Next, determine the distance between candidate clusters. Then select the closest pair and merge it. Finally, replace the two old clusters with the new combined cluster before beginning the next round. The next decision must use this updated collection, because a merge changes which clusters are available for comparison.

Why the Count Drops

Suppose a round begins with two distinct clusters, X and Y. A merge removes X and Y from the current collection and inserts one combined cluster. Therefore, that round replaces two cluster entries with one, so the number of clusters decreases by one. This is why repeated merging produces progressively less fragmented clusterings.

Single Linkage Distance

This definition extends a point-to-point distance into a cluster-to-cluster distance. To compare cluster A with cluster B, consider all distances from members of A to members of B. Single Linkage keeps the smallest one. The pair of points producing that smallest distance is enough to determine the distance between the two clusters.

The Two Defining Decisions

A linkage-based clustering algorithm is not fully specified by saying only that it merges clusters. Two decisions are required. First, define how to turn point-to-point distances into a distance between clusters. Single Linkage makes this the minimum member-to-member distance. Second, define when the repeated merging should stop. Different choices for either decision can lead to different clusterings.

Mistakes in Tracing the Process

• Treating clustering and PCA as the same task.

  The supplied material defines clustering but does not define PCA, variance maximization, principal components, or dimensionality reduction.

  Fix: Keep the topics separate and use this material to explain clustering only.

• Starting with preselected large clusters.

  Linkage-based clustering begins with every data point as its own cluster.

  Fix: Write the initial state as one single-point cluster for each data point.

• Keeping the old cluster list after a merge.

  The next decision is based on the new cluster collection.

  Fix: Remove the two merged clusters and insert their combined cluster before continuing.

• Using just one arbitrarily chosen pair of members for Single Linkage.

  Single Linkage uses the minimum distance across all member-to-member comparisons between the two clusters.

  Fix: Consider all cross-cluster member distances and select the smallest.

• Forgetting the stopping decision.

  The supplied material identifies both the cluster-distance rule and the stopping choice as necessary decisions.

  Fix: State both decisions when specifying the algorithm.

Practice the State Changes

The Algorithm in One Pass

1. Clustering is an unsupervised task that groups data points using similarity and distance choices.
2. The supplied material does not define PCA or dimensionality reduction, so those ideas should not be merged with the clustering account presented here.
3. Linkage-based clustering starts with every data point in its own cluster.
4. Each round selects the closest pair of current clusters, merges them, and updates the cluster collection.
5. A merge replaces two clusters with one, so the cluster count decreases by one.
6. Single Linkage defines cluster distance as the minimum distance between any member of one cluster and any member of the other.
7. A complete algorithm specification needs both a cluster-distance rule and a stopping rule.