余江兰 李向利 赵朋飞

摘 要：针对传统的非负矩阵分解（NMF）应用于聚类时，没有同时考虑到鲁棒性和稀疏性，导致聚类性能较低的问题，提出了基于核技巧和超图正则的稀疏非负矩阵分解算法（KHGNMF）。首先，在继承核技巧的良好性能的基础上，用L2，1范数改进标准非负矩阵分解中的F范数，并添加超图正则项以尽可能多地保留原始数据间的内在几何结构信息;其次，引入L2，1/2伪范数和L1/2正则项作为稀疏约束合并到NMF模型中;最后，提出新算法并将新算法应用于图像聚类。在6个标准的数据集上进行验证，实验结果表明，相对于非线性正交图正则非负矩阵分解方法，KHGNMF使聚类性能（精度和归一化互信息）成功地提升了39%～54%，有效地改善和提高了算法的稀疏性和鲁棒性，聚类效果更好。

关键词：非负矩阵分解;超图正则;L2，1/2矩阵伪范数;稀疏性;鲁棒性;L2，1范数

中图分类号： TN919.81

文献标志码：A

文章编号：1001-9081（2019）03-0742-08

Abstract： Focused on the problem that when  traditional Non-negative Matrix Factorization （NMF） is applied to clustering，  robustness and sparsity are not considered at the same time， which leads to low clustering performance， a sparse Non-negative Matrix Factorization algorithm based on Kernel technique and HyperGraph regularization （KHGNMF） was proposed. Firstly， on the basis of inheriting good performance of kernel technique， L2，1 norm was used to improve F-norm of standard NMF， and hyper-graph regularization terms were added to preserve inherent geometric structure information among the original data as much as possible. Secondly， L2，1/2 pseudo norm and L1/2 regularization terms were merged into NMF model as sparse constraints. Finally， a new algorithm was proposed and applied to image clustering. The experimental results on six standard datasets show that KHGNMF can improve clustering performance （accuracy and normalized mutual information） by 39% to 54% compared with nonlinear orthogonal graph regularized non-negative matrix factorization， and the sparsity and robustness of the proposed algorithm are increased and the clustering effect is improved.

Key words： Non-negative Matrix Factorization （NMF）; hypergraph regularization; L2，1/2-matrix pseudo norm; sparsity; robustness; L2，1-norm

0 引言

近年來，矩阵分解技术在数据表示方面的应用吸引了越来越多人的关注。传统的矩阵分解方法主要有主成分分析（Principal Component Analysis， PCA）、 独立分量分析（Independent Component Analysis， ICA）、 奇异值分解（Singular Value Decomposition， SVD） 和矢量量化（Vector Quantization， VQ）等。在这些方法中，原始矩阵被近似分解为多个低秩矩阵的乘积，但这些方法在处理数据时有两个共同的缺点：1）不能保证分解结果的非负性。从计算的角度看，分解结果中存在负值是正确的，但在实际问题中负值元素往往是没有意义的或无法解释的。2）传统的矩阵分解方法对数据的表示是基于整体的而不是基于部分的。

1999年，Lee等[1]在《Nature》杂志上发表文章，非负矩阵分解（Non-negative Matrix Factorization， NMF）的概念才被正式提出，并立即受到广泛的关注。NMF是一种用于数据分析的多变量分析技术[1-3]。由于它对真实存在的事物有着良好的物理解释，NMF 已经被成功应用到各种领域，比如，文本聚类[4-6]、图像表示和图像聚类[7-8]、人脸识别[9]、计算机视觉[10]、机器学习[11]和模式识别[12]等领域很多研究表明，与传统的矩阵分解方法相比，NMF都要优于传统的矩阵分解方法，例如，NMF在人脸识别[13]和文档聚类[14]中被证明优于SVD。NMF是学习对象部分的最佳选择。然而，标准的NMF也存在一些缺陷，比如：1）NMF只适用于非负数据矩阵，而数据基于部分表示的解释能力较弱;2）NMF不能探索数据的几何结构和类标签信息;3）NMF只能用于原始的特征空间，不能利用核化的性质[15]等。

