A novel cluster internal evaluation index based on hyper-balls

Jiang Xie, Pengfei Zhao, Shuyin Xia, Guoyin Wang, Dongdong ChengarXiv 2022 · DOI · arXiv

Abstract

Evaluating the quality of clustering results and determining the optimal number of clusters remains a significant challenge, particularly for datasets with complex geometries and noise. This paper introduces the Hyper-ball Cluster Internal Evaluation Index (HCVI), a robust metric that utilizes multi-granularity hyper-balls to characterize data. By moving beyond point-to-point distance metrics, HCVI effectively handles non-spherical shapes and filters out noise, providing a more accurate assessment of clustering performance across diverse data topologies.

Introduction

In cluster analysis, two fundamental questions persist: determining the optimal number of clusters ($k$) and assessing the quality of a specific partition without ground-truth labels. Traditional internal evaluation indices, such as the Silhouette Coefficient or Davies-Bouldin Index, typically rely on distances between individual points or centroids. While effective for well-separated, spherical clusters, these methods often falter when faced with arbitrary shapes (e.g., interlocking rings) or noisy environments.

The authors propose a novel internal index, HCVI, designed to be shape-agnostic and robust to noise. By representing clusters as sets of "hyper-balls" rather than raw data points, the index captures the underlying topology of the data more effectively than traditional point-based metrics.

Methodology: The Hyper-ball Approach

The core innovation of HCVI lies in its multi-granularity characterization of data using hyper-balls (HBs). This process transforms the evaluation from a point-level analysis to a more structural, "zoomed-out" perspective.

Hyper-ball Generation and Denoising

The algorithm begins by enclosing the entire dataset in a single large hyper-ball. It then iteratively splits these balls using a 2-means algorithm. To determine when to stop splitting, the authors introduce the Balance Degree (BD), defined as the difference between the maximum radius ($r_i$) of a ball and the average distance of its constituent points to the center ($r_a$). A lower BD indicates a more uniform density within the ball.

Iterative splitting of data into hyper-balls of increasing granularity.

A key feature of this method is its built-in noise handling. During the generation process, any hyper-ball containing fewer than four points is flagged as noise and excluded from the final index calculation. This "4-point rule" provides a computationally efficient way to prevent outliers from skewing the evaluation.

The HCVI Index Calculation

Once the data is represented by a set of hyper-balls, the HCVI index is calculated based on two primary components:

  1. Intracluster Compactness: Measured as the maximum distance between any two hyper-balls within the same cluster.
  2. Intercluster Separation: Measured as the minimum distance between hyper-balls belonging to different clusters.
Representation of a cluster as a collection of hyper-balls for index calculation.

The HCVI is defined as the ratio of compactness to separation, averaged across all clusters. This approach allows the index to measure the "tightness" of complex shapes (like an "S" curve) by treating them as a sequence of small, connected hyper-balls.

Results and Discussion

The HCVI index was evaluated using both synthetic datasets (such as "core vs nocore" configurations) and real-world data. Key findings include:

  • Optimal $k$ Detection: HCVI consistently identifies the true number of clusters in scenarios where traditional indices fail due to non-linear shapes or noise.
  • Efficiency: The iterative 2-means splitting process maintains near-linear time complexity, ensuring the method is scalable for large datasets.
  • Robustness: By using hyper-balls as a filter, the index is significantly less sensitive to local outliers and more focused on the global cluster structure.

Limitations and Future Work

While promising, the method relies on empirical thresholds for noise removal (4 points) and the balance degree, which may require tuning for specific high-dimensional or extremely sparse datasets. Furthermore, the final index quality is linked to the initial granularity phase. Future research will focus on automating threshold selection and testing the index's performance on massive, high-dimensional "big data" streams.

Summary updated

Abstract

It is crucial to evaluate the quality and determine the optimal number of clusters in cluster analysis. In this paper, the multi-granularity characterization of the data set is carried out to obtain the hyper-balls. The cluster internal evaluation index based on hyper-balls(HCVI) is defined. Moreover, a general method for determining the optimal number of clusters based on HCVI is proposed. The proposed methods can evaluate the clustering results produced by the several classic methods and determine the optimal cluster number for data sets containing noises and clusters with arbitrary shapes. The experimental results on synthetic and real data sets indicate that the new index outperforms existing ones.
BibTeX
@misc{xie2022novel,
  author = {Jiang Xie and Pengfei Zhao and Shuyin Xia and Guoyin Wang and Dongdong Cheng},
  title = {{A novel cluster internal evaluation index based on hyper-balls}},
  year = {2022},
  eprint = {2212.14524},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2212.14524},
}
Figure