Clustering concepts #

Most analyses start from a question with a known answer column: does spend differ by branch, does satisfaction predict recommending. Clustering starts without one. It asks whether the cases fall into groups nobody has labelled – types of customer, profiles of response – and finds them from the resemblance between the rows alone. This page explains the ideas the cluster analysis module turns on, in the order its panel meets them: what a cluster is and what can be clustered, how the distance between two cases is measured and why the variables are put on one scale first, how correlation and Gower’s coefficient stand in for a distance, how the three algorithms build their clusters and how a tree is read and cut, how the number of clusters is chosen and whether the data are clustered at all, what a bicluster is, how a solution is checked against resampling and pictured on a plot, and what a finished solution does and does not claim. The module asks for the variables to cluster on – selected in the variable list – and a clustering mode: cases, variables, or both at once. The numbers come from the café data with its three fixes applied: the 200 loyalty members are clustered on overall, spend_after and visits_after – 192 members have all three – with the variables standardized, and the six satisfaction items taste, fresh, value, friendly, quick and slow are the variables clustered in variable mode and the matrix that is biclustered. Every number is reproduced with the other options at their defaults.

What clustering does #

Clustering is the family of methods that sort objects into groups from their resemblance alone, so that the objects in one group are more alike than objects in different groups – with no outcome to predict and no labels to learn from. That is what separates it from a classification, which is taught the categories on labelled cases and then assigns new ones, and from a comparison, which starts from groups already defined. The method is given the rows, the variables to compare them on, and a way of measuring how far apart two rows are; everything else – how many groups, which case belongs where, what the groups mean – comes out of the data and the analyst’s reading of it. On the café’s 192 members, clustered on their overall rating, their spend and their visits after the menu change, k-means with three clusters returns 13 frequent visitors (on average overall 5.6, spend 10.3, visits 23.5), 96 lukewarm low-spenders (6.3, 7.5, 5.0) and 83 satisfied high-spenders (8.7, 12.2, 8.1) – three segments the till never labelled.

A cluster is one of those groups: a set of cases that the algorithm has put together, numbered 1 to k in an order that means nothing – cluster 1 of one run may be cluster 3 of the next. The number k is the count of clusters, fixed in advance by the analyst for k-means and k-medoids and chosen by where a tree is cut for hierarchical clustering; the partition is the whole assignment of every case to one cluster. Reading a cluster means reading its profile – the mean of each variable inside it against the mean of the whole sample – and naming it from what stands out, as the three café segments were named above from their visits, their spend and their rating.

Clustering cases, variables or both is the choice of what the objects are. Case clustering treats each row as an object described by its columns – the members, described by rating, spend and visits – and groups the rows. Variable clustering turns the table on its side: each column is an object described by its 192 values, two columns are close when they rise and fall together across the members, and the groups are sets of variables that behave alike – the questionnaire’s sub-scales, found without a factor model. Biclustering keeps both axes open at once and looks for a block – some rows on some columns – inside which the values cohere, leaving the rest of the table out; it is the mode for a structure that does not span every variable, such as a set of members who answer a few of the items alike and the others no differently from anyone else.

Distance #

Distance – in clustering usually called dissimilarity, since not every measure is a distance in the geometric sense – is one number saying how far apart two objects are on all their variables together: zero for two identical rows, larger the more they differ. Every algorithm on this page works from it, so the choice of measure is part of the definition of “alike”. The first two members of the café file are a member who rated the café 8, spends 6.37 and visited 6 times, and one who rated it 9, spends 7.83 and visited twice; on the raw numbers their differences are 1, 1.46 and 4, and the five measures below turn those three differences into one number in five different ways.

Euclidean distance is the straight-line distance between two points whose coordinates are the variables:

Squaring the differences before adding them means one large difference counts for more than several small ones adding up to the same total. Between the first two members it is $\sqrt{1^2+{1.46}^2+4^2}$ = 4.37 on the raw numbers, and 0.92 once the three variables are standardized. It is the default, and the only distance k-means can minimise, because a cluster’s mean is the point that minimises the squared Euclidean distances to its members.

Manhattan distance – the city-block distance – adds the absolute differences instead of squaring them:

