Graph regularization sparse coding with adaptive neighbour

YU Qinru; LU Guifu; LI Hua

doi:10.15983/j.cnki.jsnu.2023029

Journal of Shaanxi Normal University(Natural Science Edition) >

2023 , Vol. 51 >Issue 5: 75 - 83

DOI: https://doi.org/10.15983/j.cnki.jsnu.2023029

Graph regularization sparse coding with adaptive neighbour

YU Qinru ¹ ,
LU Guifu ^,²^,^* ,
LI Hua ²

Expand

¹ Wuhu Institute of Technology, Wuhu 241000, Anhui, China
² School of Computer and Information, Anhui Polytechnic University, Wuhu 241009, Anhui, China

Received date: 2022-01-20

Online published: 2023-09-28

Fold

Abstract

In the GraphSC algorithm, the Laplacian graph is pre-defined and fixed, and will not participate in the subsequent learning process of the dictionary and sparse coding, the pre-defined Laplacian graph isn’t the most suitable. Graph regularization sparse coding with adaptive neighbour algorithm (GraphSCAN) is proposed to solve the problem.The algorithm uses an adaptive method to construct a suitable local Laplacian graph, and then adds it to the SC objective function. GraphSCAN incorporates graph construction and sparse coding into a unified framework, so that graph construction and sparse coding operations are iteratively performed simultaneously. The experimental results of image clustering on CMU face data and COIL20 data support the effectiveness of the GraphSCAN algorithm.

Key words： graph regularization; sparse coding; image clustering; adaptive clustering

Cite this article

YU Qinru , LU Guifu , LI Hua . Graph regularization sparse coding with adaptive neighbour[J]. Journal of Shaanxi Normal University(Natural Science Edition), 2023 , 51(5) : 75 -83 . DOI: 10.15983/j.cnki.jsnu.2023029

在图像处理过程中,图像本身的表示形式是影响处理结果的关键因素。稀疏表示已被证明是一种极有效的图像表示算法^[1]。近年来,为了实现稀疏表示,研究人员已经开发出例如稀疏主成分分析(PCA)^[2]、稀疏非负矩阵分解(NMF)^[3]等多种算法。作为稀疏表示最典型的方法之一,稀疏编码(spares coding,SC)在机器学习、信号处理和神经科学^[4⇓⇓-7]等领域中得到了广泛的关注。

SC是利用过完备字典来线性表示图像的编码过程,其中的非零元素只占所有元素的极小部分,体现了编码的稀疏性。SC具有众多优点,如:稀疏表示时其每个数据点都表示为少量基本矢量的线性组合,表示方式更简洁;编码状的稀疏表示可以允许数据快速检索等。SC算法目前已被应用于如图像恢复^[8]、信号分类^[9]、人脸识别^[10]和图像分类^[11-12]等多个领域中。

近年来,研究人员针对SC的部分缺点提出了改进算法。对于SC计算复杂度过高的问题,文献[10]提出了一种迭代的软阈值方法,该方法在负梯度方向上取Barzilai-Borwein步长,然后将软阈值算子应用于结果,提升了SC的计算速率。 Lee等^[13]提出了一种特征符号搜索方法,将不可微L₁范数问题简化为L₁正则化最小二乘问题,从而加快了优化过程。在传统方法中,SC的字典选择也是影响算法效果的一个关键因素,然而其字典一般是从标准库中选择的^[14],甚至是从随机矩阵^[15]中生成的。因此,有些学者试图通过为稀疏编码设计一个更合适的字典来提升SC的性能。Aharon 等^[16]提出的K-SVD方法不同于之前利用标准库获得数据稀疏表示的算法,该算法使用正交匹配追踪算法(orthogonal matching pursuit, OMP)或基追踪算法(basis pursuit, BP),作为其学习词典迭代过程的一部分。还有些学者致力于将稀疏编码与经典机器学习方法相结合以提出新的理论框架。文献[17]将线性判别分析(linear discriminant analysis, LDA)与稀疏表示相结合提出了稀疏主成分判别分析的方法(sparse linear discriminant analysis,SDA),该方法可以通过重建特性、辨别力和稀疏性来进行分类。文献[11]提出了一种新的判别方法,称为监督字典学习算法(supervised dictionary learning,SDL),有效地利用图像分类任务中相应的稀疏信号分解去学习共享字典和判别模型。

以上研究都在克服原始稀疏编码的不同缺点,但是都没有考虑到数据中潜在的几何结构。Kavukcuoglu等^[18]提出了几种稀疏编码方法的变体,这些算法通过增加一些稀疏编码系数的附加约束来捕获数据中的结构,即它们可以通过添加额外的空间一致约束来学习,以获得局部不变的稀疏表示。Gao等^[19]首次提出了使用流形学习算法学习数据几何结构的方法,但未明确提出详细的优化方案,所提方法的性能仅在图像分类任务上进行了评估。Zheng等^[20]在文献[19]的基础上提出了一种新的算法,称为图正则化稀疏编码(graph regularization sparse coding,GraphSC),该算法明确考虑了数据的局部几何结构。 GraphSC通过构建一个近邻图来编码数据中的几何信息,并使用谱图理论中的图拉普拉斯算子作为光滑算子来保留局部流形结构。与传统的SC算法相比,GraphSC具有更强大的分类能力。基于文献[20]的研究,Gao等^[21]基于直方图交点的度构建相似度图,利用超图捕获样本之间的高阶关系,进一步提升了GraphSC的性能。此后,Sha等^[22]提出将低秩表示^[23](low-rank representation, LRR)引入图正则化的处理过程,并就此提出了低秩正则化稀疏编码算法(low-rank regularized spares coding,LogSC)。由于添加了低秩约束,LogSC在部分任务中获得了较GraphSC更优秀的性能。

