Fast graph-based relaxed clustering for large data sets using minimal enclosing ball.

Area of Science:

• Computer Science
• Data Science
• Machine Learning

Background:

• Graph-based Relaxed Clustering (GRC) is a spectral clustering method known for its simplicity and adaptability.
• However, GRC exhibits sensitivity to similarity measure parameters and high time complexity (O(N^3)), limiting its application to large datasets.

Purpose of the Study:

• To enhance the robustness and efficiency of Graph-based Relaxed Clustering (GRC) for large-scale data analysis.
• To develop a novel algorithm that addresses the parameter sensitivity and computational cost of existing GRC methods.

Main Methods:

• Introduced constraints to GRC, creating Constrained GRC (CGRC), to improve robustness against similarity measure parameter variations.
• Developed Fast GRC (FGRC) by integrating CGRC with a core-set-based minimal enclosing ball approximation for efficient computation.

Main Results:

• FGRC demonstrates asymptotic time complexity that is linear with the dataset size (O(N)).
• The proposed FGRC algorithm maintains the straightforwardness and self-adaptability of the original GRC.
• Validation on benchmarking and real-world datasets confirms the advantages of FGRC.

Conclusions:

• FGRC offers a fast and effective clustering solution for large datasets, overcoming the limitations of traditional GRC.
• The enhanced algorithm provides improved robustness and computational efficiency without sacrificing ease of use.