11
$\begingroup$

I don't have industry experience in data mining or big data so would love to hear you sharing some experience.

Do people actually run k-means, PAM, CLARA, etc. on a really big dataset? Or they just randomly pick out a sample from it? If they just take a sample of the dataset, would the result be reliable if the dataset is not normally distributed?

In practical situations when running these algorithms, can we tell how many iterations would it normally take until convergence occurs? Or the number of iterations always grow with the data size?

I'm asking this because I'm thinking of developing an approach to terminate the iterative algorithms before the convergence, and yet the results are still acceptable. I think it worths trying if the number of iterations are, say more than 1,000, so we can save some computational cost and time. What do you think?

Improve this question
$\endgroup$
4
  • $\begingroup$ number of iterations always grow with the data size Not necessarily. $\endgroup$
    – ttnphns
    Feb 14, 2017 at 11:29
  • $\begingroup$ There exist various criteria to stop iterations in K-means. Interestingly, simply to set the number of iterations to a fixed value (say, 10 or 20) is among reasonable ways. K-means is dedicated to be a fast method, therefore if you want a convergence criterion to be checked after every iteration that criterion must be easy/fast to compute. $\endgroup$
    – ttnphns
    Feb 14, 2017 at 11:35
  • 1
    $\begingroup$ Is there any "scientific" way to determine the maximum number of iterations to be executed? $\endgroup$
    – foo
    Feb 14, 2017 at 11:43
  • $\begingroup$ Your last comment is a good question. Honestly, I don't know. maybe other people answer it. $\endgroup$
    – ttnphns
    Feb 14, 2017 at 11:45

1 Answer 1

Reset to default
7
$\begingroup$

  1. K-means is cheap. You can afford to run it for many iterations.

  2. There are bad algorithms (the standard one) and good algorithms. For good algorithms, later iterations cost often much less than 1% of the first iteration.

  3. There are really slow implementations. Don't use them.

  4. K-means on "big" data does not exist. Because it only works on low dimensional vector data. You won't exceed the memory of a modern server with such data. yes, larger data exists - but you can't use k-means on say a month of Twitter data, because it won't give you anything useful.

With a good implementation, on a modern server, the largest dataset you can find where k-means still gives a useful result probably needs less than 1 minute to compute until convergence. So why bother thinking about a iteration limit?

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Agree. In this paper (Scalable K-Means by ranked retrieval), the authors stated that K-means converges after 20-50 iterations in all practical situations, even on high dimensional datasets as they tested. So apart from K-means, do you know any algorithm that takes a huge number of iterations until convergence? $\endgroup$
    – foo
    Feb 15, 2017 at 1:10
  • $\begingroup$ Maybe training a SVM? I believe it is iterative, trying to find the best (and smallest, since prediction depends on this!) set of support vectors. $\endgroup$
    – Has QUIT--Anony-Mousse
    Feb 15, 2017 at 8:31
  • $\begingroup$ The obvious solution to running k-means on high dimension datasets is to run PCA or other dimensionality reduction method first, then run k-means $\endgroup$
    – nico
    Mar 18, 2020 at 15:47

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.