Localized Simple Multiple Kernel K-means

Xinwang Liu, Sihang Zhou, Li Liu, Chang Tang, Siwei Wang, Jiyuan Liu, Yi Zhang

Introduction

Multiple Kernel Clustering (MKC) has emerged as a robust technique for data grouping by integrating information from diverse sources, typically represented as similarity matrices or kernels. A prominent recent advancement, SimpleMKKM, achieved state-of-the-art results by optimizing the fusion of these kernels. However, SimpleMKKM relies on a global alignment strategy, attempting to match every sample pair in the combined kernel to an ideal similarity matrix. This approach often introduces noise in high-dimensional or complex datasets, as it treats distant, unrelated samples with the same importance as close neighbors, potentially obscuring the local variations that define true clusters.

Methodology: Localized Kernel Alignment

To address the limitations of global alignment, the authors propose Localized SimpleMKKM. This method shifts the focus from global structure to local data geometry by introducing a "neighborhood mask" into the optimization process.

  1. Local Alignment Strategy: Instead of aligning the entire kernel matrix, the algorithm requires only that a sample's similarity to its $k$-nearest neighbors aligns with the cluster partition. This allows the model to ignore unreliable similarity values between distant points, enhancing robustness.
  2. Theoretical Foundation: The authors demonstrate that the original SimpleMKKM is a special case of Localized SimpleMKKM, specifically when the neighborhood is defined as the entire dataset.
  3. Efficient Implementation: Local alignment is achieved by pre-processing base kernels—multiplying them element-wise with a neighborhood matrix. These "normalized" kernels can then be used with existing SimpleMKKM optimization frameworks.
  4. Min-Max Optimization: The model employs a reduced gradient descent algorithm to solve a min-max problem, simultaneously minimizing kernel weights and maximizing clustering partition quality.

Experimental Setup

The performance of Localized SimpleMKKM was evaluated against nine state-of-the-art clustering algorithms across eight benchmark datasets, ranging from image and action recognition (MSRA, Still, Flo17, Flo102) to bioinformatics (PFD, Nonpl) and text mining (Reuters).

Results and Discussion

Localized SimpleMKKM consistently outperformed competing methods across standard metrics, including Accuracy, NMI, Purity, and Rand Index.

Comparison of kernel weights across different datasets and algorithms.

Key Performance Gains

The method showed significant accuracy improvements, notably a 17.3% gain on the Nonpl dataset and improvements between 1.1% and 8.3% on others. Despite the neighborhood calculation step, the algorithm's running time remains competitive, making it scalable to large datasets like Reuters (over 18,000 samples).

Insights on Kernel Weighting

A critical observation is the non-sparse nature of the learned weights. As shown in the figure above, unlike methods that aggressively select a single "best" kernel (e.g., ONKC or LKAM), Localized SimpleMKKM tends to distribute weights more effectively across multiple kernels. This suggests that the local alignment strategy better captures complementary information from different sources, leading to more stable and accurate clustering.

Conclusion and Future Work

Localized SimpleMKKM demonstrates that clustering is inherently a local phenomenon. By restricting alignment to a sample's neighborhood, the algorithm becomes significantly more robust to global noise.

A current limitation is the use of a fixed neighborhood based on initial average kernels. If the initial kernels are poor, the neighborhood structure may be suboptimal. Future research could explore dynamic neighborhood updates during the learning process, allowing the algorithm to refine its understanding of local structures as clusters emerge.

Summary updated

Abstract

As a representative of multiple kernel clustering (MKC), simple multiple kernel k-means (SimpleMKKM) is recently put forward to boosting the clustering performance by optimally fusing a group of pre-specified kernel matrices. Despite achieving significant improvement in a variety of applications, we find out that SimpleMKKM could indiscriminately force all sample pairs to be equally aligned with the same ideal similarity. As a result, it does not sufficiently take the variation of samples into consideration, leading to unsatisfying clustering performance. To address these issues, this paper proposes a novel MKC algorithm with a "local" kernel alignment, which only requires that the similarity of a sample to its k-nearest neighbours be aligned with the ideal similarity matrix. Such an alignment helps the clustering algorithm to focus on closer sample pairs that shall stay together and avoids involving unreliable similarity evaluation for farther sample pairs. After that, we theoretically show that the objective of SimpleMKKM is a special case of this local kernel alignment criterion with normalizing each base kernel matrix. Based on this observation, the proposed localized SimpleMKKM can be readily implemented by existing SimpleMKKM package. Moreover, we conduct extensive experiments on several widely used benchmark datasets to evaluate the clustering performance of localized SimpleMKKM. The experimental results have demonstrated that our algorithm consistently outperforms the state-of-the-art ones, verifying the effectiveness of the proposed local kernel alignment criterion. The code of Localized SimpleMKKM is publicly available at: https://github.com/xinwangliu/LocalizedSMKKM.
BibTeX
@inproceedings{liu2021localized,
  author = {Xinwang Liu and Sihang Zhou and Li Liu and Chang Tang and Siwei Wang and Jiyuan Liu and Yi Zhang},
  title = {{Localized Simple Multiple Kernel K-means}},
  booktitle = {IEEE/CVF International Conference on Computer Vision},
  year = {2021},
  doi = {10.1109/iccv48922.2021.00916},
}
Figure