2
$\begingroup$

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?

EDIT:

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?

$\endgroup$
12
  • $\begingroup$ Large data is many objects to cluster or many features (dimensionality)? $\endgroup$
    – ttnphns
    Jun 26, 2014 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, 2014 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, 2014 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, 2014 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, 2014 at 7:27

1 Answer 1

3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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