聚类是特征学习和计算机视觉的重要且具有挑战性的任务之一。图像聚类是基于内容的图像检索、图像注释和其他高级图像处理应用的重要步骤。要完成这些任务，必须获得图像的适当表示。而NMF方法作为一种处理大规模数据的矩阵分解方法，它已逐渐成为图像、文本聚类与数据挖掘等领域最受欢迎的工具之一。近年来，NMF在聚类中得到了显著的发展，特别是，具有平方误差成本函数的NMF等价于松弛k-均值聚类，因此对线性可分数据进行聚类是有效的。通过在高维空间中找到低维的流形，在聚类的过程中，流行学习可以实现维度的降低，其中流行学习算法包括等距映射（Isomap）[16]、 局部线性嵌入（Locally Linear Embedding， LLE）[17]、 拉普拉斯特征映射（Laplacian Eigenmap， LE）[18]、 局部切空间排列（Local Tangent Space Alignment， LTSA）[19]和有辨别的位置排列（Discriminative Locality Alignment， DLA）[20]等。在过去的几十年里，为了克服标准NMF的局限性，很多学者提出了很多扩展版的NMF。Li等[13]提出了一种局部非负矩阵分解（Locally Non-negative Matrix Factorization， LNMF）方法，以学习空间局部化的、视觉模式基于子空间的表示。Hoyer等[21]提出了稀疏非负矩阵分解，展示了如何显式地合并“稀疏”的概念，从而改进标准的NMF。Ding等[22]提出了凸非负矩阵分解，虽然NMF 获得的基和编码向量可以代表低维的原始数据，但它的表示并不总是反映嵌入在数据中的固有几何结构。考虑到矩阵分解和局部流行假设，Cai 等[23]在传统NMF的基础上添加流行学习，提出了图正则非负性矩阵分解（Graph regularized Non-negative Matrix Factorization， GNMF）方法。Liu等[24]提出了受限的非负矩阵分解（Constrained Non-negative Matrix Factorization， CNMF），它将标签信息合并为额外的硬约束，CNMF可以保证具有相同类标签的数据点必须合并在新的表示空间中。受流行学习和凸非负矩阵分解（CNMF）的启发，Hu等[25]提出了图正则化的凸非负矩阵分解（Graph regularized and Convex Non-negative Matrix Factorization， GCNMF）。Babaee等[26]提出了有辨别的非负矩阵分解（Discriminated Non-negative Matrix Factorization， DNMF）。为了更好地使用类标签信息，许多研究人员将标签信息约束合并到NMF的框架中，Yang等[27]提出了带有硬约束的图正规化和稀疏非负矩阵分解（Graph regularized and Sparse Non-negative Matrix Factorization with hard Constraints， GSNMFC）算法。之后，Wang等[28]提出了超图正则非负矩阵分解（Hypergraph Regularized Non-negative Matrix Factorization， HRNMF）。Tolic等[29]进一步扩展了非线性正交NMF框架，并引入了图形正则化，以获得在非线性映射后数据的局部几何结构的分解。此外，基于标准的NMF模型，在添加不同的约束条件下，还有很多扩展版的NMF被不断提出。

虽然以上这些不同版本的NMF都在不同程度上改进了标准的NMF方法，但它们并没有同时考虑到算法的稀疏性和鲁棒性等问题。为了解决以上问题，受到Wang 等[28]和Tolic等[29]的启发，本文在繼承核技巧的良好性质的基础上，用L2，1范数改进标准NMF中的F范数，并添加超图正则项尽可能多地保留原始数据间的内在几何结构信息，再将L2，1/2矩阵伪范数和L1/2正则项作为稀疏约束合并到NMF中，提出了一种新的非负矩阵分解方法，即基于核技巧和超图正则的稀疏非负矩阵分解算法（a sparse Non-negative Matrix Factorization algorithm based on Kernel technique and HyperGraph regularization， KHGNMF）。本文提出的基于核技巧和超图正则的稀疏非负矩阵分解算法有以下几个优点：

