Parallel spectral clustering in distributed systems.

Area of Science:

• Machine Learning
• Data Mining
• Computational Science

Background:

• Spectral clustering algorithms offer superior performance over traditional methods like k-means for identifying data clusters.
• A significant limitation of spectral clustering is its poor scalability concerning memory and computation time for large datasets.

Purpose of the Study:

• To address the scalability challenges of spectral clustering on large datasets.
• To investigate and compare matrix approximation techniques for efficient spectral clustering.
• To develop and evaluate a parallelized approach for spectral clustering.

Main Methods:

• Approximation of dense similarity matrices using two representative methods: matrix sparsification and the Nyström method.
• Focus on matrix sparsification by retaining nearest neighbors.
• Parallelization of both memory usage and computation on distributed systems.

Main Results:

• Empirical evaluation on a document dataset (193,844 instances) and a photo dataset (2,121,863 instances).
• Demonstrated effectiveness of the parallelized spectral clustering algorithm in handling large-scale problems.
• Comparison indicates the chosen sparsification strategy is viable for large data clustering.

Conclusions:

• The developed parallel spectral clustering algorithm effectively overcomes scalability limitations.
• Matrix sparsification via nearest neighbors is a practical approach for large-scale spectral clustering.
• The parallelized method enables efficient analysis of massive datasets, broadening the applicability of spectral clustering.