Between the first two members it is 1 + 1.46 + 4 = 6.46 raw and 1.56 standardized. Because nothing is squared, a single large difference pulls it less than it pulls the Euclidean distance, which makes it the steadier choice when a few cases carry one extreme value.

Chebyshev distance – the module’s Maximum – is the largest single difference, ${\max }_j|x_j-y_j|$, and ignores the others: 4 between the first two members raw, the visits difference alone, and 0.64 standardized. It says two cases are as far apart as their most different variable makes them, which is the right reading when one big discrepancy should decide and the rest should not soften it.

Canberra distance adds the differences each divided by the size of the two values:

A difference of 1 between 1 and 2 counts as much as a difference of 50 between 50 and 100, so small values matter in proportion, which suits counts and other non-negative variables where the scale is a ratio. Between the first two members it is 0.66 on the raw numbers. It is meant for values at or above zero: standardized variables sit on both sides of zero, and a pair straddling it – one member a little above the mean, the other a little below – scores close to a full unit apart however small the gap, so Canberra is best run with standardization off.

Minkowski distance is the family the first three belong to, with an exponent p that sets how much a large difference dominates:

At p = 1 it is the Manhattan distance, at p = 2 the Euclidean, and as p grows it approaches the Chebyshev: between the first two standardized members it reads 1.56, 0.92 and, at p = 3, 0.78, on its way down to the 0.64 of the largest difference alone. Values between 1 and 2 are the practical range – a compromise between counting every difference and letting the biggest one lead.

Standardization before clustering puts every variable on one scale, usually as z-scores – each value minus the variable’s mean, divided by its standard deviation – so that the variable with the biggest numbers does not decide the distances on its own. Rating, spend and visits are measured in points, currency and counts, with standard deviations of 1.9, 3.7 and 6.3; squared and added over the 192 members, visits hold 69% of the total variation, spend 25% and the rating 6%, so a clustering on the raw numbers is largely a clustering on visits. It shows in the result: k-means with three clusters on the raw variables gives clusters whose mean rating is 7.9, 6.9 and 7.0 – the rating hardly separates them – where the standardized clusters read 5.6, 6.3 and 8.7. Standardizing is the default and the right call whenever the variables are on different scales; it is switched off only when they share one meaningful scale and their differing spreads are part of what should be clustered, and it has no bearing on a categorical variable, which has no scale to standardize.

Correlation as a dissimilarity turns the correlation r between two variables into a distance between them: 1 − r is 0 for two columns that move in step, 1 for two unrelated ones and 2 for two that move in exact opposition, and 1 − |r| ignores the direction, so that a variable and its mirror image count as identical. On standardized columns the two readings are not a different geometry but the same one: the squared Euclidean distance between two z-scored variables is $2(n-1)(1-r)$, which is why variable clustering always standardizes. On the café’s items, quick and slow correlate at −.42, so 1 − r puts them 1.42 apart – nearly as far as two variables can be – and 1 − |r| puts them 0.58 apart, closer than taste and quick at 0.78; taste and fresh, at r = .51, are 0.49 apart either way. Cutting a tree of the six items into two groups gives, under 1 − |r|, {taste, fresh, value} and {friendly, quick, slow} – the two sub-scales the survey was built from – and under 1 − r, slow alone against the other five, because it is worded in the opposite direction. The absolute version is the one for a questionnaire with reverse-keyed items; the signed version is for variables whose direction is part of their meaning.

Gower’s coefficient is the dissimilarity for a table that mixes numbers with categories. Each variable is scored on its own terms, between 0 and 1: a numeric variable as the absolute difference divided by the variable’s range, an ordinal one the same way on its ranks, and a categorical one as 0 for the same level and 1 for different levels; the dissimilarity between two cases is the average of the scores over the variables. Between the first two café members on rating, spend, visits, branch and recommend the five scores are 0.111 (a difference of 1 on a range of 9), 0.079, 0.093, 0 (both at Riverside) and 1 (one would recommend, the other would not), which average to 0.257. The last term shows the coefficient’s character: a categorical mismatch scores a full 1 where a numeric difference scores a fraction of its range, so a categorical variable weighs heavily in the average. Clustering the members with k-medoids into three groups under Gower on those five variables gives 84 members who are Riverside-and-would-recommend, 50 who are Station-and-would-not and 58 who are Station-and-would – the two categorical columns carve the partition and the three numeric ones only shade it. It is the coefficient to use when a categorical variable genuinely belongs among the clustering variables; when every variable is numeric, a distance is the better-behaved choice.

