L2稀疏超图正则非负矩阵分解的图像聚类算法

2021-07-02陈璐瑶

现代计算机 2021年13期

陈璐瑶

（贵州师范大学数学科学学院，贵阳550025）

0 引言

在计算机视觉、模式识别、数据表示或聚类分析中，低秩矩阵分解是一种非常流行的方法。Lee等人[1]在Nature杂志上发表了非负矩阵分解（NMF）方法就是一种特殊的低秩矩阵分解的方法，与传统的算法相比，NMF避免了出现负元素，从而更具有实际物理意义。后来为了利用潜在的流形结构，Cai等人[2]提出了一种图正则NMF（GNMF）方法，该方法通过构造K-最邻近（KNN）方法来考虑数据点几何结构信息。姜伟等人[3]在图正则非负矩阵分解的基础上添加了L1稀疏约束项，得到更加有效和稀疏的系数矩阵，从而节省了存储空间，提高了分解质量。但是由于L1损失函数的结果更具鲁棒性，也就是说对于异常值更加不敏感，而L2的求解更为简单其解是唯一的。L2相对于L1具有更为平滑的特性，在模型预测中，往往比L1具有更好的预测特性。另外，超图是普通图的推广，适用于处理嵌入高维空间的低维子流形的数据，超图考虑到了数据内部的高维样本间的关系，所以要优于普通图。因此，本文在先前工作的基础上进行改进，现将L2稀疏约束项和超图正则项引入NMF中，提出新的带有L2稀疏约束和超图正则的非负矩阵分解（SHGNMF）方法，来得到更稀疏精确的结果。并在公开数据集上的进行实验，结果表明该算法优于其他相关算法。

1 预备知识

NMF是一种特殊的基于局部特征的矩阵分解方法，它侧重于对元素非负的数据进行分析。给定一个非负矩阵V=[ x1,x1,…,xn]∈Rm×n，V的每一列都是一个多维数据点。

NMF的目的是找到两个非负矩阵W∈Rm×r和H∈Rr×n，使以下目标函数式（1）最小：

为了保持数据集的内在几何结构信息，Cai等人[3]在NMF的基础上提出了以下的目标函数：

2 SHGNMF算法

在这一部分中，提出了带有L2稀疏约束和超图正则的非负矩阵分解算法（SHGNMF），它不仅可以保持数据集的内在几何结构信息，而且更加有效和稀疏，提高分解的质量，得到更精确的结果。接下来将给出更新规则和详细推导过程。

其中λ，β是大于0的常数。目标函数的第二项和第三项分别表示的是超图正则项和稀疏项。LHyper=Dv-B超图拉普拉斯矩阵，并且

下面我们采用交替非负最小二乘方法，可得到式（5）的更新规则。将目标函数重新写成：

根据以上分析，下面给出新算法。

算法1 SHGNMF算法

步骤1 V∈Rm×n，1≤r≤min{m,n，}图正则化参数λ>0，稀疏约束参数β>0，邻域大小k>0；

步骤2随机初始化矩阵W和H；

步骤3根据式（10）、式（11）更新矩阵W和H，直到满足收敛条件时停止；

步骤4输出矩阵W∈Rm×r和H∈Rr×n；

步骤5将此算法运用到图像聚类中，计算聚类性能指标精度（ACC）、归一化互信息（NMI）。

3 收敛性分析

定理1对于W≥0,H≥0，目标函数式（5）在更新迭代规则式（10）和式（11）下是非增的。

为了证明此定理，首先引入辅助函数[6]的定义：

定义1

若G(x,x')满足G(x,x')≥F(x)和G(x,x)=F(x)，

则G(x,x')是F(x)的辅助函数。

引理1若G(x,x')是F(x)的辅助函数，则F(x)在更新迭代规则：

下是非增的。

证明：根据定义1和更新迭代规则，有：

下面证明当辅助函数合理构造时，H的更新规则式（11）与式（12）是一致的。定义Fab是目标函数关于hab对应部分的辅助函数，对Fab关于H求偏导数：

接下来构造关于H合适的辅助函数，为了证明目标函数在更新规则式（11）下是非增长的。

引理2函数

由于式（15）是Fab的辅助函数，所以在更新迭代规则式（20），即式（11）下是非增的。类似地，式（10）同理可证。故而：

4 数值实验

为了验证新算法SHGNMF的有效性，将它与K-means、NMF[1]、GNMF[2]和SGNMF[3]算法进行比较。在ORL和COIL-20数据集上进行实验，并对结果进行对比。文中的所有实验均使用MATLAB 2019a软件进行编程，在处理器型号为Intel Core i5-7500 CPU@3.40GHz 3.41 GHz，系统内存为8.00 GB，64位的Win10操作系统环境下进行的。