然而,GraphSC及其改进方法中的拉普拉斯图都是预先定义且固定不变的,并不会参与之后对于字典与稀疏编码的学习过程,而预先定义的拉普拉斯图往往不是最合适的。针对这个问题,我们对GraphSC算法进行了改进,提出了自适应正则化稀疏编码(graph regularization sparse coding with adaptive neighbour,GraphSCAN)算法。我们假设数据指向较小的距离代表更可能成为邻居,因此 GraphSCAN可以从自适应性分解的结果中学习局部流形结构,并重新构造以保留精炼的局部结构,根据每个数据点的本地连通性选择自适应近邻(adaptive neighbor, AN)以获得相似度图,然后将ANs正则化约束合并到GraphSC中。GraphSCAN将图的构建和稀疏编码纳入到统一框架中,使得内部局部结构学习的过程和图稀疏编码的过程同时进行,并最终提高了GraphSC的性能。

1 相关工作

1.1 稀疏编码(SC)

SC的目的是对于给定的一个数据矩阵,找到一组捕获高级语义的基础向量(即字典),并输出数据的稀疏表示。

给定一个数据矩阵X∈[x₁,x₂,…,x_n]∈Rⁿ^×^m,X的每一列都是样本矢量。令A=[a₁,a₂,…,a_k]∈Rⁿ^×^k为字典矩阵,其中a_i表示字典中的基础向量。令E=[e₁,e₂,…,e_m]∈R^k^×^m为系数矩阵,其中每一列都是数据点的稀疏表示。每个数据点都可以表示为字典中基向量的稀疏线性组合。

稀疏编码的目标函数定义如下:

(1)

m i n s . t . ‖ a i ‖ 2 ≤ c, i = 1,2, …, k

‖X-AE

‖ F 2

+β

∑ i = 1 m

f(e_i)。

式中:‖‖_F表示矩阵的F范数;f是度量的稀疏性函数,其最直接的选择是e的L₀范数。然而,当固定字典B时,系数e的极小化问题被证明是一个NP困难问题^[24]。因此,可以转而讨论这个问题的近似或松弛。近似求解该问题有2种常用的方法,即匹配追踪(matching pursuit,MP)^[25]和基追踪(basis pursuit, BP)^[26]。MP以贪心的方式一次只寻找一个条目的解,而BP用L₁范数代替L₀范数对原问题进行凸松弛。

因此,由文献[13,26-27],可令f为f(e_i)=‖e_i‖₁,此时目标函数化为

(2)

m i n s . t . ‖ a i ‖ 2 ≤ c, i = 1,2, …, k

‖X-AE

‖ F 2

+β

∑ i = 1 m

‖e_i‖₁。

由于(2)式中的目标函数可能仅A或E是凸的,2个变量不能同时为凸。因此,可以通过固定一个变量、最小化另一个变量来迭代优化目标函数(2)。

1.2 图正则化稀疏编码(GraphSC)

GraphSC将拉普拉斯图引入SC算法,并使用图拉普拉斯正则项来保留数据局部流形结构。

对于给定一组n维数据点x₁,x₂,…,x_m,构造一个有m个顶点的最近邻图G,其中每个顶点代表一个数据点。令W为图的权重矩阵,若x_i是x_j的最近邻或者x_j是x_i的最近邻,那么W_ij=1,否则W_ij=0。定义x_i的度为d_i=

∑ j = 1 m

W_ij,且D=diag(d₁,d₂,…,d_m)。

图正则化目标函数 ^[20]可表示为

(3)

12 ∑ i, j = 1 m

(e_i-e_j)²W_ij=tr(E^TLE),

式中L是图拉普拉斯矩阵,L=D-S。由(2)、(3)式可得GraphSC的目标函数为

(4)$\begin{aligned}\min_{\begin{array}{c}\mathrm{s.t.~}\lambda\geqslant0\parallel a_i\parallel^2\leqslant c,i=1,2,\cdots,k\\\end{array}}\parallel X-AE\parallel_{\mathcal{F}}^2+\\\beta\sum_{i\operatorname{=}1}^m\parallel\boldsymbol{e}_i\parallel_1+\lambda\operatorname{tr}(\boldsymbol{E}^\mathrm{T}\boldsymbol{L}\boldsymbol{E})_0\end{aligned}$

2 自适应图正则化稀疏编码算法及其求解

利用数据的局部几何结构,GraphSC算法提升了SC算法的计算能力。但GraphSC使用的拉普拉斯图会在全局计算前预先定义且固定不变,并不参与之后对于字典与稀疏编码的学习过程。我们提出自适应方图正则化稀疏编码的算法(graph regularization sparse coding with adaptive neighbour,GraphSCAN)对GraphSC所存在的这个问题进行了改进。

2.1 GraphSCAN的算法模型

设输入的原始数据集为X,X中的任意一数据点x_i都有所有数据点{x₁,x₂,…,x_n}可以作为近邻与之连接,连接的概率为s_ij。基于数据点间的欧几里得距离构造邻域矩阵,距离越小则成为最近邻的可能性越大。本文算法的求解形式如下:

