Abstract: To address the problems of excessive feature fragmentation caused by relying on continuous relaxation assumptions and the inevitable relaxation errors introduced by subsequent truncation processing in traditional graph-regularized non-negative matrix factorization algorithms for clustering tasks, an Orthogonal Graph-regularized Non-negative Matrix Factorization algorithm based on Discrete Search (DS-OGNMF) was proposed. The suboptimal strategy of continuous coefficient solving followed by post-processing discretization was avoided, and the factorized coefficient matrix was directly constrained into a 1-bit discrete orthogonal indicator matrix. In the optimization phase, an alternating continuous and discrete optimization framework was constructed: on the one hand, the basis matrix was updated in the continuous non-negative space to ensure the stable expression of data features; on the other hand, a vectorized precise discrete search mechanism was designed. In this mechanism, the global data reconstruction cost and the local manifold penalty term based on the nearest-neighbor graph were combined and transformed into a neighborhood voting rule in the discrete space, whereby the optimal clustering assignment of each sample was directly determined through matrix operations. Through theoretical derivation, the convergence analysis of the algorithm was provided, along with a discussion on the local optimum problem. Experimental results on multiple real-world datasets such as handwritten digits and faces showed that compared with baseline algorithms such as Orthogonal Non-negative Matrix Factorization (ONMF), the DS-OGNMF algorithm effectively reduced the overlapping fragments across classes, and the clustering accuracy was increased by up to 5.9 percentage points; meanwhile, benefiting from the topological structure compensation mechanism, the algorithm demonstrated a certain degree of anti-interference capability and robustness under long-tail sample distributions and extreme occlusion conditions. The synergistic optimization mechanism of discrete constraints and manifold structures effectively enhanced the physical interpretability and classification discriminability of unsupervised representation learning in complex data environments. 

Key words: Non-negative Matrix Factorization (NMF), graph regularization, discrete search, orthogonal constraint, clustering analysis 

摘要： 针对传统图正则非负矩阵分解算法在求解聚类任务时，因依赖连续松弛假设而导致提取特征过度碎裂，以及后续截断处理不可避免引入松弛误差的问题，提出一种基于离散搜索的正交图正则非负矩阵分解算法（DS‑OGNMF）。该算法避免了对系数矩阵进行连续求解再后处理离散化的次优策略，直接将分解后的系数矩阵约束为1‑bit正交指示矩阵。在优化求解阶段，构建了连续与离散交替的寻优框架：一方面在连续非负空间中更新基底矩阵，确保数据特征的平稳表达；另一方面设计了向量化的离散搜索机制，将全局数据重构代价与基于近邻图的局部流形惩罚项相结合，转化为离散空间中的邻域投票规则，从而通过矩阵运算直接确定每个样本的最优聚类归属。通过理论推导，给出了算法的收敛性分析与针对局部最优问题的讨论。在手写数字、人脸等多个真实数据集上的实验结果表明，相较于正交非负矩阵分解（ONMF）等对比算法，DS‑OGNMF算法有效减少了跨类重叠碎片，聚类准确率最高提升5.9个百分点；同时，得益于拓扑结构补偿机制，算法在样本长尾分布与极端遮挡条件下展现出一定的抗干扰能力与鲁棒性。离散约束与流形结构协同优化机制，有效增强了无监督表示学习在复杂数据环境下的物理可解释性与分类判别力。

关键词: 非负矩阵分解, 图正则化, 离散搜索, 正交约束, 聚类分析