2021574
基于有效距离的低秩表示
陶体伟1，2，刘明霞2，王明亮3，王琳琳4，杨德运2，张强5
1.桂林理工大学信息与工程学院，广西桂林541006
2.泰山学院信息科学技术学院，山东泰安271021
3.南京航空航天大学计算机科学与技术学院，南京211106
4.泰山学院数学与统计学院，山东泰安271021
5.大连理工大学计算机科学与技术学院，辽宁大连116000
摘要：低秩表示（Low-Rank Representation，LRR）在探索数据中的低维子空间结构方面具有良好的效果，近年来引起了人们的广泛关注。然而，传统的LRR方法通常使用欧氏距离来度量样本的相似性，仅考虑相邻样本两两之间的距离信息，对于具有流形结构的数据往往不能反映其固有的几何结构。最近的研究表明，概率激励距离测量（即有效距离）可以有效地对数据的全局信息进行建模，来度量样本间的相似性。
在此基础上，提出了一种基于有效距离的低秩表示模型。该方法用稀疏表示方法计算样本之间的有效距离来构造拉普拉斯矩阵，并将其进行低秩表示拉普拉斯正则化约束，该模型不仅能表示全局低维结构，而且能捕获流形结构数据中的几何结构信息。为了评估方法的有效性，在三个公开数据集上进行了分类实验。实验结果表明，该方法比基于传统欧氏距离的方法，具有更高的分类性能和更强的鲁棒性。
关键词：低秩表示（LRR）；有效距离；稀疏表示；分类
文献标志码：A中图分类号：TP391.4doi：10.3778/j.issn.1002-8331.1912-0015
Effective Distance Based Low-Rank Representation
TAO Tiwei1，2,LIU Mingxia2,WANG Mingliang3,WANG Linlin4,YANG Deyun2,ZHANG Qiang5
1.School of Information and Engineering,Guilin University of Technology,Guilin,Guangxi541006,China
2.School of Information Science and Technology,Taishan University,Tai’an,Shandong271021,China
3.College of Computer Science and Technology,Nanjing University of Aeronautics and Astronautics,Nanjing211106,China
4.School of Mathematics and Statistics,Taishan University,Tai’an,Shandong271021,China
5.College of Computer Science and Technology,Dalian University of Technology,Dalian,Liaoning116000,China
Abstract：Low-Rank Representation（LRR）has recently attracted a great deal of attention due to its pleasing efficacy in exploring low-dimensional subspace structures embedded in data.However,conventional LRR-based methods simply use Euclidean distance to measure the similarity of samples,where cannot reflect the inherent geometric structure of data with manifold structure.Meanwhile,recent studies have shown that a probabilistically motivated distance measurement（called effective distance）can effectively model the global information of data to measure the similarity between samples.To this end,this paper proposes an Effective Distance Based Low-Rank Representation（EDLRR）model,which firstly uses the sparse representation method to calculate the effective distance between samples for constructing a Laplacian matrix,and then develops a Laplacian regularized low-rank representation term.Low rank representation model.This method can not only represent the global low-dimensional structure,but also capture the geometric structure information in the data of the manifold structure.To evaluate the effectiveness of the proposed method,this paper conducts classification experiments
基金项目：国家自然科学基金（61703301）；山东省自然科学省属高校优秀青年联合基金（ZR2019YQ
27）；泰山学院科研基金（Y-01-2018019）；泰山学者青年专家项目。
作者简介：陶体伟（1989—），男，硕士，研究领域为机器学习；刘明霞（1981—），通信作者，女，博士，教授，研究领域为机器学习，E-mail：；王明亮（1989—），男，博士，研究领域为机器学习；王琳琳（1991—），女，助教，研究领域为机器学习；杨德运（1963—），男，博士，教授，研究领域为数字图理；张强（1971—），博士，教授，研究领域为生物计算理论。收稿日期：2019-12-02修回日期：2020-03-24文章编号：1002-8331（2021）04-0141-07
141
2021574
近年，低秩表示（Low-Rank Representation，LRR）作为一种能有效挖掘数据本质结构的方法，在机器学习领域引起了人们的关注[1]，特别是在图像处理领域涉及低秩矩阵估计及低秩约束的问题是近期研究的热点。低秩表示在图像聚类、图像去噪、显著性检测、视频前景背景分离等领域有着广泛的应用。
低秩方法是鲁棒性主成分分析方法（Robust Principal Component Analysis，RPCA）的一种推广形式的模型。RPCA本质上也是寻数据在低维空间上的最佳投影问题，并且能从噪声污染的数据中恢复其本质上的低秩数据。RPCA模型隐式地假设原始数据的潜在结构为一个单独的低秩线性子空间，也就是说RPCA模型只能提取一个主子空间，即所有纯净数据所张成的子空间。但是在现实应用中，很多高维观测数据可近似来自于一个或者多个低维的线性独立子空间，且子空间的类别数以及每个数据点属于哪个子空间也是未知的。在这种情况下，如果只是简单地使用RPCA，得到的低秩矩阵就不能准确地抓住数据的子空间结构。
为了能够更好地表示数据的多个低维子空间结构，使RPCA模型更具广义性，Liu等人提出了低秩表示模型。其通过约束表示系数是低秩的，将子空间分割与噪声分离纳入一个框架中处理，这和RPCA模型相比，可以更好地处理多个低维子空间数据。
如果一个高维空间中的所有数据实际上都是几个线性子空间的并集，则利用LRR能有效地揭示数据中本质的低维结构。但在实际应用中，许多数据具有非线性几何结构，如面部图像就是在高维环境空间中的非线性子空间中采样的。因此，在这种情况下，LRR方法可能无法发现数据的内在几何结构，在特征提取过程中数据之间的局部性和相似性信息可能会丢失[2]。
为了保留嵌入高维空间的局部几何结构，许多研究人员已经考虑了流形学习（非线性特征提取）方法，
如局部线性嵌入（Locally Linear Embedding，LLE）[3]、局部保持投影（Locality Preserving Projections，LPP）[4]、邻域保留嵌入（Neighborhood Preserving Embedding，NPE）[5]和拉普拉斯特征映射（Laplacian Eigenmaps，LE）[6]。所有这些算法都受到局部不变性思想的启发，即两个数据点在数据分布的内在流形中是接近的，那么这两个点在新空间中的表示也会彼此接近。利用局部不变性思想，Zheng等人[7]提出一种图正则化低秩模型，它基于在学习过程中获得的最相关的特征来构造图，因此该图受到无关和严重损坏的特征的影响较小，并且更具区分性。其中图拉普拉斯算子是基于特征学习过程迭代学习的，这与广泛使用的非线性技术有着明显的不同，后者通过独立的预处理步骤构造核矩阵或图拉普拉斯算子作为输入。Zhu等人[8]结合LRR技术，提出了一种新的低秩图正则化结构稀疏回归方法。该方法通过低秩约束将特征嵌入到遗传数据和脑影像数据中，并通过稀疏有向图和结构稀疏正则化对遗传数据进行变量选择，可有效提高阿尔兹海默症的诊断精度。Yang等人[9]提出了非负对偶图正则化潜在低秩表示，引入双图正则化约束有效保留原始数据的内部空间结构，并在分割子空间时提高最终聚类的准确性。但是，这些方法都是基于欧氏距离来度量，通过构建子图来描述数据间的相似性结构，缺乏对数据全局结构信息的把握。最近的研究表明，概率激励距离测量（称为有效距离）可以对数据的全局结构信息进行建模。欧几里德距离一直被用来测量不同样本之间的相似性[3]。但是，数据底层的动态结构和内部关系不能完全用连通矩阵来表示，即在投影到新的子空间之前，相似矩阵中描述的信息已经失去了一些潜在的数据结构。在概率解释的驱动下，Brockmann等人提出了有效距离来发现数据间的结构相似性。结果表明，有效距离比欧几里德距离更能表现数据的全局关系信息[10]。
受上述工作的启发，本文提出了一种基于有效距离的低秩表示模型（Effective Distance Based Low-Rank Representation，EDLRR），并应用于图像分类。利用稀疏表示方法计算有效距离，可以更好地把握数据的全局信息，并使用最近邻图表示数据之间的相似性来构建数据的局部几何结构。然后将图结构合并到寻最低秩表示矩阵的优化问题中，同时将表示系数约束为非负，以便学习局部流形结构，这也使模型在物理上更具可解释性。
1相关工作
1.1有效距离
传统的相似度度量方法通常基于欧氏距离进行，然而欧氏距离仅能体现个体数值特征的绝对差异（即从数值大小的差异），无法对数据中的动态特性（比如时间序列数据的动态变化）和全局特性进行建模。然而，现实世界中两个事物之间的相似性不仅仅取决于几何坐标中的欧氏距离或者地理距离，因此在设计相似性度量准则时需要考虑样本自身的动态特性以及样本和样本之间的全局特性。
Brockmann等人在研究复杂网络驱动对传染病传播过程的影响时，提出了有效距离的概念，并利用空中运输乘客的数据来构建各个大城市之间的有效距离，以
by using three public datasets.Experimental results show that the proposed EDLRR method has highe
r classification per-formance and stronger robustness than the traditional Euclidean distance based methods.
Key words：Low-Rank Representation（LRR）;effective distance;sparse representation;classification
142
2021574此成功挖掘出病菌传播源并预测出病菌的传播状态[10]。文献[11]提出一种基于稀疏表示的方法来计算有效距离，并提出了基于有效距离的特征选择方法。实验结果表明，基于有效距离的相似度量方法在分类和聚类任务中都取得了比欧氏距离更好的性能。
有效距离的直观示意图如图1所示。在图1（a ）中，存在具有4个节点的图形，边的权重由箭头来量化表示。在图1（b ）中，将节点m 移动到节点n 处的随机游走概率表示为P (n |m )，该概率的大小由线宽表示。例如，节点A 移动到节点B 处的随机游走概率P (B |A )为1/2，其中数字2表示节点A 与其他节点的连接数。在图1（b ），从D 开始随机游走前往C 的概率和从A 开始随机游走前往B 的概率较大，即P (B
|A )=1/2，P (C |D )=1，反之则较小。在有效距离的定义中，小概率P (n |m )表示从点m 到点n 的有效距离大，大概率P (n |m )表示从点m 到点n 的有效距离小。与传统的欧式距离相比，有效距离综合考虑数据的动态结构信息以及样本与其他所有样本间的关系，因此有助于揭示数据的隐藏结构并提高模型的学习性能。
1.2LRR 模型
LRR 可以看作是RPAC 的一种推广形式[12]
。LRR
模型[1]
基于这样的假设：相关数据存在于一个低维线性子空间中。给定一组数据样本，LRR 旨在到所有数据中本质的低维结构。这和RPCA 模型相比，可以更好地处理多子空间数据。
考虑数据Y 是从由∪
i =1
k
S i 给出的多个子空间的并
集中提取的情况，其中S 1,S 2,⋯,S k 是低维子空间，则给定数据Y 的LRR 定义为以下等级最小化问题：
min Z ,E
rank (Z )+λ  Y =AZ +E
（1）
其中，rank (Z )为给定数据Y 的最低秩表示；  ⋅0表示
E 中非零元素的个数，
目的是为了拟合噪声；A 为线性张成数据空间的字典；
λ表示权重因子。由于秩函数和l 0范数的离散性质很难解决上述优化问题（1），它们都属于NP 难问题，因此提出上述优化问题的凸松弛，即将优化问题中秩函数和l 0范数放松为各自的凸包形式（矩阵核范数和l 1范数），进而再继续求解目标的凸优化问题，这就是低秩表示模型：
min Z ,E
Z *+λ  Y =AZ +E
（2）
其中，  Z *表示矩阵的核范数，即对Z 进行奇异值分解所得到的所有奇异值的和。  E 1表示E 的稀疏矩阵，即矩阵E 的所有元素的绝对值之和。
文献[13]提出了基于非负低秩稀疏图（NNLRS ）的方法，其中心思想是在半监督学习环境下构造一个好的图来发现内在的数据结构，用给定的数据表示建立一个非负的低秩稀疏图，图中边的权重是通过寻非负的低秩稀疏重建系数矩阵获得的。该矩阵将每个数据样本表示为其他数据样本的线性组合，由此获取数据子空间的低维结构和数据的局部线性结构。
该方法具体模型如下：min Z ,E
Z *+β  Z 1+λ  E 2,1
其中，  E 2,1是l 2,1范数；
参数λ用于平衡噪声的影响，使用经验值设定；l 2,1范数鼓励噪声E 为0。但是该方法没有考虑数据流形的问题。
文献[2]提出了非负稀疏拉普拉斯正则化LRR 模型
（NSHLRR ），其使用基于欧氏距离的最近邻图来构建表示数据的局部结构，引入了流行正则化约束。与文献[13]不同，它采用局部线性子空间逼近非线性流形，在效果上更好一些。本文受此启发，使用基于稀疏表示的有效距离来构建数据的局部结构。
2基于有效距离的低秩表示模型
2.1基于稀疏表示的有效距离
稀疏表示作为信号分析领域的热点问题，其本质是从过完备字典矩阵中选择尽可能少的原子来表示信号，
使学习任务得到简化，模型复杂度降低。
值得注意的是，稀疏表示方法能够有效表达数据的全局特性[14]。具体有效距离计方法如下：
给定一组训练样本X =[x 1,x 2,⋯,x n ]∈R n ×d ，其中n 代表样本的个数，d 代表特征的维数。根据稀疏重构
系数模型[15]，将每一个样本用其他的n -1个样本线性表示，即x =Aα+k ，其中A ={x 1,x 2,⋯,x i -1,x i +1,⋯,x n }，表示一个数据矩阵包含除了第i 个样本之外的所有其
A
B C
D
A
B
C
D
P (A |B )=1/4
P (C |A )=1/2
P (B |A )=1/2
P (C |D )=1
P (D |C )=1/3
（a ）权重图
（b ）概率图
图1
有效距离的图示说明
143
2021574
他样本；用W表示权重矩阵，即样本x i在稀疏表示样本x j的过程中所占的权重值，其可通过字典学习模型求解：
min W
x i-A T W2
2
+λ  W≥0（3）
根据式（3）计算求得权重系数矩阵W,W ij表示第i 个样本在第j个样本前的稀疏表示的系数。λ为正则化参数，用来约束模型稀疏性，值越小，得到的解中零元素越少，即稀疏性越小，反之则越大。
根据得到的权重系数矩阵W，对其进行归一化：
Q ij=
W ij
∑
i=1
n
W ij
（4）
Q ij越大，说明x i在稀疏重建x j时，所占的权重越大，则x i与x j之间的相似度越大，即有效距离越小。
有效距离计算如下：
ED ij=1-ln Q ij（5）因为0≤Q ij≤1，所以ln Q ij≤0，显然ED ij≥1。
2.2EDLRR算法实现及优化
在流形学习中，非线性流形是与线性子空间局部近似的，假设Y=[y1,y2,⋯,y n]是从底层流形M中采样，那么点和其邻点之间的关系也是线性的。因此可以通过其邻点构建与这些数据点的线性系数，来表示数据点的局部几何形状。
因此，本文首先构造拉普拉斯矩阵，包括3个步骤。
步骤1使用2.1节中稀疏表示方法计算样本之间的有效距离，构造有效距离矩阵ED∈R n×n。
步骤2基于每个采样点σi的有效距离计算局部尺度参数。
步骤3构建相似性矩阵。矩阵中的元素定义如下：
A ij=ì
í
î
ï
ï
expæ
正则化一个5 5随机矩阵è
ç
ö
ø
÷
-ED ij×ED ij
σiσj
0,otherwise
,if i≠j
其中度矩阵被定义为D,D为对角矩阵，其对角线元素D ii对应于与D ii=∑j A ij相关的所有相似性的总和。然后图拉普拉斯矩阵定义为[16]：
L=D-A
容易证明图拉普拉斯矩阵可以重写为min tr(ZLZ T)。
考虑到稀疏表示能够更好地捕获每个数据向量的局部结构，为了在Z上引入更丰富的信息，对Z引入了稀疏性约束[17]。稀疏LRR模型可以表示为如下公式：
min Z,E  Z
*
+λ  Z1+λ  E1
的流形学习[3，14-15]推动下，可以将拉普拉斯正则化结合到目标函数（6）中，具体EDLRR模型如下：
ì
í
î
ï
ï
min
Z,E
Z
*
+λ  Z1+βtr(ZLZ T)+γ  E1
（7）其中，L是基于有效距离的图拉普拉斯矩阵，而λ、β和γ是用于平衡正则项的惩罚参数。
本文提出的基于有效距离的LRR分类方法和LRR 方法相比，在寻求低秩系数矩阵的基础上，加入了稀疏和非负性约束，并且使用有效距离度量来构建相似度矩阵，充分考虑整个数据的全局结构，不仅保留了数据点之间的局部几何结构，也更好地把握数据的隐藏结构，改善相似度量的有效性。
基于传统的交替方向法（Alternate Direction Method，ADM），Lin等人[18]提出自适应惩罚项线性交替方法（Linearized ADM with Adaptive Penalty，LADMAP）。该方法针对ADM算法中需要引入新的辅助变量，增加计算复杂度这一问题，采用一种新的准则在每步迭代过程中自适应地更新惩罚参数，节省了存储空间和引入辅助变量矩阵逆的运算。为了获得式（7）的最优解，使用LADMAP解决这一问题的优化问题。
首先引入一个辅助变量J，以使式（7）的目标函数可分离，因此以上优化问题可以重写如下：
ì
í
î
ï
ï
min
Z,J,E
Z
*
+λ  J1+βtr(ZLZ T)+λ  E1
（8）则问题（8）的增广拉格朗日函数是：
Σ(J,E,Z,Y1,Y2)=  Z*+γ  J1+βtr(ZLZ T)+
γ  E1+M1,Y-YZ-E+M2,Z-J+
μ
2
()
Y-YZ-E2
F
+
Z-J2
F
（9）其中，M1、M2是拉格朗日乘子，μ>0是惩罚参数，在其他变量不变的情况下，通过最小化增广拉格朗日函数交替更新变量。
（1）更新Z，通过最小化公式（9）的增广拉格朗日函数，相当于最小化以下函数：
ε1=  Z*+βtr(ZL i Z T)+μ2
Z-J i+
1
μ
M1
2
F
+
μ
2
Y-YZ-E i+
1
μ
M2
2
F
（10）但是它没有闭式解，本文参照LADMAP，使用如下公式表示ε1的平滑分量：
q(Z,E i,J i,M i2,M i1)=βtr(ZL i Z T)+
μ
2
Z-J i+
1
μ
M1
2
F
+
μ
2
Y-YZ-E i+
1
μ
M2
2
F
（11）则最小化ε1可以通过解决如下问题来替代：
min
Z
Z
*
+∇zq(Z i),Z-Z i+
η1
2
Z-Z i2
F
（12）
144
2021574其中，q (S i ,E i ,J i ,M i 2,M i 1)通过其在S 处的线性化∇zq (Z i ),Z -Z i 加上近端项
η12
Z -Z i 2
F 来近似，其闭式解为：Z i +1=Θ(η1)-1æ
è
çöø÷
Z i -∇zq (Z i )η1（13）η1=2β  L 2+μk ()
1+  Y 2
2
（14）
∇zq (Z i )=β(Z i L T
+Z i L )+μi æèçöø÷Z i -J i +M i 2μi +
μi Y T
æèçö
ø
÷YZ i -Y +E i -M i 1μi （15）
其中，
Θ(η1)为奇异值算子。（2）更新E ，可以通过最小化ε(Z i +1,E ,J ,M i
2,M i 1
)来更新E 与J ：
min E γ  E 1+μ2
E -(Y -YZ +1μM 1)2
F
（16）
其闭式解为：
E i +1=S γμ
i
æèçöø÷Y -YZ i +1+1μi M i 1（17）
（3）更新J ：
min J γ  J 1+μ2
J -(Z +1μM 2)2
F
（18）
其闭式解为：
J i +1=max ìíîüý
þ
S λμi æèçöø÷Z i +1+1μi M i 2,0（19）随后交替更新拉格朗日乘子，并使用LADMAP 中
自适应更新策略来调整惩罚参数，使其能够迅速收敛，其总体流程如下。
算法1LADMAP 对EDLRR 算法的优化求解
输入：
Y ,λ,β,γ。输出：Z i +1,E i +1。
初始化：计算L ,Z 0=E 0=J 0=M 01=M 02=0,λ=8,β=4,γ=1,μ0=10-6,μmax =106；ε1=10-6,ε2=10-2。
当未收敛(k =0,1,⋯)时做以下循环：1.更新Z 2.更新E 3.更新J
4.更新拉格朗日乘子M 1、M 2M i +11=M i 1+μi (Y -YZ i +1-E i +1)M i +12=M i 2+μi (Z i +1-J i +1)
5.更新μ
μi +1=min(μmax ,ρi μi )
Where
ρk ìíîïï
ρ0,if max {η1  Z i +1-Z i ,}μi  J i +1-J i ,μi  E i +1-E i ≤ε2
1,otherwise
6.循环终止条件if
Y -YZ i +1-E i +1
Y <ε1and
max {}η1  Z i +1-Z i ,μi  J i +1-J i ,μi  E i +1-E i <ε2
由于LADMAP 的直接应用，上述算法收敛于全局
最优解。当用奇异值收缩去更新Z 时，可以使用文献[18]中所描述的秩预测策略来预测Z i +1的秩R ，它在迭代过程中慢慢增长，并稳定在真实数值上。此外，使用Lanczos 方法（求解大规模稀疏矩阵特征值问题最常用的方法之一）来计算每次迭代之前的一个奇异值和奇异
向量，这只需要将S k -∇zq (S i )
η1及其转置和向量相乘，
并通过连续矩阵向量相乘来有效地计算。在这样的处理下，本文算法每次迭代的复杂度仅为O (rn 2)，其中n 是样本数，
r 为矩阵的秩。3实验及结果分析
3.1实验设置
本文中的实验图像都经过标准化处理，实验环境为64位Windows 8.1操作系统，内存16GB ，Intel ®Core TM i5-4590********GHz ，并用Matlab R2014a 软件编程实现。
在分类实验中，选取了3个公开数据集CMU-PIE 、USPS 和UCI Zoo 。
CMU-PIE 是美国卡耐基梅隆大学建立的数据库，它包括68个人的在13种姿态条件、43种光照条件和4种表情下的4万多张照片。对于这个数据库，本文采用不同姿态、光照和表情下的每人170张每张32×32维特征的图像，共计11560张图片作为目标库，样例如图2（a ）
所示。
（a ）CMU-PIE
（b ）USPS
图2
人脸数据库和手写字体库实例
145

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。