Average-linkage clustering ($d(A,B)=\frac{1}{|A||B|}{\sum }_{x\in A,y\in B}d(x,y)$)

Average linkage merges the pair with the smallest mean cross-pair dissimilarity. This differs from the minimum used by single-linkage clustering and the maximum used by complete-linkage clustering. The convention here weights individual cross-pairs equally; weighting already formed clusters equally is a different algorithm.