1）继承了核技巧的良好性质，在实际计算中很大程度上减少了CPU运行时间，达到了优化算法的目的;

2）用L2，1范数改进标准NMF中的F范数作为目标函数的残差项，有效地处理原始数据中存在的噪声值和异常值点，提高增强了算法的鲁棒性;

3）将L2，1/2矩阵伪范数和L1/2正则项作为额外的稀疏约束，改进了算法的稀疏性。

本文的剩余部分组织结构如下。第一部分介绍了相关的背景理论知识; 第二部分主要是本文提出的新算法，包括算法的更新迭代规则和收敛性分析; 第三部分是在6个流行数据上作的数值实验; 最后部分是对本文的总结。本文中Ai表示矩阵A的第i列，Ai表示A矩阵的第i行，A是任意矩阵。

1 相关理论背景

1.1 标准的非负矩阵分解

1.2 超图学习理论

超图模型已经被证明对各种聚类或者分类任务很有好处。超图学习是在简单图的基础学习延伸而来的，简单图的模型仅仅只考虑了数据样本两两间的关系，这将导致对某些复杂关系信息的丢失，而这些信息在实际应用中是至关重要的，比如，通过成对的相似性找到两个相近的数据样本的关系是比较容易的，但是却很难推断是否有一组（超过两个）的相似数据样本。与简单图不同的是，超图可以捕捉多个数据样本之间的高阶关系数据的流行结构，从而尽可能多地保留了原始数据样本的内在几何结构信息，同时这也将有效地模拟超谱图的谱空间连接点的结构。接下来介绍一些关于超图的常用理论[28]。

为了简便起见，几何图形解释如图1，所示对应的顶点与超边的关联矩阵见表1。

1.3 核技巧学习

根据模式识别理论，低维空间线性不可分的模式通过非线性映射到高维特征空间则可能实现线性可分，但是如果直接采用这种技术在高维空间进行分类或回归会存在确定非线性映射函数的形式和参数、特征空间维数等问题。而核函数不用处理数据如何从低维空间映射到高维空间的问题，而是直接计算低维空间两个向量在高维空间的乘积，即把两个低维空间的向量映射成高维空间的内积。核函数的广泛应用于是因为它有好的性质，比如：核函数的引入很大程度上减少了计算量，可以有效地处理输入的高维数据;在计算过程中无需知道非线性变换函数的形式和参数，便于计算。

2 基于核技巧和超图正则的NMF

2.1 目标函数

在文献[29]中，Tolic等在考虑空间数据的非线性时，以强调非线性NMF的正交性来保留聚类的合理解释，并运用了核技巧的相关知识对NMF优化问题进行求解。

对原始数据作非线性映射，将其映射到高维（或无限）空间中，即xi→Φ（xi），或者：

非线性NMF旨在将两个非负因子矩阵的乘积无限逼近原始数据矩阵的映射Φ（X）。在文献[29]中，Dijana等提出的非线性正交图正则非负矩阵分解方法（Nonlinear Orthogonal Graph regularized Non-negative Matrix Factorization， NOGNMF）的目标函数如下：

此模型的优势在于运用了核技巧技术大大减少了计算量，也用了图正则项来保存原始数据间的在内几何结构以改善算法的性能，但它们却忽视了算法的稀疏性和鲁棒性，并且简单图的图正则只能计算每两个数据样本间的信息。

为了解决以上问题，更好地改进算法的稀疏性和鲁棒性，本文在保留核技巧的基础上，运用超图正则来捕捉和保留样本数据点间更多的内在和复杂的几何结构信息。由于L2，1范数具有良好的性质[31]：1）在众多的实际数据中，都包含了很多模糊的噪声值和异常值点等，而L2，1范数可以有效地处理原始数据中存在的这些问题;2）能提供一个有效的更新规则，进而能有效提高算法的稀疏性和鲁棒性;3）以它为损失函数所需的计算成本和标准的NMF几乎差不多，并且能提高算法的性能。因此，本文用L2，1范数来替代标准NMF模型中的F范数。本文提出的基于核技巧和超图正则的NMF的目标函数如下：

