From a Merge Schedule to a Tree
An agglomeration schedule records the construction of a hierarchical clustering one merge at a time. A dendrogram is a graphical record of those same merges: the original observations appear as leaves, and each branch junction marks the height at which two existing clusters joined. To draw the tree accurately, track not only which labels occur in each row, but also which observations are contained in every cluster label created along the way.
The task here is to translate the schedule, not to infer a different clustering from the data. The rows determine the topology: they say which branches meet. The height column determines the vertical position of each meeting point. A leaf order can be chosen for readability, provided the branches still represent exactly the scheduled merges. The examples below use nondecreasing merge heights, so their branches can be drawn in the usual bottom-to-top way.
A schedule may identify clusters by listing their members, such as \(\{1,2\}\), or by assigning a new label to each cluster when it is formed, such as \(C_5\). In either case, keep a membership record. If \(C_5\) contains observations 1 and 2, then a later row that merges \(C_5\) with observation 3 means the new cluster contains \(\{1,2,3\}\). It does not mean that the leaf labelled \(C_5\) should be drawn alongside the original leaves.
A Reliable Construction Procedure
Use a separate pass through the schedule to establish the tree’s structure before placing heights. At the start, every observation is a one-leaf cluster. For each row, find the two clusters named, connect their existing subtrees, and record the membership of the new cluster. Only after that membership is clear should you position the junction vertically at the row’s height.
Write each original observation once. These are the tips of the dendrogram, not the newly formed cluster labels.
Identify the two current clusters being joined and the recorded height for that merge.
Join the roots of those two clusters at the row’s height. The new junction represents their union.
Replace the two merged clusters in the working list by their union, keeping the new schedule label if one is supplied.
Confirm that each scheduled pair meets at the specified height and that the final tree contains all original leaves.
The horizontal placement is mainly a drawing choice. A useful convention is to place the two child groups side by side and keep each group’s leaves together. For a simple coordinate layout, assign leaf positions from left to right and put a junction midway between the horizontal positions of its two child roots. The vertical coordinate, by contrast, is not arbitrary: it must equal the scheduled merge height.
Worked Constructions
Worked Example: Four Leaves and Three Merge Heights
A schedule for observations 1–4 is shown below. Construct the dendrogram by identifying the clusters at each row, choosing a leaf order, and specifying all junction heights.
| Row | First cluster | Second cluster | Height | New cluster |
|---|---|---|---|---|
| 1 | 1 | 2 | 0.20 | \(C_5\) |
| 2 | 3 | 4 | 0.35 | \(C_6\) |
| 3 | \(C_5\) | \(C_6\) | 0.80 | \(C_7\) |
Step 1: Start with the four leaves. The leaves are 1, 2, 3, and 4. Place them from left to right in that order.
Step 2: Process row 1. Leaves 1 and 2 merge at height 0.20. Draw a junction above them at \(h=0.20\), and label its membership \(C_5=\{1,2\}\). With leaf positions \(x_1=1\) and \(x_2=2\), its horizontal position can be \(x_{C_5}=(1+2)/2=1.5\).
Step 3: Process row 2. Leaves 3 and 4 merge at height 0.35. Their junction is at \(h=0.35\), with \(C_6=\{3,4\}\). Their positions are \(x_3=3\) and \(x_4=4\), so \(x_{C_6}=(3+4)/2=3.5\).
Step 4: Process row 3. The row names \(C_5\) and \(C_6\), so connect the two existing cluster roots, not four separate new leaves. Put their parent junction at \(h=0.80\), horizontally at \((1.5+3.5)/2=2.5\). The final membership is \(C_7=\{1,2,3,4\}\).
Check. The tree has four leaves, the first two pairwise joins occur at 0.20 and 0.35, and those two subtrees meet at 0.80. The common mistake is to treat \(C_5\) or \(C_6\) as additional leaves; that would incorrectly produce more than four observations.
Worked Example: Following Cluster Labels Through Later Rows
A five-observation schedule assigns a new label after every merge. Build the tree and give a consistent left-to-right leaf order.
| Row | First cluster | Second cluster | Height | New cluster |
|---|---|---|---|---|
| 1 | 2 | 5 | 0.12 | \(C_6\) |
| 2 | 1 | 3 | 0.25 | \(C_7\) |
| 3 | \(C_7\) | 4 | 0.55 | \(C_8\) |
| 4 | \(C_6\) | \(C_8\) | 0.90 | \(C_9\) |
Step 1: Track membership. Row 1 gives \(C_6=\{2,5\}\). Row 2 gives \(C_7=\{1,3\}\). Row 3 therefore gives \(C_8=\{1,3,4\}\). The last row joins \(C_6\) and \(C_8\), so \(C_9=\{1,2,3,4,5\}\).
Step 2: Choose leaf order. Put leaves 2, 5, 1, 3, 4 from left to right. This keeps the members of \(C_6\) together and also keeps the members of \(C_8\) together, with the \(\{1,3\}\) pair adjacent within that group.
Step 3: Place the first two junctions. Assign horizontal positions 1, 2, 3, 4, and 5 to leaves 2, 5, 1, 3, and 4, respectively. The \(C_6\) junction is at \(h=0.12\), \(x=(1+2)/2=1.5\). The \(C_7\) junction is at \(h=0.25\), \(x=(3+4)/2=3.5\).
Step 4: Place the next two junctions. Row 3 joins the root of \(C_7\) at \(x=3.5\) to leaf 4 at \(x=5\). Thus \(C_8\) has its junction at \(h=0.55\) and may be placed at \(x=(3.5+5)/2=4.25\). Row 4 joins \(C_6\), at \(x=1.5\), to \(C_8\), at \(x=4.25\). Put the final junction at \(h=0.90\), with \(x=(1.5+4.25)/2=2.875\).
Check. The leaves are exactly 2, 5, 1, 3, and 4; the memberships at the final node combine to all five observations. The method avoids a common label trap: \(C_7\) in row 3 refers to the already formed pair \(\{1,3\}\), not to a sixth observation.
Worked Example: Reconstructing a Six-Leaf Tree with Nested Merges
A schedule for observations 1–6 is as follows. Construct a leaf order and calculate convenient horizontal coordinates for all five junctions.
| Row | First cluster | Second cluster | Height | New cluster |
|---|---|---|---|---|
| 1 | 1 | 4 | 0.10 | \(C_7\) |
| 2 | 2 | 3 | 0.18 | \(C_8\) |
| 3 | \(C_8\) | 5 | 0.42 | \(C_9\) |
| 4 | 6 | \(C_7\) | 0.60 | \(C_{10}\) |
| 5 | \(C_9\) | \(C_{10}\) | 0.95 | \(C_{11}\) |
Step 1: Compute memberships. The rows give \(C_7=\{1,4\}\), \(C_8=\{2,3\}\), \(C_9=\{2,3,5\}\), \(C_{10}=\{1,4,6\}\), and \(C_{11}=\{1,2,3,4,5,6\}\).
Step 2: Arrange leaves in groups. Use the order 2, 3, 5, 6, 1, 4. This makes the leaves of \(C_9\) a consecutive left block and the leaves of \(C_{10}\) a consecutive right block. Assign their horizontal positions 1 through 6 in that order.
Step 3: Calculate the junction positions. Row 2 joins leaves 2 and 3, at positions 1 and 2, so \(x_{C_8}=1.5\); its height is 0.18. Row 1 joins leaves 1 and 4, at positions 5 and 6, so \(x_{C_7}=5.5\); its height is 0.10. Row 3 joins \(C_8\) at 1.5 to leaf 5 at position 3, giving \(x_{C_9}=(1.5+3)/2=2.25\) at height 0.42.
Step 4: Finish the upper merges. Row 4 joins leaf 6 at position 4 to \(C_7\) at 5.5, so \(x_{C_{10}}=(4+5.5)/2=4.75\) at height 0.60. Row 5 joins \(C_9\) at 2.25 to \(C_{10}\) at 4.75, so the final junction is at \(x=(2.25+4.75)/2=3.5\) and height 0.95.
Check. The left subtree contains exactly \(\{2,3,5\}\), the right subtree exactly \(\{6,1,4\}\), and their final merge contains all six leaves. The intermediate junctions are at the five schedule heights 0.10, 0.18, 0.42, 0.60, and 0.95. Reversing the left-to-right order of either child group would also be valid if all connections were preserved.
Why the Row-by-Row Method Works
The construction follows directly from what a hierarchical merge means. At any stage, the current clusters partition the observations: every observation belongs to exactly one current cluster. A row selects two of those clusters and replaces them with their union. In the drawing, the two selected clusters already have subtrees, so their roots are precisely the two branches that must connect to the new junction.
This gives a simple invariant: after processing any number of rows, each current cluster has one corresponding subtree whose leaves are exactly the observations in that cluster. Initially, each singleton cluster corresponds to its single leaf, so the statement holds. If it holds before a merge of \(A\) and \(B\), attach their two subtree roots to one new junction. The leaves below that junction are exactly the leaves of \(A\) together with those of \(B\), which is \(A\cup B\). Thus the invariant continues to hold after the merge. The recorded height supplies the vertical coordinate of that new junction.
The argument also explains why schedule labels must be followed carefully. A label introduced in one row stands for an entire subtree in every later row where it appears. Expanding its membership in a working record is a dependable way to prevent the diagram from confusing a cluster with an individual observation.
Common Construction Errors
The most frequent error is to draw the correct branches at the wrong heights. A branch junction belongs at the height in its own merge row, not at a height chosen to make the picture look evenly spaced. Another error is to connect a new cluster label directly to the leaves named in its membership, even though those leaves have already been joined at earlier heights.
For example, suppose a row merges \(C_6\) with leaf 4 at height 0.55, and \(C_6=\{2,5\}\) was created earlier at height 0.12. The correct drawing connects the root of the \(\{2,5\}\) subtree at 0.12 to a new junction at 0.55, and connects leaf 4 to that same junction. Drawing a fresh branch from leaves 2 and 5 straight to height 0.55 erases their earlier merge.
Do not assume that leaf order is uniquely determined by the schedule. Several orders may display the same merge structure. What must remain fixed is the membership of each subtree and the height of each merge. This construction skill is aligned with the SOA Exam SRM (Statistics for Risk Modeling) syllabus.
Check Your Understanding
For each schedule, identify the memberships and junction heights needed to construct the tree. The final answer is provided for checking.
- A schedule begins with \(1,3\) at height 0.14 forming \(C_5\), then merges \(2,4\) at 0.31 forming \(C_6\), then merges \(C_5,C_6\) at 0.72. Give all three cluster memberships and the corresponding node heights. (Answer: \(C_5=\{1,3\}\) at 0.14; \(C_6=\{2,4\}\) at 0.31; final cluster \(\{1,2,3,4\}\) at 0.72.)
- Rows are \(1,5\) at 0.08 forming \(C_6\); \(C_6,2\) at 0.27 forming \(C_7\); \(3,4\) at 0.40 forming \(C_8\); and \(C_7,C_8\) at 0.83. State the membership at each new cluster and the height of the final junction. (Answer: \(C_6=\{1,5\}\); \(C_7=\{1,2,5\}\); \(C_8=\{3,4\}\); final cluster \(\{1,2,3,4,5\}\) at 0.83.)
- For leaves \(a,b,c,d,e\), the schedule is \(a,b\) at 0.16 forming \(C_6\); \(d,e\) at 0.22 forming \(C_7\); \(c,C_6\) at 0.49 forming \(C_8\); and \(C_8,C_7\) at 0.91. Give a leaf order that keeps each first-level pair together, then list the two upper junction heights. (Answer: one valid order is \(a,b,c,d,e\); upper junction heights are 0.49 and 0.91.)
- A schedule merges \(2,6\) at 0.11 into \(C_7\), then \(1,4\) at 0.24 into \(C_8\), then \(C_7,5\) at 0.50 into \(C_9\), and finally \(C_9,C_8\) at 0.88. Give the memberships of \(C_9\) and the final cluster, and state which previously formed subtrees must connect at the last node. (Answer: \(C_9=\{2,5,6\}\); final cluster \(\{1,2,4,5,6\}\); connect the roots of \(C_9\) and \(C_8=\{1,4\}\) at height 0.88.)
- For observations 1–6, the merges are \(1,2\) at 0.10; \(4,6\) at 0.20; \(3,\{1,2\}\) at 0.45; \(5,\{4,6\}\) at 0.63; and the two resulting three-observation clusters at 0.97. State the memberships of the final two child clusters and the number of leaves in the complete dendrogram. (Answer: the child clusters are \(\{1,2,3\}\) and \(\{4,5,6\}\); the complete dendrogram has 6 leaves.)