I'm wondering what are the most common/recognized methods to assess the quality of a clustering.
That is because I have developed a tool that can cluster/partition a network (in this case, a public transport network represented by a GTFS feed) in several different manners (graph partitioning, hierarchical clustering, etc ...) and my 'real' metric is almost impossible to get.
In brief, the 'real' metric would be the speed-up obtained using a cluster-based searched against the non cluster-based search. This depends on too many factors (input distribution, implementation of the search algorithms, architecture, etc ....).

I have developed a small function that can evaluate the quality of a clustering using the ratio of vertices of the border of a cluster, against the total amount of vertices. That is because it makes sense, intuitively, with my problem. But there is no mathematic foundation behind it.

My question is: What are the most common methods to assess the quality of a clustering/partitioning ?

  • $\begingroup$ Have you taken a look at recent papers and how they do it? $\endgroup$
    – dkaeae
    Jul 9 '19 at 11:44
  • $\begingroup$ @dkaeae For graph partitioning, yes, since the problem definition gives also a mean to evaluate the quality of its solution (like minimizing the weight of the cut edges, or conductance ....). As for clustering, I did not find a good survey that describe several evaluation methods. I guess it's because there is a big variety of problems to solve, and approaches, under the name 'clustering algorithm'. $\endgroup$
    – m.raynal
    Jul 9 '19 at 11:59
  • $\begingroup$ Searching a bit deeper, I found that this could be a duplicate of this question, and that there are several relevant answers on that link. It provides several measures already. $\endgroup$
    – m.raynal
    Jul 9 '19 at 13:31

Your Answer

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

Browse other questions tagged or ask your own question.