Centerless Clustering.

Area of Science:

• Computer Science
• Machine Learning
• Data Mining

Background:

• K-means and spectral clustering are popular due to their simplicity and effectiveness.
• A unified framework for k-means and graph cut models has been reviewed.
• Existing methods often have limitations in scalability and applicability.

Purpose of the Study:

• To propose a new clustering method, k-sums, based on minimizing the sum of distances within clusters.
• To develop k-sums-x, a variant that handles situations where graph data is unavailable by using features directly.
• To evaluate the computational efficiency and performance of k-sums and k-sums-x.

Main Methods:

• Proposed k-sums, a clustering algorithm utilizing a k-nearest neighbor (k-NN) graph.
• Developed k-sums-x, which takes features as input, making it suitable for graph-unavailable scenarios.
• Analyzed computational and memory complexity, showing linear scalability with the number of objects (O(nk) for k-sums, linear for k-sums-x).

Main Results:

• K-sums and k-sums-x demonstrate computational and memory overheads that scale linearly with the number of data points.
• The performance of k-sums is comparable to several state-of-the-art clustering methods.
• Extensive experiments on 10 synthetic and 17 benchmark facial datasets validate the proposed methods.

Conclusions:

• K-sums and k-sums-x offer an efficient and scalable alternative for clustering tasks.
• The proposed methods achieve competitive performance while maintaining low time complexity.
• These algorithms are particularly advantageous for large-scale facial clustering applications.