(5)$\begin{array}{l}\min _{\text {s.t. } \lambda \geqslant 0\left\|\boldsymbol{a}_{i}\right\|^{2} \leqslant c, \boldsymbol{s}_{i}^{\mathrm{T}} 1=1,0 \leqslant s_{i} \leqslant 1}\|\boldsymbol{X}-\boldsymbol{A} \boldsymbol{E}\|_{\mathrm{F}}^{2}+ \\\alpha \sum_{j=1}^{n}\left(\left\|\boldsymbol{x}_{i}-\boldsymbol{x}_{j}\right\|_{2}^{2} s_{i j}+\gamma s_{i j}^{2}\right)+ \\\beta \sum_{i=1}^{n}\left\|\boldsymbol{e}_{i}\right\|_{1}+\lambda \operatorname{tr}\left(\boldsymbol{E}^{\mathrm{T}} \boldsymbol{L}_{S} \boldsymbol{E}\right) 。 \\\end{array}$。

(5)式第1项对原始数据集X求其字典及其稀疏编码,其中矩阵X为原始数据集,A代表字典阵,E代表其稀疏阵。

(5)式第2项是自适应正则化函数,使用其完成自适应相似矩阵的构造^[28]。其中α和γ均为正则化参数,s_i∈Rⁿ^×1表示向量,其第j个元素为s_ij。在所有x_i有相同的概率即

1 n

时,第二项可写作

(6)

m i n s T i 1 = 1,0 ≤ s i ≤ 1 ∑ j = 1 n

