k-Medoids & Hierarchical Clustering
The k-medoids method and the PAM algorithm with its swap cost, the lesson's worked example (cost 23 vs 16), agglomerative (AGNES) and divisive (DIANA) hierarchical clustering, and the four cluster-distance measures behind single, complete and average linkage.
1Why k-medoids?
k-means represents a cluster by its mean, so a few outliers can pull the mean a long way. k-medoids represents each cluster by an actual object, the most centrally located one, called the medoid. That makes it less sensitive to outliers and noise.
k-means
Representative = the mean of the cluster (may not be a real point).
Sensitive to outliers.
k-medoids
Representative = a real object (the medoid).
More robust to outliers, but more expensive to compute.
2k-medoids and PAM
Choose the initial representative objects (seeds) arbitrarily. Keep replacing a representative with a non-representative object as long as the quality of the clustering improves. Quality is measured by a cost function: the average dissimilarity between each object and the representative of its cluster.
PAM (Partitioning Around Medoids) was one of the first k-medoids algorithms. It looks for k partitions of n objects:
- After a random choice of k representatives, it repeatedly tries to make a better choice.
- It analyses all possible pairs (one representative, one non-representative) and computes the clustering quality for each swap.
- A representative oⱼ is replaced by the object giving the largest reduction in error.
- The final representatives are the medoids of the clusters.
Each iteration is O(k(n − k)²). For large n and k this becomes very costly.
The PAM algorithm
Input: k (number of clusters), D (data set of n objects). Output: k clusters.
- Arbitrarily choose k objects in D as the initial representatives (seeds)
- Repeat: assign each remaining object to the cluster with the nearest representative
- Randomly select a non-representative object, o_random
- Compute the total cost S of swapping a representative oⱼ with o_random
- If S < 0, swap oⱼ with o_random to form the new set of k representatives
- Until no change
The absolute-error criterion
- E = sum of the absolute error for all objects
- p = a point in cluster Cⱼ
- oⱼ = the representative object of Cⱼ
The algorithm iterates until each representative is the medoid: the most centrally located object of its cluster.
3Worked example (from the lesson)
Same eight points as Week 13, Manhattan distance, three clusters:
A1(2, 10) · A2(2, 5) · A3(8, 4) · A4(5, 8) · A5(7, 5) · A6(6, 4) · A7(1, 2) · A8(4, 9)
Task: find the cost for initial medoids A1, A4, A7. Then swap A4 for A5 and decide whether the change is suitable.
Cost S₁ (medoids A1, A4, A7): each point's distance to its nearest medoid
| Point | to A1 (2, 10) | to A4 (5, 8) | to A7 (1, 2) | Cost |
|---|---|---|---|---|
| A1 | 0 | 5 | 9 | 0 |
| A2 | 5 | 6 | 4 | 4 |
| A3 | 12 | 7 | 9 | 7 |
| A4 | 5 | 0 | 10 | 0 |
| A5 | 10 | 5 | 9 | 5 |
| A6 | 10 | 5 | 7 | 5 |
| A7 | 9 | 10 | 0 | 0 |
| A8 | 3 | 2 | 10 | 2 |
| S₁ | 23 |
Cost S₂ (medoids A1, A5, A7):
| Point | to A1 (2, 10) | to A5 (7, 5) | to A7 (1, 2) | Cost |
|---|---|---|---|---|
| A1 | 0 | 10 | 9 | 0 |
| A2 | 5 | 5 | 4 | 4 |
| A3 | 12 | 2 | 9 | 2 |
| A4 | 5 | 5 | 10 | 5 |
| A5 | 10 | 0 | 9 | 0 |
| A6 | 10 | 2 | 7 | 2 |
| A7 | 9 | 9 | 0 | 0 |
| A8 | 3 | 7 | 10 | 3 |
| S₂ | 16 |
- If S₁ > S₂ (the swap lowers the cost), the change is suitable.
- If S₁ < S₂, the new cost is higher, so the change is not suitable.
Here S₂ = 16 < S₁ = 23, so swapping A4 for A5 is suitable. The total cost falls by 7 (swap cost S = 16 − 23 = −7 < 0).
The lesson computes S₁ = 23 but leaves S₂ for you. The table above completes it. A4 is equally far from A1 and A5 (5 each), so its cost is 5 either way.
Choose three medoids from A1–A8 (Manhattan distance). The page compares the cost with A1, A4, A7.
4Hierarchical clustering
A hierarchical method groups objects into a tree of clusters (a dendrogram).
Agglomerative (bottom-up)
Start with each object in its own cluster, then merge clusters into larger and larger ones until all objects are in one cluster or a termination condition holds.
Most hierarchical methods are agglomerative; they differ in how they define intercluster similarity.
Divisive (top-down)
Start with all objects in one cluster and split it into smaller and smaller pieces until each object is on its own, or a condition is met (e.g. a desired number of clusters, or each cluster's diameter is within a threshold).
A pure hierarchical method can't adjust once a merge or split is done. If a decision turns out to be poor, it can't backtrack and correct it.
AGNES and DIANA
| AGNES (AGglomerative NESting) | DIANA (DIvisive ANAlysis) | |
|---|---|---|
| Direction | Bottom-up: merge | Top-down: split |
| Start | Each object in its own cluster | All objects in one cluster |
| Rule in the lesson | Merge C₁ and C₂ if they contain the closest pair of objects (minimum Euclidean distance): single linkage | Split by the maximum Euclidean distance between closest neighbouring objects: complete linkage |
| End | One cluster containing everything | Each cluster holds a single object |
AGNES (steps 0 → 4): {a}, {b}, {c}, {d}, {e} → {a, b} → {d, e} → {c, d, e} → {a, b, c, d, e}
DIANA runs the same steps in reverse, from {a, b, c, d, e} back to five single objects.
Four measures of distance between clusters
Here |p − p′| is the distance between two objects p and p′, mᵢ is the mean of cluster Cᵢ and nᵢ is the number of objects in Cᵢ.
| Measure | Formula | Linkage name |
|---|---|---|
| Minimum distance | dmin(Cᵢ, Cⱼ) = minp∈Cᵢ, p′∈Cⱼ |p − p′| | Nearest-neighbour; single linkage if stopped when the nearest clusters exceed a threshold |
| Maximum distance | dmax(Cᵢ, Cⱼ) = maxp∈Cᵢ, p′∈Cⱼ |p − p′| | Farthest-neighbour; complete linkage if stopped at a threshold |
| Mean distance | dmean(Cᵢ, Cⱼ) = |mᵢ − mⱼ| | Distance between the cluster means |
| Average distance | davg(Cᵢ, Cⱼ) = (1 / nᵢnⱼ) Σp∈Cᵢ Σp′∈Cⱼ |p − p′| | Average linkage |
Minimum and maximum are two extremes, and both are overly sensitive to outliers and noisy data. Mean or average distance is a compromise that overcomes the outlier problem.
Five points on a line: a = 1, b = 2, c = 6, d = 9, e = 10. Merge the two closest clusters at each step.
- k-medoids: build the distance table, take each point's minimum distance to a medoid, add them up for the cost, compare S₁ vs S₂, and state whether the swap is suitable.
- Hierarchical: define agglomerative vs divisive, name AGNES/DIANA, and give the four distance measures with their linkage names.
5Quick revision sheet
| Concept | Remember it as |
|---|---|
| Medoid | The most centrally located real object in a cluster |
| k-medoids vs k-means | Real object vs mean; more robust to outliers |
| PAM | Partitioning Around Medoids; try swaps, keep those that lower the cost |
| PAM cost | O(k(n − k)²) per iteration: expensive for large n, k |
| Swap rule | Swap if S < 0 (new cost < old cost) |
| Error E | Σ distance of each object to its cluster's representative |
| Example | A1, A4, A7 → 23; A1, A5, A7 → 16 → swap suitable |
| Agglomerative | Bottom-up merge; AGNES; most methods |
| Divisive | Top-down split; DIANA |
| Weakness | Can't undo a merge or split |
| d_min | Nearest-neighbour / single linkage |
| d_max | Farthest-neighbour / complete linkage |
| d_mean, d_avg | Compromise; less sensitive to outliers |
?Self-check quiz
14 questions on this week. Answer them all, then press Check my answers. Your best and latest scores are saved and shown on the subject page.