Grouping unlabelled data: distance measures, hierarchical and partitional methods, and density, grid and model-based methods.
12.1 Introduction
Clustering groups records so that the records in the same cluster are similar to each other and different from the records in other clusters. It is an unsupervised method, which means that no class labels are given in advance.
ExampleShopMart clusters its 1 lakh customers according to how often they visit each month and how much they spend on an average bill. Three groups emerge: frequent low spenders who shop for daily groceries, occasional high spenders who shop at festivals, and rare low spenders.
ExplanationNobody told the algorithm that these three groups existed; it found them from the data alone. The marketing team can then design a separate offer for each group.
12.2 Similarity and distance measures
Clustering depends on measuring how similar or how far apart two records are.
ExampleTwo points are P1 = (1, 2) and P2 = (4, 6), so they differ by 4 − 1 = 3 on the first axis and by 6 − 2 = 4 on the second. The table below shows three distance measures between them; for Minkowski, 3³ + 4³ = 27 + 64 = 91, and the cube root of 91 is 4.50.
| Measure | Formula idea | Result |
|---|---|---|
| Euclidean | √(3² + 4²) | 5 |
| Manhattan | |3| + |4| | 7 |
| Minkowski with p = 3 | (3³ + 4³)^(1/3) = 91^(1/3) | 4.50 |
Example (sets)Basket 1 contains {milk, bread, eggs} and basket 2 contains {milk, eggs, butter}. The shared items are {milk, eggs}, which is 2 items, and the items in either basket are {milk, bread, eggs, butter}, which is 4 items. The Jaccard coefficient is therefore 2 ÷ 4 = 0.5, and the Jaccard distance is 1 − 0.5 = 0.5.
ExplanationThe Euclidean distance is the straight-line distance between two points, while the Manhattan distance is the "city block" distance measured along the axes. For binary data or text, the Jaccard coefficient and cosine similarity are used instead, because only the items that are shared matter. In every case, the attributes must be normalised first, or the attribute with the largest range will dominate the distance.
12.3 Hierarchical vs partitional algorithms
Clustering algorithms fall into two main families, which the table below compares.
| Feature | Hierarchical | Partitional |
|---|---|---|
| Output | A tree of nested clusters, called a dendrogram | One flat set of k clusters |
| Need k in advance | No | Yes |
| Examples | Agglomerative, divisive, CURE and Chameleon | K-means and K-medoids (PAM) |
| Strength | Shows the structure at every level | Fast on large data sets |
| Weakness | Merges cannot be undone, and the method is costly | Sensitive to the starting centres and to outliers |
Agglomerative clustering works from the bottom up. It begins with each point in a cluster of its own and repeatedly merges the two closest clusters.
ExampleFive points lie on a line at A = 1, B = 2, C = 6, D = 8 and E = 15, and they are clustered using single link. The distance between two points is the difference between their positions, as the distance matrix below shows.
| A (1) | B (2) | C (6) | D (8) | E (15) | |
|---|---|---|---|---|---|
| A (1) | 0 | 1 | 5 | 7 | 14 |
| B (2) | 1 | 0 | 4 | 6 | 13 |
| C (6) | 5 | 4 | 0 | 2 | 9 |
| D (8) | 7 | 6 | 2 | 0 | 7 |
| E (15) | 14 | 13 | 9 | 7 | 0 |
The smallest distance in the matrix is 1, between A and B, so they merge first. After that merge, the distance from {A, B} to C is the smaller of 5 and 4, which is 4; to D it is the smaller of 7 and 6, which is 6; and to E it is the smaller of 14 and 13, which is 13. The smallest remaining distance is now 2, between C and D, so they merge next. The distance from {A, B} to {C, D} is the smallest of 4, 6, 5 and 7, which is 4, and the distance from {C, D} to E is the smaller of 9 and 7, which is 7. Since 4 is smaller than 7 and 13, {A, B} merges with {C, D} at 4, and finally E joins the rest at min(13, 7) = 7.
The dendrogram in the figure should be read from the bottom up. Each horizontal bar is a merge, and it is drawn at the height of the distance at which the merge happened.
ExplanationSingle link merges the two clusters whose closest members are nearest to each other. A and B merge first, at a distance of 1, and C and D merge next, at a distance of 2. The cluster {A, B} then merges with {C, D} at a distance of 4, which is the distance from B to C. Finally, E joins at a distance of 7, which is the distance from D to E. Cutting the tree anywhere between 4 and 7 gives two clusters, {A, B, C, D} and {E}. Complete link would instead measure the distance between the farthest members of each pair of clusters.
K-means is the best-known partitional algorithm. It needs the number of clusters, k, to be chosen in advance.
ExampleThe data {2, 3, 4, 10, 11, 12, 20, 25, 30} is clustered with k = 2, using 2 and 4 as the starting means. The table below traces each round.
| Round | Cluster 1 | Cluster 2 | New means |
|---|---|---|---|
| 1 | {2, 3} | {4, 10, 11, 12, 20, 25, 30} | 2.5 and 16 |
| 2 | {2, 3, 4} | {10, 11, 12, 20, 25, 30} | 3 and 18 |
| 3 | {2, 3, 4, 10} | {11, 12, 20, 25, 30} | 4.75 and 19.6 |
| 4 | {2, 3, 4, 10, 11, 12} | {20, 25, 30} | 7 and 25 |
| 5 | No change | No change | The algorithm stops |
The new means are simple averages. In round 1, for example, cluster 1 is {2, 3}, so its mean is (2 + 3) ÷ 2 = 2.5, and cluster 2 holds 4 + 10 + 11 + 12 + 20 + 25 + 30 = 112 spread over 7 points, so its mean is 112 ÷ 7 = 16. In round 2, the point 4 is 4 − 2.5 = 1.5 from the first mean but 16 − 4 = 12 from the second, so it moves to cluster 1. In round 3, the point 10 is 10 − 3 = 7 from the first mean and 18 − 10 = 8 from the second, so it moves to cluster 1, while 11 is 8 from the first and 7 from the second, so it stays. In round 4, the point 11 is 11 − 4.75 = 6.25 from the first mean and 19.6 − 11 = 8.6 from the second, and 12 is 7.25 from the first and 7.6 from the second, so both move to cluster 1. In round 1, the point 3 is exactly 1 away from both 2 and 4; ties like this are broken by choosing the first cluster.
ExplanationIn each round, every point is assigned to its nearest mean, and the means are then recalculated. The algorithm stops when no point changes cluster. In the final clusters, the sum of squared distances from each point to its mean is (25 + 16 + 9 + 9 + 16 + 25) + (25 + 0 + 25) = 100 + 50 = 150, and K-means always tries to make this sum as small as possible. Different starting means can lead to a different final answer, which is why K-means is often run several times.
12.4 Hierarchical clustering: CURE and Chameleon
CURE (Clustering Using REpresentatives). CURE represents each cluster by several scattered points, which are then shrunk towards the centre of the cluster by a factor called α.
ExampleA long, banana-shaped cluster of delivery addresses runs along a highway. CURE represents it by 10 points spread along its length, each pulled 30 per cent of the way towards the centre, so α = 0.3. One representative point is at (10, 4), and the centre of the cluster is at (6, 2). The shrunk point is p + α × (centre − p) = (10 + 0.3 × (6 − 10), 4 + 0.3 × (2 − 4)) = (10 − 1.2, 4 − 0.6) = (8.8, 3.4).
ExplanationSeveral representative points capture the curved shape of the cluster, which a single centre could not. Shrinking the points towards the centre reduces the pull of outliers at the edges. CURE also uses random sampling and partitioning so that it can run on large data sets.
Chameleon. Chameleon first builds a graph that connects each point to its k nearest neighbours. It then splits this graph into many small pieces, and finally it merges pieces whose relative interconnectivity and relative closeness are both high.
ExampleA map contains one dense cluster of points in a city and one sparse cluster in the surrounding countryside. Chameleon keeps these two clusters separate, even though their edges are close to each other.
ExplanationChameleon's merging decisions adapt to the density of each cluster, so it correctly finds clusters of different shapes and densities.
12.5 Density-based methods: DBSCAN and OPTICS
In the figure, the filled points are core points. The hollow point lies inside a core point's Eps circle but is not dense enough to be a core point itself, so it is a border point. The red point is noise.
DBSCAN. DBSCAN uses two parameters: Eps, which is a radius, and MinPts, which is the minimum number of points needed to form a dense region.
ExampleSix points are clustered with Eps = 1 and MinPts = 3, where a point's neighbourhood includes the point itself. The table below counts each point's neighbours within a distance of 1 and labels the point.
| Point | Position | Points within distance 1 | Count | Label |
|---|---|---|---|---|
| P1 | (1, 1) | P1, P2, P3 | 3 | Core |
| P2 | (2, 1) | P2, P1, P4 | 3 | Core |
| P3 | (1, 2) | P3, P1, P4 | 3 | Core |
| P4 | (2, 2) | P4, P2, P3, P5 | 4 | Core |
| P5 | (3, 2) | P5, P4 | 2 | Border |
| P6 | (6, 5) | P6 | 1 | Noise |
The distances that matter are all exactly 1, for example from P1 = (1, 1) to P2 = (2, 1), while P1 and P4 are √(1² + 1²) = 1.41 apart and so are not neighbours. P1 to P4 each have at least 3 points within Eps, so they are core points, and because they are linked through one another they form one cluster. P5 has only 2, so it is not a core point, but it lies within Eps of the core point P4, so it is a border point of the same cluster. P6 is more than 1 away from every other point, so it is noise. In real use, the same method is applied to the GPS locations of taxi pickups with, for example, Eps = 200 metres and MinPts = 20, so that railway stations and shopping malls become clusters and isolated pickups become noise.
ExplanationA cluster grows outwards from its core points through every point that can be reached within Eps. As a result, it can follow streets and other irregular shapes, and the number of clusters is found automatically rather than chosen in advance.
OPTICS. Instead of fixing a single value of Eps, OPTICS orders the points by their reachability distance.
ExampleThe same taxi data contains very dense pickups at the airport and moderately dense pickups at a market. In the OPTICS reachability plot, the airport appears as a deep valley and the market as a shallower one.
ExplanationA single OPTICS plot reveals clusters at every level of density, so the analyst does not have to guess one value of Eps, as DBSCAN requires.
12.6 Grid-based methods: STING and CLIQUE
STING (STatistical INformation Grid). STING divides the space into rectangular cells at several levels and stores summary statistics for each cell, such as the count, mean, standard deviation, minimum and maximum.
ExampleA city map is divided into 4 zones, each zone into 16 wards, and each ward into 64 blocks, and every cell stores the number of restaurants it contains. The four zones hold 120, 30, 45 and 15 restaurants, which is 210 in total. To find wards with more than 50 restaurants, STING first checks the 4 zones; only zone 1, with 120, can contain such a ward, because no ward can hold more restaurants than its zone. STING then checks only the 16 wards of zone 1.
ExplanationSTING looks at 4 + 16 = 20 cells instead of all 4 × 16 = 64 wards, and it never reads individual restaurants. The time a query takes depends on the number of cells, not on the number of restaurants, so STING answers queries very quickly.
CLIQUE. CLIQUE combines the grid and density ideas to find dense units in subspaces of high-dimensional data, working level by level in the same way as the Apriori algorithm.
ExampleA data set holds 10,000 customers with 10 attributes, and a grid unit counts as dense if it holds at least 5 per cent of them, which is 0.05 × 10,000 = 500 customers. In one dimension, the unit "age 30 to 40" holds 2,400 customers and the unit "salary ₹8 to 12 lakh" holds 2,100, so both are dense. CLIQUE therefore combines them into the two-dimensional unit "age 30 to 40 and salary ₹8 to 12 lakh", which holds 760 customers. Since 760 is at least 500, this unit is also dense, and CLIQUE has found it without looking at the other eight attributes.
ExplanationA unit that is dense in two dimensions must also be dense in each of those dimensions on its own. CLIQUE therefore builds its candidates level by level, just as Apriori builds larger itemsets from smaller frequent ones.
12.7 Model-based method: statistical approach
Expectation-maximisation (EM). EM assumes that the data was generated by a mixture of probability distributions, and it estimates the parameters of each distribution.
ExampleThe heights of 1,000 adults form two overlapping bell curves. After some rounds, EM estimates that one group (mostly women) has a mean of 155 cm and the other (mostly men) has a mean of 170 cm, that both have a standard deviation of 7 cm, and that each group holds half the people. For a person who is 163 cm tall, the normal density is f(x) = e^(−(x − μ)² ÷ (2σ²)) ÷ (σ √(2π)). For the first group, (163 − 155)² ÷ (2 × 49) = 64 ÷ 98 = 0.653, so f = e^(−0.653) ÷ (7 × 2.507) = 0.520 ÷ 17.55 = 0.0297. For the second group, (163 − 170)² ÷ 98 = 49 ÷ 98 = 0.5, so f = e^(−0.5) ÷ 17.55 = 0.607 ÷ 17.55 = 0.0346. Because the two groups are equally large, the probabilities of belonging to them are 0.0297 ÷ (0.0297 + 0.0346) = 0.46 and 0.0346 ÷ 0.0643 = 0.54. The person therefore belongs 46 per cent to the first group and 54 per cent to the second.
ExplanationIn the expectation step, EM assigns these membership probabilities, and in the maximisation step it re-estimates the curves. The two steps repeat until the results stop changing. Unlike K-means, EM gives each point a soft membership rather than placing it firmly in one cluster.
COBWEB. COBWEB is a conceptual clustering method that builds a classification tree using a measure called category utility.
ExampleAnimals described by their covering, number of legs and habitat are placed one at a time into a tree, such as one that divides animals into mammals, birds and fish.
ExplanationEach new record is placed wherever it most improves the category utility, so the tree grows as new data arrives.
Exam points
- Clustering is unsupervised: no class labels are given.
- Hierarchical methods produce a dendrogram and need no k in advance; partitional methods such as K-means need k.
- Single link merges clusters by their closest members; complete link by their farthest members.
- CURE represents each cluster by several scattered points shrunk toward the centre.
- DBSCAN uses Eps and MinPts and labels points as core, border or noise; OPTICS orders points by reachability distance.
- STING and CLIQUE are grid-based; CLIQUE finds dense units in subspaces of high-dimensional data.
- EM is model-based and gives each point a probability of belonging to each cluster.
Independent study notes for learning purposes. Not affiliated with or endorsed by any university, publisher or course provider. Product and company names are trademarks of their respective owners.