自适应图正则化的低秩非负矩阵分解算法

余沁茹，卢桂馥，李华

（安徽工程大学 计算机与信息学院,安徽 芜湖 241009）

聚类是计算机视觉中一项受到广泛关注且充满挑战的任务。近些年来，图聚类因为相较于其他方法表现出了更好的性能而被广泛应用于图像分类、图像检索等方面[1-2]。在信息检索、计算机视觉和模式识别的许多问题中，由于样本数据的维数很高，使得从样本直接学习并聚类的的方法是往往不可行的[3]。因此，人们希望找到两个或多个低维矩阵，使它们的乘积可以很好地近似于原始矩阵，越来越多的矩阵分解技术如LU 分解、QR 分解、矢量量化和奇异值分解（singular value decomposition,SVD）、非负矩阵分解（non-negative matrix factorization,NMF）等由此被提出[4-6]。在面部识别和文档聚类任务中，NMF 已被证明优于SVD 等其他矩阵分解技术[7]。NMF 的目的是找到两个非负矩阵，它们的乘积可以很好地近似原始矩阵。由于NMF 更新规则仅允许加法运算，矩阵分解的非负约束使得学习到的成分矩阵成为基于局部的表示，且是学习对象各部分的最佳选择。为了提高NMF 的性能，学界已提出了许多NMF的拓展算法，例如L2.1范数非负矩阵分解[8]、结构不相干的低秩矩阵分解[9]等。

近年来，有些研究者提出了基于流形学习的算法，例如局部线性嵌入[10]、拉普拉斯特征图[11]等，这些研究表明，高维数据其本质分布于低维子空间。研究人员发现，在NMF 算法中引入流形学习方法获得数据的流形结构，有助于提升NMF的性能[12]。Cai 等[13-14]在NMF 的基础上结合流形学习技术提出了图非负矩阵分解算法（graph nonnegative matrix factorization,GNMF）。Zhou 等在GNMF 的基础上为NMF 添加了额外的约束[15]，进一步提出了局部学习正则化NMF（local learning regularized NMF，LLNMF）[16]。Li 等[17]提出图正则化非负矩阵分解（graph nonnegative low-rank matrix factorization,GNLMF），该方法使得图正则化时可以获得原始图像数据的低秩结构。Du 等[18]提出图嵌入正则化投影非负矩阵分解方法（graph embedding regularized projection nonnegative matrix factorization for face image feature extraction，GEPNMF），通过引入图嵌入正则化项，学习的子空间可以保留数据的局部几何结构，同时提升了算法判别力。Yin 等[19]提出一种拉普拉斯正则化低秩表示及其应用算法（Laplacian regularized low-rank representation and its applications，LLRR），该算法通过对图形的正则化，既能表示数据的全局低维结构，又能捕获数据中固有的非线性几何信息。Wang 等[20]提出一种降维局部约束图优化算法（locality constrained graph optimization for dimensionality reduction，LC-GODR），该算法将图优化和投影矩阵学习结合到了一个框架中。由于图不是预先构造并保持不变的，使得其在降维过程中的图形可以自适应更新。Meng 等[21]提出的具有稀疏和正交约束的对偶图正则化非负矩阵分解（dual-graph regularized non-negative matrix factorization with sparse and orthogonal constraints,SODNMF），此方法能同时考虑数据空间和特征空间的流形结构。受到Nie 等[22]的启发，Huang 等[23]提出了局部自适应结构的正则化非负矩阵分解算法（regularized nonnegative matrix factorization with adaptive local structure learning,NMFAN）。NMFAN 算法使用自适应学习的方法来利用数据局部结构中流形信息，但是，NMFAN 算法并没有利用数据的有效低秩结构信息。

以上这些算法通过构建拉普拉斯图来利用数据的局部流形结构信息，其所使用的图的极大地影响着算法的性能。研究人员往往利用K 近邻（K nearest neighbor，KNN）来构建图。然而，一方面，KNN 方法构造的图有可能会破坏部分原始数据的局部连通性；另一方面，其图的构造与矩阵分解的结果无关，从而使得相关算法的性能不能达到最优。此外，这些算法往往没有考虑数据的低秩结构，而数据的有效信息往往隐藏在其低秩结构中。为此，本文提出了一种自适应图正则化的非负矩阵分解算法（nonnegative low-rank matrix factorization with adaptive graph neighbors，NLMFAN）。一方面，NLMFAN 通过引入低秩约束来获得原始数据集的潜藏的有效信息，以此提升现有算法性能；另一方面，NLMFAN 将图的构造和矩阵分解的结果融入一个整体的框架中，自动从数据中学习得到图中节点的相似性，优化了算法精度。文中同时给出了一种求解NLMFAN 的有效算法，并在多种数据集上进行了实验验证本文所提出的算法的有效性。