(‖x_i-x_j

‖ 22

s_ij+γ

s i j 2

式中γ是正则化参数。因此,可以将(6)式重新表示为

(7)

m i n s T i 1 = 1,0 ≤ s i ≤ 1 s i + 1 2 γ d X i 22

。

通过求解(7)式获得的矩阵S∈Rⁿ^×ⁿ,可被视为相似度矩阵^[29^-^30]。可通过以下步骤来表示数据平滑度:

(8) \begin{array}{c}\frac{1}{2} \sum_{i, j=1}^{n}\left\|\boldsymbol{e}_{i}-\boldsymbol{e}_{j}\right\|{ }_{2}^{2} s_{i j}=\sum_{i, j=1}^{n} \boldsymbol{e}_{i} s_{i j} \boldsymbol{e}_{i}^{\mathrm{T}}-\sum_{i, j=1}^{n} \boldsymbol{e}_{i} s_{i j} \boldsymbol{e}_{j}^{\mathrm{T}}= \\\sum_{i, j=1}^{n} \boldsymbol{e}_{i}\left(\boldsymbol{D}_{s}\right)_{i i} \boldsymbol{e}_{i}^{\mathrm{T}}-\sum_{i, j=1}^{n} \boldsymbol{e}_{i} s_{i j} \boldsymbol{e}_{j}^{\mathrm{T}}= \\\operatorname{tr}\left(\boldsymbol{E}^{\mathrm{T}} \boldsymbol{D}_{S} \boldsymbol{E}\right)-\operatorname{tr}\left(\boldsymbol{E}^{\mathrm{T}} \boldsymbol{W}_{S} \boldsymbol{E}\right)= \\\operatorname{tr}\left(\boldsymbol{E}^{\mathrm{T}} \boldsymbol{L}_{S} \boldsymbol{E}\right) 。\end{array}

(5)式第3项是度量第一项中稀疏矩阵E稀疏度的函数,设f(e_i)=‖e_i‖₁作为度量函数。

(5)式第4项是局部图拉普拉斯约束函数,使用其增强传统低秩表示模型的局部性和稀疏性。其中L_S是S_i的拉普拉斯矩阵,L_S=D_S-W_S,tr( )表示矩阵的迹。

2.2 GraphSCAN的算法求解

本节提出求解GraphSCAN的更新算法,该算法通过固定其他变量更新一个变量的值来优化目标,此过程重复直到收敛。

2.2.1 固定A、E更新S

观察(5)式不难发现,在固定A、E时更新S,最小化(5)式可等价于解决下式:

(9)

m i n s ∑ i, j n

(‖x_i-x_j

‖ 22

s_ij+γ

s i j 2

)+βtr(E^TL_SE),s.t.

s T i

1=1,0≤s_i≤1,

式中ε=

λ α

。由(5)式结合(9)式有

(10)

m i n s ∑ i, j = 1 n

（‖x_i-x_j

‖ 22

s_ij+γ

s i j 2

12

ε‖e_i-e_j

‖ 22

s_ij）,s.t.

s T i

1=1,0≤s_i≤1。

可通过逐个求解的方式求解(10)式,此时(10)式等价于

(11)$\begin{array}{l} \min _{s_{i}} \sum_{i, j=1}^{n}\left(\left(\left\|\boldsymbol{x}_{i}-\boldsymbol{x}_{j}\right\|_{2}^{2}+\right.\right. \\\left.\left.\frac{1}{2} \varepsilon\left\|\boldsymbol{e}_{i}-\boldsymbol{e}_{j}\right\| \frac{2}{2}\right) s_{i j}+\gamma s_{i j}^{2}\right), \\\text { s. t. } \boldsymbol{s}_{i}^{\mathrm{T}} 1=1,0 \leqslant \boldsymbol{s}_{i} \leqslant 1 。\end{array}$

令

d i j X

=‖x_i-x_j

‖ 22

d i j E

12

‖e_i-e_j

‖ 22

,且d_i∈Rⁿ^×1,第j个元素为d_ij=

d i j X

+ε

d i j E

,将其代入(11)式可得

(12)

m i n s T i 1 = 1,0 ≤ s i ≤ 1 s i + 1 2 γ d i X 22

。

设ζ和η≥0为拉格朗日乘子,则(12)式的拉格朗日函数为

(13)R(s_i,η,ζ_i)=

12 s i + 1 2 γ i d i X 22

-η(

s T i

1-1)-

ζ T i

s_i。

根据KKT条件^[31],满足s_ij≥0,最优解可以定义为

(14)s_ij=

- 1 2 γ i d i j X + η

{

d i 1 x

d i 2 x

,…,

d i n x

}由小到大表示。如果最优s_i只有k个非零元素,则根据(14)式可知s_ik>0且s_i_,_k₊₁=0。因此,有

(15)

- 1 2 γ i d i k X + η > 0, - 1 2 γ i d i, k + 1 X + η ≤ 0 。

由(15)式和

s T i

1=1的约束,有

(16)

∑ j = 1 k - 1 2 γ i d i j X + η

=1⇒η=

1 k

1 2 k γ i ∑ j = 1 k d i j X

。

结合(15)和(16)式,可得

(17)

k 2 d i k X

12 ∑ j = 1 k d i j X

<γ_i≤

k 2 d i, k + 1 X

12 ∑ j = 1 k d i j X

。

为了获得具有k个非零值的最优s_i,可以将γ_i设置为

(18)γ_i=

k 2 d i, k + 1 X

12 ∑ j = 1 k d i j X

。

为了便于计算,可以将整体γ设置为γ₁,γ₂,…,γ_n的均值,即

(19)γ=

1 n ∑ i = 1 n k 2 d i, k + 1 X - 12 ∑ j = 1 k d i j X

。

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

2.2.2 固定S、A更新E

在固定S、A时更新E,求解(5)式即等同于求解下式:

(20)$\begin{array}{l}\min \|\boldsymbol{X}-\boldsymbol{A} \boldsymbol{E}\|_{\mathrm{F}}^{2}+\beta \sum_{i=1}^{n}\left\|\boldsymbol{e}_{i}\right\|_{1}+ \\\lambda \operatorname{tr}\left(\boldsymbol{E}^{\mathrm{T}} \boldsymbol{L}_{S} \boldsymbol{E}\right) 。\end{array}$

由于当s_i包含0时,(20)式中的L₁正则化问题是不可微的,因此本文选择采用基于坐标下降的优化方法来求解。以向量形式重写后,‖X-AE

‖ F 2

可写为

(21)

∑ i = 1 n

‖x_i-Ae_i‖²。

拉普拉斯正则项tr(E^TL_SE)可写为

(22)tr(E^TL_SE)=tr

∑ i, j = 1 n L i, j e i e T j

∑ i, j = 1 n

L_ij

e T J

e_i=

∑ i, j = 1 n

L_ij

e T i

e_j。

结合(21)、(22)式可重写如下:

(23)min‖x_i-Ae_i

‖ F 2

+β

∑ i = 1 n

‖e_i‖₁+λ

∑ i, j = 1 n

L_ij

e T i

e_j。

在更新e_i时,其他向量{e_j}_j₌₁是固定的,因此可得

(24)

m i n e i

f(e_i)=‖x_i-Ae_i

‖ F 2

+β

∑ j = 1 k

e i (j)

|+λL_ij

e T i

e_j+

e T i

h_i,

式中h_i=2α

∑ j ≠ i L i j e j

且

e i (j)

是e_i的第j个系数。通过参考文献[22]中提出的有关稀疏编码的求解过程,可以将(24)式的求解过程总结如下。

定义h(s_i)=‖x_i-Ae_i

‖ F 2

+λL_ij

e T i

e_j+

e T i

h_i,

∇ i (j)

|e_i|作为e_i的第j个系数的可微分值。因此,实现f(s_i)最优值的最优条件可改写为

(25)

∇ i (j) h e i | + β s i g n (e i (j)) = 0, 若 | e i | > 0, | ∇ i (j) h e i | | ≤ β, 若 e i (j) = 0 。

当其不符合最佳条件时,最佳子梯度

∇ i (j)

f(e_i)为

(26)

e i (j) = 0, ∇ i (j) h e i | + β s i g n (e i (j)) = 0, ∇ i (j) h e i | > β, s i g n (e i (j)) = - 1, ∇ i (j) h e i | < - β, s i g n (e i (j)) = 1 。

通过替换|

e i (j)

|为

e i (j)

(

e i (j)

>0),-

e i (j)

(

e i (j)

<0)或0(

e i (j)

=0)去掉L₁范数的约束。此时,原问题可以简化为标准的无约束二次优化问题(QP)并通过线性方法求解。由此,可得算法1以描述求解(20)式的详细算法过程。

算法1 图正则化稀疏码算法
输入:m数据点的数据集X,字典A,图拉普拉斯矩阵L,参数λ、β。
输出:最优系数矩阵E^=[ $e 1 $ , $e 2 $ ,…, $e m $ ]。
步骤1 对所有满足1≤i≤m的i do;
步骤2 初始化:e_i= $0 →$ ,θ= $0 →$ ,Π=∅,其中θ_j∈{1,0,-1}表示sign( $e i (j)$ );
步骤3 从e_i中选择零系数、j=argmax_j $∇ i (j)$ h\|e_i\|的项。仅在提高(25)式局部结果的情况下改变e_i;
步骤4
1)定义 $A^$ 是A的子矩阵,它仅包含与活动集相对应的列。令 $e^i$ 和 $h^i$ 为e_i、h_i的子向量, $θ^$ 为与活动集相对应的θ。
2)计算得出结果。
无约束QP:
$m i n e i$ g( $e^i$ )=‖x_i- $A^e^i ‖ F 2$ +β $θ^T e^i$ +
(27) λL_ii $e^T i$ e_i+ $e^T i$ h_i。
令 $∂ g (e^i) ∂ e^i$ =0,可以在当前活动集下获得e_i的最优值
(28) $e^i n e w$ =( $A^T A^$ +γL_iiI)^-1 $A^T x i - (β θ^+ h^) 2$ ,
式中I是单位矩阵。
3)在从 $e^i$ 到 $e^i n e w$ 的闭合线段上执行离散线搜索。
4)从活动集合中去除 $e^i$ 的零系数并更新θ=sign(e_i)。
步骤5 检查最优性条件步骤
1)非零系数的最优性条件: $∇ i (j)$ h(e_i)+βsign( $e i (j)$ )=0,∀ $e i (j)$ ≠0,如果不满足条件1),转到Step4(不进行任何操作);否则判断条件2)。
2)零系数的最优条件:\| $∇ i (j)$ h(e_i)\|≤β,∀ $e i (j)$ =0,如果不满足条件(2),转到Step3;否则返回e_i作为解决方案,以 $e i *$ 表示。
步骤6 结束

