對稱加權(quán)算法對數(shù)據(jù)矩陣補全的優(yōu)化研究

劉 云， 鄭文鳳， 張 軼

(昆明理工大學信息工程與自動化學院， 昆明 650500)

1 引 言

數(shù)據(jù)分析中經(jīng)常存在數(shù)據(jù)值的缺失，在數(shù)據(jù)預(yù)處理中補全丟失數(shù)據(jù)可進行更有效的數(shù)據(jù)分析，廣泛應(yīng)用于圖像處理，醫(yī)療疾病預(yù)測和電子商務(wù)推薦等領(lǐng)域[1].尤其高維數(shù)據(jù)的矩陣稀疏性很強，解決數(shù)據(jù)矩陣稀疏問題可以實現(xiàn)數(shù)據(jù)補全，用低秩矩陣分解(Low-Rank Matrix Factorization, LRMF) 重構(gòu)矩陣是解決數(shù)據(jù)矩陣補全 (Matrix Completion，MC)問題的主流方法[2-3].LRMF引起了非凸優(yōu)化問題，傳統(tǒng)方法用矩陣的秩凸近似解，即核范數(shù)近似優(yōu)化[4].

Fan等人[5]基于稀疏因子分解方法，將不完整矩陣分解為密集矩陣和稀疏矩陣，提出加速近端交替線性最小化(Accelerated Proximal Alternating Linearized Minimization, APALM)算法,解決了稀疏分解方法的非凸優(yōu)化問題，更適合對從多個子空間提取的數(shù)據(jù)進行矩陣補全.Zhang等人[6]根據(jù)非凸非光滑秩(Nonconvex Nonsmooth Rank, NNR)松弛函數(shù)，建議使用雙重NNR(Double Nonconvex Nonsmooth Rank, DNNR)函數(shù)近似低秩恢復(fù)函數(shù)，提出通用的迭代重加權(quán)奇異值函數(shù) (Iteratively Reweighted Singular Values Function, IRSVF)算法，閉式解決了DNNR函數(shù)最小化收斂問題，性能上優(yōu)于其他核范數(shù)加權(quán)方法，更適合解決數(shù)據(jù)矩陣補全非凸優(yōu)化問題.Canyi等人[7]建議使用l0范數(shù)的非凸替代矩陣的奇異值近似低秩函數(shù)，提出迭代重加權(quán)核范數(shù)(Iteratively Reweighted Nuclear Norm,IRNN)算法來解決非凸非光滑低秩最小化問題，并通過將各種稀疏性強加于奇異值向量上，解決了加權(quán)奇異值閾值問題，比傳統(tǒng)方法更適合低秩矩陣恢復(fù).

為降低傳統(tǒng)MC算法的計算復(fù)雜度，提高補全精度，提出對稱加權(quán) (Symmetric Weighting，SW)算法.主要針對非凸LRMF的正則化補全模型，利用稀疏性提出加權(quán)MC模型；再對分解后的矩陣因子選擇共同的對稱矩陣加權(quán)，通過正則化矩陣聯(lián)合列稀疏性耦合矩陣因子，利用列修剪減少矩陣列元素，促進矩陣秩最小化達到目標矩陣的秩；結(jié)合塊坐標下降(Block Coordinate Descent, BCD)[8]和交替最小二乘法 (Alternating Least Squares，ALS)[9],交替迭代得到最優(yōu)低秩補全數(shù)據(jù)矩陣.仿真結(jié)果，相比于現(xiàn)有的算法,SW算法可以更快更準確地補全數(shù)據(jù)，并且適用于高維數(shù)據(jù)補全.

2 正則化矩陣分解補全

假設(shè)不完整矩陣Y之間的元素有較高的連續(xù)性，采樣產(chǎn)生一個低秩結(jié)構(gòu)化矩陣X，通過低秩最小化來恢復(fù)其缺失的元素，如圖1.

為了優(yōu)化低秩矩陣恢復(fù)，首先提出一個通用的矩陣秩最小化問題，如下式.

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 正則化低秩矩陣分解補全流程

為了優(yōu)化低秩最小化問題，通常對低秩數(shù)據(jù)矩陣X進行分解，如圖1用矩陣Um×r和矩陣Vn×r的轉(zhuǎn)置相乘表示，即X=UVT.其中r≤ min(m,n)，這種方法在處理大規(guī)?；蚋呔S數(shù)據(jù)時可以減少相關(guān)變量的大小，使計算復(fù)雜度O(mn) 降低到O( (m+n)r)[11].新的LRMF優(yōu)化秩最小化的補全模型如下式.

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

(3)

