GPVI: An Internal Index Based on Grouping Partition for Clustering Validity Validation

In supervised learning, algorithm evaluation is guided by those performance measures relying on known class labels, such as accuracy. Instead, in unsupervised learning, one can use internal indices that only rely on properties intrinsic to datasets as labels are usually not available. As an important research branch in unsupervised learning, significant effort has been made to solve clustering validation issues, especially the internal indices. Most of the existing internal indices either cannot handle arbitrarily shaped clusters or have complex hyperparameters to set up. In this paper, we focus on internal clustering validity index and propose the Grouping Partition Validity Index (GPVI), a new validity index using the Three-Sigma rule and the Minimum Spanning Tree (MST). Furthermore, a mixing-level variant, denoted as GPVI-M (M for “mixing-level”), is derived from GPVI to increase sensitivity to local overlap. The advantage of GPVI and GPVI-M is that they are parameter free and are designed to be robust across diverse cluster geometries and challenging conditions such as nonconvexity, overlap, imbalance, and moderate noise. The key technology of GPVI and GPVI-M is to divide a cluster into multiple smaller clusters for analysis. Experiments on fifteen datasets show the effectiveness of our indices for clustering validity evaluation. Especially, our indices demonstrate the ability to cope with those datasets with special properties, such as non-convex shape, mixed shape, imbalance, outliers and noise.