贵州师范大学数学科学学院，贵州 贵阳

收稿日期：2022年12月28日；录用日期：2023年1月21日；发布日期：2023年1月31日

摘要

图学习的方法只考虑了样本间的关系，忽略了样本间的高维结构，基于欧氏距离的非负矩阵模型易受到噪声和异常值的影响。为解决以上问题，给出一种基于L_2,1范数的超图正则化非负矩阵分解(L_2,1HNMFL)方法，并给出了算法的更新规则。通过在COIL20和ORL经典数据集上与其他算法的比较验证了该算法的有效性。

关键词

L_2,1范数，超图学习，聚类分析，非负矩阵分解

Hypergraph Regular Nonnegative Matrix Factorization Based on L_2,1 Norms

Xuechun Wen

School of Mathematical Sciences, Guizhou Normal University, Guiyang Guizhou

Received: Dec. 28^th, 2022; accepted: Jan. 21^st, 2023; published: Jan. 31^st, 2023

ABSTRACT

The graph learning method only considers the relationship between samples, but ignores the high-dimensional structure between samples. The non-negative matrix model based on Euclidean distance is easily affected by noise and outliers. To solve the above problems, a hypergraph regularization nonnegative matrix factorization (L_2,1HNMFL) method based on L_2,1 norm is presented, and the updating rules of the algorithm are given. The effectiveness of this algorithm is verified by comparing it with other algorithms on classical data sets COIL20 and ORL.

Keywords:L_2,1 Norm, Hypergraph Learning, Cluster Analysis, Nonnegative Matrix Decomposition

Copyright © 2023 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

1. 引言

聚类是特征学习和计算机视觉中的一项重要但具有挑战性的任务。对于图像聚类任务，最重要的是找到原始数据的有效表示。为了挖掘出原始数据中内在的结构信息，许多研究人员已经做了大量的工作。最流行的特征提取方法包括主成分分析 [1] (PCA)、奇异值分解 [2] (SVD)、概念分解 [3] (CF)非负矩阵分解 [4] (NMF)等。1999年，Lee和Seung [4] 在《自然》杂志上首次提出了非负矩阵分解的概念。NMF的目标是得到两个非负矩阵，基矩阵和编码矩阵，其乘积尽可能接近原始矩阵。由于NMF的良好性能，在Lee和Seung的工作之后，许多标准NMF的变体被提出，用于从不同的观点改进NMF。

为了提高NMF的稀疏性，Li等人提出了一种加入局部约束的局部NMF [5] (LNMF)。在此之后，Chen等人在NMF中引入了局部坐标约束 [6]。Cai等人提出了一个图正则化 [7] NMF (GNMF)，试图涉及数据空间的几何信息。GNMF通过构造一个k最近邻(kNN)图来对几何结构进行编码。因为一个简单图中的一条边只能连接两个顶点，GNMF只考虑了两个样本之间的成对关系，而忽略了样本间的高维结构。为了探索样本之间的高阶关系，Zeng等人通过构建一个编码更多样本之间关系的超图，开发了一个超图正则化 [8]，因为超图可以连接两个以上的顶点，HNMF可以找出数据的高阶关系。

上述方法在某种程度上确实改进了标准的NMF。然而，由于原始数据中所包含的潜在噪声会影响聚类和分类的性能。当数据包含噪声或离群值时，特征和样本的误差都是平方的，因此有一些噪声特征或一些离群值的误差较大将支配目标函数。Kong等人提出了鲁棒非负矩阵分解算法 [9]，克服了标准NMF算法对噪声和异常值敏感的缺点。

为了减轻噪声或异常值的影响，处理高维、包含噪声和异常值的数据。整合L_2,1范数和超图正则化的优点，给出了一种基于L_2,1范数的超图正则化非负矩阵分解。在COIL20和ORL数据集上的实验结果表明，L_2,1HNMFL方法在聚类精度和归一化互信息上优于四种具有代表性的方法k-means、NMF、L_2,1NMF和GNMF。在第二节中，简要回顾了标准NMF及其一些具有代表性的变体。在第三节中，详细描述了L_2,1HNMFL方法并给出了有效的迭代更新规则。第四节展示了在数据集上的实验结果。最后，在第五节中简要地总结了这篇论文。

