Efficient Multiple Kernel k-Means Clustering With Late Fusion

Siwei Wang, En Zhu, Jingtao Hu, Miaomiao Li, Kaikai Zhao, Ning Hu, Xinwang Liu

Introduction

Clustering serves as a cornerstone of unsupervised machine learning, enabling the discovery of latent structures within unlabeled data. In modern applications, data is frequently "multi-view," meaning it is characterized by multiple distinct feature sets or modalities. For instance, a multimedia object might be represented by visual descriptors, textual tags, and audio signals. Multiple Kernel k-Means (MKKM) has emerged as a popular framework for multi-view clustering by representing each view as a kernel matrix.

Despite its effectiveness, traditional MKKM methods often fall into a "speed trap." Most existing algorithms rely on "early fusion"—combining multiple kernels into a single optimal kernel before clustering. This process typically involves eigenvalue decompositions or complex optimization routines that scale cubically ($O(n^3)$) with the number of samples ($n$). Consequently, these methods become computationally prohibitive for medium-to-large datasets. This paper proposes a novel approach to bridge this gap, maintaining high performance while slashing the time cost to a linear scale ($O(n)$).

The Late Fusion Approach

To address the scalability bottleneck, this research introduces a shift from early fusion to Late Fusion (LF). Instead of seeking a consensus kernel before clustering, the proposed framework fuses the clustering results (assignment matrices) derived from individual kernels. The transition to late fusion is motivated by the observation that while individual kernels contain high-dimensional information, the essential clustering structure is captured in the lower-dimensional assignment matrices. By aligning these matrices, the algorithm avoids the expensive $O(n^3)$ operations associated with large-scale kernel matrices.

The core of the methodology involves two primary algorithms:

  1. Average-MKKM-LF: This variant assumes all data views are equally informative. It seeks a consensus clustering matrix ($H$) that minimizes the distance to the average of all individual view-based assignment matrices ($H_p$).
  2. Adaptive-MKKM-LF: Recognizing that real-world data views vary in quality and relevance, this version introduces an adaptive weighting mechanism. It learns a weight ($\gamma$) for each view, automatically prioritizing more reliable data sources during the consensus-building process.

Mathematical Alignment and Optimization

A significant challenge in late fusion is the "label switching" problem: because clustering is unsupervised, "Cluster 1" in one view may correspond to "Cluster 3" in another. The authors resolve this by incorporating permutation matrices ($W_p$) to mathematically "rotate" and align the different views. The resulting optimization problem is solved using a three-step alternate iteration process that updates the consensus matrix $H$, the permutation matrices $W_p$, and the view weights $\gamma_p$. This decoupled approach ensures that each step is computationally lightweight and theoretically guaranteed to converge, typically within fewer than 10 iterations.

Experimental Evaluation

The researchers evaluated the proposed algorithms against state-of-the-art (SOTA) methods across six diverse benchmark datasets: Digital (handwritten digits), Flower17 and Flower102 (botanical images), ProteinFold (biological folding data), Caltech101 (object recognition), and CCV (Columbia Consumer Video).

Performance and Accuracy

The late fusion approach demonstrated superior or competitive accuracy across all benchmarks. For example, on the Flower102 dataset, the proposed algorithms achieved approximately 44% accuracy, a significant improvement over traditional MKKM (~22%) and matching or beating more complex SOTA methods. This suggests that late fusion acts as an effective ensemble learning technique, where the consensus process filters out noise from individual kernels.

Efficiency and Scalability

The most dramatic results were observed in computational efficiency. On the CCV dataset, the Average-MKKM-LF algorithm completed in roughly 125 seconds, whereas a leading competitor (MKC-LKA) required over 281 seconds. More importantly, scalability tests on the Caltech datasets showed that while competing methods experienced exponential growth in processing time as sample sizes increased (from Caltech102-5 to Caltech102-30), the proposed LF algorithms maintained a strictly linear growth curve. This makes the proposed method suitable for large-scale applications in fields like video analysis and bioinformatics.

Conclusion

By shifting the focus from kernel fusion to result fusion, this work provides a highly scalable and effective alternative for multi-view clustering. The use of permutation-based alignment and adaptive weighting ensures that the efficiency gains do not come at the cost of accuracy. While the initial step of performing individual k-means clusterings still carries a base cost, the overall linear complexity of the fusion process represents a significant leap forward for practical kernel-based learning. Future work may extend this late fusion framework to other unsupervised tasks and explore more sophisticated consensus mechanisms for attribute weighting.

Summary updated

Abstract

The recently proposed multiple-kernel clustering algorithms have demonstrated promising performance in various applications. However, most of the existing methods suffer from high computational complexity and intensive time cost. To address this issue, we propose to fulfill multiple kernel k-means clustering via a late fusion manner. In specific, we design two multiple kernel k-means algorithms with late fusion, whose computational complexities linearly grow with the number of samples. The proposed algorithms integrally optimize the various clustering matrices into the optimal consensus clustering results iteratively. Furthermore, we analyze the computational complexities of the proposed algorithms and theoretically prove their convergence. As demonstrated by the experiments on six benchmark datasets, our algorithms achieve comparable or better clustering performance to state-of-the-art ones with less time cost, which demonstrates the advantages of the late fusion in multiple kernel k-means.
BibTeX
@article{wang2019efficient,
  author = {Siwei Wang and En Zhu and Jingtao Hu and Miaomiao Li and Kaikai Zhao and Ning Hu and Xinwang Liu},
  title = {{Efficient Multiple Kernel k-Means Clustering With Late Fusion}},
  journal = {IEEE Access},
  year = {2019},
  doi = {10.1109/access.2019.2904887},
}
Figure