Accelerated K-means clustering in metric spaces.

Area of Science:

• Computer Science
• Data Science
• Bioinformatics

Background:

• K-means clustering is a widely used data partitioning algorithm.
• Lloyd's method, an adaptive K-means algorithm, iteratively refines clusters.
• The computational bottleneck in Lloyd's method is assigning data points to cluster centers.

Purpose of the Study:

• To enhance the efficiency of K-means clustering.
• To introduce the vantage-point tree as a novel approach for faster cluster assignment.
• To evaluate the performance of this method on simulated and real-world molecular data.

Main Methods:

• Implementation of the vantage-point tree for K-means clustering.
• Clustering molecular databases using physicochemical properties.
• Comparison with optimized brute-force Lloyd's method and other pruning strategies.

Main Results:

• The vantage-point tree significantly accelerates cluster membership assignment.
• Demonstrated efficiency on both simulated and real-world molecular datasets.
• Performance improvements are notable in low- and medium-dimensional metric spaces.

Conclusions:

• The vantage-point tree offers a computationally efficient alternative for K-means clustering.
• This method is particularly effective for large-scale molecular data analysis.
• Vantage-point trees can optimize iterative clustering algorithms in various domains.