11
$\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$
  • $\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
  • 2
    $\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
1
$\begingroup$

My take after a quick read of the references.

First of all, Lance and Williams's original paper mentions that their linear scheme works (and offers computational advantage) only for combinatorial strategies. Is minimax linkage such a combinatorial strategy? In other words, does it depend (linearly) on pair-wise distances? By the defintion of minimax distance it is clear that this is implausible.

It is like the difference between mean and median computation in statistics. Mean is linear while Median is non-linear. There is no linear combination that can compute median from mean (although in certain limited cases they can coincide).

Second, the authors do not mention the form (or values) of the $\alpha, \beta, \gamma$ parameters in a hypothetical Lance-Williams method for minimax linkage. But in any case they are constants and $\alpha(\cdot)$ can be constant or rational functions of the respective cluster sizes (per the original Lance-Williams reference).

$G_2$ might not be of the same cardinality in the two panels, but minimax linkage distance depends on radius of cluster not cardinality (unlike average or centroid linkage) and the two examples have same radius thus $\alpha(G_2)$ is same in both cases.

Another way to see that this is the case is a plausible variation of the proof where $G_2$ in both cases has both same radius and same cardinality but different configuration.

enter image description here

Maybe such a proof would make it more clear. But I will leave it at that, at this point.

| improve this answer | |
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.