I have made a new algorithm that is specifically crafted for clustering very large datasets. In order to document it as a research paper, I have to choose one or two internal (no-label) cluster evaluation measures to evaluate my algorithm. Which algorithm do you think is generally the best choice for big datasets? And why?


My algorithm is a modified version of Expectation-Maximization Gaussian mixture models. In other words, the whole data is described by

$$P_(x) = \sum_{k=1}^{K}\pi(c_k)\mathcal{N}(\mu_k,\Sigma_k)$$

where $\pi(c_1),\ldots,\pi(c_K)$ are mixture weights. The main difference between my algorithm and regular EM is that it uses some sampling and approximation tricks that accelerate EM. The objective function is the same (the log-likelihood which is to be maximized).

Should I use log-likelihood as the evaluation metric? or use other (which?) internal measures for such task? Is it rational?

  • $\begingroup$ Large data is many objects to cluster or many features (dimensionality)? $\endgroup$ – ttnphns Jun 26 '14 at 6:59
  • $\begingroup$ @ttnphns In my settings, I mean many instances, but average dimensionality. E.g. 100M instances, 100 clusters, 200 feautres, that is ~100GB of data! $\endgroup$ – Ali Jun 26 '14 at 7:04
  • $\begingroup$ You see, any clustering algorithm is "inclined" to produce clusters of a specific shape or clusters having a specific type of density. So, one of the "validation metrics" should be theoretically close to your algorithm. Still, some other metrics should be different, - for you to show that your algo is robust enough to data and can cope with clusters other algos can cope with. $\endgroup$ – ttnphns Jun 26 '14 at 7:15
  • $\begingroup$ So, nobody can recommend you any concrete until you describe your algorithm (with example). This site may be a good place to do it! $\endgroup$ – ttnphns Jun 26 '14 at 7:17
  • $\begingroup$ @ttnphns Yep, exactly! For example, k-means is inclined to make spherical clusters, therefore it is usually evaluated using sum-of-squared error (SSE) which also assumes the clusters to be spherical (i.e. clusters having the same variance and no correlation between features). My question is actually whether there exits an evaluation measure for ellipsoidal clusters? (having different variances for each dimension, or even having a full co-variance matrix?) $\endgroup$ – Ali Jun 26 '14 at 7:27

No measure will work well for big data.

Every measure is an aggregation, say an average.

By adding more data, this aggregation will only change at the very last digit(s).

In most cases, a sample will already yield a result of the same quality; by the law of large numbers.

But on the other hand, you'll quickly run into the situation where your numerical precision is an issue. Unless you have a very good implementation, chances are that numerical issues with your "big data" implementation will actually make the result worse than one on a sample, where these effects did not yet occur.

For EM type of algorithms, starting values will likely have much more influence than different algorithms. Same for k-means: adding more data doesn't really improve results. Because the algorithm only computes a rough aggregation of your data; and aggregating more data doesn't change the outcome a lot anymore.


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.