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 at 21:00

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.