这里的λ、 β、α、ξ、η、δ是平衡因子，定义权重矩阵S=Φ（X），P、Q是系数矩阵，LHyper表示超图拉普拉斯矩阵，即LHyper=Dv-HW（De）-1HT。第1项是目标函数的残差项，即原始数据矩阵和低秩近似矩阵的残差;第2项是超图正则项，旨在尽可能多地保留原始数据矩阵数据样本点间的内在几何结构信息;第3、4项是L2，1/2矩阵伪范数，作用在于有效控制对应变量的稀疏性;第5项是结合PPT的l1范数和P的l2范数，在具体实验中，期望这一项的值是很小的，它可以减小与冗余度和不相关特性对应变量的权重。

是L1/2正则项，δ是正则化参数，L1/2正则项作为稀疏约束合并到NMF中，以提高算法的稀疏性。由于L1/2-NMF[29]能够有效利用数据固有的稀疏性，与标准的NMF和其他的稀疏NMF方法相比，它更具有优势。

2.3 收敛性分析

类似于文献[3]，本文借助辅助函数来证明定理1。辅助函数的定义如下：

3 数值实验

聚类，指根据数据点之间的相似性将数据集划分为不同的类别，如图2所示，聚类是机器学习和数据挖掘的一個基本话题。

本章主要介绍了NMF方法在图像聚类中的运用。本文选取了常用的6个流行标准数据集进行聚类实验，即ORL64×64，orlraws10P，Pixraws10P，ORL32×32，ORL，COIL20。对部分数据集的图片如图3和图4所示。

3.1 实验设置

文中本文所有的数值计算都是在处理器为Intel Core i5-6500 CPU@3.20GHz，内存为8.00GB的64位操作系统上进行的，算法代码用Matlab R2016a进行编写。经过多次实验，本文最终所有的参数选取如下λ=0.01，α=10，ξ=0.9，β=3.2，η=2.66，σ=0.22。在此基础上分别选取了三种核技巧技术，即高斯核技巧、幂指数技巧和拉普拉斯核技巧，计算方式分别被定义为：

3.2 实验结果展示及分析

这一节主要是分析本文的数值实验。为了验证KHGNMF算法的聚类性能，将本文的KHGNMF算法与NOGNMF算法[29]比较，表1分别展示了运用高斯核技巧、幂指数核技巧和拉普拉斯核技巧，在6个标准数据集上所获得的实验结果。核函数的优势在于不显示定义的映射函数，而是在高维空间中直接使用核函数进行计算。以核技巧的计算方式来看，三种核函数具有一定的相通性。

从表1中高斯核聚类部分可以看出，在这6个数据集中计算出的两种算法的精度相差并不大，对NMI而言，在orlraws10P、Pixraws10P和COIL20这3个数据集上KHGNMF算法的表现更加明显，因此，这说明在运用高斯核技巧的情况下，本文提出的新算法是有效的。分析表2的幂指数核聚类部分，可以得到，在数据集ORL64×64，ORL32×32和ORL上，虽然NOGNMF算法和KHGNMF算法性能差别不大，但仍然是KHGNMF的结果更好一些;而在orlraws10P，Pixraws10P和COIL20这三个数据集上，与NOGNMF算法相比，KHGNMF算法的ACC分别成功提升了41%，50%和39.17%，NMI成功提升了47，52和54个百分点，这进一步验证了本文提出的算法的有效性。

與高斯核和幂指数核的聚类效果类似，从拉普拉斯核部分可以看出，仍然是在orlraws10P，Pixraws10P和COIL20这三个数据集上的实验结果更好，整体来看都是KHGNMF算法的效果更好。因此，本文提出的KHGNMF方法是有效的，并且要优于已有的算法，纵观表2，在选取幂指数核技巧时，实验结果是最佳的，这说明幂指数核技巧更有助于提高算法的新能。

4 结语

