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.
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:
- Intracluster Compactness: Measured as the maximum distance between any two hyper-balls within the same cluster.
- Intercluster Separation: Measured as the minimum distance between hyper-balls belonging to different clusters.
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