通常矩陣X的秩r未知，高估重構(gòu)矩陣X的秩r為d，有d≥r，因此要懲罰UVT的秩，找到實際的秩r.考慮如下矩陣乘積UVT的一階分解，如下式.

(4)

根據(jù)秩的可加性，降低式(4)右邊項的一個秩會導(dǎo)致左邊項UVT的秩相應(yīng)減少.由此引入一個列修剪過程，即通過迭代刪除矩陣中被清零的列，逐漸降低計算復(fù)雜度[12].

其次，考慮矩陣U和V的聯(lián)合列稀疏性，添加一個正則化過程，用l2范數(shù)表示懲罰項優(yōu)化MC模型，如下式.

(5)

該正則化方法中，ui和vi分別是矩陣U和V的第i列元素，通過正則化矩陣因子中的列元素降低模型的復(fù)雜度.考慮矩陣Y可能添加了獨立同分布的高斯噪聲，根據(jù)拉格朗日定理式(5)可以等效如下式.

(6)

(7)

如果在式(5)中給分解后的矩陣因子添加一個權(quán)重，可以促進稀疏性，更快得到式(7)中的低秩補全矩陣.

3 對稱加權(quán)(SW)算法

目前已經(jīng)有很多優(yōu)化矩陣補全問題的加權(quán)方案.其中，重加權(quán)Frobenius范數(shù)優(yōu)化矩陣補全模型如下式.

(8)

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

(9)

tr{X}表示矩陣X的跡，可知W是對稱權(quán)重矩陣，且每次迭代的W值由上一次迭代后獲得的矩陣X計算得到，

W= (XTX)p/2-1

(10)

當p=1時，Schatten-p范數(shù)等價于核范數(shù)‖X‖*，根據(jù)LRMF非凸性，常用矩陣X的核范數(shù)近似代替矩陣的秩解決非凸優(yōu)化問題.式(1)中秩最小化問題用加權(quán)核范數(shù)解決，得到新的矩陣補全模型，

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

(11)

(12)

因此，可以定義一個具有嚴格上界的核范數(shù)來解決式(11)中的最小化問題，如下式.

(13)

利用核范數(shù)在矩陣U和V產(chǎn)生一個平滑度，促進了低秩最小化.

3.1 SW算法

基于正則化矩陣分解補全，分別對數(shù)據(jù)矩陣因子U和V加權(quán)，得到加權(quán)目標函數(shù)，如圖2所示.其次，利用ALS方法可以更好地處理稀疏矩陣的分解問題，得到數(shù)據(jù)補全的最優(yōu)矩陣.

圖2 對稱加權(quán)矩陣補全框圖Fig.2 Symmetrical weighted matrix completionblock diagram

結(jié)合式(13)得到矩陣的重加權(quán)Frobenious范數(shù)和的最小化補全模型，如下式.

(14)

為了解決上述最小化問題，定義一個低秩函數(shù)，如下式.

(15)

根據(jù)式(10)利用對稱性設(shè)置權(quán)值WU=(UTU)p-1和WV=(VTV)p-1，當p=1時，WU=WV=Id,可以得到式(13)中的核范數(shù)變分形式，假設(shè)WU=WV=W，有

(16)

式中，0

(17)

正則化聯(lián)合列稀疏性可以更快的懲罰秩，但該方法具有不光滑性且不可以分離矩陣U和V中的元素.為了使優(yōu)化問題變得光滑，根據(jù)函數(shù)中的正則化項，添加一個很小的正常數(shù)η2得到可微優(yōu)化[14].

(18)

該簡易方法緩解了梯度不連續(xù)的點，可以得到使目標函數(shù)最小化的唯一平穩(wěn)點.則根據(jù)正則化矩陣分解補全模型定義的目標函數(shù)f(U,V)如下式，

(19)

最后，結(jié)合BCD和ALS處理U和V，首先通過給定一個可用的初始化矩陣V更新為矩陣Vk，每次迭代時最小化目標函數(shù)的局部上界得到Uk+1；其次,使用Uk+1最小化另一個局部上界得到Vk+1.該方法解決了兩個矩陣因子的不可分性，主要步驟如下.

步驟1在點 (Uk,Vk)對f(U,Vk)近似二階泰勒展開，該展開式定義為上界函數(shù)h(U|Uk,Vk)，求其最小化.h(U|Uk,Vk) 是嚴格凸的，此松弛方法可以閉式表達，得到最優(yōu)的低秩補全矩陣.

(20)

其中，

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

(21)

(22)

(23)

式中，

(24)

步驟2在點 (Uk+1,Vk)對f(Uk+1,V)近似二階泰勒展開，定義為上界函數(shù)l(V|Uk+1,V)，求其最小化.