2.2.3 固定S、E更新A

在固定S、E时更新A,最小化(4)等同于求解下式:

(29)

m i n A

‖X-AE

‖ F 2

,s.t.‖a_i‖²≤c,i=1,2,…k。

使用拉格朗日对偶法对(29)式进行求解。令ε=[ε₁,ε₂,…,ε_k]为与不等式约束相关联的拉格朗日乘数,则拉格朗日对偶函数为

(30)g(ε)=inf_BL(A,ε)=inf_B(‖X-AE

‖ F 2

∑ i = 1 k

ε_i(‖e_i‖²-c))。

令Λ为k×k的对角矩阵,其对角线数Λ_ii=λ_i。那么L(A,ε)可写作

(31)$\begin{array}{l}L(\boldsymbol{A}, \boldsymbol{\varepsilon})=\|\boldsymbol{X}-\boldsymbol{A} \boldsymbol{E}\|{ }_{\mathrm{F}}^{2}+ \\\quad \operatorname{tr}\left(\boldsymbol{A}^{\mathrm{T}} \boldsymbol{A} \boldsymbol{\Lambda}\right)-c \operatorname{tr}(\boldsymbol{\Lambda})= \\\operatorname{tr}\left(\boldsymbol{X}^{\mathrm{T}} \boldsymbol{X}\right)-2 \operatorname{tr}\left(\boldsymbol{A}^{\mathrm{T}} \boldsymbol{A} \boldsymbol{\Lambda}\right)+\operatorname{tr}\left(\boldsymbol{E}^{\mathrm{T}} \boldsymbol{A}^{\mathrm{T}} \boldsymbol{A} \boldsymbol{E}\right)+ \\\operatorname{tr}\left(\boldsymbol{A}^{\mathrm{T}} \boldsymbol{A} \boldsymbol{\Lambda}\right)-c \operatorname{tr}(\boldsymbol{\Lambda}) 。\end{array}$

令(31)式的一阶导数等于零即可获得最佳解A^*,即

(32)A^*EE^T-XE^T+A^*Λ=0。

这时,有

(33)A^*=XE^T(EE^T+Λ)^-1。

将(33)式代入(31)式可得

(34) $\begin{aligned}g(\boldsymbol{\varepsilon}) & =\operatorname{tr}\left(\boldsymbol{X}^{\mathrm{T}} \boldsymbol{X}\right)-2 \operatorname{tr}\left(\boldsymbol{X} \boldsymbol{E}^{\mathrm{T}}\left(\boldsymbol{E} \boldsymbol{E}^{\mathrm{T}}+\boldsymbol{\Lambda}\right)^{-1} \boldsymbol{E} \boldsymbol{X}^{\mathrm{T}}\right)- \\& \operatorname{ctr}(\boldsymbol{\Lambda})+\operatorname{tr}\left(\left(\boldsymbol{E} \boldsymbol{E}^{\mathrm{T}}+\boldsymbol{\Lambda}\right)^{-1} \boldsymbol{E} \boldsymbol{X}^{\mathrm{T}} \boldsymbol{X} \boldsymbol{E}^{\mathrm{T}}\right)= \\& \operatorname{tr}\left(\boldsymbol{X}^{\mathrm{T}} \boldsymbol{X}\right)-\operatorname{tr}\left(\boldsymbol{X \boldsymbol { E } ^ { \mathrm { T } }}\left(\boldsymbol{E} \boldsymbol{E}^{\mathrm{T}}+\boldsymbol{\Lambda}\right)^{-1} \boldsymbol{E} \boldsymbol{X}^{\mathrm{T}}\right)- \\& \operatorname{ctr}(\boldsymbol{\Lambda}) 。\end{aligned}$

由此可得拉格朗日对偶函数

(35)

m i n Λ

tr(XE^T(EE^T+Λ)^-1EX^T)+ctr(Λ),s.t.ε_i≥0,i=1,2,…,k。

(35)式可以通过牛顿法或共轭梯度来求解。令Λ^*为最优解,那么最优A^*=XE^T(EE^T+Λ)^-1。由于不能保证EE^T+Λ可逆,因此本文算法使用伪逆代替直接求逆。

至此,GraphSCAN的算法步骤可总结如下。

