A Graph Theoretic Criterion for Determining the Number of Clusters in a Data Set

This article is concerned with procedures for determining the number of clusters in a data set. Most of the procedures or stopping rules currently in use involve finding internally coherent and externally isolated clusters, but do not derive from the formal structure of the respective clustering model. Based on the graph theoretic concepts of minimal spanning tree, maximal spanning tree, and homomorphic function, a new criterion is advanced that yields a well-defined clustering solution. Its performance in determining the number of clusters in several empirical data sets is evaluated by comparing it to four prominent stopping rules. It is shown that the proposed criterion not only possesses mathematically attractive properties but also may contribute to solving the number-of-clusters problem.