Robust MST-Based Clustering Algorithm.

Area of Science:

• Data Science
• Machine Learning
• Computer Science

Background:

• Minimax similarity focuses on data point connectedness.
• The grouping principle excels at arbitrarily-shaped clusters but struggles with noise and outliers.
• Existing methods face challenges with isolated objects and merging distinct clusters.

Purpose of the Study:

• To propose a robust minimum spanning tree (MST)-based clustering algorithm.
• To overcome the limitations of the grouping principle in handling noisy data and outliers.
• To enhance the accuracy and reliability of data clustering for complex datasets.

Main Methods:

• A density-based coarsening phase to create supernodes from connected objects, forming a low-rank matrix.
• A greedy method for partitioning supernodes based on minimax similarity using the low-rank matrix.
• Assignment of data points to clusters via their corresponding supernodes.

Main Results:

• The proposed MST-based algorithm demonstrates robustness against noise and outliers.
• Successfully separates distinct clusters that might otherwise merge.
• Outperforms existing clustering algorithms on synthetic and real-world datasets.

Conclusions:

• The robust MST-based clustering algorithm effectively addresses limitations of previous methods.
• Offers improved performance in identifying arbitrarily-shaped clusters even with noisy data.
• Provides a reliable approach for data point assignment through supernode representation.