1
$\begingroup$

I'm conjecturing that with Complete-linkage clustering two elements from the same cluster will always be closer to each other some other element from another cluster.

In more formal terms:

Let $C$ be a clustering. $\not\exists z \in C_j$ s.t. $\bigtriangleup(x, z) < \bigtriangleup(x, y)$ where $x,y \in C_i$, $C_i \neq C_j$ and $C_i, C_j \in C$.

I haven't been able to prove the conjecture yet, thus I'm wondering whether I'm right or wrong. If this is indeed the case, I would much appreciate a sketch a proof. I'm pretty sure I can work my way from there.

On a side note (not that I think it makes a difference), I'll be applying the clustering algorithm on a one-dimensinal dataset.

Your input is much appreciated.

$\endgroup$
1
  • $\begingroup$ Did you perhaps manage to prove your conjecture meanwhile? $\endgroup$
    – VividD
    May 11, 2017 at 12:09

2 Answers 2

1
$\begingroup$

Complete-linkage clustering tends to find compact clusters with equal diameters. It is define the inter-group distances as the largest distance of objects between two clusters. Beside, it is may produce clusters that has the same number of objects and the distance between objects is contiguous. maximum distance of objects in two clusters

So, I can say that your conjecture is correct. I cannot wait for any experts to explain this in detail.

$\endgroup$
1
$\begingroup$

I may have missed something in the definition in Wikipedia, but wouldn't the set {1,2,4,5,7,8} with $\Delta(x,y) = |x-y|$ be a counterexample? After the 4th step there are two clusters, {{1,2}, {4,5}}, {7,8} and x=5, y=1, z=7 seems to violate your claim.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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