How to inform the space and time complexity of K-means, SOM and Hierachical clustering

Question

In the paper I am writing, one of the reviewers asked for an

"a simple computational complexity analysis or time computational demands of their method"

My question is : Can I simply report the space and time complexities I found in the references bellow ?

Kmeans: space-> $O((n+M))$,  time-> $O(Mn)$ 
SOM: space->$O(M^2)$, time-> $O(Mn)$
hierarchical clustering: space->$O(n^2)$, time-> $O(n^2logn)$

where $M$ is the number of neurons(clusters), $n$ the number of data points.

OR or should I try to explain more? When I started to look for the space and time complexity of the three algorithms: kmeans, SOM, and hierarchical clustering, I found the two references bellow:

In the book :Challenging Problems and Solutions in Intelligent Systems, they state that the memory (space) complexity can be estimated by $O(M^2)$ and the time complexity can be estimated as $O(Mn)$, where $M$ is the number of neurons and  $n$ the number of data points.
However in the SOM training the dataset is presented for several epochs, so should the time complexity be  $O(MnId)$, where $I$ is the number of epochs (iteractions) and $d$ the dimension? Also, the space complexity should be $O((M+n)d)$?

This would be similar to what I found in this paper A Survey on Clustering Algorithms and Complexity Analysis for Kmeans. In Kmeans, the spacecomplexity is $O((n+M)d)$,  and the time complexity is  $O(MnId)$ . Should I keep the $I$ ( number of interactions) and draw the $d$ dimension since it would be include in all cases?

Tom Anderson · Answer

Are you looking for time estimates are for training or for testing? Time complexity $O(Mn)$ would simply appear to be a lookup operation for each of the $n$ elements, i.e. no updating of the neighbors. In that case, why $O(M^2)$ for storage? Wouldn't there just be a single codebook value for each element in the map?

In my experience there are many different estimates for SOM training. If you are doing the in-depth calculations for each portion of the algorithm, I think I agree with the following (for training SOM via the batch algorithm):

“… in BSOM-t the computation of the neighborhood terms needs $O(m^2)$
  operations, the assignment step runs in time $O(nmd) + O(nm^2)$ and the
  recalculation of the weight vectors runs in time $O(nd) + O(m^2d)$.
  Therefore, the complexity of BSOM is $O(m^2) + O(nmd) + O(nm2) + O(m^2d)$,
  and that of BSOM-t is $Niter · (O(m^2) + O(nmd) + O(nm^2) + O(m^2d)$.” Le
  Thi, H. A., & Nguyen, M. C. (2014, p.1353). Self-organizing maps by
  difference of convex functions optimization. Data Mining and Knowledge
  Discovery, 28(5–6), 1336–1365.
  http://doi.org/10.1007/s10618-014-0369-7

Here, BSOM is batch SOM, BSOM-t is training using BSOM for a number of iterations, m is the number of nodes in the map, n is the number of observations in the training data, d is the number of distances and is related to the size of the neighbourhood.

Note that this is assuming sequential. If the map was parallelized using GPU, it could be a different story.

How to inform the space and time complexity of K-means, SOM and Hierachical clustering

One Answer

Add your own answers!

Ask a Question