2. 预备知识

给定的非负数据矩阵 $X=\left(x_1,x_2,\cdots ,x_n\right)$，$x_i\in R^m$ 表示一个数据点。标准NMF定义为：

$\underset{U,V}{\min }{\Vert X-UV\Vert }_F^2,U\ge 0,V\ge 0$

上述问题通常通过迭代更新算法来解决，其中U和V的迭代更新方法如下：

$u_{ik}\leftarrow u_{ik}\frac{{\left(X{V}^{\text{T}}\right)}_{ik}}{{\left(UV{V}^{\text{T}}\right)}_{ik}}$,

$v_{ki}\leftarrow v_{ki}\frac{{\left(U^{\text{T}}X\right)}_{kj}}{{\left(U^{\text{T}}UV\right)}_{kj}}$.

为了提高NMF的鲁棒性，Kong等人提出L_2,1NMF算法，能够降低数据集中噪声和异常值的影响。目标函数定义为：

$\underset{U,V}{\min }{\Vert X-UV\Vert }_{2,1},U\ge 0,V\ge 0$

其中L_2,1范数定义为 ${\Vert Y\Vert }_{2,1}={\displaystyle \underset{i=1}{\overset{m}{\sum }}\sqrt{{\displaystyle \underset{j=1}{\overset{n}{\sum }}{Y}_{ij}^2}}}={\displaystyle \underset{i=1}{\overset{m}{\sum }}{\Vert Y_i,:\Vert }_2}$

迭代更新规则为

$u_{ik}\leftarrow u_{ik}\frac{{\left(XG{V}^{\text{T}}\right)}_{ik}}{{\left(UVG{V}^{\text{T}}\right)}_{ik}}$,

$v_{kj}\leftarrow v_{kj}\frac{{\left(U^{\text{T}}XG\right)}_{kj}}{{\left(U^{\text{T}}UVG\right)}_{kj}}$.

为了保持数据的局部几何结构，Cai等人提出了GNMF，目标函数为

$\underset{U\ge 0,V\ge 0}{\min }{\Vert X-UV\Vert }_F^2+\lambda Tr\left(VL{V}^{\text{T}}\right)$

其中 $L=D-W$ 是图拉普拉斯矩阵。W是图的权重矩阵，D是对角矩阵， $D_{ii}={\displaystyle \underset{j}{\sum }{W}_{ij}}$。

因为一个简单图中的一条边只能连接两个顶点。为了考虑样本之间的高维结构，Zeng等人提出了超图正则化。下面将简单地介绍超图的一些基本定义 [10]：

给定一个超图 $G=\left(A,E,S\right)$，其中A表示超图中所有顶点的集合，E表示所有超边的集合，任意一个超边 $e\in E$ 是顶点集A的一个子集。S是超图的权重矩阵，它是一个对角矩阵，元素 $s\left(e\right)$ 表示超边e权重

