1
$\begingroup$

So there are lots of clustering algorithms with different characteristics. What I am interested in now is a clustering algorithm which guarantees to find the optimal clustering result (if exists). And consequently, the algorithm would be deterministic.

E.g. DBSCAN is deterministic but is it guaranteed to find the optimal clustering solution? For k-means, this doesn't apply since it is non-deterministic and it can get stuck in local minima.

  1. So is there a clustering algorithm which guarantees to find the optimal solution?
  2. And are clustering algorithms classified by their "Finding optimal solution" characteristic? If a clustering algorithm X is deterministic, does it mean that it finds the best clustering that exists? Thanks!
Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ What do you mean by "the optimal solution"? Different methods imply different concepts of what a good clustering is, so they will find different solutions, which often all have their own merits. There is no such thing as a general definition of what an "optimal clustering" means. You may want to read this: arxiv.org/abs/1503.02059 $\endgroup$
    – Christian Hennig
    Commented Apr 28, 2021 at 9:54
  • 1
    $\begingroup$ To find the global optimum of a given objective function (such as the k-means one) is a different issue, see your other question. But for clustering in general there is no generally accepted best objective function. $\endgroup$
    – Christian Hennig
    Commented Apr 28, 2021 at 10:02
  • $\begingroup$ Thank you for your clear answers @Lewian $\endgroup$
    – Erik
    Commented Apr 28, 2021 at 11:07

1 Answer 1

Reset to default
1
$\begingroup$

There is no general efficient algorithm that gives you globally optimal solution given a general optimisation problem (even narrowed down to clustering, but that is an optimisation problem as well), as also mentioned in the comments.

Improve this answer
$\endgroup$

Your Answer

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

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