I have instances for which the only thing I know is $70\%$ of the distance matrix.

I know some of these points form groups of correlated points (each point of a group is "close" to every point of the same group). I want to find these clusters of "close" points.

I chose a distance threshold. Each pair of points closer than this distance is linked by an edge. I get then a graph to which I apply a graph clustering algorithm. In order to select the 'best' parameters, I want to choose a quality metric. My objective is to regroup the points that form very interconnected groups.

I first tried to compare the silhouettes of the clusters for different parameters, but I feel uncomfortable that $30\%$ of the pairwise distances are ignored, and I am not sure this metric is appropriate with respect to my objective. Anyone has a more appropriate measure?


1 Answer 1


I'd disregard the 30% of the affinity matrix you don't know. I'd try to maximize my success rate on the 70% that I do know.

If I understood correctly, the question boils down to: how to evaluate clustering algorithms?

If you have access to the ground truth (i.e. the cluster to which each data point belongs to), there are several ways: entropy and purity are the most widely used - you can find a very good explanation of both in this website. However, the best one is clustering error, which some call maximum matching. You can see a very good example in this video.

If you don't have access to the ground truth, all you can rely on are intrinsic metrics. Basically, a good clustering results in small intra-cluster variance (all data points in a cluster are close to each other) and large inter-cluster variance (all cluster centroids are far apart from each other). You can see more details in this paper.


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.