(Agglomerative) Hierarchical Clustering: Which linkage for the detection of outliers?

Question

In (agglomerative) hierarchical clustering (and clustering in general), linkages are measures of "closeness" between pairs of clusters.

The single linkage $\mathcal{L}_{1,2}^{\min}$ is the smallest value over all $\Delta(X_1, X_2)$.

The complete linkage $\mathcal{L}_{1,2}^{\max}$ is the largest value over all $\Delta(X_1, X_2)$.

The average linkage $\mathcal{L}_{1,2}^{\text{mean}}$ is the average over all distances $\Delta(X_1, X_2)$.

The centroid linkage $\mathcal{L}_{1,2}^{\text{cent}}$ is the Euclidean distance between the cluster means of the two clusters.

We can clearly see the outliers as "singletons" in a dendrogram:

(From https://www.statisticshowto.com/hierarchical-clustering/)

Which of these linkages is best for the detection of outliers?

Answer 1

Let's say an object is a singleton at high level in complete linkage, and say that there are otherwise bigger clusters. This means only that the maximum distances between the object and the other clusters are large; the singleton object can still be close to quite a number of objects of the clusters, and is therefore not necessarily an outlier.

A high level singleton of single linkage is separated from all clusters, its minimum distance to all clusters is large, so its distance to all other objects is large. In this sense it is well qualified to be called outlier. The only issue is that some people would say that there could also be small groups of outliers, which will not normally show up as singletons in any algorithm, but in single linkage an object may not be singleton anymore if it is close to one single other object.

Average linkage is a compromise between these two; it can have the problem that complete linkage has potentially missing outliers, but it is less likely. I don't have much experience with the centroid method, but I'd expect it to behave similarly to average linkage in this respect.

So single linkage is probably most suitable, at least if an outlier in your definition is an object that is far away from all the others.

Answer 2

Upon trying to work with Lewian's answer above, I found it to be lacking in clarity, so I've attempted to use his answer to write my own version below.

A linkage is a measure of closeness between pairs of clusters. It depends on the distance between the observations in the clusters.

Let's assume that an outlier is defined as an object that is "far" from all the others.

In the case of a complete linkage, we are using the largest value of the distance function over the observations of the two clusters. Therefore, if the other cluster is large (with observations spread), then there might be some observations that are much closer than the observations used for the maximum distance calculation; however, they would not be taken into account when using the complete linkage. Therefore, the singleton would not necessarily be an outlier.

In the case of a single linkage, we are using the smallest value of the distance function over the observations of the two clusters. Therefore, a singleton's minimum distance to all clusters is comparatively (to the complete linkage) large, so its distance to all other observations is comparatively (to the complete linkage) large. Therefore, if even by using the smallest value we find that some observations are classified as singletons, then chances are that they actually are indeed outliers.

The average linkage and the centroid linkage seem to be between the two extremes of the complete linkage and the single linkage. Therefore, I would say that the single linkage is most suitable for detecting outliers.