Clustering evaluation metrics with subquadratic time complexity

Question

It exists many evaluation metrics but often they are quadratic or more on number of data points preventing any application on massive data sets as RAND or Silhouette indexes.

For the moment i used :

External metrics

• Normalized Mutual Information, NMI

Internal metrics

• Davies Bouldin, which is in $O(n.c^2)$ with $c$ the number of clusters

I implemented both under Spark framework in Scala here for those who are interested but i would be happy to know if others exists, especially concerning internal metrics because even if Davies Bouldin could be a good evaluation metric, it is in my opinion, only with elliptic clusters.

Answer 1

Rand index is not more expensive than NMI, it's O(n) when implemented correctly.

There are like 40 internal evaluation indexes. I am fairly certain there are several that are not quadratic in runtime. Just go through the list, and document your findings for the next one with the same question.

Spark sucks for clustering. It can do k-means and GMM but both are very slow compared to other tools. They don't scale. The attempts at implementing DBSCAN for Spark are even worse. They were found to return incorrect results to crash, and to scale worse than single-core implementations such as ELKI (not to speak of parallel HPC implementations):

Helmut Neukirchen. Survey and Performance Evaluation of DBSCAN Spatial Clustering Implementations for Big Data and High-Performance Computing Paradigms

It's just not what Spark is good at. And given all the "extensions" for it - that often have a very low quality - you quickly run into problems and don't know who is to blame and where to fix them.

Make sure to benchmark.