Abstract:

With the widespread application of multi-view data in real-world scenarios, clustering with incomplete views has emerged as a significant challenge in machine learning. Traditional anchor graph-based clustering algorithms rely on complete instances to build the anchor graphs. This dependency leads to insufficient anchors for capturing the underlying data structure under high missing rates, while failing to fully leverage the benefits of anchors when missing rate is low. To address the limitations of traditional methods, including restricted anchor selection, inflexible weight assignment, and high computational complexity, this paper proposed an incomplete multi-view clustering algorithm based on a Sample-Complementary Anchor Graphs (IMVC-SAC). First, the algorithm introduces a cross-view anchor complementation mechanism, which adaptively selects anchors from both shared samples and view-specific samples to enhance data structure representation, particularly under high missing rates. Second, it establishes a missing pattern-aware weighting model that dynamically adjusts the contribution of each view to the similarity matrix based on the missing pattern and degree of the samples. Finally, by leveraging the properties of doubly stochastic non-negative matrix factorization, the time complexity of spectral clustering is reduced from cubic to linear with respect to the sample size. Experimental results on five public datasets demonstrate that the proposed IMVC-SAC algorithm outperforms state-of-the-art methods in clustering performance. Notably, it maintains robust and effective clustering even under high missing rates, validating its superiority.

Key words: incomplete multi-view clustering, anchor graph, sample complementarity, similarity matrix fusion, spectral clustering