A Validity Index for Clustering Evaluation by Grid Structures

The evaluation of clustering results plays an important role in clustering analysis. Most existing indexes are designed for the evaluation of results from the most-used K-means clustering algorithm; it can identify only spherical clusters rather than arbitrary clusters. However, in recent decades, various algorithms have been proposed to cluster arbitrary clusters that are nonspherical, such as ones with arbitrary shapes, different sizes, distinct densities, and instances where there is overlap among clusters. To effectively solve these issues, in this paper, we propose a new validity index based on a grid-partitioning structure. First, all data points in a dataset are assigned to a group of partitioned grids. Then, each cluster is normalized towards a spherical shape, and the number of empty and intersecting grids in all clusters is computed. The two groups of grids serve as the background of each cluster. Finally, according to various clustering results, the optimal number of clusters is obtained when the number of total grids reaches its minimal value. Experiments are performed on real and synthetic datasets for any algorithms and datasets, revealing the generalization and effectiveness of the new index.