的大小。把一个顶点和一条超边的关系记为关联矩阵H，则关联矩阵H表示为 $H\left(a_i,e_j\right)=\{\begin{array}{cc}0& a_i\notin e_j\\ 1& a_i\in e_j\end{array}$。

对于任意顶点 $a\in A$，顶点a的度定义为 $d\left(a\right)={\displaystyle \underset{e\in E}{\sum }s\left(a\right)H\left(a,e\right)}$，对于超边 $e\in E$，它的度定义为 $\delta \left(e\right)={\displaystyle \sum _{e\in E}H\left(a,e\right)}$。超图的权重矩阵为S，其元素 $s_{ij}$ 表示为 $s_{ij}={\displaystyle \underset{e\in E}{\sum }{\displaystyle \underset{\left(i,j\right)\in e}{\sum }\frac{s\left(e\right)}{\delta \left(e\right)}}}$。超图拉普拉斯矩阵 $L_{Hyper}=D_a-B$，$B=HS{D}_e^{-1}{H}^{\text{T}}$。

3. 基于L_2,1范数的超图正则化非负矩阵分解

在这一部分中，给出了基于L_2,1范数的超图正则化非负矩阵分解算法(L_2,1HNMFL)，不仅可以克服数据中噪声和异常值的影响，还可以保持数据集的内在几何结构，得到更加准确的聚类效果。下面先介绍目标中正则化项。

3.1. 目标函数

首先介绍坐标编码的概念 [11]。

定义：坐标编码是一对 $\left(\gamma ,C\right)$，$C\in R^d$ 是一组锚点， $\gamma$ 是 $x\in R^d$ 到 ${\left[{\gamma }_v\left(x\right)\right]}_{v\in C}\in R^{\left|C\right|}$ 的映射。得到物

理近似式： $\gamma \left(x\right)={\displaystyle \underset{v\in C}{\sum }{\gamma }_v}\left(x\right)v$。

根据上式，基矩阵U的列可以看作是一组锚点，而数据集中的每个数据点都可以用锚点的线性组合来表示。编码矩阵V的列包含了数据点相对于锚点的坐标。为了获得稀疏编码，每个数据点都应该表示为只有几个附近锚点的线性组合，即每个数据点应该只足够接近几个锚点。这可以通过引入局部坐标约束来实现，局部坐标约束可以表述为以下问题：

$J_1={\displaystyle \underset{k=1}{\overset{K}{\sum }}\left|v_{ki}\right|}{\Vert u_k-x_i\Vert }^2$

将上式整合到鲁棒的NMF中，并且增加超图正则项，目标函数定义为：

$J_{L_{21}HNMFL}={\Vert X-UV\Vert }_{2,1}+\alpha {\displaystyle \underset{i=1}{\overset{N}{\sum }}{\displaystyle \underset{k=1}{\overset{K}{\sum }}\left|v_{ki}\right|}}{\Vert u_k-x_i\Vert }^2+\lambda Tr\left(V{L}_{Hyper}{V}^{\text{T}}\right)$ (1)

s.t. $U=\left[u_1,\cdots ,u_K\right]\in R^{M\times K}>0$,$V=\left[v_1,\cdots ,v_N\right]\in R^{K\times N}>0$.

3.2. 更新规则

下面给出更新规则和推导过程，经过简单运算，(1)式可以改写为：

$J_{L_{21}HNMFL}={\Vert X-UV\Vert }_{2,1}+\alpha {\displaystyle \underset{i=1}{\overset{N}{\sum }}{\Vert \left(x_i{1}^{\text{T}}-U\right){\Lambda }_i^{1/2}\Vert }_F^2}+\lambda Tr\left(V{L}_{Hyper}{V}^{\text{T}}\right)$

其中 $\alpha$ 和 $\lambda$ 是大于0的常数。目标函数的第二项和第三项分别是局部坐标约束项和超图正则化项。 ${\Lambda }_i=diag\left(\left|V_i\right|\right)\in R^{K\times K}$，根据迹的知识，目标函数可以写为：

$\begin{array}{c}{J}_{L_{21}HNMFL}=2Tr\left(X^{\text{T}}IX-2X^{\text{T}}IUV+V^{\text{T}}{U}^{\text{T}}IUV+\mu {\displaystyle \underset{i=1}{\overset{N}{\sum }}\left(x_i{1}^{\text{T}}{\Lambda }_{i}1x_i^{\text{T}}-2x_i{1}^{\text{T}}{\Lambda }_i{U}^{\text{T}}+U{\Lambda }_i{U}^{\text{T}}\right)}\right)\\ +\lambda Tr\left(V{L}_{Hyper}{V}^{\text{T}}\right)\end{array}$

其中， $I_{ii}=1/2\sqrt{{\displaystyle \underset{j=1}{\overset{n}{\sum }}{\left(X-UV\right)}_{ij}^2}}$，$L_{Hyper}=D_a-B$，$B=HS{D}_e^{-1}{H}^{\text{T}}$。

设 ${\psi }_{ik}$ 和 ${\varphi }_{kj}$ 分别是 $u_{ik}$ 和 $v_{kj}$ 的拉普拉斯乘子。 $\Psi =\left[{\psi }_{ik}\right]$ 和 $\Phi =\left[{\varphi }_{kj}\right]$ 是对应的拉普拉斯矩阵，则拉普拉斯扩展式L为：

$L={\Vert X-UV\Vert }_{2,1}+\alpha {\displaystyle \underset{i=1}{\overset{N}{\sum }}{\Vert \left(x_i{1}^{\text{T}}-U\right){\Lambda }_i^{1/2}\Vert }_F^2}+\lambda Tr\left(V{L}_{Hyper}{V}^{\text{T}}\right)-Tr\left(\Psi U^{\text{T}}\right)-Tr\left(\Phi V^{\text{T}}\right)$

令 $\frac{\partial L}{\partial U}=0$ 和 $\frac{\partial L}{\partial V}=0$，得到：

$\Psi =-2IX{V}^{\text{T}}+2IUV{V}^{\text{T}}+\mu {\displaystyle \underset{i=1}{\overset{N}{\sum }}\left(-2x_i{1}^{\text{T}}{\Lambda }_i+2U{\Lambda }_i\right)}$

$\Phi =-2U^{\text{T}}IX+2U^{\text{T}}IUV+\mu \left(C-2U^{\text{T}}X+D\right)+2\lambda V{L}_{Hyper}$

定义列向量 $C={\left(c,\cdots ,c\right)}^{\text{T}}$。设 $C={\left(c,\cdots ,c\right)}^{\text{T}}$ 是一个 $K\times N$ 矩阵，其行为 $c^{\text{T}}$。定义列向量 $p=diag\left(U^{\text{T}}U\right)\in R^K$。设 $P=\left(p,\cdots ,p\right)$ 为一个 $K\times N$ 矩阵，其列为p。根据上式，关于L_2,1HNMFL算法的迭代公式为：

$u_{jk}\leftarrow u_{jk}\frac{{\left(IX{V}^{\text{T}}+\mu {\displaystyle \underset{i=1}{\overset{N}{\sum }}\left(x_i{1}^{\text{T}}{\Lambda }_i\right)}\right)}_{jk}}{{\left(IUV{V}^{\text{T}}+\mu {\displaystyle \underset{i=1}{\overset{N}{\sum }}U{\Lambda }_i}\right)}_{jk}}$, (2)

$v_{ki}\leftarrow v_{ki}\frac{{\left(2U^{\text{T}}IX+2\mu U^{\text{T}}X+2\lambda VHS{D}_e^{-1}{H}^{\text{T}}\right)}_{ki}}{{\left(2U^{\text{T}}IUV+\mu C+\mu D+2\lambda V{D}_a\right)}_{ki}}$. (3)

4. 实验

4.1. 数据集的描述

ORL数据集：ORL人脸数据库共由总共400张人脸图像组成，为40个个体在不同光照条件、有/没有眼镜和不同面部表情的情况下的10张灰度人脸图像。所有图像的分辨率都被调整为32 × 32。

COIL20数据集：数据集由20个物体的1440张图像组成，灰度大小为32 × 32。每个物体有72张不同的图像，所有的图像都是黑色的背景。

4.2. 比较的方法

为了验证算法的有效性，与四种具有代表性的方法k-means、NMF、L₂₁NMF和GNMF进行比较。

4.3. 实验设计

在实验中，使用了两个通常使用的测量方法来评估算法的效果，分别是聚类精度(AC)和归一化互信息(NMI) [12]。

聚类精度(AC)定义为：

$\text{AC}=\frac{{\displaystyle \underset{i=1}{\overset{n}{\sum }}\delta \left(gn{d}_i,map\left(r_i\right)\right)}}{n}$

其中 $gn{d}_i$ 是数据集给出的标签， $r_i$ 是聚类算法提供的标签， $map\left(r_i\right)$ 是将 $r_i$ 映射到等价标签的排列映射函数， $\delta \left(x,y\right)$ 是delta函数，如果 $x=y$，其值为1，否则为0。

互信息(NMI)可以衡量两个集群集之间的相似性，在聚类应用中得到了广泛的应用。设C和 $C^{\prime }$ 为两组集，然后将MI定义为

$\text{MI}\left(C,C^{\prime }\right)={\displaystyle \underset{c_i\in C,{c^{\prime }}_j\in C^{\prime }}{\sum }p\left(c_i,{c^{\prime }}_j\right)\log \frac{P\left(c_i,{c^{\prime }}_j\right)}{p\left(c_i\right)\cdot p\left({c^{\prime }}_j\right)}}$

其中， $p\left(c_i\right)$ 和 $p\left({c^{\prime }}_j\right)$ 分别表示属于集群C和集群 $C^{\prime }$ 的样本的概率。 $P\left(c_i,{c^{\prime }}_j\right)$ 表示一个样本同时属于C和 $C^{\prime }$ 的联合概率。然后将NMI定义为：

$\text{NMI}\left(C,C^{\prime }\right)=\frac{\text{MI}\left(C,C^{\prime }\right)}{\max \left(H\left(C\right),H\left(C^{\prime }\right)\right)}$

其中 $H\left(C\right)$ 和 $H\left(C^{\prime }\right)$ 分别表示C和 $C^{\prime }$ 的信息熵。

在实验中，在一定范围内改变了参数，以寻找所给出的方法的最佳性能，正则化参数 $\mu$ 和 $\lambda$ 在{0.001、0.01、0.1、0、1、10、100、1000}中进行选择。所有方法对上述数据集的聚类结果如表1~4所示。对于每个给定的聚类数k，从数据集中随机选择的不同类重复10次测试运行，并聚类性能的方差和平均值。

表1. COIL20上的聚类准确度(AC)

表2. COIL20上的归一化互信息(NMI)

表3. ORL上的聚类准确度(AC)

表4. ORL上的归一化互信息(NMI)

4.4. 实验结果与分析

通过以上两个数据集上的实验结果进行分析，可以得出：

1) k-means的聚类性能不如其他方法。这表明，通过其他方法获得的高维样本的低维表示在数据聚类中是有用的，并可以提高聚类性能。2) 在大多数情况下，GNMF的性能优于NMF，这验证了几何结构在矩阵分解算法中的重要作用。3) 由于L_2,1HNMFL算法是利用局部约束来保持几何结构，并利用L_2,1范数来保持稀疏性，故L_2,1HNMFL算法优于所有其他算法。4) 与其他方法相比，给出的L_2,1HNMFL算法在测试的AC和NMI值上都获得最好的聚类性能。这表明，通过将超图的构造和局部约束合并到一个统一的框架中，L_2,1HNMFL算法比其他方法具有更强的判别能力。

5. 结语

新方法给出了一个基于超图正则化和局部约束的聚类模型，可以有效地处理高维、稀疏和有噪声的数据。在COIL20数据集和ORL数据集上，聚类精度分别提高了6.90%和4.83%，归一化互信息分别提高了3.08%和2.30%。

文章引用

文学春. 基于_2,1范数的超图正则化非负矩阵分解
Hypergraph Regular Nonnegative Matrix Factorization Based on _2,1 Norms[J]. 应用数学进展, 2023, 12(01): 451-458. https://doi.org/10.12677/AAM.2023.121048

参考文献