I'm going over the Agglomerative Clustering algorithm in sklearn.cluster.AgglomerativeClustering
. It supports four linkage methods:
- Ward minimizes the sum of squared differences within all clusters. It is a variance-minimizing approach and in this sense is similar to the k-means objective function but tackled with an agglomerative hierarchical approach.
- Maximum or complete linkage minimizes the maximum distance between observations of pairs of clusters.
- Average linkage minimizes the average of the distances between all observations of pairs of clusters.
- Single linkage minimizes the distance between the closest observations of pairs of clusters.
As far as I understand these four methods seem to be deterministic, i.e., there is no need to run either of them over many iterations to "converge" to a stable solution.
But Wikipedia's Hierarchical clustering article states that:
Except for the special case of single-linkage, none of the algorithms (except exhaustive search in $O(2^{n}))$ can be guaranteed to find the optimum solution.
This confuses me. Does this mean that there is a stochastic process involved in either of these methods?