Projected Affinity Values for Nyström Spectral Clustering.

Area of Science:

• Machine Learning
• Kernel Methods
• Data Mining

Background:

• Nyström approximation is widely used for out-of-sample extensions in kernel methods, particularly for large-scale data clustering and classification.
• The standard Nyström method relies on an empirical affinity vector (k) to measure similarity between new data points and the training set.

Purpose of the Study:

• To propose an improved Nyström approximation by replacing the empirical affinity vector with its projection on leading eigenvectors.
• To address constraints in kernel space for new data points, specifically lying on the unit sphere and maintaining affinity values close to the original k.

Main Methods:

• Introduced a modified affinity vector, k*, defined as the projection of the original affinity vector onto the leading eigenvectors of the training set (k* = ∑(i=1 to c) k^T u_i u_i).
• Formulated the problem as a Quadratic Optimization Over a Sphere (QOOS) problem based on kernel space constraints.
• Proved that the projection onto leading eigenvectors is the optimal solution to the QOOS problem.

Main Results:

• The proposed k* slightly improves the performance of the Nyström approximation.
• Experimental results demonstrate that k* achieves comparable or superior clustering performance compared to other affinity matrix modification methods.
• Performance was evaluated using accuracy and Normalized Mutual Information (NMI).

Conclusions:

• Replacing the empirical affinity vector with its projection on leading eigenvectors offers a marginal but consistent improvement in Nyström approximation.
• The k* method provides a robust alternative for enhancing similarity measurements in kernel-based large-scale data analysis.
• This approach yields competitive or better results in clustering tasks, validating its effectiveness.