I have written k means clustering code in c#. I am clustering random 99 text articles of Sports Area which I downloaded from Github for different values of K i.e.3,4,5,6,7. I want to analyze the time period taken for K means Clustering

Following is the time taken for different values of K

K = 3     Time taken = 2 and half hour
K = 4     Time taken = 3 hour 30 minute
K = 5     Time taken = 3 hour 50 minute
K = 6     Time taken = 3 hour 32 minute
K = 7     Time taken = 3 hour 35 minute

As you can see that time taken increases from K= 3 to K =5 and then decreases for K=6 and increases again for K = 7.

My question : Is this result valid? As the value of K increases shouldn't time taken by K means algorithm also increase? Suggestions needed

  • 1
    $\begingroup$ Did you check also the number of iterations taken before convergence in each case? $\endgroup$
    – Giuseppe
    Nov 24 '18 at 13:07
  • 1
    $\begingroup$ It (the number of iterations needed to converge to a given threshold) is data-dependent and not clearly related to k. Moreover, if k is very large so it approaches the number of objects, less time will be needed. $\endgroup$
    – ttnphns
    Nov 24 '18 at 16:09

It seems you have only performed one run per k. As K-Means clustering is very sensitive to initialization and often does not produce the same result twice, I consider your sample too small to judge the influence of k on the runtime of k-means.

Further, as Giuseppe points out, the number of iterations are most certainly not equal across your 5 runs.

Finally, as ttnphns points out, the number of iterations - thus the time needed - is data-dependent.

Your result therefore seems valid. The runtime of your algorithm depends on multiple factors (data properties, initialization) and therefore does not neccesarily increase proportionally with k.

Have a look at Run time analysis of the clustering algorithm (k-means) for further information and material on the topic.

  • $\begingroup$ The no of iterations were different for each value of K...I did not note them but I remember it being different..... $\endgroup$ Nov 25 '18 at 10:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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