0
$\begingroup$

I'm trying to find out if these algorithm still work if i replace the Euclidean space with metric space defined on the input point set. But i'm having some trouble figuring it out for some of them. I have:

  1. k-means clustering using Lloyd algorithm, with random initialization
  2. DBSCAN using the graph-approach
  3. DBSCAN using the Box-Graph
  4. Single-link agglomerative clustering

I think only DBSCAN using the Box-Graph still works if we replace it with metric space, but I'm not quite sure if that's correct, what assumptions are made do no longer hold for the other algorithms?

Improve this question
$\endgroup$
3
  • $\begingroup$ $k$-means algorithm will not work directly in the metric spaces because you need to find the centroid of a set of points. In general metric spaces, there is no concept of the centroid. See here for more discussion. $\endgroup$
    – Inuyasha Yagami
    Commented Jun 16, 2021 at 16:36
  • $\begingroup$ However, you can use $k$-means++ algorithm in general metric spaces. It is as good as the $k$-means algorithm. $\endgroup$
    – Inuyasha Yagami
    Commented Jun 16, 2021 at 16:37
  • 1
    $\begingroup$ This is a nice exercise. If you understand each of those algorithms, it should be a mechanical process to work through each line of pseudocode to verify whether it can be done in an arbitrary metric space. That seems like something you should be able to do yourself. What progress have you made and is there any specific uncertainty you've run into as you do that analysis? $\endgroup$
    – D.W. ♦
    Commented Jun 16, 2021 at 18:53

0

Reset to default

Your Answer

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

Browse other questions tagged or ask your own question.