Multiple Kernel k-Means With Low-Rank Neighborhood Kernel

Qiyuan Ou, Long Gao, En ZhuIEEE Access 2021 · OpenReview

Abstract

Multiple kernel clustering (MKC) algorithms leverage complementary information from various data views to improve clustering performance. However, many existing methods fail to ensure that the learned consensus kernel reflects the underlying cluster structure, which should ideally be low-rank. This paper introduces Multiple Kernel $k$-Means with Low-Rank Neighborhood Kernel (MKKM-LR), a novel approach that re-parameterizes the kernel matrix to enforce a low-rank structure while searching within a neighborhood of base kernels. Experimental results across 13 benchmark datasets demonstrate that MKKM-LR significantly outperforms state-of-the-art algorithms.

Introduction

In the era of big data, information is often collected from multiple sources or "views"—such as different image descriptors, text features, or genomic markers. Multi-view clustering seeks to integrate these views to uncover the latent structure of the data. Multiple Kernel Clustering (MKC) has emerged as a powerful tool in this domain, using kernel functions to map data into high-dimensional spaces.

A common strategy in MKC is to learn a consensus kernel that is a linear combination of several base kernels. While methods like Optimal Neighborhood Kernel Clustering (ONKC) have improved this by searching for an optimal kernel in the neighborhood of this combination, they often ignore the intrinsic low-rank property of an ideal similarity matrix. In a dataset with $k$ distinct clusters, the ideal kernel matrix should have a rank of $k$. Without this constraint, the learned kernels often contain significant noise, which "blurs" the cluster boundaries and degrades performance.

The MKKM-LR Framework

The proposed MKKM-LR algorithm addresses the limitations of previous MKC methods by integrating a low-rank constraint directly into the kernel learning process. The core innovation lies in combining the flexibility of neighborhood search with the structural rigor of low-rank constraints.

1. Low-Rank Re-parameterization

Instead of adding a soft penalty term (like the nuclear norm) to the objective function, MKKM-LR uses a re-parameterization scheme. The consensus kernel $B$ is defined as:

$$B = W \Sigma W^T$$

where $W$ is an orthogonal matrix and $\Sigma$ is a diagonal matrix containing the top $c$ eigenvalues. By choosing $c \ll n$ (where $n$ is the number of samples), the model forces the kernel to be low-rank, effectively filtering out noise that does not align with the cluster structure. This re-parameterization makes the low-rank property an intrinsic part of the model's geometry.

MKKM-LR searches for an optimal kernel $B$ that remains close to the linear combination of base kernels. This "neighborhood" approach provides the flexibility needed to adapt to the specific geometry of the data while the low-rank constraint maintains structural integrity.

3. Matrix-Induced Regularization

To handle redundancy among base kernels, the model includes a regularization term that promotes diversity among the selected base kernels. This ensures that the consensus kernel captures a broad spectrum of information from the different views rather than over-relying on highly similar kernels.

4. Optimization Strategy

The authors developed an efficient four-step iterative algorithm to solve the resulting optimization problem. It updates the cluster assignments ($U$), the kernel weights ($\lambda$), and the low-rank components ($W$ and $\Sigma$) one at a time. Notably, the model typically reaches its convergence condition within just 3 iterations, making it computationally viable for practical applications.

Experimental Evaluation

The performance of MKKM-LR was evaluated on 13 benchmark datasets, including image recognition (e.g., YALE, Orl), bioinformatics (e.g., ProteinFold), and document clustering (e.g., Cornell).

Comparative Performance

MKKM-LR was compared against 9 state-of-the-art algorithms. It achieved the highest scores on 11 out of 13 datasets across three key metrics: Accuracy (ACC), Normalized Mutual Information (NMI), and Purity.

A standout result was observed on the warpAR10P dataset, where MKKM-LR achieved an accuracy of 55.38%, representing a 16.1% improvement over the second-best algorithm, ONKC (47.69%).

Robustness and Convergence

Sensitivity analysis showed that MKKM-LR is robust to its hyperparameters ($\rho$ and $\delta$), suggesting it isn't overly sensitive to "fine-tuning" for specific datasets. Furthermore, the algorithm demonstrates rapid convergence, often reaching its optimal state within 3 to 5 iterations, despite the added complexity of the low-rank constraints.

Conclusion

MKKM-LR represents a significant step forward in multiple kernel clustering. By combining the flexibility of neighborhood kernel learning with the structural rigor of low-rank re-parameterization, it effectively mitigates the impact of noise in multi-view data. While the selection of the rank $c$ remains a manual process, the algorithm's superior performance and stability make it a powerful tool for complex clustering tasks. Future research will focus on automating rank selection and improving scalability for extremely large datasets.

Summary updated

Abstract

Multiple kernel clustering algorithms achieve promising performances by exploring the complementary information from kernel matrices corresponding to each data view. Most of the existing methods aim to construct a consensus kernel for the afterward clustering. However, they ignore that the desired kernel is supposed to reveal the cluster structure among samples and thus to be low rank. As a consequence, the corresponding clustering performance could decrease. To address this issue, we propose a low-rank kernel learning approach for multiple kernel clustering. Specifically, instead of regularizing the consensus kernel with low-rank constraints, we use a re-parameterize scheme for the kernel matrix. Meanwhile, the consensus kernel is located in the neighborhood area of the linear combination of base kernels. An alternate optimization strategy is designed to solve the resulting optimization problem. We evaluate the proposed method on 13 benchmark datasets with 9 state-of-the-art algorithms. As is demonstrated by experimental results, our proposed algorithm achieves superior clustering scores against the compared algorithms on the reported popular multiple kernel datasets.
BibTeX
@inproceedings{ou2021multiple,
  author = {Qiyuan Ou and Long Gao and En Zhu},
  title = {{Multiple Kernel k-Means With Low-Rank Neighborhood Kernel}},
  booktitle = {IEEE Access},
  year = {2021},
  url = {https://openreview.net/forum?id=ZEjYtyaaoAL},
}
Figure