# Hierarchical clustering using Average Linkage

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: Sorry about the quality of the picture. Is it correct?

• 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. – ttnphns Dec 20 '16 at 19:09

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)


• Oke, and the proof seems to be correct, right? – penguina Dec 21 '16 at 16:41