The algorithms #

K-means clustering picks k centre points, assigns every case to the nearest centre, moves each centre to the mean of the cases assigned to it, and repeats until nothing moves. The result minimises the within-cluster sum of squares – the squared Euclidean distances from every case to its own cluster’s mean, added up – so its clusters are round-ish, of similar spread, and cut from one another by straight boundaries; an elongated or ring-shaped group is broken into pieces. Where it stops depends on where it started, since the procedure only ever improves and never restarts, so it is run from many random starting sets and the best is kept. It needs k fixed in advance and the Euclidean distance, since the mean is the point that minimises squared Euclidean distances and nothing else. On the café’s standardized rating, spend and visits with k = 3 it converges in two passes to the 13, 96 and 83 members above, and the split accounts for 249 of the 573 units of total variation – 43.5% – with the rest left inside the clusters.

A medoid is the member of a cluster that is on average least dissimilar to the other members – the most central case, as the mean is the most central point – and k-medoids is the clustering that uses medoids as its centres: each case is assigned to the nearest medoid and each medoid is swapped for another member of its cluster whenever the swap lowers the total dissimilarity, until no swap helps. Because a medoid is a real case rather than a computed point, the method runs on any dissimilarity, Gower and the correlations included, and a far-out case cannot drag a centre towards itself as it drags a mean. On the café’s three standardized variables with k = 3, k-medoids returns 70, 48 and 74 members around medoids that are members 75, 83 and 48 of the file – a member who rated 7, spends 6.58 and visited 4 times, one at 5, 10.86 and 7, and one at 9, 11.78 and 8 – so each segment can be described by a real member of it.

Hierarchical clustering starts from every case as its own cluster and, at each step, merges the two clusters that are closest, until one cluster holds everything; the record of the 191 merges the 192 members go through is a tree, and a solution with k clusters is that tree cut where k branches remain. Nothing is fixed in advance and nothing is random – the same data and settings always give the same tree – and the tree shows every nested solution at once, so the choice of k can be read off the structure instead of asserted. What “closest” means for two clusters, rather than two cases, is the linkage, and it shapes the result as much as the distance does. Ward’s linkage on the café’s three variables cut at three gives 119, 64 and 9 members – 9 heavy visitors averaging 27 visits, split off first.

A dendrogram is the drawing of that tree: the cases along the bottom, each merge a horizontal bar joining two branches, and the bar’s height the dissimilarity at which the merge happened – low bars join cases that were alike, high bars join groups that had little in common. A horizontal line across the tree is a cut, and the branches it crosses are the clusters: a cut just under the top bar gives two clusters, a cut under the next gives three. The gaps between successive bar heights are what the tree says about k: a long climb from one bar to the next means the two groups merged there were well apart. On the café tree under Ward’s linkage the last three merges sit at heights 12.5, 12.8 and 16.2 – a wide step to the final merge and a narrow one before it, so the tree separates two groups clearly and three only just.

Linkage is the rule that says how far apart two clusters are, given the distances between their members; every hierarchical algorithm needs one, since after the first merge it compares groups, not points. The choice decides the shape of the clusters that form.

Single linkage takes the distance between two clusters as the distance between their two closest members. A cluster can therefore grow by one near neighbour at a time into a long chain – chaining – so it finds elongated, irregularly shaped groups that the other linkages break up, and on data with no such shapes it swallows almost everything into one cluster and leaves the isolated cases as singletons: on the café’s three variables cut at three it returns 190 members, 1 and 1.

Complete linkage takes the distance between two clusters as the distance between their two farthest members, so two groups merge only when everything in one is close to everything in the other. Its clusters are compact and of similar diameter, and a single far-out case can hold a whole merge back, since it sets its cluster’s farthest point: on the café’s variables cut at three it gives 79, 111 and 2 members, the 2 being a pair of outlying members that no group wanted.

