I found the following article on "Hierarchical Clustering With Prototypes via Minimax Linkage".

It is stated in Property 6 that

Minimax linkage cannot be written using Lance–Williams updates.

A succinct proof using a counter-example is given:

Proof. Figure 9 shows a simple one-dimensional example that could not arise if minimax linkage followed Lance– Williams updates. The upper and lower panels show two configurations of points for which the right side of (4) is identical but the left side differs; in particular, $d(G_1 \cup G_2,H) = 9$ for the upper panel, whereas $d(G_1 \cup G_2,H) = 8$ for the lower panel.

But I do not understand their proof. For both cases (upper and lower panels), $d(G_1,H) = 16$, $d(G_2,H) = 7$, $d(G_1,G_2) = 5$.

I cannot see any reason that $\alpha(G_2)$ in the first case must equal $\alpha(G_2)$ in the second case. For instance, $G_2$ has not the same cardinal.

  • $\begingroup$ I also don't quite follow why $\alpha(G_2)$ can't be different... so I'm not sure if that make sense but if you would add another point in $G_2$ after the first one for the upper panel, the numbers wouldn't change but now $G_1$ and $G_2$ have the same cluster size and therefore $\alpha(G_2)$ must be the same in both cases!?! $\endgroup$ – oW_ Oct 4 '19 at 21:00
  • 1
    $\begingroup$ Indeed their argument seems to hinge on $\alpha$ being the same in both cases. Thenis that the left-hand side does change (from 9 to 8) but not the RHS. Did you check Lance-Williams article for the definition of $\alpha$ and its dependence on $G_2$? I'll try to see and come back. Your values, though, are correct. Assuming $\alpha$ doesn't chance those values show that Lance-Wallis relation doesn't hold for their example. $\endgroup$ – MASL Jan 3 at 18:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.