9
$\begingroup$

My wish is to describe the time complexity of several clustering approaches. For example, suppose we have $n$ data points in $m$ dimensional space.

Suppose further that the pairwise dissimilarity matrix $\Delta$ of $n\times n$ dimensions is already computed and that we have already spent $O(m\cdot n^2)$ steps. What is then the time complexity just of

  • hierarchical clustering (HC) using Ward's linkage
  • HC using complete linkage
  • HC using average linkage
  • HC using single linkage
  • $k$-medoid approach
  • $k$-means approach

Is there any benefit if the dissimilarity matrix $\Delta$ is not already computed? As I understand it is necessary for HC and $k$-medoid approach but not for $k$--means?

Thank you for your help!

Improve this question
$\endgroup$
2
  • $\begingroup$ This is a CS question, not a question about statistical analysis. It would be perfectly suitable for the SE site on algorithms currently in the proposal stage at area51.stackexchange.com/proposals/5120/… . $\endgroup$
    – whuber
    Jan 12, 2011 at 16:07
  • $\begingroup$ You can also transform the distance matrix into an edge-weighted graph and apply graph clustering methods (e.g. van Dongen's Markov CLustering algorithm or my Restricted Neighbourhood Search Clustering algorithm), but this is more of an OR question than a straightforward algorithms question (not to mention that graph clustering algorithms are generally unsuitable for dense graphs, which kind of defeats the purpose of turning the distance matrix into a graph) $\endgroup$
    – Andrew D. King
    Jan 12, 2011 at 17:31

2 Answers 2

Reset to default
7
$\begingroup$

Single linkage clustering is almost the same as minimum spanning trees in complete graphs, easy O(n^2) time. For O(n^2) time for other agglomerative clustering methods (including I'm pretty sure average and complete linkage) see my paper "Fast hierarchical clustering and other applications of dynamic closest pairs", SODA '98 and JEA '00.

Improve this answer
$\endgroup$
6
$\begingroup$

You have to be careful with some of the methods. Specifically, k-means and k-medoids are iterative schemes that you run "till you're done". SO it's not meaningful to talk about the overall running time of these schemes, but it is meaningful to talk about the running time of a single iteration. For $k$-means, it's easy: each iteration takes $O(kn)$ time to identify the nearest centers and do the new center computation. For $k$-medoids, the new-center computation can take longer: that depends on what procedure you use, and if $k$ is small, the computation of new-centers can dominate the asymptotics.

Update: As JeffE points out below in comments, there are certain variants of $k$-means that do have guaranteed convergence in polynomial time, while also yielding quality answers. There's nothing that I'm aware of for $k$-medoids though.

Improve this answer
$\endgroup$
2
  • 3
    $\begingroup$ Why is it "not meaningful"? There are several recent papers on the number of iterations until k-means converges (meaning an iteration leaves the clustering unchanged), or until it reaches some desired approximation ratio. $\endgroup$
    – Jeffε
    Jan 12, 2011 at 17:45
  • $\begingroup$ but they assume either some property of the data, or some specific variant of the algorithm (like the k-means++ method, or the smoothed variant). The question as I read it seemed to refer more to generic variants. Your point is well taken though. $\endgroup$
    – Suresh Venkat
    Jan 12, 2011 at 18:36

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.