An Efficient Clustering Validity Index Based on Granular-Ball Structure

Internal clustering validity indices (CVIs) are tools used to evaluate and optimize unsupervised clustering algorithms. However, most existing internal CVIs are computed based on all data points in the dataset, involving repeated pairwise computations (e.g., Euclidean distances), which leads to low evaluation efficiency and makes them susceptible to noise. Some methods improve these indices by selecting representative points. Unfortunately, the process of selecting these representative points is often complex, especially for large-scale datasets. In this paper, we introduce the granular-ball structure, the granularball set, as representative points to represent the original dataset. A granular-ball contains multiple adjacent data points. The granular-ball set preserves the distribution of the original data clusters while significantly reducing the dataset size and some noisy data points. Based on the granular-balls, we construct an efficient CVI using the Minimum Spanning Tree (MST), which is applicable to clusters of arbitrary shapes. Experimental results on both synthetic and real-world datasets show that the generation of granular-balls is highly efficient. The proposed index constructed on these granular-balls exhibit high evaluation efficiency and accuracy, enabling effective assessment of datasets with arbitrary shapes and noise.