0
$\begingroup$

Suppose we have the points $2^0$,$2^1$, ...,$2^n$ on $x$-axis. If we are using Euclidian distance, draw a sketch of the hierarchical clustering tree we would obtain for the average linkage method.

What I've done:

Let $1 < k < n$ and $C_K$ be the $k$-th cluster obtained in hierarchy. We define the following distances:

$d'=d(C_{k-1},2^k) = \frac{\sum_{i=0}^{k-1} (2^k - 2^i)}{k}$ si

$d''=d(2^k,2^{k+1}) = 2^k$

$d'=\frac{k2^k-\sum_{i=0}^{k-1}2^i}{k}=\frac{k2^k-(2^k-1)}{k}=\frac{(k-1)2^k+1}{k}$

$d'=\frac{(k-1)2^k+1}{k}=\frac{k2^k+1-2^k}{k}<\frac{k2^k}{k}=d''$, $1 < k < n$

Then, the dendrogram will be something like this:dendrogram Sorry about the quality of the picture. Is it correct?

$\endgroup$
1
  • $\begingroup$ I've added self study tag. Did you try to a small real data snippet? - compute it as you show and draw a tree. Then give the data to a cluster analysis program and get the tree; compare. $\endgroup$
    – ttnphns
    Commented Dec 20, 2016 at 19:09

1 Answer 1

0
$\begingroup$

Yes. A simple confirmation is just to implement it. Here is an implementation in R

Tree = hclust(DistMatrix, method="average")
plot(Tree)
plot(Tree, hang=-1)
n = 8
Points = 2^(1:n)
Points
[1]   2   4   8  16  32  64 128 256

DistMatrix = dist(Points)
Tree = hclust(DistMatrix, method="average")
plot(Tree, hang=-1)

Dendrogram

$\endgroup$
1
  • $\begingroup$ Oke, and the proof seems to be correct, right? $\endgroup$
    – penguina
    Commented Dec 21, 2016 at 16:41

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.