1 相关工作

1.1 非负矩阵分解（NMF）

NMF 是一种广泛使用的矩阵分解算法。它试图将一个非负矩阵分解为两个阶乘矩阵，其乘积是其自身的最佳近似值。给定一个数据矩阵X=[x1x2···xn]∈RM×N的每一列都是样本矢量，NMF的目的是找到两个非负矩阵U=[uik]∈RM×K和V=[vik]∈RN×K，使得它们的乘积可以很好地近似于原始矩阵X：

即标准NMF 的目标是搜索两个非负矩阵U和V以优化以下目标

其中||·||F表示矩阵的F 范数，同时其存在以下更新规则的表示形式：

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

为了能在NMF 算法中保留其内在结构的同时探索数据的局部几何结构，近几年将流形学习与NMF 相结合的算法研究成为热点。Cai 等[13]通过将图正则化项融入到标准NMF 算法框架中提出了图正则化非负矩阵分解(GNMF)，其目标函数如下：

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

2 自适应低秩非负矩阵分解算法

研究表明，原始图像数据通常嵌入位于高维欧式空间中的非线性低维流形上，且其有效信息通常隐藏在低秩结构中。另外，在图正则化相关算法中所使用的图一般是预先定义的，其图的构造与算法的其他部分往往互相独立。因此，这些算法使用的图并不一定是最优的。为此，在本小节提出一种自适应图正则化的非负矩阵分解算法NLMFAN，该算法同时兼顾了原始图像数据的有效低秩结构和自适应图构造。

2.1 NLMFAN 的算法模型

设输入的原始数据集为X，先给出本文NLMFAN 算法的求解形式如下：

目标函数的第1 项为在rank(L)≤r,cord(E)≤e条件的约束下通过原始数据集X求其低秩形式L，再对得出的结果使用NMF 分解。其中矩阵X为原始数据集，L代表矩阵的低秩部分，E代表其稀疏部分，U、V由L非负矩阵分解得出。r为L的秩范围，e为E设置的稀疏范围，rank（L）表示矩阵L的秩，card（E）表示矩阵E的非零条目数，1表示一个所有元素都为1 的列向量。

目标函数的第2 项为自适应正则项，使用其完成自适应相似矩阵的构造，其中α均为正则化参数。此处我们直接基于数据点间的欧几里得距离构造邻域矩阵，并设距离越小则成为最近邻的可能性越大。原数据集X中的任意一数据点xi，都有所有数据点{x1,x2,···,xn}可以作为近邻与xi连接，连接的概率为sij。si∈Rn×1表示向量，其第j个元素为sij。在此基础上，可以得到相似度矩阵构建的求解函数为

上述相似度矩阵求解的问题存在简化的可能，即我们仅基于欧氏距离求解距离最近的点，并设其与xi的连通概率为1，其他的点概率都为0。此时，对于式（7）中所有的数据点xi，除其之外的所有同数据集的点都存在相同的连通概率即。此时，式（7）可写作：

结合式（7）和（8）可得目标函数中的第2 项，即自适应正则项为

其中γ是正则化参数。通过求解式（9）获得的矩阵S∈Rn×n，可被视为相似度矩阵[22]。当我们假设每个点可以被表示为一个向量vi时，则有：

式中：Ls是S的拉普拉斯矩阵，LS=DS−WS；D5∈Rkxh是的对角阵。

目标函数的第3 项是局部图拉普拉斯约束函数，用其来衡量数据低维表示的平滑度，其中tr(·)表示矩阵的秩。

2.2 NLMFAN 的算法求解

设计了一种有效的更新算法来求解NLMFAN，该算法通过固定其他变量迭代更新一个变量的值来优化目标，此过程重复直到收敛。

2.2.1 固定U、V更新S

观察式（6），不难发现在固定变量U、V的情况下更新S的最小化，式（6）可等价于解决式（11）：

本文可以对每个i解决式（12），此时式（12）可等价于：

设ζ和η≥0 为拉格朗日乘子，可以写出式（11）的拉格朗日函数：

根据KKT 条件[23]，满足sij≥0，最优解可以定义为

结合式（17）和（18），可以得到：

为了获得具有k个非零值的最优si，可以将γi设置为

