对称加权算法对数据矩阵补全的优化研究

刘 云， 郑文凤， 张 轶

(昆明理工大学信息工程与自动化学院， 昆明 650500)

1 引 言

数据分析中经常存在数据值的缺失，在数据预处理中补全丢失数据可进行更有效的数据分析，广泛应用于图像处理，医疗疾病预测和电子商务推荐等领域[1].尤其高维数据的矩阵稀疏性很强，解决数据矩阵稀疏问题可以实现数据补全，用低秩矩阵分解(Low-Rank Matrix Factorization, LRMF) 重构矩阵是解决数据矩阵补全 (Matrix Completion，MC)问题的主流方法[2-3].LRMF引起了非凸优化问题，传统方法用矩阵的秩凸近似解，即核范数近似优化[4].

Fan等人[5]基于稀疏因子分解方法，将不完整矩阵分解为密集矩阵和稀疏矩阵，提出加速近端交替线性最小化(Accelerated Proximal Alternating Linearized Minimization, APALM)算法,解决了稀疏分解方法的非凸优化问题，更适合对从多个子空间提取的数据进行矩阵补全.Zhang等人[6]根据非凸非光滑秩(Nonconvex Nonsmooth Rank, NNR)松弛函数，建议使用双重NNR(Double Nonconvex Nonsmooth Rank, DNNR)函数近似低秩恢复函数，提出通用的迭代重加权奇异值函数 (Iteratively Reweighted Singular Values Function, IRSVF)算法，闭式解决了DNNR函数最小化收敛问题，性能上优于其他核范数加权方法，更适合解决数据矩阵补全非凸优化问题.Canyi等人[7]建议使用l0范数的非凸替代矩阵的奇异值近似低秩函数，提出迭代重加权核范数(Iteratively Reweighted Nuclear Norm,IRNN)算法来解决非凸非光滑低秩最小化问题，并通过将各种稀疏性强加于奇异值向量上，解决了加权奇异值阈值问题，比传统方法更适合低秩矩阵恢复.

为降低传统MC算法的计算复杂度，提高补全精度，提出对称加权 (Symmetric Weighting，SW)算法.主要针对非凸LRMF的正则化补全模型，利用稀疏性提出加权MC模型；再对分解后的矩阵因子选择共同的对称矩阵加权，通过正则化矩阵联合列稀疏性耦合矩阵因子，利用列修剪减少矩阵列元素，促进矩阵秩最小化达到目标矩阵的秩；结合块坐标下降(Block Coordinate Descent, BCD)[8]和交替最小二乘法 (Alternating Least Squares，ALS)[9],交替迭代得到最优低秩补全数据矩阵.仿真结果，相比于现有的算法,SW算法可以更快更准确地补全数据，并且适用于高维数据补全.

2 正则化矩阵分解补全

假设不完整矩阵Y之间的元素有较高的连续性，采样产生一个低秩结构化矩阵X，通过低秩最小化来恢复其缺失的元素，如图1.

为了优化低秩矩阵恢复，首先提出一个通用的矩阵秩最小化问题，如下式.

min[rank(X)] s.t. A(X) =b

(1)

在式(1)中，X∈Rm×n，b∈Rl，rank(X)表示矩阵的秩，A表示X映射到b的线性算子[10].MC的一般模型如下式.

min[rank(X)] s.t.Ω(Y) =Ω(X)

(2)

图1 正则化低秩矩阵分解补全流程

为了优化低秩最小化问题，通常对低秩数据矩阵X进行分解，如图1用矩阵Um×r和矩阵Vn×r的转置相乘表示，即X=UVT.其中r≤ min(m,n)，这种方法在处理大规模或高维数据时可以减少相关变量的大小，使计算复杂度O(mn) 降低到O( (m+n)r)[11].新的LRMF优化秩最小化的补全模型如下式.

min[rank(UVT)] s.t.Ω(Y) =Ω(UVT)

(3)

通常矩阵X的秩r未知，高估重构矩阵X的秩r为d，有d≥r，因此要惩罚UVT的秩，找到实际的秩r.考虑如下矩阵乘积UVT的一阶分解，如下式.

(4)