Average linkage – UPGMA, the unweighted pair-group method with arithmetic mean – takes the mean of all the member-to-member distances between the two clusters, a compromise between the nearest pair and the farthest one that produces moderately sized, balanced clusters and is the linkage whose tree heights most faithfully reproduce the original distances. McQuitty’s linkage – WPGMA, the weighted version – averages differently: when two clusters merge, the new cluster’s distance to any other is the plain mean of its two parts’ distances, whatever their sizes, so a small cluster counts as much as a large one it joins.

Ward’s method merges, at each step, the pair of clusters whose union increases the total within-cluster sum of squares the least – the same quantity k-means minimises, pursued greedily one merge at a time. It favours compact clusters of similar size and is the usual default for a hierarchical run on numeric data; because its criterion is a sum of squared Euclidean distances, it assumes that distance and is on shaky ground with another. The module’s Ward’s (D2) is the version that takes the distances themselves, rather than their squares, as its input, so its tree heights are on the distance scale.

Centroid and median linkage take the distance between two clusters as the distance between their centres – the centroid, the mean of each cluster’s members, or the median, the midpoint between the two clusters that formed it, which weights them equally regardless of size. Both have a peculiarity the other linkages do not: a new cluster’s centre can lie closer to a third cluster than either of its parts did, so the next merge happens at a lower height than the one before it – an inversion, drawn in the dendrogram as a bar below the two it joins. On the café’s three variables, 9 of the 191 centroid merges are inversions, and the cut at three gives 187, 3 and 2 members. An inversion is a real feature of the data under that linkage, not an error, but it makes the tree hard to read and cut.

Choosing the number of clusters #

Clustering tendency is whether the cases bunch into groups at all, rather than spreading as evenly as random points would – the question before how many, since every algorithm returns clusters on any data, grouped or not.

The Hopkins statistic measures it by comparing two sets of nearest-neighbour distances: from points drawn uniformly at random over the range of the data to the nearest real case, and from as many real cases to their nearest other case,

where the $u_i$ are the random points’ distances and the $w_i$ the real cases’. On evenly scattered data the two kinds of distance are alike and H is near 0.5; when the cases bunch, real cases sit close to one another while random points fall into the empty space between the bunches, and H climbs towards 1; below 0.25 the cases are spaced more regularly than chance, like a grid. From 0.75 up the data are read as clustered. On the café’s three standardized variables, probed with 19 random points – one per ten members – H = 0.81: the members are far from evenly spread, not least because visits are heavily skewed and a few heavy visitors sit far out on their own.

The Duda–Hart test asks the narrower question whether two clusters describe the data better than one. It splits the data in two and compares the within-cluster sum of squares of the split, Je(2), with the sum of squares around the single overall mean, Je(1); the ratio is below 1, since a split can only reduce the scatter, and the test asks whether it is lower than a split of structureless, normally distributed data would make it – a significant p says two clusters beat one. On the café’s variables the best two-cluster split leaves 410.5 of the 573 units of variation, a ratio of 0.716 with p = .078: not enough to reject a single cluster at the .05 level, although Hopkins found the points far from even. The two do not contradict each other – Hopkins sees that the cloud is lumpy, Duda–Hart that it does not break cleanly into two halves.

Within-cluster dispersion is usually measured by the within-cluster sum of squares, W: the squared distance from every case to its own cluster’s mean, added up over the clusters – the quantity k-means minimises – and variance explained is the share of the total variation that lies between the clusters instead, 1 − W ⁄ T with T the total sum of squares. Both improve every time k grows – with as many clusters as cases, W is 0 – so neither can pick k by its best value. On the café’s variables W falls from 410.5 at k = 2 to 323.7 at 3 and 128.5 at 10, and variance explained climbs from 28% through 44% to 78%.

The elbow method reads k off the shape of that falling curve instead: plotted against k, W drops steeply while each new cluster splits a real group and flattens once the new clusters only cut groups that were already there, and the elbow where the steep part turns into the flat one is the candidate. The module marks it as the point furthest from the straight line joining the curve’s first and last points, and marks none when the curve is too straight to have a bend – the café’s curve bends most at k = 5. It is a reading aid, not a test: many curves bend gradually, and the elbow moves with the range tested.

Hartigan’s rule turns the comparison of neighbouring k into a number: for each k it sets W at k against W at k + 1,