为了便于计算，可以将整体γ设置为γ1,γ2,···,γn的均值，即

通过取γi的平均值，所有si的平均非零元素应为k。我们不直接搜索正则化参数γ，而是搜索近邻数k。因为k是一个整数并且其值是有限的（即0≤k≤n），所以参数搜索会更加容易。

2.2.2 固定S、V更新U

观察式（6），不难发现在固定变量S、V的情况下更新U的最小化，式（6）可等价于解决下式：

在优先求解L时，求解式（22）可转换为先求解式（23）再求解U的过程：

将式（23）可拆两个子问题来解决。当固定L或E时，有：

可见式（24）对于L或E都是凸的，因此可以固定一个变量并更新另一个，直到收敛。通过迭代X−Et−1将奇异值赋给Lt，在X−Lt上进行相同操作得到Et，由此得到两个子问题的解。

但是，在每次迭代中求X−Et−1的SVD 都很耗时。 本文采用文献[24]中提出的双边随机投影（bilateral random projection ,BRP）来解决式（24）。

对于给定的矩阵X∈Rmexh，其r个BRPs 如下:

式中：A1∈Rn×r,A2∈Rm×r是随机矩阵，那么X的秩r逼近为

由此可计算得出L。在此基础上，对式（28）求解：

可以看出式（28）为式（1）中的标准NMF式。因此，对于等式中的U，我们有式（3）中完全相同的迭代更新规则：

2.2.3 固定S、U更新V

观察式（6），不难发现在固定变量S、U的情况下更新V的最小化，式（6）可等价于解决下式：

参考2.2.2 节中方法可得一确定L。由此，化式（30）为

为了约束V≥0，令ξ ∈Rn×c表示对应的拉格朗日乘数，则可以将拉格朗日函数定义为

根据KKT 条件[23]满足ξijvij=0，有：

则式（35）遵从如下迭代规则：

至此，可以给出NLMFAN 的算法求解步骤。

算法1自适应图正则化的低秩非负矩阵分解算法

2.3 NLMFAN 算法收敛性分析

定理1对于U≥0,V≥0，式(6)中的目标在式(14)、(21)、(36)中的更新规则下不增加，因此收敛。

证明显然，式(14)可以用第2.2 节中描述的闭式解来解决。因此，我们只需要证明式(21)和式(36)在每次迭代中的更新规则下目标值是不增加的。 此外，因为式(6)中目标的第2 项与U无关，第1 项在计算L时不涉及U值的更新，且计算得出L后的操作符合标准NMF 分解，所以NLMFAN 中的U更新规则与原始NMF 完全相同。 因此，可以使用NMF 收敛的证明方式来证明在等式中更新规则下目标没有增加。有关详细信息，可参考文献[17]。

现在，只需要证明在式(36)中的更新规则下我们的目标不会增加即可，而式(32)中更新规则其实等价于文献[25]中式(26)、(36)的收敛性证明可参考文献[25]附录中证明过程，此处不列出。

3 现实数据集实验评估

3.1 实验数据集

为了评估本文提出方法的性能，我们在实际基准数据集进行了实验。

本文实验用到的数据集包括CLUTO 数据工具及UCI 机器学习数据集。其中，CLUTO 是一个软件包，用于对低维和高维数据集进行聚类，并分析各种聚类的特征。CLUTO 的数据工具包中包含的信息检索、客户购买交易、网络、地理信息系统、科学和生物学等数据集非常适于聚类测试。UCI 机器学习数据集是加州大学欧文分校提出的用于机器学习的数据库，该数据库目前共有559个数据集，其数目还在不断增加。UCI 数据集是一个常用的标准测试数据集。

选取CLUTO 数据工具中的4个数据集（Cacmcisi 、Hitech、K1a、K1b）与UCI 机器学习数据集4个数据集（Abalone、Krvs、Wdbc、Vote）进行实验。表1 给出了各数据集及其特征。

表1 数据集及特征Table1 Description of data sets

3.2 实验步骤

为了进一步评估所提出方法的性能，将NLMFAN 与一些经典算法和最新算法进行了对比实验。主成分分析（principal component analysis,PCA）：经典的降维方法[26]。NMF：标准NMF 算法[6]。LLNMF（2009）：使用局部结构学习的NMF算法[16]。GNMF（2011）：图正则化的NMF[13-14]。NMFAN（2020）：具有局部自适应结构的正则化NMF 算法[25]。

