Hierarchical and k-means clustering, high-dimensional data, CLIQUE, PROCLUS, non-Euclidean spaces and streams, with Lab 8.
Clustering groups objects so that objects in the same cluster are more similar to each other than to objects in other clusters. It is unsupervised: no class labels are given, and the algorithm discovers the groups itself. Clustering is used for customer segmentation, document organisation, image segmentation, anomaly detection and as a preprocessing step for other methods. This chapter completes syllabus Unit IV: it covers the main families of algorithms, the special problems of high-dimensional and non-Euclidean data, and clustering for streams and parallel systems, each with a worked example.
10.1 Clustering techniques – overview and distance measures
Clustering algorithms fall into several families. Partitioning methods divide n objects into k groups and improve the grouping iteratively; K-means, K-medoids (PAM) and CLARA are examples. Hierarchical methods build a tree of nested clusters, either by merging (agglomerative) or by splitting (divisive); BIRCH and CURE are scalable variants. Density-based methods such as DBSCAN and OPTICS define clusters as dense regions separated by sparse ones, so they can find clusters of any shape and ignore noise. Grid-based methods such as STING and CLIQUE divide the space into cells and cluster the cells. Model-based methods fit a statistical model, such as a Gaussian mixture estimated by the EM algorithm, to each cluster. Subspace and projected methods such as CLIQUE and PROCLUS look for clusters that exist only in some of the dimensions.
| Family | Idea | Examples |
|---|---|---|
| Partitioning | Divide n objects into k groups, improve iteratively | K-means, K-medoids (PAM), CLARA |
| Hierarchical | Build a tree of nested clusters | AGNES, DIANA, BIRCH, CURE |
| Density-based | Dense regions separated by sparse ones | DBSCAN, OPTICS |
| Grid-based | Quantise space into cells | STING, CLIQUE |
| Model-based | Fit a statistical model per cluster | Gaussian mixture (EM), SOM |
| Subspace / projected | Clusters in subsets of dimensions | CLIQUE, PROCLUS |
Every clustering method depends on a distance (or similarity) measure, and the right one depends on the data. Euclidean distance √Σ(xᵢ − yᵢ)² is the straight-line distance for numeric data. Manhattan distance Σ|xᵢ − yᵢ| adds the absolute differences, like walking city blocks. Cosine similarity measures the angle between vectors and suits text, where document length should not matter. Jaccard distance, 1 − |A ∩ B| / |A ∪ B|, compares sets. Edit distance counts the insertions and deletions needed to turn one string into another.
Worked example – computing distances.
- Points P = (2, 3) and Q = (5, 7): Euclidean = √((5 − 2)² + (7 − 3)²) = √(9 + 16) = 5; Manhattan = |3| + |4| = 7.
- Sets A = {a, b, c} and B = {b, c, d}: |A ∩ B| = 2 and |A ∪ B| = 4, so Jaccard similarity = 0.5 and Jaccard distance = 0.5.
- Documents as word counts u = (1, 1, 0) and v = (1, 0, 1): cosine = (1 × 1 + 1 × 0 + 0 × 1) / (√2 × √2) = 1 / 2 = 0.5.
- Strings "cat" and "cart": one insertion (r) turns cat into cart, so the edit distance is 1.
10.2 Hierarchical clustering
Hierarchical clustering builds a nested tree of clusters, drawn as a dendrogram, in which the height of each joint shows the distance at which two clusters were merged. Cutting the dendrogram at a chosen height gives a particular set of clusters, so the number of clusters does not have to be fixed in advance. The agglomerative (bottom-up) approach starts with every point as its own cluster and repeatedly merges the two closest clusters until one remains. The divisive (top-down) approach starts with all points in one cluster and repeatedly splits clusters until every point stands alone. How the distance between two clusters is measured is called the linkage. Single linkage uses the minimum distance between any two of their points and tends to produce long chains; complete linkage uses the maximum distance and gives compact clusters; average linkage uses the average of all pairwise distances; centroid linkage uses the distance between cluster centres; and Ward's method merges the pair that least increases the total within-cluster variance. The agglomerative algorithm is: compute the distance matrix; merge the closest pair of clusters; update the matrix using the chosen linkage; and repeat. It needs at least O(n²) time and memory, so it suits small and medium datasets, and a merge once made can never be undone.
Worked example – single linkage. Five one-dimensional points: A = 1, B = 2, C = 6, D = 8, E = 15.
| A | B | C | D | E | |
|---|---|---|---|---|---|
| A | 0 | 1 | 5 | 7 | 14 |
| B | 0 | 4 | 6 | 13 | |
| C | 0 | 2 | 9 | ||
| D | 0 | 7 | |||
| E | 0 |
- The smallest distance is A–B = 1, so merge A and B at height 1.
- Single-linkage distances from AB: to C = min(5, 4) = 4, to D = min(7, 6) = 6, to E = min(14, 13) = 13. The smallest entry in the updated matrix is C–D = 2, so merge C and D at height 2.
- AB–CD = min(AC, AD, BC, BD) = min(5, 7, 4, 6) = 4; AB–E = 13; CD–E = min(9, 7) = 7. Merge AB and CD at height 4.
- ABCD–E = min(13, 7) = 7, so merge everything at height 7.
- Cutting the tree at height 5 gives two clusters, {A, B, C, D} and {E}; cutting at height 3 gives three, {A, B}, {C, D} and {E}.
- With complete linkage, AB–CD would be max(5, 7, 4, 6) = 7 and CD–E = max(9, 7) = 9, so AB and CD would merge at 7 and E would join at max(14, 13, 9, 7) = 14 — the same order here, but at greater heights.
Each joint sits at the distance at which its two clusters merged (1, 2, 4 and 7). A horizontal cut at height 5 crosses two vertical lines, giving the two clusters {A, B, C, D} and {E}.
10.3 K-means clustering
K-means is the most widely used partitioning algorithm. It divides n points into a chosen number k of clusters, each represented by its centroid (the mean of its points), so as to minimise the sum of squared errors (SSE) — the total squared distance from each point to its centroid. The algorithm is: (1) choose k and pick k initial centroids, at random or with the smarter k-means++ method; (2) assign each point to its nearest centroid; (3) recompute each centroid as the mean of the points assigned to it; and (4) repeat steps 2 and 3 until the assignments stop changing. K-means is simple and fast — each iteration is linear in n — but k must be chosen in advance, the result depends on the initial centroids (so it is usually run several times), it is sensitive to outliers, and it assumes roughly spherical clusters of similar size. The value of k is chosen with the elbow method (plot SSE against k and look for the bend), the silhouette score, or the gap statistic.
Worked example. Points (1-D): 2, 4, 10, 12, 3, 20, 30, 11, 25; k = 2; initial centroids 2 and 4.
| Iteration | Cluster 1 | Mean | Cluster 2 | Mean |
|---|---|---|---|---|
| 1 | {2, 3} | 2.5 | {4, 10, 11, 12, 20, 25, 30} | 16 |
| 2 | {2, 3, 4} | 3 | {10, 11, 12, 20, 25, 30} | 18 |
| 3 | {2, 3, 4, 10} | 4.75 | {11, 12, 20, 25, 30} | 19.6 |
| 4 | {2, 3, 4, 10, 11, 12} | 7 | {20, 25, 30} | 25 |
| 5 | no change | 7 | no change | 25 |
- Iteration 1: 3 is equally close to 2 and 4 (tie broken to cluster 1); every other point is nearer to 4. New means: (2 + 3) / 2 = 2.5 and (4 + 10 + 11 + 12 + 20 + 25 + 30) / 7 = 112 / 7 = 16.
- Iteration 2: 4 is nearer 2.5 (distance 1.5) than 16; 10 is nearer 16 (6) than 2.5 (7.5). Means 3 and 108 / 6 = 18.
- Iteration 3: 10 is nearer 3 (7) than 18 (8). Means 19 / 4 = 4.75 and 98 / 5 = 19.6.
- Iteration 4: 11 (6.25 vs 8.6) and 12 (7.25 vs 7.6) move to cluster 1. Means 42 / 6 = 7 and 75 / 3 = 25.
- Iteration 5: no point changes cluster, so the algorithm stops.
- Final SSE: cluster 1 = 25 + 16 + 9 + 9 + 16 + 25 = 100; cluster 2 = 25 + 0 + 25 = 50; total SSE = 150.
Blog lab: K-means clustering lab
Lab 8 (R) – K-means clustering and visualisation on the iris dataset
install.packages(c("factoextra", "cluster"))
library(factoextra); library(cluster)
data(iris)
X <- scale(iris[, 1:4]) # standardise the 4 measurements
# Choose k with the elbow method
set.seed(123)
wss <- sapply(1:10, function(k) kmeans(X, centers = k, nstart = 25)$tot.withinss)
plot(1:10, wss, type = "b", pch = 19, xlab = "Number of clusters k",
ylab = "Total within-cluster SS", main = "Elbow method")
fviz_nbclust(X, kmeans, method = "silhouette") # alternative: silhouette
# Fit k-means with k = 3
km <- kmeans(X, centers = 3, nstart = 25)
km$size; km$centers
# Compare clusters with the true species (not used in training)
tab <- table(Cluster = km$cluster, Species = iris$Species)
tab
cat("Cluster purity:", round(sum(apply(tab, 1, max)) / nrow(iris), 3), "\n")
cat("Avg silhouette:", round(mean(silhouette(km$cluster, dist(X))[, 3]), 3), "\n")
# Visualise
fviz_cluster(km, data = X, geom = "point", ellipse.type = "convex",
main = "K-means clusters of iris (PCA projection)")
plot(iris$Petal.Length, iris$Petal.Width, col = km$cluster,
pch = as.integer(iris$Species), xlab = "Petal length", ylab = "Petal width",
main = "Colour = cluster, shape = species")
Setosa forms its own cluster almost perfectly; versicolor and virginica overlap, so a few flowers are misassigned (purity is typically around 0.83).
10.4 Clustering high-dimensional data
High-dimensional data — text documents with thousands of words, gene-expression profiles, images — has hundreds or thousands of attributes, and ordinary clustering breaks down. The curse of dimensionality means that, as dimensions increase, the distances between all pairs of points become almost equal, so the idea of a "nearest" point loses meaning. Many attributes are irrelevant to the cluster structure and act as noise that hides it. Data becomes extremely sparse, so density estimates fail. And different clusters may be defined by different subsets of attributes: one group of customers may be similar in age and income, another in location and product choice. Four approaches are used. Dimensionality reduction (PCA, SVD) projects the data to fewer dimensions before clustering, but it applies one global projection that may not suit every cluster. Subspace clustering (CLIQUE) searches all subspaces for dense regions. Projected clustering (PROCLUS) assigns each cluster its own set of relevant dimensions. Frequent-pattern-based clustering uses itemset mining to find groups.
Worked example – why high-dimensional space is "empty". Consider points spread uniformly in a unit hypercube with side 1. The fraction of the volume lying within 0.05 of the surface is 1 − 0.9^d, because the inner cube has side 1 − 2 × 0.05 = 0.9.
| Dimensions d | Inner volume 0.9^d | Volume near the surface 1 − 0.9^d |
|---|---|---|
| 2 | 0.81 | 19% |
| 10 | 0.349 | 65.1% |
| 100 | 0.0000266 | 99.997% |
In 100 dimensions almost every point lies near the edge of the space, far from every other point, which is why full-dimensional distance-based clustering fails and subspace methods are needed.
10.5 CLIQUE
CLIQUE (CLustering In QUEst) is a grid-based, density-based subspace clustering algorithm that automatically finds clusters in subsets of the dimensions. It partitions every dimension into ξ equal-width intervals, which divides the space into grid units. A unit is dense if the fraction of points in it exceeds a density threshold τ. CLIQUE then searches bottom-up using the Apriori property: a k-dimensional unit can be dense only if all of its (k − 1)-dimensional projections are dense, so it starts with dense 1-D units, joins them into candidate 2-D units, keeps those that are dense, and so on. Adjacent dense units in the same subspace are connected to form clusters, and each cluster is finally described by a minimal expression such as "0 ≤ x < 10 AND 0 ≤ y < 10". CLIQUE finds subspace clusters automatically, is insensitive to the order of the data, scales linearly with the number of points and produces readable descriptions. Its weaknesses are that results depend on ξ and τ, the grid may cut natural clusters, and a single density threshold may not suit every subspace.
Worked example. Ten points in [0, 30) × [0, 30): (2, 5), (4, 8), (6, 4), (8, 7), (12, 25), (15, 22), (14, 27), (25, 12), (27, 14), (28, 3). Grid ξ = 3 per dimension ([0, 10), [10, 20), [20, 30)); a unit is dense if it holds ≥ 30% of the points, i.e. ≥ 3 points.
- 1-D units on x: [0, 10) has 4 points, [10, 20) has 3 and [20, 30) has 3 — all dense.
- 1-D units on y: [0, 10) has 5 points (5, 8, 4, 7, 3); [10, 20) has 2 (12, 14) — not dense; [20, 30) has 3 (25, 22, 27) — dense.
- Candidate 2-D units: only combinations of dense 1-D units, i.e. 3 x-intervals × 2 y-intervals = 6 candidates instead of 9 — the Apriori pruning.
- Counts: x[0, 10) × y[0, 10) = 4 ✓; x[10, 20) × y[20, 30) = 3 ✓; x[20, 30) × y[0, 10) = 1 (only (28, 3)); the other three = 0.
- Result: two clusters — Cluster 1: 0 ≤ x < 10 AND 0 ≤ y < 10 (4 points) and Cluster 2: 10 ≤ x < 20 AND 20 ≤ y < 30 (3 points). The points (25, 12), (27, 14) and (28, 3) lie in sparse units and are treated as noise.
10.6 PROCLUS
PROCLUS (PROjected CLUStering) is a top-down, k-medoid-based projected clustering algorithm. The user gives the number of clusters k and the average number of dimensions l per cluster, and PROCLUS finds k clusters, each with its own set of relevant dimensions. It works in three phases. In the initialisation phase it draws a random sample and greedily picks a set of well-separated points as candidate medoids. In the iterative phase it chooses k medoids; for each medoid it looks at the points in its neighbourhood and selects the dimensions along which those points are closest to the medoid (smallest average distance); it assigns every point to the nearest medoid using the Manhattan segmental distance — the Manhattan distance over the medoid's chosen dimensions divided by the number of those dimensions; and it replaces "bad" medoids, such as those with very few points, repeating while the clustering improves. In the refinement phase it recomputes each cluster's dimensions from the final clusters, reassigns the points, and marks points far from every medoid as outliers.
Worked example – choosing dimensions and measuring distance. Medoid m = (2, 1, 1, 9) in four dimensions, l = 2.
- The points near m have average distances to m of 0.8 on dimension 1, 6.1 on dimension 2, 0.5 on dimension 3 and 4.2 on dimension 4. The two smallest are dimensions 3 and 1, so this cluster's dimensions are D = {1, 3}.
- Point x = (3, 8, 1, 5). Manhattan segmental distance over D = (|3 − 2| + |1 − 1|) / 2 = (1 + 0) / 2 = 0.5.
- Over all four dimensions the average would be (1 + 7 + 0 + 4) / 4 = 3.0. Ignoring the irrelevant dimensions 2 and 4 shows that x really is close to m in this cluster's subspace.
| Basis | CLIQUE | PROCLUS |
|---|---|---|
| Approach | Bottom-up, grid- and density-based | Top-down, partition (k-medoid) based |
| Input | Grid size ξ, density threshold τ | Number of clusters k, average dimensions l |
| Overlap | A point can belong to clusters in several subspaces | Each point in one cluster or an outlier |
| Output | Dense regions in every subspace | k clusters, each with its own dimensions |
10.7 Frequent pattern-based clustering methods
Frequent pattern-based clustering uses frequent-itemset mining to find clusters, which suits high-dimensional, sparse data well because it works with shared patterns instead of full-dimensional distances. In frequent term-based text clustering, each document is treated as a set of terms; frequent term sets are mined with a minimum support; and each frequent term set defines a cluster made of the documents that contain it, which is also naturally labelled by those terms. In clustering by pattern similarity (pCluster, biclustering), used for gene-expression data, a cluster is a set of objects that show the same rise-and-fall pattern over a subset of attributes, even when their absolute values differ; for two objects x, y and two attributes a, b the pScore |(xₐ − x_b) − (yₐ − y_b)| must be no more than a threshold δ. CLIQUE itself is an example of the idea, since it applies the Apriori property to dense grid units. These methods overcome the curse of dimensionality and produce clusters that are easy to interpret.
Worked example 1 – clustering documents by frequent term sets (minimum support 2 documents).
| Document | Terms |
|---|---|
| D1 | data, mining, cluster |
| D2 | data, mining, rule |
| D3 | data, mining, cluster, graph |
| D4 | neural, network, learning |
| D5 | neural, network, deep |
- Frequent term sets: {data, mining} in D1, D2, D3 (support 3); {data, mining, cluster} in D1, D3 (support 2); {neural, network} in D4, D5 (support 2).
- Clusters: "data mining" = {D1, D2, D3}, with a sub-cluster "data mining cluster" = {D1, D3}; and "neural network" = {D4, D5}. The labels come for free from the term sets.
Worked example 2 – pScore. Gene g₁ has expression values (2, 5, 3) and gene g₂ has (12, 15, 13) under three conditions. For conditions 1 and 2: |(2 − 5) − (12 − 15)| = |−3 − (−3)| = 0. The genes rise and fall together, shifted by 10, so they form a perfect pCluster even though their Euclidean distance √(100 + 100 + 100) = 17.3 is large.
10.8 Clustering in non-Euclidean space
In a non-Euclidean space — strings, sets, documents or nodes of a graph — distances can be measured, but there is no meaningful "average" point: we cannot average two strings. So a cluster cannot be represented by a centroid. Instead it is represented by a clustroid, an actual member of the cluster chosen as its most central point. The clustroid is the point that minimises one of: the sum of distances to the other points, the maximum distance to any other point, or the sum of squared distances (the ROWSUM). The GRGPF algorithm (Ganti, Ramakrishnan, Gehrke, Powell and French) clusters very large non-Euclidean datasets that do not fit in memory. It organises clusters in a tree similar to a B-tree: leaves hold cluster summaries and interior nodes hold samples of clustroids from their subtrees. Each cluster summary stores the number of points N, the clustroid, its ROWSUM, the k points closest to the clustroid and the k points farthest from it. A new point travels down the tree to the nearest cluster and is added; the ROWSUMs are updated; and if one of the nearby points would now be a better clustroid, it takes over. Clusters that grow too large are split, and overflowing leaves split as in a B-tree. Other options are K-medoids (PAM), which also uses actual points as centres, and graph-based or spectral clustering for networks.
Worked example – finding the clustroid. A cluster has four strings with these edit distances (insertions and deletions):
| abcd | aecdb | abecb | ecdab | |
|---|---|---|---|---|
| abcd | 0 | 3 | 3 | 5 |
| aecdb | 3 | 0 | 2 | 2 |
| abecb | 3 | 2 | 0 | 4 |
| ecdab | 5 | 2 | 4 | 0 |
| Point | Sum of distances | Maximum distance | Sum of squares (ROWSUM) |
|---|---|---|---|
| abcd | 3 + 3 + 5 = 11 | 5 | 9 + 9 + 25 = 43 |
| aecdb | 3 + 2 + 2 = 7 | 3 | 9 + 4 + 4 = 17 |
| abecb | 3 + 2 + 4 = 9 | 4 | 9 + 4 + 16 = 29 |
| ecdab | 5 + 2 + 4 = 11 | 5 | 25 + 4 + 16 = 45 |
By all three criteria, aecdb is the clustroid.
10.9 Clustering for streams and parallelism
Stream clustering. When points arrive as a stream, the clustering of the most recent N points must be maintained in limited memory. The BDMO algorithm (Babcock, Datar, Motwani and O'Callaghan) extends the DGIM idea of section 8.3. Points are grouped into buckets whose sizes are powers of 2; at most one or two buckets of each size are kept, and sizes never decrease going back in time. Each bucket stores its size, the timestamp of its most recent point, and the cluster summaries of its points (centroid or clustroid, number of points, and other statistics). When there are too many buckets of one size, the two oldest are merged into a bucket of twice the size, and their clusters are combined — for example by merging pairs of nearby clusters until the right number remains. To answer a query about the last N points, the clusters of the buckets that cover the window are merged. Other stream methods include CluStream, which keeps many small micro-clusters online and clusters them into macro-clusters offline on request; STREAM, which runs k-median on successive chunks; and DenStream, which is density-based.
Parallel clustering. Very large datasets are clustered in parallel on a cluster of machines. K-means fits the MapReduce model (section 11.1) naturally. The data is split across many machines. In the map step, each machine assigns its points to the nearest current centroid and emits, for each centroid, the partial sum of its assigned points and their count. In the reduce step, the partial sums and counts for each centroid are added and divided to give the new centroid. The new centroids are broadcast to all machines and the process repeats until convergence. Tools include Spark MLlib (KMeans, BisectingKMeans), Apache Mahout and Hadoop MapReduce.
Worked example 1 – merging cluster summaries (BDMO). Two buckets are merged. One has a cluster with centroid (2, 3) and 4 points; the other has a nearby cluster with centroid (4, 5) and 6 points.
- Merged count = 4 + 6 = 10.
- Merged centroid = ((4 × 2 + 6 × 4) / 10, (4 × 3 + 6 × 5) / 10) = (32 / 10, 42 / 10) = (3.2, 4.2) — a weighted average, so no raw points are needed.
- Bucket sizes before a new point: 1, 1, 2, 4. After it: 1, 1, 1, 2, 4 → merge the two oldest size-1 buckets → 1, 2, 2, 4.
Worked example 2 – one MapReduce k-means step for centroid C₁.
- Mapper 1 assigns 4 points to C₁ with coordinate sums (10, 14); mapper 2 assigns 2 points to C₁ with sums (6, 10).
- The reducer adds them: sums (16, 24), count 6.
- New C₁ = (16 / 6, 24 / 6) = (2.67, 4.0). Only sums and counts cross the network, not the points themselves.
Independent study notes written in my own words, for learning purposes. Not affiliated with any university or course provider. R, RStudio, Hadoop, Amazon S3, Tableau, Power BI and other product names are trademarks of their respective owners.