and Hartigan’s rule of thumb is that a value above 10 means the (k + 1)-th cluster is still worth adding, so the count to stop at is the first k whose value falls to 10 or below. On the café data it is 50.7 at k = 2 and still 16.2 at k = 9 – above 10 at every k tested, so on these variables the rule never says stop: the within-cluster sum of squares keeps falling steadily rather than levelling off at a natural count.

The silhouette scores how well each case sits in its cluster. With a the case’s average dissimilarity to the other members of its own cluster and b its average dissimilarity to the members of the nearest other cluster,

which runs from −1 to +1: near +1 the case is much closer to its own cluster than to any other, near 0 it lies on the border between two, and below 0 it is closer to a neighbouring cluster than to its own and is probably misassigned. The average silhouette width over all cases grades the whole partition, and Kaufman and Rousseeuw’s bands read it as strong structure from 0.70, reasonable from 0.50, weak from 0.25 and no substantial structure below that. On the café’s variables the average peaks at k = 3 with 0.303 and stays between 0.275 and 0.303 from 2 to 10 clusters – every k sits in the weak band, so the three segments are real tendencies in the data rather than well-separated groups.

The Calinski–Harabasz index is the ratio of between-cluster to within-cluster variation, each divided by its degrees of freedom,

with B the between-cluster and W the within-cluster sum of squares. Higher is better – it rewards clusters that are tight and far apart at once – and the degrees of freedom keep it from simply growing with k; it assumes compact, roughly spherical clusters. On the café data it lies between 69.9 and 75.7 at every k from 2 to 10, highest at k = 6 – a nearly flat profile that favours no count strongly.

The Davies–Bouldin index looks at each cluster’s worst neighbour: for every pair of clusters it adds their two scatters – each the mean distance of a cluster’s members from its centre – and divides by the distance between the two centres, takes for each cluster the largest such ratio, and averages those over the clusters. Lower is better: zero would be clusters with no spread at all, and a value above 1 says that a typical cluster’s nearest neighbour is closer than their combined spreads. On the café data it falls from 1.37 at k = 2 to its lowest, 0.975, at k = 6.

The Dunn index is the smallest dissimilarity between two cases in different clusters divided by the largest dissimilarity between two cases in the same cluster. Higher is better, and a value above 1 would mean every cluster is narrower than the gap to the next; because both ends of the ratio are single extreme pairs, one outlying case can move it a long way, which makes it a strict but fragile index. On the café data it never exceeds 0.09 – the clusters touch, as the silhouette said – and its best, 0.085, is again at k = 6.

The gap statistic compares how tight the clusters are with how tight the same number of clusters would be on data that has none: it clusters a hundred reference samples drawn uniformly over a box shaped to the data’s own spread, and takes the gap between the reference samples’ average log within-cluster dispersion and the observed one,

so a large gap means the real clusters are much tighter than chance would produce. Tibshirani, Walther and Hastie’s rule then picks the smallest k whose gap is at least the next k’s gap less that one’s standard error – the smallest k that more clusters do not clearly improve on – and when that is k = 1, the data are no better clustered than the reference. On the café data the gap stays near 1.0 from 2 to 10 clusters without ever rising clearly, and the rule returns k = 1: against a reference that shares the data’s spread, the café’s three variables show no cluster structure the gap can detect.

When the indices disagree – and on real data they usually do – it is because each measures something different: the silhouette the fit of individual cases, Calinski–Harabasz and Davies–Bouldin the compactness and separation of round clusters, Dunn the single worst pair, the gap the difference from a structureless reference. Each has its own lean, too: the gap favours few clusters, Calinski–Harabasz and Davies–Bouldin assume spherical ones, Dunn follows outliers. On the café’s three variables the silhouette picks 3, the elbow 5, Calinski–Harabasz, Davies–Bouldin and Dunn 6, and the gap 1, while Hartigan never stops and Duda–Hart does not reject a single cluster. That spread is the finding: the members vary along gradients rather than falling into sharply separated types, and any k in that range is a way of summarising them – to be chosen by which solution is most interpretable and holds up when the sample is redrawn, not by which index won.

Biclustering #