根据秩的可加性，降低式(4)右边项的一个秩会导致左边项UVT的秩相应减少.由此引入一个列修剪过程，即通过迭代删除矩阵中被清零的列，逐渐降低计算复杂度[12].

其次，考虑矩阵U和V的联合列稀疏性，添加一个正则化过程，用l2范数表示惩罚项优化MC模型，如下式.

(5)

该正则化方法中，ui和vi分别是矩阵U和V的第i列元素，通过正则化矩阵因子中的列元素降低模型的复杂度.考虑矩阵Y可能添加了独立同分布的高斯噪声，根据拉格朗日定理式(5)可以等效如下式.

(6)

(7)

如果在式(5)中给分解后的矩阵因子添加一个权重，可以促进稀疏性，更快得到式(7)中的低秩补全矩阵.

3 对称加权(SW)算法

目前已经有很多优化矩阵补全问题的加权方案.其中，重加权Frobenius范数优化矩阵补全模型如下式.

(8)

tr{(XTX)(XTX)p/2-1}=

(9)

tr{X}表示矩阵X的迹，可知W是对称权重矩阵，且每次迭代的W值由上一次迭代后获得的矩阵X计算得到，

W= (XTX)p/2-1

(10)

当p=1时，Schatten-p范数等价于核范数‖X‖*，根据LRMF非凸性，常用矩阵X的核范数近似代替矩阵的秩解决非凸优化问题.式(1)中秩最小化问题用加权核范数解决，得到新的矩阵补全模型，

min[rank(‖X‖*,W)] s.t.Ω(Y) =Ω(X)

(11)

(12)

因此，可以定义一个具有严格上界的核范数来解决式(11)中的最小化问题，如下式.

(13)

利用核范数在矩阵U和V产生一个平滑度，促进了低秩最小化.

3.1 SW算法

基于正则化矩阵分解补全，分别对数据矩阵因子U和V加权，得到加权目标函数，如图2所示.其次，利用ALS方法可以更好地处理稀疏矩阵的分解问题，得到数据补全的最优矩阵.

图2 对称加权矩阵补全框图Fig.2 Symmetrical weighted matrix completionblock diagram

结合式(13)得到矩阵的重加权Frobenious范数和的最小化补全模型，如下式.

(14)

为了解决上述最小化问题，定义一个低秩函数，如下式.

(15)

根据式(10)利用对称性设置权值WU=(UTU)p-1和WV=(VTV)p-1，当p=1时，WU=WV=Id,可以得到式(13)中的核范数变分形式，假设WU=WV=W，有

(16)

式中，0

(17)

正则化联合列稀疏性可以更快的惩罚秩，但该方法具有不光滑性且不可以分离矩阵U和V中的元素.为了使优化问题变得光滑，根据函数中的正则化项，添加一个很小的正常数η2得到可微优化[14].

(18)

该简易方法缓解了梯度不连续的点，可以得到使目标函数最小化的唯一平稳点.则根据正则化矩阵分解补全模型定义的目标函数f(U,V)如下式，

(19)

最后，结合BCD和ALS处理U和V，首先通过给定一个可用的初始化矩阵V更新为矩阵Vk，每次迭代时最小化目标函数的局部上界得到Uk+1；其次,使用Uk+1最小化另一个局部上界得到Vk+1.该方法解决了两个矩阵因子的不可分性，主要步骤如下.

步骤1在点 (Uk,Vk)对f(U,Vk)近似二阶泰勒展开，该展开式定义为上界函数h(U|Uk,Vk)，求其最小化.h(U|Uk,Vk) 是严格凸的，此松弛方法可以闭式表达，得到最优的低秩补全矩阵.

(20)

其中，

h(U|Uk,Vk)=f(Uk,Vk)+tr{(U-

(21)

(22)

(23)

式中，

(24)

步骤2在点 (Uk+1,Vk)对f(Uk+1,V)近似二阶泰勒展开，定义为上界函数l(V|Uk+1,V)，求其最小化.

(25)

其中，

l(V|Uk+1,Vk)=f(Uk+1,Vk)+tr{(V-

(26)

(27)

算法1对称加权算法(SW)

输入：

1) 不完全矩阵Y

2) 低秩正则化参数λ>0

初始化：

3)k=0,U0,V0,D(U0,V0)

迭代计算：

6)k=k+1

