3
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – gung - Reinstate Monica
    Aug 10, 2015 at 16:34
  • 1
    $\begingroup$ 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". $\endgroup$
    – ttnphns
    Aug 10, 2015 at 17:22
  • $\begingroup$ 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? $\endgroup$
    – Digio
    Aug 10, 2015 at 18:39
  • 1
    $\begingroup$ @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. $\endgroup$
    – gung - Reinstate Monica
    Aug 10, 2015 at 19:09
  • $\begingroup$ @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? $\endgroup$
    – gung - Reinstate Monica
    Aug 10, 2015 at 19:17

3 Answers 3

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – anymous.asker
    Aug 11, 2015 at 17:44
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
1
$\begingroup$

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
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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