對稱加權算法對數據矩陣補全的優化研究

劉 云， 鄭文鳳， 張 軼

(昆明理工大學信息工程與自動化學院， 昆明 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算法的收斂速度明顯提高，更高效地完成數據矩陣補全.下步將根據各類數據矩陣的稀疏程度和特性，繼續深入研究這種稀疏度對算法性能的影響.