A bicluster is a block of the data table – a subset of the cases on a subset of the variables – inside which the values are coherent, while the rest of the table is left out of the description: a cluster is a set of rows that resemble one another on every column, a bicluster a set of rows that resemble one another on some columns and may differ freely on the others. Biclusters can overlap – a case or a variable can belong to several, or to none – and how many there are is either fixed in advance or found by the algorithm. On the six café items, the BiMax algorithm with three biclusters at its default settings returns 36 members who rated value and friendly above their medians, 36 who rated taste and value above theirs, and 11 who rated quick and slow above theirs – eleven members who agreed both that their order came quickly and that the service was slow, a contradiction a clustering on all six items would never isolate.

The plaid model describes the table as a background plus layers: the background is fitted first to the whole table – a grand mean plus a shift per case and per variable – and each layer is a block of cases and variables inside which the values sit at their own level – a constant for the block, plus a shift per case and per variable – added on top of whatever lies beneath it. The layers are peeled off one at a time, each fitted to what the earlier ones left unexplained, and a candidate layer is kept only when it accounts for more than a randomly placed block of the same size would; when no candidate does, the search stops, which is how the model decides its own number of biclusters. On the six café items it finds no layer at all, whether or not the items are standardized: the items’ structure is two broad factors that touch every member, not blocks of members set apart on a few items, so nothing rises above the background.

Binarization turns every value into a 1 or a 0 by cutting each variable at a chosen quantile of its own values – above the cut is 1, at or below it is 0 – and a binary biclustering then looks for blocks that are all 1s: cases that are all high on a set of variables. Cutting each variable at its own quantile rather than the whole table at one value is what lets variables on different scales be searched together. BiMax finds the blocks that cannot be extended by another row or column without admitting a 0 – inclusion-maximal – so its biclusters are as large as the 1s allow and only as many as the search is asked for. On the café items cut at their medians it produces the three blocks quoted above.

Mean squared residue is the measure of a block’s coherence used by the Cheng and Church algorithm and reported by the module for every bicluster: how far the block’s values depart from a pattern of one shift per row plus one shift per column,

where $a_{iJ}$ and $a_{Ij}$ are the row and column means inside the block and $a_{IJ}$ its overall mean. A block in which every case is a constant shift from every other has H = 0, whatever its values; the whole table has some larger H, and a bicluster is a block whose residue is small against it. On the six standardized café items the whole table has H = 0.74, and Cheng and Church’s first bicluster, 42 members on the five items other than slow, has H = 0.14 – a fifth of the table’s. The threshold a block must stay under is what the analyst sets, and the module expresses it as a fraction of the table’s own residue so that the same setting means the same thing on any data.

Within-bicluster correlation is the other way of scoring a block’s coherence: the average correlation between every pair of the block’s rows across its columns. It asks only whether the rows rise and fall together, not by how much, so rows that follow one pattern at different amplitudes – one member’s answers swinging twice as widely as another’s – score high here and poorly on the mean squared residue, which expects a constant shift between rows. Higher is better, up to 1, and a row holding one value across the block’s columns correlates with nothing and is left out. On the six café items, BiMax’s two biclusters at k = 2 average r = 0.49 and a residue of 0.040; a block that scores well on both is coherent in the strictest sense, and a large gap between the two means its rows share a shape but not a scale.

Sparse factor biclusters are what the FABIA algorithm finds: it fits a factor model in which each factor’s loadings on the cases and scores on the variables are pushed towards zero for all but a few, so that a factor lives on a small block of the table, and that block is the bicluster. Because the pushing is soft, nothing is ever exactly zero, and membership is decided by a threshold on the factor values – a lower threshold admits more variables into each bicluster, a higher one more cases. It suits noisy numeric data with several overlapping patterns, and its number of biclusters is the number of factors asked for.

Checkerboard structure is the pattern the spectral algorithm looks for: the cases sorted into a few groups and the variables into a few groups, so that the table, reordered, is a grid of blocks each at its own level – like a chessboard whose squares differ in shade. It finds the two sortings from the leading singular vectors of the normalised table, pairs each case group with each variable group, and keeps the pairs whose block is large enough and whose values are tight enough. It is the algorithm for a table that is entirely block-structured, as a set of respondents from distinct populations answering distinct item groups would be; a table with one or two blocks in a sea of noise is the plaid model’s territory.

Checking and picturing a solution #

