Staleness-Reduction Mini-Batch K-Means.

Area of Science:

• Computer Science
• Data Science
• Machine Learning

Background:

• K-means (km) is a popular clustering algorithm known for its simplicity and quality.
• Standard km faces challenges with high computational complexity and long processing times.
• Mini-batch km (mbatch km) improves speed by using data subsets but can reduce convergence quality due to iteration staleness.

Purpose of the Study:

• To introduce a novel algorithm, staleness-reduction mini-batch k-means (srmbatch km).
• To combine the computational efficiency of mbatch km with the high clustering quality of standard km.
• To develop a scalable algorithm suitable for multicore CPUs and many-core GPUs.

Main Methods:

• The proposed staleness-reduction mini-batch k-means (srmbatch km) algorithm.
• Implementation leveraging massive parallelism for efficient execution on multicore CPUs and GPUs.
• Comparative analysis against standard k-means and mini-batch k-means.

Main Results:

• srmbatch km significantly reduces computational costs compared to standard km.
• srmbatch km demonstrates faster convergence, up to 40x-130x speedup over mbatch km for equivalent target loss.
• srmbatch km achieves a lower final loss (0.2%-1.7%) compared to mbatch km, indicating improved clustering quality.

Conclusions:

• srmbatch km effectively addresses the trade-off between speed and quality in mini-batch k-means.
• The algorithm offers a practical solution for large-scale clustering tasks on modern hardware.
• srmbatch km represents a significant advancement in efficient and high-quality clustering.