7) 判断是否收敛，收敛时输出，否则转步骤4)

输出：

算法1中，步骤1)～2)输入需要补全的矩阵Y和正则化参数λ，根据式(2)和式(3)对低秩矩阵采样分解.

步骤3)初始化迭代次数k=0,则分解后的低秩矩阵因子为U0和V0.再由式(24)运算得到D(U0,V0)，代入式(23)和(27)得到近似的Hessian矩阵.

步骤4)～5)根据式(20)和式(25)交替计算局部目标函数的最小值，两次连续迭代间的重构数据相对减少时算法收敛，得到最优的低秩矩阵因子.

3.2 SW算法收敛性分析

SW算法每次迭代的最小化函数h(U|Uk,Vk) 和l(V|Uk+1,V) 是函数f(U,Vk) 和f(Uk+1,V)的严格上界，因此，局部替代函数是实际目标函数的上界.如命题1，算法每次迭代后的目标函数单调递减.

命题1通过SW算法产生的顺序集{Uk,Vk}的目标函数是单调递减的，如式(28)，

f(Uk+1,Vk+1)≤f(Uk+1,Vk)≤f(Uk,Vk)

(28)

证明：已知h(U|Uk,Vk)≥f(U,Vk)，结合式(20)有，

h(Uk+1|Uk,Vk)≤h(Uk|Uk,Vk)≡f(Uk,Vk)

(29)

由已知条件可得h(Uk+1|Uk,Vk)≥f(Uk+1,Vk)，所以，

f(Uk+1,Vk)≤f(Uk,Vk)

(30)

同理可证，

f(Uk+1,Vk+1)≤f(Uk+1,Vk)

(31)

结合式(30)和式(31)，可得到命题1.

命题2在k→∞时，目标函数f(Uk,Vk)收敛，有f∞≥0.

证明 通过命题1可知SW 算法的目标函数单调递减，并且下界是0，因此，当k→∞时，f∞≥0.通过该结论可以分析算法的收敛点和收敛速度.

1) 收敛到平稳点.

SW算法通过单调递减的目标函数更新矩阵(Uk,Vk) ,可以推出目标函数到平稳点的收敛速度.给出任何一对(U,V) ,通过下面的最小化问题定义矩阵U*和V*.

(32)

(33)

用Δ((U,V),(U*,V*))表示(U,V) 和(U*,V*)之间的相似度测量.

(34)

推论：算法中目标函数f(U,V)的连续目标值的差值有下界，结果如式(35),

f(Uk,Vk)-f(Uk+1,Vk+1)≥

Δ((Uk,Vk),(Uk+1,Vk+1))

(35)

命题3当且仅当(U,V)是SW算法得到的平稳点时,Δ((U,V),(U*,V*)) = 0.

证明：假设(U,V)是一个平稳点，U=U*,V=V*, 很容易证明Δ((U,V),(U*,V*)) = 0.其次，由式(35)可知Δ((U,V),(U*,V*))非负，若Δ((U,V),(U*,V*)) =0，则有，

h(U|U,V)-h(U*|U,V)=0

(36)

l(V|U*,V)-l(V*|U*,V)=0

(37)

h(U|U,V) 和l(V|U*,V)是严格凸函数，(U*,V*)是唯一极值解，因此，只有当(U,V) =(U*,V*)时，结论成立.所以(U*,V*)也是最小化目标函数的一个平稳点.

如上所述,Δ((Uk,Vk),(Uk+1,Vk+1))用来量化算法连续迭代生成的(Uk,Vk)和(Uk+1,Vk+1)之间的距离，当Δ= 0时，算法收敛到平稳点(Uk+1,Vk+1).

2) 收敛速度.

当λ>0时，由算法产生的序列{Uk,Vk}的极值点是目标函数f(U,V)的一个平稳点.定义一个值ξk，ξk=Δ((Uk,Vk),(Uk+1,Vk+1))，假设一个K→∞.

f(U1,V1)-f∞<∞

(38)

(39)

4 仿真分析

4.1 数据集

