Multiway spectral clustering with out-of-sample extensions through weighted kernel PCA

Area of Science:

• Machine Learning
• Data Mining
• Computer Vision

Background:

• Spectral clustering is a powerful technique for data analysis.
• Extending spectral clustering to handle new data points (out-of-sample extension) is a significant challenge.
• Existing methods often lack efficient model selection criteria.

Purpose of the Study:

• To propose a new formulation for multiway spectral clustering.
• To enable out-of-sample extension for clustering models.
• To introduce a novel model selection criterion for clustering.

Main Methods:

• A weighted kernel principal component analysis (PCA) approach using primal-dual least-squares support vector machine (LS-SVM) formulations.
• Eigendecomposition of a modified similarity matrix derived from data.
• Development of the Balanced Line Fit (BLF) criterion for model selection based on out-of-sample extension.

Main Results:

• The proposed method demonstrates effective out-of-sample extension, allowing for training, validation, and testing of clustering models.
• The Balanced Line Fit (BLF) criterion effectively identifies optimal clustering parameters within a learning framework.
• Experimental results show improved performance in generalization to new samples and reduced computation times on toy problems and image segmentation tasks.

Conclusions:

• The new spectral clustering formulation offers a robust and efficient method for data analysis.
• The out-of-sample extension capability enhances the practical applicability of the clustering model.
• The BLF criterion provides a reliable approach for model selection in spectral clustering.