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$
  • $\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 Dec 20 '16 at 19:09
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$
  • $\begingroup$ Oke, and the proof seems to be correct, right? $\endgroup$ – penguina Dec 21 '16 at 16:41

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.