Why a Fixed-Cluster Cut Requires Counting
A dendrogram records a sequence of unions: at each agglomerative step, two current clusters combine into one. If a study begins with \(n\) individual observations, each such union reduces the number of clusters by exactly one. Therefore, to obtain a specified number \(K\) of clusters, count the required merges rather than estimating the answer from the apparent vertical spacing of branches.
This matters especially when several merge heights are close. A small gap may make the display look as though there is a natural dividing line, but the task “form \(K\) clusters” is determined by the requested count. If the dendrogram also reports a merge schedule, that schedule gives the sequence to follow. Heights alone do not always reveal the sequence.
The Merge Count and How to Use It
Let the initial partition consist of \(n\) singleton clusters, one for each observation. At merge 1, two clusters become one, so the count changes from \(n\) to \(n-1\). At merge 2, it changes to \(n-2\). Repeating this reasoning gives the count after any \(r\) merges.
To find the partition with \(K\) clusters, set \(n-r=K\) and solve for \(r\). This gives the required number of merges, \(r=n-K\). The reasoning depends on binary agglomerative steps: each step combines two clusters into one. It does not apply unchanged if a procedure records a simultaneous multiway merge as one step.
Count the observations represented by the leaves. Initially, each observation is its own cluster.
For a requested \(K\), calculate \(n-K\). This is the number of merges to include.
Use the agglomeration schedule or the tree structure to identify the first \(n-K\) merges. Do not include the next merge.
List the resulting groups and verify that there are exactly \(K\) clusters and that every observation appears once.
A merge height is the height shown for a union in the dendrogram, according to the distance or criterion used by the clustering method. When heights are nondecreasing along the merge sequence, a horizontal line between two successive distinct heights can represent the partition after the earlier merges. But that visual shortcut has conditions. Equal heights can make a particular \(K\) unavailable from a single horizontal cut under a convention that includes all merges at that height. Also, some methods can produce a later merge at a lower height than an earlier merge. In those cases, use the stated merge sequence to determine the fixed-\(K\) partition.
Worked Example: Choosing Four Clusters When Heights Are Close
A hypothetical portfolio segmentation contains seven observations, \(A,B,C,D,E,F,G\). Its agglomeration schedule is: merge 1, \(A\) with \(B\) at height 0.20; merge 2, \(D\) with \(E\) at 0.22; merge 3, cluster \(AB\) with \(C\) at 0.61; merge 4, \(F\) with \(G\) at 0.62; merge 5, cluster \(ABC\) with \(DE\) at 0.95; merge 6, cluster \(ABCDE\) with \(FG\) at 1.20. What partition has \(K=4\) clusters?
Method. There are \(n=7\) observations and the target is \(K=4\), so the number of merges to include is \(n-K=7-4=3\).
After merge 1, the clusters are \(AB,C,D,E,F,G\): six clusters. After merge 2, they are \(AB,C,DE,F,G\): five clusters. After merge 3, \(C\) joins \(AB\), giving \(ABC,DE,F,G\): four clusters.
Answer and check. The partition is \(\{A,B,C\},\{D,E\},\{F\},\{G\}\). It contains four clusters, and all seven observations appear exactly once. Merge 4, at height 0.62, is not included. The close heights 0.61 and 0.62 do not change the merge count; including both would leave only three clusters.
Common mistake avoided. A reader may see the short height gap and include both nearby joins. The count check prevents this: after four merges the number of clusters would be \(7-4=3\), not the requested four.
Tied Heights and More Than One Valid Partition
A tie occurs when two or more currently eligible merges have the same minimum dissimilarity. A clustering implementation may resolve that tie by choosing one eligible pair first, then updating the available distances and continuing. When different tied choices are valid, the resulting merge sequence, and therefore the partition at a particular \(K\), need not be unique.
The exact fixed-\(K\) instruction still has a clear counting rule: take the partition after the required number of recorded binary merges. However, if the tie-breaking choice is unspecified, the data and method may allow multiple partitions with that count. State the tie and the alternative outcomes rather than pretending that the dendrogram determines a unique grouping.
Worked Example: A Tied Merge Can Change the Four-Cluster Partition
Consider six hypothetical observations \(A,B,C,D,E,F\) under single linkage. Suppose the distances among \(A,B,C\) are all 0.50, the distance between \(D\) and \(E\) is 0.50, and all distances between these groups and \(F\), or between the two groups, exceed 0.50. The requested number of clusters is \(K=4\).
Method. Here \(n=6\), so \(n-K=6-4=2\) merges are required. Initially there are four eligible pairs at the tied minimum height 0.50: the three pairs among \(A,B,C\), and the pair \(D,E\). Consider two valid tie resolutions.
Resolution 1. Merge \(A\) with \(B\). The current clusters are \(AB,C,D,E,F\), or five clusters. Under single linkage, the distance from \(AB\) to \(C\) is \(\min(d(A,C),d(B,C))=0.50\), so \(AB\) with \(C\) is still tied with \(D\) and \(E\). If that second merge is selected, the result is \(ABC,D,E,F\).
Resolution 2. Merge \(A\) with \(B\) first, then merge \(D\) with \(E\), which is also tied at 0.50. The result is \(AB,C,DE,F\).
Answer and check. Both results contain four clusters after two merges. They are different partitions, so the tie-breaking rule matters to membership even though the requested count is fixed.
Common mistake avoided. Treating all joins drawn at the same height as one indivisible operation can skip over the requested count. For a binary schedule, count the recorded merges; if the tie resolution is not supplied, report the possible partitions consistent with the tie.
When Merge Heights Do Not Show Merge Order
For methods whose merge heights are nondecreasing, lower merge heights occur earlier in the sequence. That implication is not valid for every linkage method. Some methods can have a later merge displayed at a lower height than an earlier one. In such a case, height is not a reliable way to reconstruct chronological order. Follow the dendrogram’s topology or the supplied agglomeration schedule, and use the merge count to select the partition.
Worked Example: Following the Schedule When a Later Height Is Lower
A hypothetical five-observation dendrogram is accompanied by this merge schedule: merge 1 joins \(A\) and \(B\) at height 4.0; merge 2 joins \(C\) and \(D\) at height 3.0; merge 3 joins clusters \(AB\) and \(CD\) at height 5.0; merge 4 joins \(ABCD\) and \(E\) at height 6.0. Find the partition with \(K=3\).
Method. There are \(n=5\) observations and \(K=3\), so exactly \(5-3=2\) merges are needed. Following merge 1 gives \(AB,C,D,E\), or four clusters. Following merge 2 gives \(AB,CD,E\), or three clusters.
Answer and check. The requested partition is \(\{A,B\},\{C,D\},\{E\}\). It has three clusters and covers all five observations. Although merge 2 has height 3.0, below the height 4.0 of merge 1, the schedule explicitly places it second. Do not sort the merges by height.
Common mistake avoided. Assuming every dendrogram’s heights increase with time would incorrectly put the height-3.0 merge first. The cluster count is determined by the recorded sequence, not by sorting the heights.
Graphical Cuts, Counts, and Exam Traps
A horizontal cut is a convenient visual representation when the merge heights are nondecreasing and the cut falls between successive heights. The branches that remain separate below the cut identify the clusters. For distinct successive heights, a cut between those heights includes the lower merges and excludes the next one.
A fixed cluster count and a fixed height are different instructions. With tied heights, a cut that includes all nodes at a particular height may include multiple merges and jump past the requested \(K\). With nonmonotone heights, a horizontal line may not encode the chronological prefix of merges in the straightforward way. When the question specifies \(K\), the safest procedure is to calculate \(n-K\), follow the schedule, and then count the clusters.
A frequent arithmetic trap is to count merges rather than clusters incorrectly. For example, with \(n=10\) observations and a target of \(K=7\), the required merges are \(10-7=3\), not four. If the first three merges are \(AB\), \(CD\), and \(EF\), the clusters are \(AB,CD,EF,G,H,I,J\), which is seven. Including a fourth merge would leave six.
A second trap is to confuse a cluster’s name with its members. If a schedule labels a newly formed cluster “cluster 5,” that label is only an identifier. To state the partition, trace its members back to the original observations. Finally, if tied choices lead to different memberships, distinguish what is determined (the number of clusters after the specified number of merges) from what may not be determined (a unique membership partition without a tie-breaking rule).
Check Your Understanding
For each problem, calculate the merge count first, then verify the resulting number of clusters.
- A data set has nine observations \(A\) through \(I\). The first three merges are \(AB\), \(CD\), and \(EF\). What is the partition with six clusters? (Answer: \(AB, CD, EF, G, H, I\).)
- Six observations \(A,B,C,D,E,F\) have the schedule: merge \(AB\), merge \(CD\), then merge cluster \(AB\) with cluster \(CD\). What is the partition after three merges, and how many clusters remain? (Answer: \(ABCD, E, F\); three clusters.)
- Seven observations have successive merges \(AB\) at 0.31, \(CD\) at 0.32, \(EF\) at 0.33, and \(AB\) with \(C\) at 0.34. What is the partition at \(K=4\), and is the fourth merge included? (Answer: \(AB, CD, EF, G\); no, only the first three merges are included.)
- Five observations include a tied single-linkage choice among \(A,B,C\), all pairwise distances equal to 0.40, and a tied pair \(D,E\) at 0.40; all distances between these groups exceed 0.40. After first merging \(A\) with \(B\), give two possible partitions at \(K=3\). (Answer: \(ABC,D,E\) if \(AB\) then joins \(C\); or \(AB,DE,C\) if \(DE\) is the second merge.)
- A five-observation schedule has merge 1 \(AB\) at height 2.8 and merge 2 \(CD\) at height 2.1. What is the partition at \(K=3\), and which merge comes first? (Answer: \(AB,CD,E\); \(AB\) comes first according to the schedule, despite its greater height.)