非负低秩图嵌入算法*

刘国庆，卢桂馥，周 胜，宣东东，曹阿龙

安徽工程大学 计算机与信息学院，安徽 芜湖241000

1 引言

互联网上的数据图像、视频、语音等都含有非常丰富的研究价值，这些数据通常是高维的，计算机是处理这些高维数据的重要工具，而数据在计算机中通常是以矩阵的形式进行存储的，对高维数据的处理即是对高维矩阵的处理，因此矩阵分解被作为一种有效的数据处理方法。近年来，非负矩阵分解方法（non-negative matrix factorization，NMF）[1]在模式识别、图像聚类[2]、语音识别等领域已得到了广泛的应用，且都取得了很好的应用效果。1999年Lee 和Seung 在Nature杂志上所提出的非负矩阵分解算法[1]是一种基于局部特征提取的方法，也是一种有效的图像表示工具[3]，该方法分解后矩阵中的所有元素均是非负的，NMF 在心理学和生理学上构造的依据是对整体的感知是由组成整体的部分感知所构成的，这恰恰也符合人类大脑对事物的直观理解。

为了改善NMF 算法的性能，很多学者在NMF 算法的基础提出了许多改进的算法，Cai 等在标准NMF方法的基础上考虑数据所携带的几何信息，提出了图正则化非负矩阵分解算法（graph regularized nonnegative matrix factorization for data representation，GNMF）[4]。为了能够获取原始图像数据的低秩结构，Li 等提出了图正则化非负低秩矩阵分解算法（graph regularized non-negative low-rank matrix factorization for image clustering，GNLMF）[5]。Du 等提出一种图嵌入正则化投影非负矩阵分解人脸图像特征提取方法（graph embedding regularized projection nonnegative matrix factorization for face image feature extraction，GEPNMF）[6]，该方法将图嵌入正则项融入到投影非负矩阵分解的目标函数中，使得其求得的子空间能在保持数据空间的流形几何结构的同时，更具判别力。为了能够同时利用数据的全局信息和局部信息来进行图形的学习，Wen 等提出一种自适应图正则化的低秩表示方法（low-rank representation with adaptive graph regularization，LRR-AGR）[7]。为了在多视角聚类过程中同时考虑特征权重和数据高维性问题，Liu等提出一种基于特征加权和非负矩阵分解的多视角聚类算法（multiview clustering algorithm based on feature weighting and nonnegative matrix factorization，FWNMF-MC）[8]。Yin 等提出一种拉普拉斯正则化低秩表示及其应用算法（Laplacian regularized low-rank representation and its applications，LLRR）[9]，该算法通过对图形的正则化，既能表示数据的全局低维结构，又能捕获数据中固有的非线性几何信息。Wang 等提出一种降维局部约束图优化算法（locality constrained graph optimization for dimensionality reduction，LCGODR）[10]，该算法将图优化和投影矩阵学习结合到了一个框架中，由于图是预先构造并保持不变的，使得其在降维过程中的图形可以自适应更新。为了同时考虑数据空间和特征空间的流形结构，Meng 等提出一种具有稀疏和正交约束的对偶图正则化非负矩阵分解（dual-graph regularized non-negative matrix factorization with sparse and orthogonal constraints，SODNMF）[11]。为了有效地处理非线性数据，Xiao 等提出一种鲁棒核低秩表示算法（robust kernel low-rank representation，RKLRR）[12]。Wan 等提出一种低秩稀疏图嵌入的半监督特征选择方法（semi-supervised feature selection for low rank sparse graph embedding，LRSE）[13]，该方法充分利用有标签数据和无标签数据，分别学习其低秩稀疏表示，在目标函数中同时考虑数据降维前后的信息差异和降维过程中的结构信息，通过最小化信息损失函数使数据中的有用信息尽可能地保留下来，从而可以选择出更具判别性的特征。为了在NMF 方法中融入几何信息，研究人员尝试将传统图嵌入框架[14]引入到NMF 方法中[15-16]。其中，非负图嵌入算法（non-negative graph embedding，NGE）是一个统一的非负数据分解框架。它除了NMF 目标函数外，还给出一个嵌入图的目标函数，该目标函数保留了由内在图和惩罚图描述的数据几何信息，并将数据重构误差进行最小化。由于NMF 数据重构的非负性，NGE 将最大化“内在”和最小化“惩罚”这两个相反的目标函数转化为单一的最小化目标函数，从而保持了目标函数有效解。尽管NGE 框架具有较好的优越性，但在现实世界的应用中它仍存在对噪声数据和不可靠图敏感以及鲁棒性差的缺点。为了解决上述问题，本文提出了一种非负低秩图嵌入算法（non-negative low rank graph embedding，NLGE），该算法同时考虑了原始图像数据的几何信息和有效低秩结构，使得其鲁棒性有了进一步的提高。

