1
$\begingroup$

I had someone ask me about k-medoids at work and don't know about the performance of this algorithm over other clustering algorithms (namely k-means as it is most similar to it). In this case, it was recommended for use on taxonomic data (ie bacterial/viral species/strains), but I do not know why this is better.

time complexity of k medoids is $O(k * (n-k)^2)$.

  1. is time complexity of a comparable k-means algorithm the same?
  2. When would you use one or the other?
  3. What qualities does one look for to use k-medoids?
  4. What are the differences in the output?
Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ k-means relies, as its name implies, on computing the mean of multiple data points. Therefore, you should not use it when averaging different datapoints does not make sense. An example of such a scenario is time series. $\endgroup$
    – noe
    Commented Apr 3, 2020 at 17:56

1 Answer 1

Reset to default
2
$\begingroup$

1) Time complexity of KMEANS

As explained in this post :

KMeans is an NP-hard problem. However, running a fixed number $t$ of iterations of the standard algorithm takes only $O(t*k*n*d)$, for $n$ (d-dimensional) points, where $k$ is the number of centroids (or clusters). This what practical implementations do (often with random restarts between the iterations).

2) When would you use one over the other?

As mentioned in this Wikipedia article, K-medoids is less sensitive to outliers and noise because of the function it minimizes.

It is more robust to noise and outliers as compared to k-means because it minimizes a sum of pairwise dissimilarities instead of a sum of squared Euclidean distances.

Also, K-medoids can use a variety of similarity measures where K-means is limited to euclidian (pairwise) distance. Excellent explanation [here].(https://stats.stackexchange.com/a/81496/279276)

3) What qualities does one look for to use k-medoids?

I would recommend using it whenever Euclidean Distance does not make sense in your data. If Euclidean Distance does not make sense (i.e. unrelated categorical variables : "has wings", "# of legs"), minimizing the sum of squared Euclidian distances probably won't either.

4) What are the differences in the output

The main difference is that medoids (equivalent to centroïds in K-Means) belong to the data points. You will never have a medoid that is somewhere between points. Instead, it will be superimposed on an existing point. This post shows it clearly.

It makes sense, especially for a categorical feature (# of legs), not to have a cluster center at 3.347 legs.

Hope this helps.

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.