How many types of Linkage in clustering?

vishrut-singhal · 13 May 2021 12:57

The process of Hierarchical Clustering involves either clustering sub-clusters(data points in the first iteration) into larger clusters in a bottom-up manner or dividing a larger cluster into smaller sub-clusters in a top-down manner. During both the types of hierarchical clustering, the distance between two sub-clusters needs to be computed. The different types of linkages describe the different approaches to measure the distance between two sub-clusters of data points. The different types of linkages are:-

Single Linkage: For two clusters R and S, the single linkage returns the minimum distance between two points i and j such that i belongs to R and j belongs to S.

$L(R, S) = min(D(i, j)), i\epsilon R, j\epsilon S$

Complete Linkage: For two clusters R and S, the single linkage returns the maximum distance between two points i and j such that i belongs to R and j belongs to S.

$L(R, S) = max(D(i, j)), i\epsilon R, j\epsilon S$

Average Linkage: For two clusters R and S, first for the distance between any data-point i in R and any data-point j in S and then the arithmetic mean of these distances are calculated. Average Linkage returns this value of the arithmetic mean.

$L(R, S) = \frac{1}{n_{R}+n_{S}}\sum {i=1}^{n{R}}\sum {j=1}^{n{S}} D(i, j), i\epsilon R, j\epsilon S$

where

$n_{R}$ – Number of data-points in R

$n_{S}$ – Number of data-points in S