本文的贡献主要有以下三方面：（1）针对现实世界原始图像数据集中普遍存在的噪声数据，对原始图像数据集进行低秩处理，获取原始图像数据集的有效低秩结构，提出一种非负低秩图嵌入算法（NLGE）；（2）设计了一种求解NLGE 的有效迭代算法；（3）给出了该算法的收敛性证明。通过在标准数据库上的实验，验证了NLGE 算法的优越性。

2 相关工作2.1 非负矩阵分解（NMF）

设训练样本数据为Χ=[x1,x2,…,xN]，xi∈Rm，Ν是训练样本总数，相应的类标签表示为{cici∈{1,，Νc为类别数。NMF 方法试图找到两个非负矩阵W∈Rm×r，H∈Rr×N，其乘积最佳逼近原始矩阵Χ，NMF 的最小化目标函数如下：

2.2 图正则非负矩阵分解（GNMF）

为了能够发现数据隐藏信息的有效表示方法，同时又考虑数据的内蕴几何结构，Cai 等通过将图正则化项融入到标准的NMF 框架中提出了图正则非负矩阵分解算法（GNMF）。该算法在矩阵分解过程中强调降维后的数据保持原始数据的几何信息，并假设两个数据点在原始数据空间中的几何距离如果是邻近的话，那么其在基于新的基向量低维表示中相对应的数据点也应该是邻近的。与传统的降维算法相比，流形学习算法能够揭示原始图像数据的内蕴几何结构，寻找高维数据在低维空间中的紧密嵌入。GNMF 的目标函数表示如下：

其中，tr(HLapHT)是图正则项，Lap是图拉普拉斯矩阵，图正则化参数λ>0 。Cai 等在文献[4]中给出了如下的迭代更新规则：

其中，Dap是对角矩阵，Lap=Dap-Sap。

3 非负低秩图嵌入（NLGE）

研究表明，现实世界中的数据往往是嵌入在高维欧式空间中的非线性低维流形上的[17]。另外，原始图像数据中一般含有潜在的噪声数据和不可靠图，实际上有效信息常常隐藏在它的低秩结构中；致使NMF 方法和许多改进的NMF 方法在图像聚类和分类应用中的表现性能不理想。为了提高NMF 算法在非监督聚类和监督分类中的有效性，本文提出了一种非负低秩图嵌入算法，该算法明确考虑了原始图像数据的有效低秩结构和数据的几何信息。

3.1 NLGE 的算法模型

为了挖掘原始图像数据的有效低秩结构部分，把X近似表示为L+S的加和，其中L表示数据X的低秩部分，S表示稀疏噪声部分，之后再对L进行NGE 操作，以获得原始数据图像的有效低维表示。则有：

其中，min 表示当矩阵L、S满足约束条件时，式（7）的最小取值，W为基矩阵，H是系数矩阵，l表示低秩矩阵L秩的范围集，s表示矩阵S的稀疏范围集，rank(L)表示矩阵L的秩，card(S)表示矩阵S中的非零元素的个数。

图嵌入往往涉及到内在图G，它描述了训练数据间的有利关系，而惩罚图Gp={X,Sp}则描述了训练数据之间的不利关系，Lp=Dp-Sp。则有：

其中，NK(i)表示同一类中k最近邻xi的索引集。

其中，NKp(i) 表示不同类中xi的Kp最近邻的索引集。为了使NMF 和NGE 的符号保持一致，将系数矩阵H分为两部分，即：

其中，W1∈Rm×d，W2∈Rm×(r-d)。

所需要的训练数据的低维表示H1旨在保留内在图的特性，同时避免惩罚图的特性。在这里，(W2,H2)是(W1,H1)的互补空间，它们以相加的方式重建原始数据。以往的研究表明：一方面，内在图和惩罚图在NGE 中起着重要的作用，然而当图像具有不需要的结构时，NGE 的性能会有所下降。另一方面，对同一类的样本构造内在图，而惩罚图则将不同类的样本连接起来，在现实应用中NGE 仍存在对噪声数据和不可靠图敏感以及鲁棒性差的缺点。为了增强NGE算法的性能，在NGE 算法中融合图像的低秩结构，其目标函数定义如下：

3.2 NLGE 的求解算法

本文通过迭代方法求解式（13），NLGE 算法可以通过求解下面两个子问题来解决。

（1）低秩矩阵的恢复

低秩矩阵恢复子问题的目标函数可以表示如下：

其中，l是低秩结构L的秩，s是被稀疏噪声影响的数量。虽然问题（14）对于L和S是非凸的，但是如果L或S中的一个被固定，则下面的子问题是凸的。

式（15）中的两个子问题可以通过固定其的一个更新另一个来解决，直到收敛为止。本文使用了双边随机投影（bilateral random projection，BRP）[18]求解问题（14）。对于给定的矩阵X∈Rm×N，则Y1和Y2表示如下：

其中，A1∈RN×r，A2∈Rm×r都是随机矩阵，则L表示如下：

在文献[18]中给出了获取右随机投影Y1用于建立更好的左投影矩阵A2，而Y2用于建立更好的右投影矩阵A1。为了防止矩阵X的奇异值退化，Roweis[19]提出了用来代替X ，则的BRP 和表示如下：

通过对Y1和Y2进行QR分解，求得L如下：

在求出低秩矩阵L之后，再进一步对L进行NGE 分解以获得原始数据集的低维表示。

（2）优化W和H

在描述非负低秩图嵌入的迭代过程之前，先介绍两个概念：辅助函数和M矩阵，以及一些用于算法推导和收敛性证明的引理。

定义1函数G(A,A′)是F(A)的辅助函数，满足下面条件：

定义2矩阵B被称为M矩阵，满足条件：（1）Bij≤0,i≠j；（2）矩阵B的所有特征值的实部都是正的。

引理1如果G是F的辅助函数，则F在下面迭代更新规则下是非增的。

其中，t表示第t次迭代。

引理2如果矩阵B是M矩阵，则矩阵B的逆矩阵中的元素是非负的，即

固定矩阵H优化W，对于给定的矩阵H，目标函数式（13）中关于基矩阵W的目标函数可以重写如下：

根据上述函数，注意到矩阵W的不同行向量在优化时是彼此独立的，因此式（25）可以进一步简化为如下的形式：

其中，Wi表示W的第i行向量，Xi是矩阵X的第i行向量，定义，函数F(Wi)的辅助函数可以定义如下：

固定W优化H，对于给定的W，同样式（13）关于H的目标函数可以写为如下：

在这里定义f(H)=λ‖L-WH‖2，F(H)辅助函数被定义如下：

其中，g(H,Ht)被表示成如下形式：

根据文献[1]中的相关证明，显然有g(H,Ht) 是f(H)的辅助函数，则进一步可以得出G(H,Ht)是F(H)的辅助函数，然后通过求解函数G(H,Ht)关于H的最小化来计算Ht+1。

G(H,Ht)关于H的梯度矩阵设置如下：

如果i≤d，系数矩阵Ht+1的第i行向量表示为，使用下面的设置来更新

同样，如果d<i≤r，则可通过下面的设置进行更新。

然后，计算出：

3.3 NLGE 算法的收敛性证明

定理1在NLGE 算法中给出的迭代过程收敛到局部最优。

证明在这里定义：

根据W的更新规则，有：

同样，根据H的更新规则，有：

因此，可以得出如下的结论：

根据上述所给的目标函数有F(Wt,Ht)≥0，且F(Wt,Ht)单调下降有下界，因此NLGE 算法在所给迭代规则下收敛到局部最优。

3.4 NLGE 算法的步骤

输入：数据矩阵X∈Rm×N，参数λ,r,d,K,Kp。

输出：最优基矩阵和数据的低维表示矩阵H。

（1）对X进行BRP 操作，求出Y1和Y2；

（2）对Y1和Y2进行QR分解，求出数据矩阵X的低秩结构L；

（3）对矩阵L进行NGE 分解；

（4）计算

（5）求得最优基矩阵W和数据的低维表示矩阵H。

3.5 NLGE 算法的计算复杂度分析

对于一个算法来说在每一次的迭代过程中计算复杂度是至关重要的，在这一部分对NLGE 算法在每一次迭代过程中的计算复杂度进行详细的分析。其中，N表示训练样本的总数，m表示特征维数，r表示原始图像数据进行矩阵分解后的矩阵特征维数，通常有r≪m，q表示整数。本文首先讨论了关于快速低秩的近似问题，随机矩阵Y1=XA1和Y2=XTA2是原始数据矩阵X的秩为r的近似值，L的计算包括一个r×r的逆矩阵和三个矩阵的乘积。因此，对于稠密矩阵X需要2Nmr次计算来获得BRP。要获得式（18）中的L需要r2(2N+r)+Nmr次的计算，式（18）中的L被认为是从Y1和Y2中恢复的秩为r的矩阵X，A1和A2是独立的高斯随机矩阵。

对于式（22）的方法，需要一个r×r的逆矩阵和五个矩阵的乘积。对于一个稠密矩阵X需要2(2q+1)×Nmr次计算来获得BRP，进行QR分解需要2r2(N+2r)+Nmr次计算来获得L。式（22）的方法通过增加q来减小式（18）方法的误差，当A1和A2由Y1和Y2构成时，获得BRP 需要额外增加Nmr次计算。

在式（18）和式（22）中本文使用了基于双边随机投影（BRP）的低秩近似，根据上述总结如下：当整数q=0 时，对于稠密矩阵X，式（18）被使用，此时Y1和Y2不进行QR分解，在这种情况下，在每一次的迭代过程中要获得矩阵L需要r2(2N+r)+4Nmr次计算；当整数q>0 时，式（22）被使用，这时要获得L需要r2(m+3N+4r)+(4q+4)×Nmr次计算在每一次的迭代过程中。之前的研究表明，非负矩阵分解算法（NMF）在每一次的迭代过程中需要Nmr次计算，非负图嵌入算法（NGE）在每一次的迭代更新过程中需要Nr2+Nmr+mr2次计算，本文所提出的非负低秩图嵌入算法（NLGE）在q=0 时，在每一次的迭代更新过程中需要r2(2N+r)+4Nmr+Nr2+Nmr+mr2次计算；当q>0 时，需要r2(m+3N+4r)+(4q+4)×Nmr+Nr2+Nmr+mr2次计算。一般情况下，在NLGE 算法的计算复杂度中增加了Nr2和Nmr两个加项，使得NLGE算法的鲁棒性得到一定程度的提高。

4 实验和结果分析

为了验证NLGE 算法的优异性，分别在ORL、CMU PIE 和YaleB、USPS 四个数据库上进行了实验。在本文的实验中，利用了Matlab 2016 平台进行仿真实验，操作系统为Windows 10，64 位的操作系统和基于X64 的处理器，运行内存为8 GB。

4.1 实验所用数据库

ORL 人脸库是由剑桥大学实验室所创建，图像包括了表情、姿态、光照条件和面部表情的变化。它由40个人共400 张面部图像组成，每个人有10 张灰度图像，由于照片拍摄于不同的时期，人脸和面部表情有着不同程度的变化，深度旋转和平面旋转可达20°，在本文的实验中，图像的大小为32×32，图1 是用于实验的部分ORL 人脸图像。

Fig.1 Example of some images in ORL database图1 ORL 数据库中的部分图像示例

CMU PIE 人脸库包含41 368 张68 名志愿者在13 种不同姿势，43 种不同照明条件下的面部图像，并有4 种不同的表情方式。在本文的实验中，选择姿态C05 中的图像进行实验，并将其压缩为32×32 像素，图2 是用于实验的部分CMU PIE 人脸图像。

YaleB 人脸数据库由38个人的2 432 张人脸组成，每个人大约有64 张在不同光照条件下的灰度图像，在本文的实验中，图像的大小为32×32，图3 是用于实验的部分YaleB 人脸图像。

USPS 数据库包含10个手写数字，其类别从“0”到“9”不等，整个数据库有9 298 张灰度图像。图4 是用于实验的部分USPS 图像。

Fig.2 Example of some images in CMU PIE database图2 CMU PIE 数据库中的部分图像示例

Fig.3 Example of some images in YaleB database图3 YaleB 数据库中的部分图像示例

Fig.4 Example of some images in USPS database图4 USPS 数据库中的部分图像示例

4.2 算法比较

为了验证NLGE 算法的有效性，将它与NMF、GNMF、NGE、NLMF、GNLMF、RNGEL1、RNGEL21等算法进行了比较，详细算法如下：

NMF：非负矩阵分解算法[1]，它试图找出两个非负低维矩阵，其乘积近似为原始矩阵。

GNMF：图正则化非负矩阵分解算法[4]，它试图通过构造一个简单的图来包含数据中的内在几何信息。

NGE：图嵌入算法[14]，它明确考虑了原始数据图像携带的几何信息。

NLMF：非负低秩矩阵分解算法[5]，它试图挖掘原始图像数据集的有效低秩结构。

GNLMF：图正则化非负低秩矩阵分解[5]，它将隐藏在图像集中的有效低秩结构部分和数据的流行结构进行融合。

RNGEL1：L1范数的鲁棒非负低秩图嵌入算法[16]，该算法把L1 范数融入到标准图嵌入算法的目标函数中。

RNGEL21：L21 范数的鲁棒非负低秩图嵌入算法[16]，该算法把L21 范数融入到标准图嵌入算法的目标函数中。

4.3 实验中各算法的主要参数设置

K-means：聚类的类别数设置为Nc（实际类别），重复运行次数设置成20。

NMF：最大迭代次数设置为100，重复运行次数设置成20。

GNMF：最大迭代次数设置为100，平衡参数λ设置为100，权重取0-1 权重，取最近邻参数K=5，重复运行次数设置成20。

NGE：设置r=d，权重取0-1 权重，取最近邻参数K=5，平衡参数λ的范围设置成lgλ∈[-3,4]，迭代次数设置为1 000，参数norm（范数）设置为2，调整不同的矩阵维数d来得到最佳结果，重复运行次数设置成20。

NLMF：最大迭代次数设置成100，重复运行次数为20。

GNLMF：最近邻数设置为5，图正则化参数设置为100，重复运行次数为20。

RNGEL1：设置r=d，权重取0-1 权重，取最近邻参数K=5，平衡参数λ的范围设置成lgλ∈[-3,4]，迭代次数设置为1 000，参数norm（范数）设置为1，调整不同的矩阵维数d来得到最佳结果，重复运行次数设置成20。

RNGEL21：设置r=d，权重取0-1 权重，取最近邻参数K=5，平衡参数λ的范围设置成lgλ∈[-3,4]，迭代次数设置为1 000，参数norm（范数）设置为21，调整不同的矩阵维数d来得到最佳结果，重复运行次数为20。

NLGE：调整不同的维数d来得到最优的结果，内在图S和惩罚图SP的最近参数分别设置K=3，KP=30，平衡参数λ的范围设置为lgλ∈[-3,4]，迭代次数设置为1 000，参数norm（范数）设置为2，重复运行次数为20。

4.4 评价准则

使用标准化互信息（normalized mutual information，NMI）从信息点来评估聚类的质量，该方法被广泛用于聚类结果的评价，定义了集群分配之间的相互信息和类的基本真值标记，其标准化是集群分配和真值标记熵的平均值。NMI的定义如下：

这里，C={c1,c2,…,cN}是由已知的类提供的真实值标签，S={s1,s2,…,sN}是一个特殊的聚类结果，I(S,C)是具有基本真值标签聚类分配的相互信息，H(S)是聚类结果的熵。

正确率（AC）是另一种用于度量分类结果的方法，AC的定义为：

其中，δ(∙,∙)是delta 函数，ci为样本的真实类别，si为用算法对样本求出的类别。

4.5 性能的评价和比较

通过在4个数据库上进行实验来验证本文所提出的NLGE 算法的优越性。

Fig.5 NMI of each algorithm on ORL database图5 各算法在ORL 库上的NMI

Fig.6 NMI of each algorithm on CMU PIE database图6 各算法在CMU PIE 库上的NMI

Fig.7 NMI of each algorithm on YaleB database图7 各算法在YaleB 库上的NMI

根据表1、图5、图6、图7 和图8 可以看出，NMF的聚类性能最差，均低于其他聚类算法。在聚类算法中，本文所提出的NLGE 算法由于考虑了数据的低秩结构和流形信息，使得它比其他算法的聚类性能要优异。由表2、图9、图10、图11 和图12 可知，NMF算法的分类正确率均低于其他算法，这是因为其他算法考虑了数据的流形结构或低秩结构，表明在矩阵分解过程中考虑数据几何结构和低秩结构是非常重要的。由于NLGE 算法同时考虑了原始图像数据的几何信息和有效低秩结构，因此其分类准确率高于其他分类算法，这表明数据的几何结构和低秩结构在特征提取中起着重要作用，进而提高分类的准确率。实验中，随机选取样本数据，并重复进行20次，最终的结果是这20 次实验结果的平均值。实验结果表明本文所提出的NLGE 算法不仅可以有效获取原始图像数据集的有效低秩结构，还增强了抗噪声的鲁棒性，使得其在聚类和分类的情况下都表现出一定的优异性能。

Table 1 Clustering results NMI of each algorithm on 4 databases表1 各算法在4个数据库上的聚类结果NMI %

Fig.8 NMI of each algorithm on USPS database图8 各算法在USPS 库上的NMI

Fig.9 AC of each algorithm on ORL database图9 各算法在ORL 库上的AC

Fig.10 AC of each algorithm on CMU PIE database图10 各算法在CMU PIE 库上的AC

Fig.11 AC of each algorithm on YaleB database图11 各算法在YaleB 库上的AC

Table 2 Classification results AC of each algorithm on 4 databases表2 各算法在4个数据库上的分类结果AC %

Fig.12 AC of each algorithm on USPS database图12 各算法在USPS 库上的AC

根据表3可以看出，NMF的运行时间少于GNMF，这是因为NMF 只需要更新两个变量，而GNMF 算法要先对原始数据构建图，然后进行变量的更新。NGE 算法要完成内在图和惩罚图的构建和变量的更新，因此其运行时间大于NMF 和GNMF。本文所提出的NLGE 算法先对原始图像数据进行低秩处理，然后进行内在图和惩罚图的构建，最后进行变量的更新，因此其运行时间一般大于其他算法的运行时间。

Table 3 Running time of each algorithm on 4 databases表3 各算法在4个数据库上的运行时间 s

5 结束语

本文提出了一种非负低秩图嵌入算法（NLGE），该算法明确考虑了原始图像数据集的有效低秩结构和几何信息，图嵌入和数据重构的联合稀疏性对噪声有一定的鲁棒性。另外，还给出了求解NLGE 算法的迭代公式和收敛性证明，使得NLGE 算法在有噪声数据情况下表现出较好的性能。最后，NLGE 在ORL、CMU PIE、YaleB 和USPS 数据库上的实验表现出较高的识别率和较好优越性。