(25)

其中，

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

(26)

(27)

算法1對稱加權(quán)算法(SW)

輸入：

1) 不完全矩陣Y

2) 低秩正則化參數(shù)λ>0

初始化：

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

迭代計算：

6)k=k+1

7) 判斷是否收斂，收斂時輸出，否則轉(zhuǎn)步驟4)

輸出：

算法1中，步驟1)～2)輸入需要補全的矩陣Y和正則化參數(shù)λ，根據(jù)式(2)和式(3)對低秩矩陣采樣分解.

步驟3)初始化迭代次數(shù)k=0,則分解后的低秩矩陣因子為U0和V0.再由式(24)運算得到D(U0,V0)，代入式(23)和(27)得到近似的Hessian矩陣.

步驟4)～5)根據(jù)式(20)和式(25)交替計算局部目標函數(shù)的最小值，兩次連續(xù)迭代間的重構(gòu)數(shù)據(jù)相對減少時算法收斂，得到最優(yōu)的低秩矩陣因子.

3.2 SW算法收斂性分析

SW算法每次迭代的最小化函數(shù)h(U|Uk,Vk) 和l(V|Uk+1,V) 是函數(shù)f(U,Vk) 和f(Uk+1,V)的嚴格上界，因此，局部替代函數(shù)是實際目標函數(shù)的上界.如命題1，算法每次迭代后的目標函數(shù)單調(diào)遞減.

命題1通過SW算法產(chǎn)生的順序集{Uk,Vk}的目標函數(shù)是單調(diào)遞減的，如式(28)，

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

(28)

證明：已知h(U|Uk,Vk)≥f(U,Vk)，結(jié)合式(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)

結(jié)合式(30)和式(31)，可得到命題1.

命題2在k→∞時，目標函數(shù)f(Uk,Vk)收斂，有f∞≥0.

證明 通過命題1可知SW 算法的目標函數(shù)單調(diào)遞減，并且下界是0，因此，當k→∞時，f∞≥0.通過該結(jié)論可以分析算法的收斂點和收斂速度.

1) 收斂到平穩(wěn)點.

SW算法通過單調(diào)遞減的目標函數(shù)更新矩陣(Uk,Vk) ,可以推出目標函數(shù)到平穩(wěn)點的收斂速度.給出任何一對(U,V) ,通過下面的最小化問題定義矩陣U*和V*.

(32)

(33)

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

(34)

推論：算法中目標函數(shù)f(U,V)的連續(xù)目標值的差值有下界，結(jié)果如式(35),

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

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

(35)

命題3當且僅當(U,V)是SW算法得到的平穩(wěn)點時,Δ((U,V),(U*,V*)) = 0.

證明：假設(shè)(U,V)是一個平穩(wěn)點，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)是嚴格凸函數(shù)，(U*,V*)是唯一極值解，因此，只有當(U,V) =(U*,V*)時，結(jié)論成立.所以(U*,V*)也是最小化目標函數(shù)的一個平穩(wěn)點.

如上所述,Δ((Uk,Vk),(Uk+1,Vk+1))用來量化算法連續(xù)迭代生成的(Uk,Vk)和(Uk+1,Vk+1)之間的距離，當Δ= 0時，算法收斂到平穩(wěn)點(Uk+1,Vk+1).

2) 收斂速度.

當λ>0時，由算法產(chǎn)生的序列{Uk,Vk}的極值點是目標函數(shù)f(U,V)的一個平穩(wěn)點.定義一個值ξk，ξk=Δ((Uk,Vk),(Uk+1,Vk+1))，假設(shè)一個K→∞.

f(U1,V1)-f∞<∞

(38)

(39)

4 仿真分析

4.1 數(shù)據(jù)集

