自动加权多图正则化Lp光滑非负矩阵分解算法
2023-06-09何雁雁
何雁雁
（贵州师范大学数学科学学院，贵阳 550025）
0 引言
在文本聚类、图像处理、模式识别等领域，往往能遇到非负高维矩阵。所以，适用于非负数据降维的方法——非负矩阵分解（NMF）［1］开始受到人们的广泛关注。随后，人们将不同的正则项以及约束加入到NMF 模型中构成新的模型，并应用于数据聚类与分类［2］，图像还原［3］以及盲源信号分离［4］等领域。Cai 等［5］提出了图正则化非负矩阵分解（GNMF），该算法将图正则项与NMF 算法相结合，考虑数据内部的几何结构信息。图的构造对GNMF 算法有着至关重要的影响，因此，文献［6］提出了多图正则化非负矩阵分解算法（MGNMF），该算法通过优化权重［7］，将多个图按照线性组合的方式构成一个多图正则项加入到NMF 算法中。在自加权多视图学习（AMGL）［8］的基础上， Shu 等［9］提出自加权多图正则化非负矩阵分解（PAMGNMF）。在不同的数据集上，该算法能够对不同的图自动加权，从而更广泛地应用于实际问题中。此外，文献［10］提出了图正则化Lp光滑非负矩阵分解算法（GSNMF），该算法不仅能够保留数据的内部几何结构，而且能够得到更加光滑且精确的结果。
为了在近似数据内部几何结构的基础上，得到更加光滑且精确的解，将自动加权多图正则项以及Lp光滑约束加入到NMF 模型中，本文提出了自动加权多图正则化Lp光滑非负矩阵分解模型（AMGSNMF）。该模型通过多个图的线性组合构成多图正则项来近似原始数据中的内部几何流形结构，利用Lp光滑约束项的优点来获得光滑且精确的解。
1 相关工作
1.1 非负矩阵分解和图正则非负矩阵分解
基于矩阵非负的约束，NMF 算法［1］是一种用低维非负矩阵乘积近似高维非负矩阵的算法。给定非负矩阵X= [x1,x2, …,xN] ∈RM×N+，其中，X的每一列代表一个样本点，NMF 算法的目的是寻找两个非负矩阵U∈RM×K和V∈RN×K，使U和VT的乘积近似于原始矩阵X，表示为如下优化问题：
其中，‖∙ ‖F表示矩阵的Frobenius-范数。Lee等［1］利用乘性更新法提出了以下更新方式：
通过迭代，获得优化问题（1）的局部最优解。
然而，NMF 算法并不能够较好地保留数据的内部几何结构，为了解决这一问题，Cai 等［5］提出了GNMF算法，其优化问题如下：
其中：α> 0 是正则化参数；Tr(∙) 表示矩阵的迹；L=D-W是图拉普拉斯矩阵，W是权重矩阵，D是对角矩阵，其对角元素为。
1.2 图正则化光Lp滑非负矩阵分解
在考虑数据集内部几何结构的同时，GSNMF 算法［10］加入了Lp光滑约束，其优化问题如下：
1.3 无参数的自动加权多图正则化非负矩阵分解
文献［9］利用AMGL 算法［8］中的无参数多图正则项，提出了PAMGNMF 算法，该算法求解如下优化问题：
其中：α> 0 是正则化参数；τ= (τ1,τ2, …,τI)，τi是第i个图的权重。
2 自动加权多图正则化Lp光滑非负矩阵分解
在本节中，将具体介绍自动加权多图正则化Lp光滑非负矩阵分解模型，再利用交替更新法求解该模型，提出自动加权多图正则化Lp光滑非负矩阵分解算法（AMGSNMF）。
2.1 自动加权多图正则化Lp光滑非负矩阵分解模型
在NMF模型中，加入自动加权多图正则项，这样能更精确地近似数据内部几何结构。在自动加权多图正则化非负矩阵分解的基础上，对基矩阵进行Lp光滑约束，从而能够得到一个更加光滑且精确的分解结构，提高聚类效果。所以，提出了自动加权多图正则化Lp光滑非负矩阵分解模型：
其中，1
2.2 优化目标函数
对于变量U和V而言，优化问题（5）的目标函数OAMGSNMF是非凸函数，但是若固定变量U或者V中的一个，只考虑一个变量，则它是凸函数，因此，寻找优化问题（5）的全局最优解是非常困难的，但是可以通过乘性更新法寻找局部最优解。先将优化问题（5）的目标函数OAMGSNMF转换为如下形式：
2.2.1 优化U和V
对于约束条件uik≥0 和vjk≥0，分别使用拉格朗日乘子φik和ϕjk，则得到如下拉格朗日函数：
其中，Ψ =[φik]，Φ =[ϕjk]。式（7）分别关于U、V求偏导得：
通过式（8）和式（9），得出如下关于uik和vjk的更新公式：
2.2.2 优化τ
在每一次迭代更新中，不同图的权重τi也需要更新，在AMGSNMF 算法中，设τi的更新规则如下：
由更新公式（10）、（11）和（12）可得AMGSNMF算法，详见算法1。
算法1 自动加权多图正则化Lp光滑非负矩阵分解
输入：数据矩阵X,正则化参数α，μ以及p,设置权重为，随机构造非负矩阵U0和V0
输出：基矩阵U和系数矩阵V
1. 构 造I个k邻 近 图(W1,W2, …,WI)，并 计算其对应的拉普拉斯矩阵(L1,L2, …,LI)
2. fori=1, 2, …
3. 根据式（10）更新Ui
4. 根据式（11）更新Vi
5. 根据式（12）更新τi
6. if 满足停止准则
7. 得到最终的U和V
8. end if
9. end for
3 数据集及实验评估
为了评估AMGSNMF算法的性能，在COIL20和ORL数据集上进行实验。
3.1 算法的评估
利用Frobenius-范数来衡量UVT和X逼近程度，将AMGSNMF算法与NMF、GNMF、GSNMF、PAMGNMF、AMGSNMF 算法进行比较。并且通过精确度（ACC）［11］和归一化互信息（NMI）［11］这两个指标来评价聚类效果。
3.2 聚类结果
表1～表4依次给出了算法在COIL20 和ORL 数据集上的聚类结果。为了克服初值对实验结果的影响，选取不同的聚类数K对结果进行评估。对于给定的K，进行10 次重复的实验，实验结果的均值和误差在表中显示。
表1 在COIL20数据集上的聚类精确度
表2 在COIL20数据集上的归一化互信息
表3 在ORL数据集上的聚类精确度
表4 在ORL数据集上的归一化互信息
从表1～表4 可以观察到，AMGSNMF 算法在两个数据集上的ACC 和NMI 大多数情况下是最高的，与NMF、GNMF、GSNMF 算法相比，ACC 和NMI 分别至少提高了6.25% 和2.76%, 与PAMGNMF 算法对比，聚类效果也有一些提升，这说明了AMGSNMF 算法能获得更精确的结果，从而提高聚类的效果。
3.3 参数实验
在AMGSNMF 算法中，有以下几个参数需要进行实验，分别为多图正则化参数α,Lp范数的参数p以及Lp正则化参数μ。
首先，图1表示不同α的取值对聚类结果的影响。由图1 可以看出，AMGSNMF 算法的聚类效果会随着α取值的增大而逐渐变好。
图1 参数α对各类算法聚类性能的影响
当p从1.1 到1.9 变 化 时， 在COIL20 以 及ORL数据集的不同类别中进行实验，图2显示了聚类结果。可以看出，当参数p选取不同值时，AMGSNMF算法在大多数情况下，依旧能够保持很高的聚类精确度以及归一化互信息。
图2 参数p对各类算法聚类性能的影响
最后， 针对μ的变化，在COIL20 和ORL 数据集中，分别选取了5 类和30 类进行实验，最终实验结果如图3 所示。可以看出，当μ变化时，AMGSNMF算法的效果在大多数情况下，依旧好于其他算法。
图3 参数μ对各类算法聚类性能的影响
4 结语
本文提出了新的自动加权多图正则化Lp光滑非负矩阵分解算法。该算法应用自动加权多图正则项来逼近数据的原始内部几何结构，应用Lp光滑约束来获得更精确且光滑的解。实验结果表明，在聚类效果上，AMGSNMF算法表现得比其他算法都更好。多图正则项能够有效地逼近原始数据的内部几何结构，但是，如何构造多图正则项是一个难题，需要下一步继续研究。
