1
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ Does this answer your question? Can sub-optimality of various hierarchical clustering methods be assessed or ranked? $\endgroup$
    – ttnphns
    Apr 24, 2020 at 16:09
  • $\begingroup$ Agglomerative Hierarchical clustering is a greedy algorithm. Only with single linkage it guarantees reaching "global optimum" in its goal. $\endgroup$
    – ttnphns
    Apr 24, 2020 at 16:11
  • $\begingroup$ @ttnphns my question was more aimed at the presence of randomness within these methods, rather than then optimization to global or local results. It's a very interesting question nonetheless, thank you! $\endgroup$
    – Gabriel
    Apr 24, 2020 at 20:37

1 Answer 1

Reset to default
1
$\begingroup$

Even deterministic optimization algorithms are often only approximate. (And clustering algorithms are optimization algorithms, since they try to minimize or maximize some objective function, typically a measure of impurity.)

In some cases, no algorithms are known that are guaranteed to reach an optimal solution in feasible time for large instances, so we are forced to use approximations. When we are lucky, we at least have guarantees on the approximation error.

So: no, being nonstochastic is not a sufficient condition for an algorithm to always yield an optimal result.

Improve this answer
$\endgroup$
2
  • $\begingroup$ So, if I'm understanding correctly although these methods are nonstochastic they will still converge to different solutions for multiple runs due to being approximate? Is this correct? $\endgroup$
    – Gabriel
    Apr 24, 2020 at 16:43
  • 2
    $\begingroup$ No, given the same starting point, they will always converge to the same optimum if they are nonstochastic. It's just that this optimum may only be a local one, not a global one. It's often a good idea to run optimization algorithms, whether stochastic or not, multiple times with different starting values. $\endgroup$
    – Stephan Kolassa
    Apr 25, 2020 at 7:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.