與類似算法仿真一致，仿真分析采用數(shù)據(jù)稀疏性較強的通用數(shù)據(jù)源MovieLens數(shù)據(jù)集，該數(shù)據(jù)集包含用戶信息、電影信息以及多個用戶對多部電影的評分，其評分數(shù)據(jù)矩陣非常稀疏，因此，可用該數(shù)據(jù)集來研究數(shù)據(jù)矩陣的缺失填補算法，對潛在用戶的評分進行預(yù)測[17](MovieLens開源數(shù)據(jù)集網(wǎng)站https://grouplens.org/datasets/movielens/).其中，MovieLens100 K是經(jīng)過充分研究的大型數(shù)據(jù)集，包含在不同時段收集的用戶評分，用整數(shù)1到5表示.

表1 MovieLens100 K的數(shù)據(jù)集信息

如表1所示，在MovieLens100 K數(shù)據(jù)集缺失93.7%的評分數(shù)據(jù)，稀疏性很強.我們分別對數(shù)據(jù)隨機采樣65%，50%和35%作為訓(xùn)練集，25%，35%和45%作為驗證集，其余作為測試集.建立一個943×1682的電影評分矩陣，假設(shè)不同用戶的評分之間存在較高的相關(guān)性，找出低秩結(jié)構(gòu)數(shù)據(jù)矩陣，進行數(shù)據(jù)補全.

4.2 歸一化平均絕對誤差分析

為了評估算法的補全精度，對歸一化平均絕對誤差(Normalized Mean Absolute Value Error，NMAE)進行分析[5-6].card(·)表示集合的基數(shù)，NMAE定義為

表2 在兩種條件下算法對隨機采樣數(shù)據(jù)的NMAE

從表2中可以看到，隨機采樣65%的訓(xùn)練數(shù)據(jù)集時，算法在達到收斂時的NMAE值最小，且有適當?shù)尿炞C數(shù)據(jù)調(diào)整超參數(shù)，優(yōu)化模型.因此，在保證驗證集和測試集的比例上，盡可能多采樣訓(xùn)練數(shù)據(jù)得到的模型泛化能力更好.針對最優(yōu)的訓(xùn)練模型，分別得出4種算法在不同迭代時間下的補全誤差，分析NMAE值.

圖3 條件A中采樣MovieLens100K數(shù)據(jù)集的精度分析

圖4 條件B中采樣MovieLens100 K數(shù)據(jù)集的精度分析

從圖3和圖4可以看出，在A，B兩種條件下，算法的NMAE值隨迭代次數(shù)的增加都逐漸減小，最終趨于平穩(wěn)點.APALM和IRNN算法收斂時的NMAE值穩(wěn)定在0.2～0.3，IRSVF和SW算法收斂時的NAME值穩(wěn)定在0.1～0.2.IRNN算法迭代的時間最久，APALM算法雖減少了迭代次數(shù)，但精度不夠高，IRSVF算法的計算量仍然較大，而SW算法誤差最低，提高了補全精度，并且在條件A中該算法的時間復(fù)雜度明顯降低.

4.3 收斂性分析

通過迭代產(chǎn)生的矩陣因子序列之間的相似度測量，計算兩個連續(xù)目標函數(shù)之間的差值，可以得到算法收斂時的情況.針對A，B兩種條件，在第一種采樣數(shù)據(jù)訓(xùn)練的模型中分析APALM，IRSVF，IRNN和SW算法的收斂性.

圖5 條件A中連續(xù)目標函數(shù)差值隨時間的演變

圖6 條件B中連續(xù)目標函數(shù)差值隨時間的演變

從圖5和圖6可以看出四種算法在收斂時的情況.IRSVF和IRNN算法在兩種條件下的平均每次迭代時間復(fù)雜度很高，并且收斂效果不好.其他兩種算法的收斂效果差不多，但在條件A中明顯看出APALM算法收斂時的迭代時間更長.SW算法在兩種條件下的收斂效果都較好且平均每次迭代的時間復(fù)雜度最低，特別是在條件A中收斂時的時間不到其他算法的20%.

通過NMAE和收斂性分析表明，SW算法對比于其他三種算法可以更精確的補全數(shù)據(jù)矩陣，并且降低時間計算復(fù)雜度并不會影響該算法的補全性能.其次，SW算法的列修剪優(yōu)化在很大程度上減少了計算負擔，使仿真數(shù)據(jù)集收斂時的迭代次數(shù)更少，收斂速度明顯比現(xiàn)有算法快，可更高效的進行補全.

5 結(jié) 論

用矩陣表示數(shù)據(jù)集，可以高效解決數(shù)據(jù)分析中的缺失元素問題，高維數(shù)據(jù)矩陣也可以用低維特征表示或重構(gòu).根據(jù)LRMF的補全模型，利用正則化矩陣聯(lián)合列稀疏性，進行列修剪降低計算復(fù)雜度.然后基于加權(quán)稀疏矩陣的思想，對矩陣因子對稱加權(quán)得出正則化加權(quán)矩陣補全模型及目標函數(shù).最后，結(jié)合BCD和ALS方法，使SW算法迭代得出最優(yōu)低秩補全矩陣.仿真結(jié)果表明，SW算法與現(xiàn)有算法相比具有更高的精度，適用于處理大量和高維的數(shù)據(jù).其次，SW算法的收斂速度明顯提高，更高效地完成數(shù)據(jù)矩陣補全.下步將根據(jù)各類數(shù)據(jù)矩陣的稀疏程度和特性，繼續(xù)深入研究這種稀疏度對算法性能的影響.