7
$\begingroup$

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.

$\endgroup$

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.