本文实验条件为Intel(R)Core(TM)i7-1065G7 1.50 GHz CPU，16 GB DDR3 内存，Matlab2019b。在后续的性能评估中，以准确率（accurity,ACC）、标准互信息率（normalized mutual information,NMI）两个指标作为评价算法性能好坏的标准，在8个基准数据集上测试算法。实验中所用算法的参数已结合原论文根据需要调节至最优。

在每个数据集上都进行了算法精度与收敛速度测试，并从8个数据集中选取了4个用于测试λ参数对聚类性能的影响。

3.3 CLUTO 数据集实验

CLUTO 的4个文档数据集上进行了每组10次实验。实验结果均值如表2 所示。

表2 各算法在CLUTO 数据集上聚类结果比较Table2 ACC and NMI of clustering on CLUTO database %

从表2 中可以看出： NMF 相关算法的聚类结果还是优于传统聚类方法。同时，在NMF 算法中，NLMFAN 算法显示出了优于其他几种方法的聚类效果。尤其是与改进前的NMFAN 算法相比，NLMFAN 算法在每个数据集上的精度及平均精度均有所提高。

图1 展现了在CLUTO 的4个数据集上NLMFAN算法的收敛情况。图中目标函数值即最小误差值。可以看出，本文方法在数据集上均可快速收敛，迭代次数均在50 次内。

图1 NLMFAN 在CLUTO 数据集上的收敛曲线Fig.1 Convergence curves of NLMFAN on CLUTO database

3.4 UCI 数据集实验

本节使用了与上节相同的几种算法在UCI的4个文档数据集上进行了每组十次实验。实验结果如表3 所示。

从表3 中可以看出：在UCI 数据集上，NLMFAN算法的聚类效果基本优于其他算法，同时其在Abalone 数据集上的实验数据较原有的其他算法有5.89%～0.57%的提升。图2 呈现了在UCI 的4个数据集上NLMFAN 算法的收敛情况。可以看出，NLMFAN 算法在几个数据集上均有收敛，且速度较快。

图2 NLMFAN 在UCI 数据集上的收敛曲线Fig.2 Convergence curve of NLMFAN on UCI database

表3 各算法在UCI 数据集上聚类结果比较Table3 ACC and NMI of clustering on UCI database %

3.5 参数选择实验

本节对算法中λ参数的选择进行讨论。本文从CLUTO 中选取了Hitech、K1b，从UCI 中选取了Abalone、Krvs，总计4个数据集进行实验。

从图3 可以看出：

图3 各算法中λ 参数对性能的影响Fig.3 Influence ofλparameter on different algorithms

1）除了NMF以外，GNMF、NMFAN、NLMFAN都受到λ值的影响。总体来说，当λ的值取在10 以内时NLMFAN 可以获得较好的聚类结果，当λ取到10 时可以获得所有算法平均最优结果。

2）除了在Hitech 数据集上有明显的波动外，GNMF 在其他数据集上都没有明显波动变化，说明其受λ的影响不大。而根据提出GNMF 的文献[13]中对其的实验结果表明，GNMF 的结果会在固定λ值时，根据其选取的最近邻数k值的变化而变化。这是因为GNMF 的精度主要依赖于其通过KNN 方法构建的拉普拉斯图，且其图构造与NMF 相互独立的计算模式使得该特征的表现尤为明显。而NMFAN 与NLMFAN 依赖的则是自适应选择最近邻后生成相似度矩阵的结果，即式（6）中包含基于相似度矩阵S的拉普拉斯矩LS阵 的项，该项即为受到λ影响的图正则项。

4 结束语

在本文中，提出了一种自适应图正则化的非负矩阵分解算法（NLMFAN）。

1）提出了一种新的具有低秩特性的自适应邻域GNMF 模型，同时也设计了一种求解NLMFAN的高效求解算法；

2）NLMFAN 方法可以在低秩约束条件下同时执行局部结构学习和矩阵分解过程，即可以根据分解的结果自适应地学习局部流形结构，并重新构造合适的图以保留精炼的局部结构；

3）传统的基于图的方法通常基于固定的数据图对数据进行聚类，容易受到预先构造的不准确的图的影响。NLMFAN 通过引入自适应邻居（adaptive neighbors，ANs）正则项对迭代中的相似度矩阵进行修正，从而减少分配ANs 对数据点之间相似性带来的改变。

然而在许多聚类应用中，数据中的噪声是通过结构或组聚类来分布的，本文算法中并未考虑空间联系。在未来的工作中，我们将把结构化稀疏性作为约束来提升NLMFAN 的性能。