How to measure cluster quality with distance matrix?

When performing clustering with an algorithm such as K-means, it's possible to construct a plot that shows the intra cluster variability according to the number of clusters to see if there is an elbow that suggest an optimal number of clusters.

However, when working with a dissimilarity matrix (with all values in the range 0-1), it's not so obvious how to measure the quality of clusters obtained. Suppose I had a dataset with a mixture of numerical, categorical and ordinal variables, so I couldn't calculate the loss function with which K-means works, for example.

In this case, I can run K-medoids or hierarchical clustering, but how can I produce some metric that could suggest the number of clusters, analog to the inter/intra variability of algorithms that work with only numeric data?

• Regarding your recent (deleted) question about clustering algorithms that can use a distance matrix, & this one, you might be interested in my answer here: How to use both binary and continuous variables together in clustering? There, I demonstrate some ways of trying to determine the number of clusters. Aug 10 '15 at 16:34
• when working with a dissimilarity matrix... it's not so obvious how to measure the quality of clusters obtained I would not concur. Generally, it makes no difference how was the input. Many clustering criterions can be computed for either type of input. Search internet (starting with reading wikipedia article "Clustering") and this site for "clustering criterions", "cluster validity indices", "best number of clusters". Aug 10 '15 at 17:22
• There is a graph clustering metric called 'modularity'. It is used to find the optimal community structure of a graph, i.e. the number of clusters in the dataset represented by that graph. You can empirically set a threshold to your dissimilarity matrix in order to convert it to the adjacency matrix of a weighted graph and then use graph metrics to get what you want... Does that make sense? Aug 10 '15 at 18:39
• @Digio, why not write that up as an answer. It might be an interesting contribution. There seem to be a couple of posts about modularity in graph clustering, but none seem to start from non-graph data & circle through that route as a way to estimate the number of clusters. Aug 10 '15 at 19:09
• @ttnphns, you have a bunch of good answers about clustering already. Are there any you might recommend the OP to read, in regards to this question? Aug 10 '15 at 19:17

If you read the section on internal cluster validation in Wikipedia, you will learn about a dozen measures for evaluation that require paiwise distances. E.g.

• Silhouette index
• Dunn's index
• Davids-Bouldin

and many more.

On the other hand, none of them has me really convinced yet.

• Well I thought the same - I mean they all look at different criteria that might not necessarily correspond each other. I guess a mixture of different metrics would be the ideal. Graph-based modularity also seems promising, although it would require finding yet another parameter. Aug 11 '15 at 17:44

I would suggest you to model your data as a graph and then use graph clustering algorithms and metrics to get what you want. A normalised (dis)similarity matrix is equivalent to the adjacency matrix of a complete, weighted, undirected graph. If you empirically set a threshold to that matrix (below which all values will become zero) you can also add a structure to that graph. For a given partition of the graph, the modularity metric will quantify the total strength of its clusters, therefore by maximising that metric you can get the optimal community structure (data clustering). An exact solution to modularity optimisation is a NP-hard problem but there are many (meta)heuristic packages that do the task. Once you've clustered your graph you can isolate clusters into subgraph and quantify their individual strength using graph metrics such as weighted degree centrality.

Unfortunately there is no package (that I know of) that can automate the adjacency matrix creation since finding the optimal threshold is a manual process. However, once you have that matrix, R and Mathematica have great packages to do the rest.

You can produce the metric using e.g. the cluster.stats function of fpc R package, and have a look at the metrics it offers.

The function computes several cluster quality statistics based on the distance matrix put as the function argument, e.g. silhouette width, G2 index (Baker & Hubert 1975), G3 index (Hubert & Levine 1976).

Example use case:

library(fpc)
data(data_ratio)
d <- dist.GDM(data_ratio)
p <- pam(d, 5, diss = TRUE)
c = cluster.stats(d = d,
p$clustering, silhouette = TRUE, G2 = TRUE, G3 = TRUE) c$avg.silwidth
c$g2 c$g3