Cluster stability is whether a cluster found in this sample would be found again in another sample from the same population. The indices used in choosing the number of clusters grade a partition on the very cases that produced it, so they cannot tell a real group from a lucky cut of these rows; stability asks the question by resampling. The rows are drawn again with replacement – a bootstrap sample, the same size as the data, in which some cases appear twice and others not at all – the resample is clustered with the same settings, every case is classified to the nearest of the new clusters, and each original cluster is matched to the new cluster that resembles it most. The resemblance is the Jaccard similarity, the number of members two sets share divided by the number in either: a cluster of 13 that comes back as 12 of its members plus 3 others scores 12 ⁄ 16 = 0.75. Repeated a hundred times, each cluster gets a mean Jaccard, and a count of the resamples that recovered it (0.75 or more) and that dissolved it (0.5 or less). Hennig’s reading of the mean is highly stable from 0.85, stable from 0.75, a pattern with doubtful membership from 0.60, and not to be trusted below that. With the bootstrap seed at 42, the café’s three k-means segments score 0.61 for the 13 frequent visitors, 0.79 for the 96 lukewarm low-spenders and 0.78 for the 83 satisfied high-spenders: the two large segments come back in about seven resamples out of ten, while the frequent visitors dissolve in 38 of the 100 – a handful of far-out cases whose group depends on which of them a resample happens to draw. A cluster can be well cut in this sample, with a good silhouette, and still fail to reappear; stability is the only one of the diagnostics that asks about the next sample.

A consensus partition is a partition built from many clusterings of the data rather than one. Each resample’s clustering says, for every pair of cases, whether the two landed together; averaged over the resamples, that gives the co-association of the pair – 1 for two cases that were together every time, 0 for two that never were – and the table of co-associations is itself clustered, so that cases which reliably travel together form a consensus cluster. Set beside the solution actually reported, it shows which of the reported boundaries the resamples upheld. Two summaries read it: the agreement between the two partitions, as an adjusted Rand index, and the proportion of ambiguous clustering (PAC), the share of pairs whose co-association lies between 0.1 and 0.9 – pairs the resamples neither reliably kept together nor reliably separated, near 0 for a grouping the data pin down. On the café’s three k-means segments, with the seed at 42, the consensus partition keeps all 13 frequent visitors and all 96 lukewarm low-spenders where the reported solution put them and moves 9 of the 83 satisfied high-spenders into the lukewarm group: an adjusted Rand of 0.83, good agreement, with the disagreement confined to the border between the two large segments. Its PAC is 0.52, though – half of all pairs were split in some resamples and joined in others. A low agreement or a high PAC does not make the consensus right and the reported partition wrong, since both are cuts of the same data; it says the data do not settle the grouping, which is a reason to report the solution with caution rather than a different solution to report.

The adjusted Rand index measures how far two partitions of the same cases agree. It looks at every pair of cases and asks whether the two partitions treat the pair alike – both put the two together, or both keep them apart – and then corrects that share for the agreement two random partitions with the same cluster sizes would reach by chance. It is 1 for identical partitions, whatever the clusters are numbered, near 0 for agreement no better than chance, and can dip below 0. Steinley’s reading takes 0.90 and above as excellent agreement, 0.80 as good and 0.65 as moderate.

The cophenetic correlation measures how faithfully a tree reproduces the dissimilarities it was built from. Any two cases are joined in a dendrogram at some height – the height of the first merge that puts them in one branch – and that height is the tree’s version of their dissimilarity, the cophenetic distance; the cophenetic correlation is the ordinary correlation between the two, taken over every pair of cases. At 1 the tree’s heights and the original dissimilarities rise and fall together exactly; the usual mark of a tree that represents its data well is 0.75. It grades the whole tree, not a cut of it, so it does not change with k. On the café’s three standardized variables the Ward tree scores 0.50 and the average-linkage tree 0.79 – average linkage is the one built to keep the heights faithful, and it does – yet the average tree cut at three gives 187, 3 and 2 members, where the Ward tree gives the three usable segments. A faithful tree and a useful cut are different virtues, and the cophenetic correlation speaks only to the first.