本文针对NMF运用到图像聚类中时性能较低的问题，提出了一种新的NMF方法（KHGNMF算法）;并将新算法用于解决图像聚类问题，在6个流行图像数据库的实验结果表明，与已有的NOGNMF算法相比，KHGNMF算法成功地提升了其聚类性能，进而验证了本文提出的算法是有效的。NMF是否能运用在更多的聚类分析中，是有待研究的下一个新问题。

参考文献 （References）

[1] LEE D， SEUNG H S. Learning the parts of objects by non-negative matrix factorization [J]. Nature， 1999， 401： 788-791.

[2] LIU W， ZHENG N. Non-negative matrix factorization based methods for object recognition [J]. Pattern Recognition Letters， 2004， 25（8）： 893-897.

[3] LEE D D， SEUNG H S. Algorithms for non-negative matrix factorization [J]. Neural Information Processing Systems， 2000（12）： 556-562.

[4] COSTA G， ORTALE R. XML document co-clustering via non-negative matrix tri-factorization [C]// Proceedings of the 2014 IEEE 26th International Conference on Tools with Artificial Intelligence. Washington， DC： IEEE Computer Society， 2014： 607-614.

[5] DHILLON I S. Co-clustering documents and words using bipartite spectral graph partitioning [C]// Proceedings of the 2001 ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2001： 269-274.

[6] SUN P， KIM K J. Document clustering using non-negative matrix factorization and fuzzy relationship [J]. Korea Communications Society Journal， 2010， 14（2）： 239-246.

[7] LIAO Q， ZHANG Q. Local coordinate based graph-regularized NMF for image representation [J]. Signal Processing， 2016， 124： 103-114.

[8] EGGERT J， WERSING H， KORNER E. Transformation-invariant representation and NMF [C]// Proceedings of the 2004 IEEE International Joint Conference on Neural Networks. Piscataway， NJ： IEEE， 2004： 2535-2539.

[9] LONG X， LU H， PENG Y， et al. Graph regularized discriminative non-negative matrix factorization for face recognition [J]. Multimedia Tools and Applications， 2014， 72（3）： 2679-2699.

[10] WANG Y， JIA Y， HU C， et al. Non-negative matrix factorization framework for face recognition [J]. International Journal of Pattern Recognition and Artificial Intelligence， 2005， 19（4）： 495-511.

[11] PEHARZ R， PERNKOPF F. Sparse non-negative matrix factorization with l0-constraints [J]. Australasian Journal of Special Education， 2012， 80（1）： 38-46.

[12] LU N， MIAO H. Structure constrained non-negative matrix factorization for pattern clustering and classification [J]. Neurocomputing， 2016， 171： 400-411.

[13] LI S Z， HOU X W， ZHANG H J， et al. Learning spatially localized， parts-based representation [C]// Proceedings of the 2001 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Washington， DC： IEEE Computer Society， 2001，1： 207-212.

[14] XU W， LIU X， GONG Y， et al. Document clustering based on non-negative matrix factorization [C]// Proceedings of the 26th Annual International ACM SIGIR Conference on Research and Development in Informaion Retrieval. New York： ACM， 2003： 267-273.

[15] HUA W， HE X. Discriminative concept factorization for data representation [J]. Neurocomputing， 2011， 74（18）： 3800-3807.

[16] TENENBAUM J B， SILVA V D， LANGFORD J C. A global geometric framework for nonlinear dimensionality reduction [J]. Science， 2000， 290（5500）： 2319-2323.

[17] ROWEIS S T， SAUL L K. Nonlinear dimensionality reduction by locally linear embedding [J]. Science， 2000， 290（5500）： 2323-2326.

[18] BELKIN M， NIYOGI P. Laplacian eigenmaps and spectral techniques for embedding and clustering [C]// Proceedings of the 14th International Conference on Neural Information Processing Systems： Natural and Synthetic. Cambridge， MA： MIT Press， 2001： 585-591.

[19] ZHANG Z， ZHA H. Principal manifolds and nonlinear dimensionality reduction via tangent space alignment [J]. Society for Industrial and Applied Mathematics Journal on Scientific ComputingJournal of Shanghai University （English Edition）， 2004， 8（4）： 406-424.

