Average Linkage Agglomerative Clustering

Single Link

$$d(\{A,B\}, C) = min(d(A,C), d(B,C))$$

Complete Link

$$d(\{A,B\}, C) = max(d(A,C), d(B,C))$$

Average link

$$d(\{A,B\}, C) = average(d(A,C), d(B,C))$$

Centroid link

$$d(\{A,B\}, C) = d(\mu_{AB},C)$$

Ward link

$$d(A, B) = \sqrt{2 * \frac{n_A * n_B}{n_A + n_B}||\mu_{A}-\mu_{B}||^2}$$

Example 1

	x₁	x₂
A	1	2
B	2	3
C	5	8
D	8	8
E	1	0
F	0	1

Distance

d(x₁, x₂)	A	B	C	D	E	F
A	0
B	1.41	0
C	7.21	5.83	0
D	9.22	7.81	3.00	0
E	2.00	3.16	8.94	10.63	0
F	1.41	2.83	8.60	10.63	1.41	0

Example 2

	x₁	x₂
A	1	2
B	2	3
C	5	8
D	8	8
E	1	0
F	0	2

Distance

d(x₁, x₂)	A	B	C	D	E	F
A	0
B	1.41	0
C	7.21	5.83	0
D	9.22	7.81	3.00	0
E	2.00	3.16	8.94	10.63	0
F	1.00	2.24	7.81	10.00	2.24	0

Example 3

	x₁	x₂
A	0	5
B	1	4
C	5	8
D	9	2
E	2	0
F	5	8
G	7	7

	A	B	C	D	E	F	G
A	0
B	1.41	0
C	5.83	5.66	0
D	9.49	8.25	7.21	0
E	5.39	4.12	8.54	7.28	0
F	8.00	7.07	4.24	3.16	7.81	0
G	7.28	6.71	2.24	5.39	8.60	2.24	0

Example 4

A	1	1
B	2	2
C	2	1
D	6	5
E	7	5
F	8	6

Code

from scipy.cluster.hierarchy import dendrogram, linkage
import matplotlib.pyplot as plt
data = [
    [1, 2],
    [2, 3],
    [5, 8],
    [8, 8],
    [1, 0],
    [0, 2]
]
Z = linkage(data, method='centroid')
dendrogram(Z, labels=['A', 'B', 'C', 'D', 'E', 'F'])
plt.show()