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.
- 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.
- 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.
- 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.
- 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.
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