Abstract
Incomplete multi-view clustering is a critical technique for processing real-world data where various perspectives (views) may be missing information. Traditional methods typically assume "balanced incompleteness," where every view lacks a similar proportion of data. However, real-world scenarios often present "unbalanced incompleteness," resulting in strong views (low incompleteness) and weak views (high incompleteness). This imbalance causes existing methods to fail due to matrix dimension mismatches and suboptimal weighting. In this paper, we introduce the Unbalanced Incomplete Multi-view Clustering (UIMC) method. Inspired by biological evolution, UIMC utilizes a novel "view evolution" scheme to dynamically weight views based on their completeness. By integrating weighted multi-view subspace clustering with a low-rank representation for data recovery, UIMC effectively diminishes the impact of noise and missing data. Experimental results show that UIMC improves clustering performance by up to 40% across multiple metrics compared to state-of-the-art methods.
Introduction
Multi-view clustering (MVC) leverages diverse data sources—such as text, images, and metadata—to group instances more accurately than single-view methods. A persistent challenge in this field is the "incomplete view" problem, where some instances are missing from certain views. While significant progress has been made in incomplete multi-view clustering, most existing algorithms operate under the assumption that the missing rate is uniform across all views.
In practice, this assumption rarely holds. For example, in a dataset of web pages, almost all pages have text (a strong view), but only a small fraction may contain video content (a weak view). Standard methods struggle with this disparity because they often require aligned matrices of identical dimensions or treat all views as equally informative, which allows noisy, incomplete views to degrade the final consensus. UIMC addresses these issues by treating view integration as an evolutionary process where the most informative views dominate the clustering outcome.
The UIMC Framework
1. The Scheme of View Evolution
UIMC introduces a biological metaphor for optimization: "survival of the fittest." The algorithm categorizes views based on their missing rates:
- Strong Views: Views with a missing rate below the average. These are considered highly reliable.
- Weak Views: Views with a missing rate above the average. These contain useful but sparse information.
- Dying Views: Views with so little data that they cannot contribute to a meaningful cluster.
During the iterative optimization process, UIMC updates the weights of each view. Strong views "eat" the weights of weak views, increasing their influence on the final clustering result, while dying views are eventually phased out. This ensures that the consensus matrix is driven by the most complete and reliable data sources.
2. Solving Dimension Mismatch with Laplacian Graphs
A major technical hurdle in unbalanced clustering is that different views have different numbers of available instances, leading to matrices of varying sizes. UIMC bypasses this by constructing Laplacian graphs for each view. These graphs map relationships between the total number of instances ($m \times m$) rather than just the available ones. By using these graphs as a bridge, the algorithm can align views mathematically regardless of their specific missing patterns.
3. Data Recovery via Low-Rank Representation
To handle noise and fill in missing information, UIMC employs a robust low-rank representation. The authors developed a novel $\Gamma$-norm (Gamma-norm) combined with an $L_{2,1}$-norm. Unlike the standard nuclear norm, which can sometimes deviate from the true matrix rank, the $\Gamma$-norm provides a more accurate approximation for recovering the underlying data structure. This dual-norm approach effectively denoises the data while preserving the essential features required for clustering.
Experimental Results
The researchers evaluated UIMC against eight state-of-the-art methods, including PVC, MIC, and DAIMC, across four diverse datasets: BUAA (faces), 3-Sources (news), BBC (documents), and Handwritten Digits. To test the robustness of the algorithm, they artificially induced varying rates of incompleteness to simulate unbalanced data.
Performance on Unbalanced Data
UIMC demonstrated significant superiority in unbalanced scenarios. On the Handwritten Digit dataset (with an average missing rate of 0.4), UIMC achieved:
- 44.50% improvement in Accuracy (ACC)
- 42.70% improvement in Normalized Mutual Information (NMI)
- 43.15% improvement in Purity
Even when tested on balanced incomplete data, UIMC remained the top performer, showing improvements of 11% to 17% over existing techniques. This suggests that the evolutionary weighting scheme is beneficial even when the disparity between views is less extreme.
Convergence and Efficiency
Despite an iterative 9-step optimization procedure based on the Alternating Direction Method of Multipliers (ADMM), UIMC exhibits strong convergence properties. Empirically, the algorithm typically stabilizes within 16 iterations, making it viable for practical applications.
Conclusion
UIMC represents a significant step forward in multi-view clustering by specifically addressing the reality of unbalanced data. By utilizing the scheme of view evolution and Laplacian graph alignment, it provides a mathematically sound way to integrate views of varying quality.
While the current iteration of UIMC faces some computational bottlenecks due to the $O(n^3)$ complexity of matrix inversions and SVD operations, it sets a new benchmark for accuracy in incomplete data environments. Future work will focus on integrating online learning techniques to scale the algorithm for massive, web-scale datasets.
Summary updated