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

Area of Science:

• Data Science
• Computer Science
• Statistics

Background:

• Current methods for determining the number of clusters often lack formal grounding in clustering models.
• Existing stopping rules focus on cluster coherence and isolation but are not model-derived.

Purpose of the Study:

• To introduce a new criterion for identifying the optimal number of clusters in a dataset.
• To provide a mathematically rigorous approach to cluster analysis.
• To evaluate the performance of the new criterion against established methods.

Main Methods:

• Utilizing graph theoretic concepts, including minimal spanning trees and maximal spanning trees.
• Developing a novel criterion based on homomorphic functions for clustering.
• Comparing the proposed criterion with four existing stopping rules on empirical datasets.

Main Results:

• The new criterion demonstrates mathematically attractive properties.
• The proposed method effectively determines the number of clusters in various datasets.
• Performance evaluation shows the criterion's potential to solve the number-of-clusters problem.

Conclusions:

• The novel graph-theory-based criterion offers a robust solution for determining the number of clusters.
• This approach provides a mathematically sound alternative to existing, less formal stopping rules.
• The criterion has practical implications for data analysis and cluster validation.