GBSK: Skeleton Clustering via Granular-ball Computing and Multi-Sampling for Large-Scale Data

Area of Science:

• Data Mining
• Machine Learning
• Computational Statistics

Background:

• Traditional density-based clustering methods face computational bottlenecks, limiting scalability.
• Accurate topological preservation is crucial for effective cluster analysis.

Purpose of the Study:

• Introduce Granular-Ball SKeleton clustering (GBSK) as a scalable algorithm with near-linear time complexity.
• Preserve topological accuracy in clustering large, high-dimensional datasets.
• Provide a computationally efficient alternative to traditional density-based clustering.

Main Methods:

• GBSK sketches a geometric density skeleton, connecting high-density modes to capture cluster connectivity.
• Utilizes adaptive granular-ball construction for local data approximation.
• Employs multi-stage sampling for rapid density estimation and a refinement process for robust mode aggregation.
• Introduces an adaptive variant (AGBSK) with reduced hyperparameters.

Main Results:

• GBSK achieves near-linear time complexity, significantly outperforming state-of-the-art methods in speed.
• Maintains competitive accuracy on datasets up to 100 million instances and 3072 dimensions.
• Demonstrates orders-of-magnitude speedup over existing algorithms.

Conclusions:

• GBSK and AGBSK offer a computationally efficient and scalable solution for density-based clustering.
• The proposed method effectively balances speed and accuracy for large-scale data analysis.
• Granular-ball density statistics provide a viable proxy for kernel density estimation in mode extraction.