算法2 自适应图稀疏编码算法
输入:数据矩阵X∈ $R + m × n$ 的初始值,簇号c,参数k、λ、α、β;
输出:字典矩阵A、稀疏编码E。
步骤1 初始化字典矩阵A、稀疏编码E;
步骤2 重复
1)通过算法1更新字典矩阵A;
2)通过(35)式更新稀疏编码E;
3)对于每个i,通过求解(13)式更新S的第i行。其中d_i∈Rⁿ^×1,第j个元素为d_ij=‖x_i-x_j $‖ 22$ +β‖e_i-e_j $‖ 22$ ;
直到收敛;
步骤3 求得结果。

3 实验

我们在2个图像数据集(CMU-PIE数据库和COIL20图像数据库)上进行聚类实验。实验中以聚类准确率(accuracy, ACC)、标准互信息率(normalized mutual info, NMI)2个指标作为评价标准,实验环境为Intel(R) Core(TM) i7-1065G7 1.50 GHz CPU,16 GiB DDR3内存,MATLAB 2019b。

3.1 实验步骤

为了进一步评估所提出方法的性能,我们对GraphSCAN与一些经典算法和最新算法进行了对比实验。

1)k-means:最常用的基于欧式距离的聚类算法^[32] 。

2)主成分分析(principal component analysis,PCA):经典的降维方法^[33]。

3)SC:经典SC算法。

4)GraphSC:图正则化的SC^[20]。

5)LogSC:最新的基于拉普拉斯图正则化的SC^[22]。

实验中所用对比算法的参数已结合原论文进行了调节,使得其性能达到最优。

3.2 图像聚类实验

3.2.1 CMU-PIE数据集上的测试

我们首先在CMU-PIE数据集上进行实验, CMU-PIE人脸数据库包含68个人总共41 368张人脸图像。每个图像的大小为32×32,每个像素256个灰度级,每个图像都由1 024维矢量表示。

我们进行的聚类实验的簇数C范围为4~68。对于除68以外的每个簇,对不同随机选择的簇进行20次测试运行,并通过对20个测试取平均值来获得最终的性能得分。对于每个测试,首先应用比较算法中的每个算法,学习数据的新表示形式,然后在新的表示空间中应用k-means。我们用不同的初始化将k-means在原数据集上重复50次,并记录关于k-means目标函数的最佳结果。PCA投影降维后,维数为64。对于SC、GraphSC、LogSC、GraphSCAN算法,基向量维度设为128。

实验结果如表1所示,本文GraphSCAN算法基本优于其他算法(表中加粗数据)。GraphSCAN的ACC和NMI均值分别为86.28%和94. 41%,明显高于现有优秀算法LogSC在PIE数据集上的表现。同时,基于图的SC算法结果均优于标准SC算法。这说明结合图的SC可以获得更好的性能,且通过自适应邻居获得相似度图的方法比仅使用k -NN进行构造的图算法获得的结果精度更高。由于局部流形结构的学习和稀疏编码是同时进行的,即从编码的结果中自适应地学习内在局部结构,并且重新构造因子以保留数据的精炼局部结构。因此,可以更好探索数据内在局部结构。通过为每个数据点选择自适应和最佳邻居,该方法可以提高一般情况下的聚类性能。

表1 CMU-PIE数据集的聚类结果

Tab.1 Clustering results of CMU-PIE data set 单位:%

C	ACC										NMI
C	k-means	PCA	SC	GraphSC		LogSC		GraphSCAN			k-means		PCA		SC		GraphSC		LogSC	GraphSCAN
4	38.64	47.23	90.21		93.56		85.08		94.32	53.46		65.83		95.85		95.45		91.49		95.31
12	32.75	32.90	90.56		91.34		84.66		92.64	50.53		65.38		94.45		94.60		93.56		94.63
20	30.17	30.45	82.43		88.54		84.29		90.87	49.88		64.71		90.80		94.50		91.36		95.24
28	28.43	28.78	78.00		86.79		83.94		86.82	47.84		64.26		89.50		94.28		87.47		95.43
36	28.94	28.83	71.85		82.73		83.40		83.27	46.90		63.67		86.42		94.28		87.01		94.79
44	25.64	27.95	66.73		80.61		83.48		82.73	46.76		62.35		82.33		93.12		85.13		93.86
52	27.62	27.65	63.89		78.17		83.27		80.97	46.23		60.09		80.00		92.33		85.07		93.12
60	25.14	27.71	61.35		78.51		82.98		78.63	43.40		48.57		76.5		92.89		83.76		92.92
平均值	29.67	31.44	75.63		85.03		83.89		86.28	48.13		61.86		86.98		93.93		88.11		94.41

注:加粗表明本文算法优于其他算法的数据。

3.2.2 COIL20数据集上的测试

我们在COIL20数据集上也进行了实验, COIL20图像库包含20个对象1 440张32×32的灰度图像(每个对象72个图像),每个图像由1 024维向量表示。实验设置与CMU-PIE数据集上的实验基本相同,但限制于数据集大小,此处以2~20的簇数进行20次实验,通过对20个测试取平均值来获得最终的性能得分。对于此数据集,PCA降维后的维数为175;对于SC、GraphSC、GraphSCAN算法,基向量维度设为256。

实验结果如表2所示,GraphSCAN的ACC和NMI均值分别为88.07%和87.63%。与LogSC相比,GraphSCAN的性能略有提升,且二者都优于同样基于图的GraphSC算法。这说明将图优化的概念引入使用图方法的GraphSC中,可以提高原有算法的性能。

表2 COIL20数据集的聚类结果

