12

When it comes to compare a new clustering algorithm, one always wants to show the advantages of his/her method over existing and well known methods. Going this way may mislead one to ignore disadvantages proposed method.

For clustering results, usually people compare different methods over a set of datasets which readers can see the clusters with their own eyes, and get the differences between different methods results.

There are some metrics, like Homogeneity, Completeness, Adjusted Rand Index, Adjusted Mutual Information, and V-Measure. To compute these metrics, one needs to know the true labels of data-set, so we may test algorithms with classification data-sets to have true labels and then evaluate results.

Another metrics, like Silhouette Coefficient works only with data and clustering results.

I want to know what measures are most preferred and if there is any other metric which does not require true labels of data-set.

Stephan Kolassa
  • 95,027
  • 13
  • 197
  • 357
Mehraban
  • 535
  • 2
  • 7
  • 15
  • 1
    I think that the question raised is so broad... And perhaps you should make it more specific. One notion, however. Each clustering algorithm has its objective function, the goal; and it is how well it pursues its goal is the criterion. Goals are different because various definitions of what is cluster and what is density exist. – ttnphns Apr 30 '14 at 09:01
  • There are many existing questions on existing clustering metrics. Even Wikipedia "knows" plenty of such measures. There is a whole bunch of literature on this, after all. – Has QUIT--Anony-Mousse May 01 '14 at 11:10
  • @Anony-Mousse I've narrowed down the question. Is it still too broad? – Mehraban Jun 17 '14 at 12:09
  • Does not help much: ''preference'' is subjective. Everybody seems to use a different metric. And there are plenty of internal evaluation measures such as Dunn and davis-bouldin index (see wikipedia), AIC, BIC, Silhouette, CdBW, ... that do not require labels. **No measure is perfect.** Each relies on assumptions that may or may not hold for your data. – Has QUIT--Anony-Mousse Jun 17 '14 at 13:21

1 Answers1

7

It seems that you ask for internal validation measures (using only the data without reference to anything else) to compare different algorithms. This is fraught with perils. See e.g. the answer by Anony-Mousse here: https://stats.stackexchange.com/questions/88550/using-the-gap-statistic-to-compare-algorithm. My original answer (below) discusses external validation measures. It is still useful perhaps.

Here are two standard approaches (there may be more). The first is to use a gold standard and compute a distance or similarity between clusterings. Many people use the adjusted Rand index, but I think the Variance of Information distance (VI) or split/join distance are better suited for this. (See e.g. my answers here: Comparing clusterings: Rand Index vs Variation of Information and here: Forgiving measure for external cluster validation). This is still not straightforward -- a clustering can be consistent with a a gold standard (be a sub-clustering or super-clustering) and this has to be taken into account but often is not. I've seen a case where a very coarse classification was used (large classes), and the other clustering algorithms just produced more fine-grained result (subclusterings with respect to this coarse gold standard).

The second is to have some kind of annotation -- a classification associated with the nodes, where each node can have multiple labels. In biology this could be the GO (Gene Ontology) classification. It is then possible to compute an enrichment score (e.g. using the hypergeometric distribution) for each cluster (check which labels are overrepresented in the clustering). This is also not entirely straightforward (as collections of P-values have to be compared), but both approaches are definitely very informative if care is taken.

Community
  • 1
micans
  • 1,689
  • 8
  • 11
  • 1
    I may refer to my own answer [there](http://stats.stackexchange.com/a/88553/3277) which is not in consent with Anony-Mousse. It seem that the whole domain is dwelt by opinions, not one truth. "Gold standard" approach, too. Have you seen absolute, non-relative gold standards? – ttnphns Apr 30 '14 at 10:40
  • Well, with a gold standard there is the issue that the data might not be consistent with the gold standard, or that the gold standard has issues. I prefer pragmatic and open-minded approaches in clustering. Absolute statements are usually useless. I don't know exactly what an absolute gold standard is, but I don't think such a thing is needed. A good and useful annotation (such as Gene Ontology - it has issues but is definitely useful), *good data*, and the willingness to explore data rather than crowbar it, gets you a long way. – micans Apr 30 '14 at 11:14