Multidimensional scaling (MDS) places the objects on a flat plot so that the distances between the points reproduce the dissimilarities between the objects as closely as two dimensions allow – a map drawn from a table of distances, the way a road atlas’s mileage chart could be turned back into a map. It is one of the family of methods called ordination, and its purpose here is to show whether the clusters are separated in the data or only in the partition table: points coloured by cluster that form distinct clouds are clusters the dissimilarity itself separates; clouds that run into one another are clusters the algorithm drew through a continuum. Classical (metric) scaling reproduces the dissimilarities themselves and reports its fit as the share of their structure the two dimensions carry; on Euclidean distances it gives the same picture as the first two principal components. Non-metric scaling, after Kruskal, keeps only the order of the dissimilarities – the closest pair should be closest on the plot, the next closest next – which suits a dissimilarity whose ranking means more than its size, and reports its misfit as stress, read as excellent at 0.025 or below, good at 0.05 and fair at 0.1. On the café’s three standardized variables, classical scaling’s two dimensions carry 75% of the structure, and non-metric scaling reaches a stress of 0.15, past fair: a quarter of the differences between members is not on the plot, so two points that sit close together on it may still be members who differ – on the dimension the plot left out. The picture always looks confident; the fit is what says how much of it to believe, and it is read before the picture.

A biplot draws the cases and the variables on one plot: the cases as points on the first two principal components, as in a classical MDS plot, and each variable as an arrow from the centre pointing the way it increases. An arrow pointing into a cluster’s part of the plot is a variable that runs high in that cluster, which is how the plot says which variables produce a separation the MDS plot only shows exists. The angle between two arrows reads as their correlation – narrow for variables that move together, a right angle for unrelated ones, opposite for variables that pull against each other – and an arrow’s length says how well the two components represent it, so a short arrow’s direction is the weakest claim on the plot. On the café’s three standardized variables the first component carries 46% of the variation and the second 29%; all three arrows lean the same way along the first component, since rating, spend and visits are weakly but positively correlated with one another (r = .13 to .24), and the second component pulls the rating and the visits to opposite sides, with spend between them and the shortest arrow. The frequent visitors sit out along the visits arrow, the satisfied high-spenders towards the rating and spend arrows, and the lukewarm low-spenders on the far side from all three – the three segments’ profiles, read off one picture. What the two components leave out – a quarter of the variation here – is not in the picture, arrows included: the rating and visits arrows stand at about 100° on screen though the two variables correlate at .13, since each is only partly drawn.

What a solution can and cannot claim #

A cluster solution is a description of one sample under one set of choices – these variables, this dissimilarity, this algorithm, this k – and not a discovery that the groups exist. Every algorithm returns clusters: k-means asked for three finds three in uniformly scattered points, and a tree can be cut at any height. On the café’s three variables the same k = 3 gave 13, 96 and 83 members under k-means, 70, 48 and 74 under k-medoids, 119, 64 and 9 under Ward’s linkage and 190, 1 and 1 under single linkage – four honest answers to four differently posed questions, none of them wrong. What a solution can claim is what its diagnostics support: the module’s second step compares candidate values of k on indices of how compact and separated the clusters are, and its third step can ask whether each cluster reappears when the sample is redrawn – a cluster that dissolves under resampling was a feature of these 192 members and not of the population they came from. Report the choices with the result, name the clusters from their profiles rather than from a story decided beforehand, and treat them as types only once they have turned up again in other data.

Where this appears in DataSuite #

The cluster analysis module is built on these ideas: its first step chooses the mode, the standardization, the algorithm, the distance metric and the linkage, or a biclustering algorithm with its settings; its second step compares solutions across a range of k; its third step runs the chosen solution with its validity metrics – the cophenetic correlation among them for a tree – its profiles and dendrogram, the resampling checks of cluster stability and the consensus partition, and the multidimensional scaling and biplot pictures, and can write the cluster memberships back into the dataset. The factor analysis module is the other way of grouping variables, by a latent model rather than a tree; the Standardize and recoding rules of data transformation prepare a variable by hand when the module’s own standardization is not what is wanted; and the descriptive statistics module, run on the inserted cluster column as a grouping variable, is where a solution’s profiles are examined further.

A marketer: customers → cases, purchase measures → clustering variables, the segments → clusters; an ecologist: sampling sites → cases, species counts → clustering variables with Canberra as the distance; a psychometrician: questionnaire items → variables clustered in variable mode under 1 − |r|, the groups → sub-scales.