Tab.2 Clustering results of COIL20 data set

C	ACC										NMI
C	k-means	PCA	SC	GraphSC		LogSC		GraphSCAN			k-means		PCA		SC		GraphSC		LogSC	GraphSCAN
2	63.75	63.33	76.81		94.31		95.78		96.39	64.86		65.42		78.02		90.56		89.72		91.53
4	60.97	62.22	74.79		92.86		92.62		92.64	62.78		64.03		77.71		88.06		90.81		91.18
6	60.50	60.97	72.81		90.67		90.76		90.28	60.11		61.67		77.21		88.56		84.16		90.81
8	58.75	58.67	72.64		87.92		87.70		88.62	59.38		60.42		76.69		85.48		86.92		88.78
10	56.88	56.67	70.39		86.17		86.68		87.66	59.03		59.31		76.01		83.06		85.13		87.28
12	56.88	56.46	69.55		85.39		86.37		86.91	58.61		59.10		76.01		83.06		83.76		86.43
14	56.22	56.46	67.92		84.74		86.75		86.10	56.89		57.78		72.83		82.11		84.45		86.71
16	56.22	56.46	64.86		84.27		84.00		85.35	56.89		54.03		72.08		80.81		83.40		85.28
18	55.46	56.46	64.86		83.39		83.58		84.11	54.53		54.28		71.35		78.75		86.45		85.00
20	53.40	56.46	64.11		82.29		82.50		82.61	53.29		54.03		72.01		77.85		82.67		83.33
平均值	57.90	58.42	69.87		87.20		87.67		88.07	58.64		59.01		74.99		83.83		85.75		87.63

注:加粗表明最优。

结合对PIE数据集进行的聚类实验结果可以看出,通过将自适应拉普拉斯图构建的概念引入带有几何信息编码的稀疏表示中,可以有效提高学习性能。

3.3 参数选择实验

观察目标函数(5)可以看出,GraphSCAN中包含了α、β、λ 3个参数。根据文献[20,28]中实验不难发现,虽然α、β取值会影响实验结果,但是由于其取值范围较小,且因其改变而影响的实验结果误差不大,故此处仅讨论对算法中参数取值范围及实验结果影响较大的参数λ的选择。

考虑到实验数据集包含的数据量,这里选择COIL20以及CEU-PIE 2个数据集及PCA、SC、GraphSC、GraphSCAN 4种算法进行了实验。所有实验均使用ACC、NMI指标作为算法评价标准。为了公平地比较所有方法,所有算法都在不同的参数设置下进行,且在每个参数设置下,均会独立重复实验20次。所有方法的迭代次数都根据经验设置为50,GraphSCAN中α、β两个参数粗略取值为α=λ、β=0.3进行实验(更好的参数调整可以给本文算法带来更优秀的性能)。聚类的数量设置为真实类的数量。

试验结果如图1所示。可以看出,在CEU-PIE数据集上当λ取到0.1时以及在COIL20数据集上当λ取到1时可获得较好的结果,其结果显示GraphSCAN与GraphSC算法取到λ最优值过程中指标变化趋势相差较小。以上结果表明,实际对算法影响较大的部分为SC之前进行的图构造过程。

显示原图|下载原图ZIP|生成PPT

图1 各算法中参数λ对性能的影响

Fig.1 The influence of parameter λ on different algorithms

4 结语

为优化GraphSC算法,本文将自适应拉普拉斯图构建的方法引入GraphSC中,提出了自适应图正则化稀疏编码算法GraphSCAN。该算法通过使用自适应方法定义构建合适的局部拉普拉斯图,再使用构建好的图参与SC的运算,图的构建与稀疏编码的运算同时迭代进行。本文在2个图像数据集上进行了实验,并与相关算法进行了比较分析,验证了GraphSCAN的有效性。

References

Publishing order | Descend order by publishing year | Descend order by cited within

[1]	AGARWAL S, AWAN A, ROTH D. Learning to detect objects in images via a sparse,part-based representation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2004, 26(11):1475-1490. DOI

[2]	ROWEIS S. EM algorithms for PCA and SPCA[C]// Proceedings of the 1997 Conference on Advances in Neural Information Processing Systems. New York: ACM, 1998: 626-632.

[3]	HOYER P. Nonnegative matrix factorization with sparseness constraints[J]. Journal of Machine Learning Research, 2004, 5 (9): 1457-1469.

[4]	ELAD M, AHARON M. Image denoising via sparse and redundant representations over learned dictionaries[J]. IEEE Transactions on Image Processing:A Publication of the IEEE Signal Processing Society, 2006, 15(12):3736-3745. DOI

[5]	YANG J C, YU K, GONG Y H, et al. Linear spatial pyramid matching using sparse coding for image classification[C]// 2009 IEEE Conference on Computer Vision and Pattern Recognition. Miami: IEEE, 2009:1794-1801.

[6]	LEWICKI M, SEJNOWSKI T. Coding time-varying signals using sparse,shift-invariant representations[C]// Advances in Neural Information Processing Systems. Denver: NIPS 1999.

[7]	OLSHAUSEN B A, FIELD D J. Emergence of simple-cell receptive field properties by learning a sparse code for natural images[J]. Nature, 1996, 381(6583):607-609. DOI

[8]	DONOHO D L, ELAD M, TEMLYAKOV V N. Stable recovery of sparse overcomplete representations in the presence of noise[J]. IEEE Transactions on Information Theory, 2006, 52(1):6-18. DOI

