Online multi-view clustering with incomplete views

Weixiang Shao, Lifang He, Chun-Ta Lu, Philip S. Yu

Abstract

Clustering massive multi-view datasets presents significant challenges, particularly when data views are incomplete and memory constraints limit the use of traditional offline algorithms. We introduce Online Multi-view Clustering (OMVC), a framework that leverages weighted Nonnegative Matrix Factorization (NMF) and second-order optimization to process data in manageable chunks. OMVC effectively handles missing views through dynamic weighting and achieves state-of-the-art accuracy with a minimal memory footprint. Our evaluation on diverse datasets, including large-scale benchmarks like Reuters and YouTube, demonstrates that OMVC is both scalable and highly competitive with offline methods.

Introduction

Multi-view data, which integrates information from multiple sources or modalities, typically enhances clustering performance. However, real-world applications face two primary hurdles: incompleteness and scalability. Incomplete views occur when certain data points lack specific modalities, while scalability issues arise because most existing multi-view algorithms are "offline," requiring the entire dataset to be loaded into memory. OMVC addresses these challenges simultaneously by providing an online processing mechanism that maintains global context without the prohibitive memory costs of offline approaches.

Methodology

OMVC models the clustering task as a joint weighted Nonnegative Matrix Factorization (NMF) problem. The algorithm processes data in mini-batches, maintaining a global basis matrix and aggregating information into two compact summary matrices ($A$ and $B$). This ensures that the memory complexity remains $O(s)$, where $s$ is the chunk size, rather than $O(N)$, the total number of instances.

To handle missing data, OMVC employs a dynamic weighting scheme. Instead of simple imputation, it uses a diagonal weight matrix that assigns high confidence to observed data and lower, dynamically calculated weights to imputed values. This prevents the model from over-trusting estimated data. Furthermore, OMVC incorporates Lasso ($L_1$) regularization for sparsity and robustness, and utilizes Second-order Projected Gradient Descent (PGD) to accelerate convergence. By incorporating the Hessian matrix, the algorithm achieves faster optimization than standard first-order methods.

Experimental Evaluation

The performance of OMVC was evaluated on four datasets: WebKB (1,051 documents, 2 views), Handwritten Digit (2,000 numerals, 5 views), Reuters Multilingual (111,740 documents, 5 languages), and YouTube Multiview (92,457 videos, 3 views). The latter two datasets served as critical tests for scalability.

NMI on WebKB

As shown in Figure 1, OMVC rapidly converges to the performance level of the state-of-the-art offline method (MIC) on the WebKB dataset. While offline methods like MIC require significantly more time (~1,133 seconds vs. ~16 seconds for OMVC), OMVC achieves comparable Normalized Mutual Information (NMI) within a few passes.

Results and Scalability

OMVC consistently outperformed other online NMF variants across all benchmarks. A key finding is the algorithm's ability to handle large-scale data where offline methods fail due to memory exhaustion.

NMI on Reuters

In Figure 5, the scalability of OMVC is evident. On the Reuters dataset, OMVC maintains a clear performance lead over other online methods. The dynamic weighting strategy proves essential here, as it allows the model to extract useful signals from partial views while mitigating noise from missing data.

Conclusion and Future Work

OMVC represents a significant step forward in scalable multi-view clustering. By combining online NMF with intelligent weighting for incomplete data, it offers a practical solution for big data applications. Future research directions include developing automated methods for determining the number of clusters ($K$) and integrating these online principles into deep learning architectures, such as multi-view autoencoders, to handle more complex data structures.

Summary updated

BibTeX
@inproceedings{shao2016online,
  author = {Weixiang Shao and Lifang He and Chun-Ta Lu and Philip S. Yu},
  title = {{Online multi-view clustering with incomplete views}},
  booktitle = {IEEE BigData},
  year = {2016},
  url = {https://openreview.net/forum?id=CM2ztHcxkR6},
}
Figure