[20] ZHANG T， TAO D， LI X， et al. Patch alignment for dimensionality reduction [J]. IEEE Transactions on Knowledge and Data Engineering， 2009， 21（9）： 1299-1313.

[21] HOYER P O. Non-negative matrix factorization with sparseness constraints [J]. Journal of Machine Learning Research， 2004， 5（1）： 1457-1469.

[22] DING C H Q， LI T， JORDAN M I. Convex and semi-nonnegative matrix factorizations [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2009， 32（1）： 45-55.

[23] CAI D， HE X， HAN J， et al. Graph regularized non-negative matrix factorization for data representation [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2011， 33（8）： 1548-1560.

[24] LIU H， WU Z， CAI D， et al. Constrained non-negative matrix factorization for image representation [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2012， 34（7）： 1299-1311.

[25] HU W， CHOI K S， WANG P， et al. Convex non-negative matrix factorization with manifold regularization [J]. Neural Networks： the Official Journal of the International Neural Network Society， 2015， 63： 94-103.

[26] BABAEE M， TSOUKALAS S， BABAEE M， et al. Discriminative nonnegative matrix factorization for dimensionality reduction [J]. Neurocomputing， 2016， 173（P2）： 212-223.

[27] YANG S， HOU C， ZHANG C， et al. Robust non-negative matrix factorization via joint sparse and graph regularization for transfer learning [J]. Neural Computing and Applications， 2013， 23（2）： 541-559.

[28] WANG W， QIAN Y， TANG Y. Hypergraph-regularized sparse NMF for hyperspectral unmixing [J]. IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing， 2016， 9（2）： 681-694.

[29] T0LIC D， ANTULOVFANTULIN N， KOPRIVA I， et al. A nonlinear orthogonal non-negative matrix factorization approach to subspace clustering [J]. Pattern Recognition， 2018（82）： 40-55.

DIJANA T， NINO A-F， IVICA K， et al. A nonlinear orthogonal non-negative matrix factorization approach to subspace clustering [EB/OL]. [2018-07-12]. https：//arxiv.org/pdf/1709.10323.pdf.

TOLIC D， ANTULOVFANTULIN N， KOPRIVA I. A nonlinear orthogonal non-negative matrix factorization approach to subspace clustering [EB/OL]. [2018-07-12]. https：//arxiv.org/pdf/1709.10323.pdf.

[30] GAO Y， JI R， CUI P， et al. Hyperspectral image classification through bilayer graph-based learning [J]. IEEE Transactions on Image Processing， 2014， 23（7）： 2769-2778.

[31] KONG D， DING C， HUANG H. Robust nonnegative matrix factorization using L2，1-norm [C]// Proceedings of the 20th ACM International Conference on Information and Knowledge Management. New York： ACM， 2011： 673-682.

[32] DING C， ZHOU D， HE X， et al. R1-PCA： rotational invariant L1-norm principal component analysis for robust subspace factorization [C]// Proceedings of the 23rd International Conference on Machine Learning. New York： ACM， 2006： 281-288.

[33] SHI C， RUAN Q， AN G， et al. Hessian semi-supervised sparse feature selection based on L2，1/2-matrix norm [J]. IEEE Transactions on Multimedia， 2014， 17（1）： 16-28.

[34] HUANG T-M， KECMAN V， KOPRIVA I. Kernel based algorithm for mining huge data set [J]. Studies in Computational Intelligence， 2006，17： 11-60.

[35] PAPADIMITRIOU C H， STEIGLITZ K. Combinatorial optimization： algorithms and complexity [J]. IEEE Transactions on Acoustics， Speech and Signal Processing， 1998， 32（6）： 1258-1259.

[36] 曹大為，贺超波，陈启买，等.基于加权核非负矩阵分解的短文本聚类算法[J].计算机应用，2018，38（8）：2180-2184.（CAO D W， HE C B，CHEN Q M， et al. Short text clustering algorithm based on weighted kernel nonnegative matrix factorization[J]. Journal of Computer Applications， 2018， 38（8）： 2180-2184.）