[9]	HUANG K, AVIYENTE S. Sparse representation for signal classification[M]//Advances in Neural Information Processing Systems 19.Cambridge:the MIT Press, 2007.

[10]	WRIGHT J, YANG A Y, GANESH A, et al. Robust face recognition via sparse representation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2009, 31(2):210-227. DOI PMID

[11]	MAIRAL J, BACH F, PONCE J, et al. Supervised dictionary learning[C]// Advances in Neural Information Processing Systems. Vancouver: NIPS, 2009: 1033-1040.

[12]	IROFTI P, STOICAN F, PUIG V. Fault handling in large water networks with online dictionary learning[J]. Journal of Process Control, 2020, 94:46-57. DOI

[13]	LEE H, BATTLE A, RAINA R, et al. Efficient sparse coding algorithms[C]//Advances in Neural Information Processing Systems. Vancouver:NIPS, 2007: 801-808.

[14]	ZHU H, NG M K. Structured dictionary learning for image denoising under mixed Gaussian and impulse noise[J]. IEEE Transactions on Image Processing, 2020, 29:6680-6693. DOI

[15]	CANDES E J, TAO T. Near-optimal signal recovery from random projections:universal encoding strategies?[J]. IEEE Transactions on Information Theory, 2006, 52(12):5406-5425. DOI

[16]	AHARON M, ELAD M, BRUCKSTEIN A. K-SVD:An algorithm for designing overcomplete dictionaries for sparse representation[J]. IEEE Transactions on Signal Processing, 2006, 54(11):4311-4322. DOI

[17]	QIAO Z H, ZHOU L, HUANG J Z. Sparse linear discriminant analysis with applications to high dimensional low sample size data[J]. IAENG International Journal of Applied Mathematics, 2009, 39(1):48.

[18]	KAVUKCUOGLU K, RANZATO M, FERGUS R, et al. Learning invariant features through topographic filter maps[C]//2009 IEEE Conference on Computer Vision and Pattern Recognition. Miami:IEEE, 2009:1605-1612.

[19]	GAO S H, TSANG I W H, CHIA L T, et al. Local features are not lonely-Laplacian sparse coding for image classification[C]// 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. San Francisco: IEEE, 2010:3555-3561.

[20]	ZHENG M, BU J J, CHEN C, et al. Graph regularized sparse coding for image representation[J]. IEEE Transactions on Image Processing, 2011, 20(5):1327-1336. DOI PMID

[21]	GAO S H, TSANG I W H, CHIA L T. Laplacian sparse coding,hypergraph Laplacian sparse coding,and applications[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2013, 35(1):92-104. DOI

[22]	SHA L D, SCHONFELD D, WANG J. Graph Laplacian regularization with sparse coding for image restoration and representation[J]. IEEE Transactions on Circuits and Systems for Video Technology, 2020, 30(7):2000-2014.

[23]	YIN M, GAO J B, LIN Z C. Laplacian regularized low-rank representation and its applications[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2016, 38(3):504-517. DOI PMID

[24]	NATARAJAN B K. Sparse approximate solutions to linear systems[J]. SIAM Journal on Computing, 1995, 24(2):227-234. DOI

[25]	MALLAT S G, ZHANG Z F. Matching pursuits with time-frequency dictionaries[J]. IEEE Transactions on Signal Processing, 1993, 41(12):3397-3415. DOI

[26]	CHEN S S, DONOHO D L, SAUNDERS M A. Atomic decomposition by basis pursuit[J]. SIAM Review, 2001, 43(1):129-159. DOI

[27]	TENENBAUM J B, DE SILVA V, LANGFORD J C. A global geometric framework for nonlinear dimensionality reduction[J]. Science, 2000, 290(5500):2319-2323. DOI PMID

[28]	HUANG S D, XU Z L, KANG Z, et al. Regularized nonnegative matrix factorization with adaptive local structure learning[J]. Neurocomputing, 2020, 382:196-209. DOI

[29]	PEI X B, CHEN C B, GONG W H. Concept factorization with adaptive neighbors for document clustering[J]. IEEE Transactions on Neural Networks and Learning Systems, 2018, 29(2):343-352. DOI PMID

[30]	NIE F P, WANG X Q, HUANG H. Clustering and projected clustering with adaptive neighbors[C]// KDD 14: Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2014:977-986.

[31]	LEMARÉCHAL C S.L. Vandenberghe,convex optimization[J]. European Journal of Operational Research, 2006, 170(1):326-327. DOI

[32]	LEE D D, SEUNG H S. Algorithms for non-negative matrix factorization[C]//Advances in Neural Information Processing Systems. Vancouver:NIPS, 2001.

[33]	JOLLIFFE I T. Principal components analysis[C]// International Conference on Document Analysis & Recognition. New York: IEEE, 1998.

Options

Outlines

模态框（Modal）标题

Abstract

Cite this article

1 相关工作

1.1 稀疏编码(SC)

1.2 图正则化稀疏编码(GraphSC)

2 自适应图正则化稀疏编码算法及其求解

2.1 GraphSCAN的算法模型

2.2 GraphSCAN的算法求解

2.2.1 固定A、E更新S

2.2.2 固定S、A更新E

2.2.3 固定S、E更新A

3 实验

3.1 实验步骤

3.2 图像聚类实验

3.2.1 CMU-PIE数据集上的测试

表1 CMU-PIE数据集的聚类结果

3.2.2 COIL20数据集上的测试

表2 COIL20数据集的聚类结果

3.3 参数选择实验

图1 各算法中参数λ对性能的影响

4 结语

References