与类似算法仿真一致，仿真分析采用数据稀疏性较强的通用数据源MovieLens数据集，该数据集包含用户信息、电影信息以及多个用户对多部电影的评分，其评分数据矩阵非常稀疏，因此，可用该数据集来研究数据矩阵的缺失填补算法，对潜在用户的评分进行预测[17](MovieLens开源数据集网站https://grouplens.org/datasets/movielens/).其中，MovieLens100 K是经过充分研究的大型数据集，包含在不同时段收集的用户评分，用整数1到5表示.

表1 MovieLens100 K的数据集信息

如表1所示，在MovieLens100 K数据集缺失93.7%的评分数据，稀疏性很强.我们分别对数据随机采样65%，50%和35%作为训练集，25%，35%和45%作为验证集，其余作为测试集.建立一个943×1682的电影评分矩阵，假设不同用户的评分之间存在较高的相关性，找出低秩结构数据矩阵，进行数据补全.

4.2 归一化平均绝对误差分析

为了评估算法的补全精度，对归一化平均绝对误差(Normalized Mean Absolute Value Error，NMAE)进行分析[5-6].card(·)表示集合的基数，NMAE定义为

表2 在两种条件下算法对随机采样数据的NMAE

从表2中可以看到，随机采样65%的训练数据集时，算法在达到收敛时的NMAE值最小，且有适当的验证数据调整超参数，优化模型.因此，在保证验证集和测试集的比例上，尽可能多采样训练数据得到的模型泛化能力更好.针对最优的训练模型，分别得出4种算法在不同迭代时间下的补全误差，分析NMAE值.

图3 条件A中采样MovieLens100K数据集的精度分析

图4 条件B中采样MovieLens100 K数据集的精度分析

从图3和图4可以看出，在A，B两种条件下，算法的NMAE值随迭代次数的增加都逐渐减小，最终趋于平稳点.APALM和IRNN算法收敛时的NMAE值稳定在0.2～0.3，IRSVF和SW算法收敛时的NAME值稳定在0.1～0.2.IRNN算法迭代的时间最久，APALM算法虽减少了迭代次数，但精度不够高，IRSVF算法的计算量仍然较大，而SW算法误差最低，提高了补全精度，并且在条件A中该算法的时间复杂度明显降低.

4.3 收敛性分析

通过迭代产生的矩阵因子序列之间的相似度测量，计算两个连续目标函数之间的差值，可以得到算法收敛时的情况.针对A，B两种条件，在第一种采样数据训练的模型中分析APALM，IRSVF，IRNN和SW算法的收敛性.

图5 条件A中连续目标函数差值随时间的演变

图6 条件B中连续目标函数差值随时间的演变

从图5和图6可以看出四种算法在收敛时的情况.IRSVF和IRNN算法在两种条件下的平均每次迭代时间复杂度很高，并且收敛效果不好.其他两种算法的收敛效果差不多，但在条件A中明显看出APALM算法收敛时的迭代时间更长.SW算法在两种条件下的收敛效果都较好且平均每次迭代的时间复杂度最低，特别是在条件A中收敛时的时间不到其他算法的20%.

通过NMAE和收敛性分析表明，SW算法对比于其他三种算法可以更精确的补全数据矩阵，并且降低时间计算复杂度并不会影响该算法的补全性能.其次，SW算法的列修剪优化在很大程度上减少了计算负担，使仿真数据集收敛时的迭代次数更少，收敛速度明显比现有算法快，可更高效的进行补全.

5 结 论

用矩阵表示数据集，可以高效解决数据分析中的缺失元素问题，高维数据矩阵也可以用低维特征表示或重构.根据LRMF的补全模型，利用正则化矩阵联合列稀疏性，进行列修剪降低计算复杂度.然后基于加权稀疏矩阵的思想，对矩阵因子对称加权得出正则化加权矩阵补全模型及目标函数.最后，结合BCD和ALS方法，使SW算法迭代得出最优低秩补全矩阵.仿真结果表明，SW算法与现有算法相比具有更高的精度，适用于处理大量和高维的数据.其次，SW算法的收敛速度明显提高，更高效地完成数据矩阵补全.下步将根据各类数据矩阵的稀疏程度和特性，继续深入研究这种稀疏度对算法性能的影响.