Source-linked AI summary
One-Pass Incomplete Multi-view Clustering
Menglei Hu, Songcan Chen
TL;DR
Incomplete multi-view clustering must handle missing instances while avoiding the high computational and memory costs of predominantly offline methods on large datasets. OPIMC combines subspace learning with regularized and weighted matrix factorization, directly produces clustering results, and uses global statistics for termination. Experiments on four real datasets report efficient and effective clustering, although performance can be poor in early passes under high incompleteness and small chunks.
Problem
Incomplete multi-view clustering is difficult because missing instances violate complete-view assumptions, while existing methods are mostly offline and costly for large-scale data.
Method
OPIMC is a one-pass subspace-learning framework that uses regularized and weighted matrix factorization, direct clustering outputs, and two global statistics for termination.
Results
Across four real datasets, OPIMC is reported to be efficient and effective, taking only 1%-2% of OMVC running time while obtaining relatively better clustering results.
Takeaways & Limitations
OPIMC provides a practical approach to large-scale incomplete multi-view clustering with substantially lower running time than OMVC.
Takeaways & Limitations
At incomplete rate 0.4 on WebKB, OPIMC performs terribly in the first few passes when the chunk size is small, before improving after further passes.
Abstract
from arXiv · showhide
Real data are often with multiple modalities or from multiple heterogeneous sources, thus forming so-called multi-view data, which receives more and more attentions in machine learning. Multi-view clustering (MVC) becomes its important paradigm. In real-world applications, some views often suffer from instances missing. Clustering on such multi-view datasets is called incomplete multi-view clustering (IMC) and quite challenging. To date, though many approaches have been developed, most of them are offline and have high computational and memory costs especially for large scale datasets. To address this problem, in this paper, we propose an One-Pass Incomplete Multi-view Clustering framework (OPIMC). With the help of regularized matrix factorization and weighted matrix factorization, OPIMC can relatively easily deal with such problem. Different from the existing and sole online IMC method, OPIMC can directly get clustering results and effectively determine the termination of iteration process by introducing two global statistics. Finally, extensive experiments conducted on four real datasets demonstrate the efficiency and effectiveness of the proposed OPIMC method.
Introduction
Multi-view clustering seeks to exploit consistency and complementary information across heterogeneous data sources, but missing instances and large-scale data make incomplete multi-view clustering difficult. OPIMC addresses this setting with matrix-factorization-based one-pass learning, direct clustering results, and global-statistics-based termination.
- Motivation: Multi-view data combine multiple modalities or heterogeneous sources, whose consistency and complementary information can support clustering.Examples include web documents represented by URLs and page words, and 3D objects viewed from different angles.
- Existing approaches: Existing multi-view clustering methods mainly learn either a shared latent subspace or a unified similarity matrix.Subspace approaches make views comparable in a shared space, whereas spectral approaches extend single-view spectral clustering.
- Problem: Incomplete multi-view clustering arises when instances are missing from some views, violating the completeness assumption and complicating clustering.Most existing incomplete multi-view methods are offline and struggle with large-scale datasets because of high time and memory costs.
- Problem: Large-scale incomplete multi-view data are difficult to store and process offline, while the existing online method OMVC has issues with normalization, missing-instance handling, and convergence determination.These limitations leave large-scale incomplete multi-view clustering as an urgent problem.
- Proposed framework: OPIMC is a one-pass incomplete multi-view clustering framework for large-scale data based on subspace learning, regularized matrix factorization, and weighted matrix factorization.It directly produces clustering results and uses two global statistics to determine iteration termination, reducing clustering time.
Related Work
Prior incomplete multi-view methods are largely offline and unsuitable for large-scale data because of their time and space complexity. OPIMC is presented as a more general and feasible algorithm for efficient large-scale incomplete multi-view clustering.
- Multi-view clustering: Subspace and spectral approaches are the two broad categories of multi-view clustering methods.Subspace methods learn a shared latent representation, while spectral methods learn a unified similarity matrix.
- Online incomplete clustering: Incomplete multi-view approaches are mostly offline and have high time and space complexities on large-scale datasets, motivating one-pass learning.One-pass learning requires only one pass over the data and is described as efficient for streaming settings.
- Contribution: OPIMC is proposed as a more general and feasible incomplete multi-view clustering algorithm for efficiently and effectively handling large-scale data.
Proposed Approach
OPIMC combines regularized and weighted matrix factorization to cluster incomplete multi-view data in an online, chunk-based process. It shares clustering assignments across views, handles missing instances through weights, and uses global statistics to monitor convergence and limit memory use.
- Model formulation: OPIMC factorizes each view into view-specific U^(v) matrices and a shared clustering matrix V, with K equal to the number of dataset categories.The shared V captures cross-view consistency while each U^(v) represents a view-specific subspace.
- Missing-view handling: Weighted matrix factorization uses binary weights to exclude missing instances from each view's reconstruction objective.The indicator and weight matrices encode whether each instance is present in a view.
- Online optimization: The optimization processes view data in chunks, updating view factors and chunk-level clustering indicators alternately.Chunk-based processing is designed for data matrices that cannot fit into memory and maintains low computational and storage complexity.
- Clustering updates: For each chunk, clustering indicators are obtained by assigning instances to the nearest clustering centers across views.The row-minimum indexes of the distance matrix determine the 1-of-K assignments.
- Convergence and termination: Two global statistics record loss information while requiring O(d_vs) memory, enabling termination determination with small memory overhead.The objective is updated through accumulated statistics as new chunks arrive.
- Convergence and output: The objective is nonincreasing under alternating optimization, which finds at least a locally optimal solution; the algorithm returns clustering results after processing the chunks.The procedure also fills degenerative clustering centers during iterative updates to prevent degradation, especially for the first chunk.
Experiment
Experiments on four real-world multi-view datasets evaluate OPIMC under incomplete-view settings, comparing clustering quality, runtime, parameter sensitivity, convergence, and block size. OPIMC approaches or exceeds comparison methods while substantially reducing runtime, though performance depends on passes, incomplete rate, and chunk size.
- Clustering performance: OPIMC approaches offline IMC after two passes on WebKB and outperforms four comparison methods; similar behavior appears on Digit.The comparison covers clustering performance across Figure 1 panels.
- Clustering performance: OPIMC achieves its best results after one pass on Reuters, while its performance decreases as the pass number increases.This result is reported for the large-scale Reuters dataset.
- Clustering performance: OPIMC produces excellent results on Youtube and performs much better than the other methods.The reported comparison uses the Youtube results in Figure 1.
- Runtime: OPIMC takes only 1%-2% of OMVC running time while obtaining relatively better clustering results.The runtime comparison is reported in Table 2 alongside other method comparisons.
- Convergence: When average loss converges, both NMI and AC obtain stable values, supporting the use of convergence to determine termination.The convergence study tracks average loss across passes and relates it to Figure 1 performance.
- Parameter studies: Larger block sizes generally improve clustering results, but they also increase space complexity; s = 250 gives high NMI and AC values.The block-size study uses Digit with incomplete rate 0.4 and evaluates s in {2, 5, 10, 50, 100, 250}.
Conclution
OPIMC addresses large-scale incomplete multi-view clustering by modeling missing instances with matrix factorization and using global statistics to obtain clusters and stop iterations. Experiments on four real-world datasets support its efficiency and effectiveness.
- OPIMC addresses large-scale incomplete multi-view clustering with regularized and weighted matrix factorization that considers missing instances.
- Two global statistics let OPIMC directly obtain clustering results and determine when to terminate iteration.
- Experiments on four real-world multi-view datasets demonstrate the method’s efficiency and effectiveness.