陳 熙，鄧杰臣，席勢(shì)鴻，劉曉辰，張相君，馮月華

（上海工程技術(shù)大學(xué) a.機(jī)械與汽車工程學(xué)院；b.航空運(yùn)輸學(xué)院（飛行學(xué)院）；c.數(shù)理與統(tǒng)計(jì)學(xué)院，上海 201620）

隨著信息技術(shù)的發(fā)展，人們能獲取的信息越來(lái)越多，但從這些龐大的信息中尋找出自己所感興趣的信息比較困難，而推薦系統(tǒng)可以通過(guò)搜集不同用戶的信息需求來(lái)自動(dòng)預(yù)測(cè)出用戶可能需要的信息，并將這些信息推送給用戶.目前，推薦系統(tǒng)廣泛應(yīng)用于各種領(lǐng)域，如電影、音樂(lè)、新聞、書(shū)籍、研究文章、搜索查詢、金融服務(wù)、人壽保險(xiǎn)等[1].

推薦系統(tǒng)中一個(gè)典型是Netflix 推薦系統(tǒng)[2].Netflix 是一家提供電影租賃服務(wù)的公司，擁有超過(guò)兩千萬(wàn)的用戶群，每位用戶都可依據(jù)自己的感受對(duì)觀賞過(guò)的電影進(jìn)行1～5 分的評(píng)價(jià).由于影片數(shù)目眾多，影評(píng)人不可能將每部影片都看完才評(píng)出分值.相對(duì)于整個(gè)數(shù)表構(gòu)成的矩陣，已知分值對(duì)應(yīng)的元素個(gè)數(shù)很少，而且通常僅有很少的幾個(gè)因素能夠影響和決定用戶對(duì)某部電影的評(píng)價(jià)，從而矩陣可以看作是低秩的，矩陣填充理論為這個(gè)數(shù)表的未知元素的精確填充提供了可行途徑[3].

針對(duì)矩陣填充問(wèn)題，國(guó)內(nèi)外眾多學(xué)者提出諸多求解此問(wèn)題的算法，如奇異值閾值算法(SVT)、固定點(diǎn)連續(xù)算法(FPC)、不精確的增廣Lagrange乘子法(IALM)等[3?4].這些算法中最為復(fù)雜的部分是計(jì)算奇異值分解(Singular Value Decomposition，SVD)，并且IALM 被證明是這些算法中最精確和有效的算法.對(duì)于SVD 的計(jì)算，古典方法為L(zhǎng)ANSVD 算法[5]，但該方法在數(shù)據(jù)量很大時(shí)效率較低.Drineas 等[6]提出線性時(shí)間的SVD 方法，此方法雖然在效率上有很大提升，但其精度差[4].此外，計(jì)算SVD 的方法還有隨機(jī)SVD，帶有子空間迭代的隨機(jī)SVD、TUXV、FFSRQR 算法等[4,7]，由于這些方法需要多次訪問(wèn)原始數(shù)據(jù)，因此在數(shù)據(jù)量特別大的情形下其效率有待改進(jìn).

為提高求解矩陣填充問(wèn)題的效率，本研究基于隨機(jī)算法策略，高效數(shù)據(jù)訪問(wèn)的要求并結(jié)合IALM 算法，提出一種新的高效算法求解矩陣填充問(wèn)題，并用Matlab 軟件實(shí)現(xiàn)該算法.

1 隨機(jī)算法

任意給定一個(gè)矩陣A∈Rm×n，其奇異值分解(SVD)是將A分 解成3 個(gè)矩陣的乘積，即A=UΣV.其中，U=(u1,u2,···um)∈Rm×m和V=(v1,v2,···vn)∈Rn×n為正交矩陣，對(duì)角矩陣Σ ∈Rm×n的對(duì)角元滿足σ1≥σ2≥···≥σm≥0.在大數(shù)據(jù)分析和機(jī)器學(xué)習(xí)中，SVD 已成為一種關(guān)鍵的分析工具[4].

隨著大數(shù)據(jù)時(shí)代到來(lái)，SVD 和QR 等經(jīng)典的高內(nèi)存消耗和高計(jì)算復(fù)雜度的算法已經(jīng)無(wú)法滿足時(shí)代發(fā)展需求.近年來(lái)隨機(jī)算法的發(fā)展為構(gòu)造近似SVD 算法提供一個(gè)強(qiáng)大的工具.與古典確定性的數(shù)值算法比較，隨機(jī)算法簡(jiǎn)單而有效，運(yùn)行效率更高，更具魯棒性，使用內(nèi)存空間更少.Tropp 等[7]基于列隨機(jī)采樣提出了單步隨機(jī)奇異值分解(SPRSVD)算法計(jì)算給定矩陣的近似SVD，具體內(nèi)容見(jiàn)算法1.其中，符號(hào)“?”表示矩陣的廣義逆.該算法只在最開(kāi)始時(shí)用到原始數(shù)據(jù)集，因此具有高效的數(shù)據(jù)訪問(wèn)能力.

算法1 SPRSVD 算法

輸入：矩陣A∈Rm×n，目標(biāo)秩k，過(guò)采樣參數(shù)p≥0，整數(shù)l≥(k+p).輸出：

包含矩陣A的前k個(gè)近似左奇異向量的列正交矩陣U∈Rm×k；

包含矩陣A的前k個(gè)近似奇異值的對(duì)角矩陣Σ ∈Rk×k；

包含矩陣A的前k個(gè)近似右奇異向量的列正交矩陣V∈Rn×k.過(guò)程：

生成兩個(gè)一致獨(dú)立同分布的高斯矩陣?1∈

計(jì)算Y=A?1,W=?2A；

計(jì)算Y的正交矩陣Q:Q=orth(Y)；

計(jì)算B=(?2Q)?W；

計(jì)算B的奇異值分解:[U,Σ,V]=svd(B)；

計(jì)算U=Q?U；

計(jì)算U=U(:,1:k),Σ=Σ(1:k,1:k),V=V(:,1:k).

2 矩陣填充問(wèn)題

矩陣填充問(wèn)題的基本內(nèi)容是通過(guò)少量觀測(cè)值來(lái)恢復(fù)整個(gè)矩陣，核心是一個(gè)在隨機(jī)約束下的仿射秩最小問(wèn)題:

式中：M為待恢復(fù)的原始矩陣；?為均勻隨機(jī)采樣集.由于求解此類問(wèn)題是NP 難問(wèn)題，目前主流思想是將該模型轉(zhuǎn)化為核范數(shù)最小問(wèn)題，表達(dá)式為

式中：∥X∥?為核范數(shù)，表示X的奇異值之和.矩陣填充問(wèn)題式(1)可以改寫(xiě)為

式中：π?:Rm×n→Rm×n為一個(gè)正交投影算子，它使在 ?內(nèi)的元素不發(fā)生改變，而在 ?外的元素為零.在文獻(xiàn)[8]中，作者應(yīng)用IALM 算法求解上述問(wèn)題，具體見(jiàn)算法2.在算法2 中，Sω(x)=sgn(x)·max(|x|?ω,0)是一個(gè)軟收縮算子且x∈Rn,ω>0，為 ?的補(bǔ)集.

算法2 IALM 算法

輸入：原始矩陣M，采樣數(shù)據(jù)集 ?，采樣元素π?(M)，正數(shù)λ,μ0,精度 tol，ρ>1.

輸出：

矩陣對(duì)(Xk,Ek).

過(guò)程：

k=0,Y0=0,E0=0；

當(dāng)算法不收斂時(shí)，開(kāi)始循環(huán)操作：

更新μk+1=，k=k+1，當(dāng)∥M?Xk?Ek∥F/∥M∥F

3 新算法IALM-SPRSVD

在大數(shù)據(jù)環(huán)境中，數(shù)據(jù)集越來(lái)越大，對(duì)算法的效率要求也越高.算法2 中計(jì)算代價(jià)最大的是循環(huán)中計(jì)算SVD，因此本節(jié)將用SPRSVD 取代算法2 中的SVD，得到更高效的求解矩陣填充問(wèn)題的算法，并將此算法命名為IALM-SPRSVD，具體見(jiàn)算法3.

算法3 IALM-SPRSVD 算法

輸入：原始矩陣M，采樣數(shù)據(jù)集 ?，采樣元素π?(M)，正數(shù)λ,μ0,，精度 tol，ρ>1.目標(biāo)秩kr=5，過(guò)采樣參數(shù)p=5.

輸出：

矩陣對(duì)(Xk,Ek).

過(guò)程：

k=0,Y0=0,E0=0；

當(dāng)算法不收斂時(shí)，開(kāi)始循環(huán)操作：

更新μk+1=k=k+1，當(dāng)∥M?Xk?Ek∥F/

4 數(shù)值試驗(yàn)

在本節(jié)中，通過(guò)幾個(gè)數(shù)值試驗(yàn)驗(yàn)證新算法IALM-SPRSVD，并與LANSVD 以及Matlab 自帶的svds 命令進(jìn)行比較.針對(duì)IALM 算法中需要計(jì)算SVD 的步驟分別用LANSVD、SVDS 和SPRSVD方法，對(duì)應(yīng)的算法分別命名為IALM-LANSVD、IALM-SVDS 和IALM-SPRSVD.所有試驗(yàn)都是在一臺(tái)擁有2.9 GHz Intel Core i5 處理器和8Gb RAM的筆記本電腦上進(jìn)行的.本研究選取Jester Joke 數(shù)據(jù)集來(lái)完成數(shù)值實(shí)驗(yàn)，該數(shù)據(jù)集可以在Jester 網(wǎng)站下載.Jester Joke 數(shù)據(jù)集由73,421 個(gè)用戶針對(duì)100 個(gè)笑話產(chǎn)生的410 萬(wàn)個(gè)評(píng)分組成，具體包括以下3 個(gè)子集.

jester-1:數(shù)據(jù)來(lái)自24 983個(gè)用戶，他們對(duì)36個(gè)或更多的笑話進(jìn)行了評(píng)級(jí)；

jester-2:數(shù)據(jù)來(lái)自23 500個(gè)用戶，他們對(duì)36個(gè)或更多的笑話評(píng)分；

jester-3:數(shù)據(jù)來(lái)自24 938個(gè)用戶，他們對(duì)15～35個(gè)笑話評(píng)分.

對(duì)于每個(gè)數(shù)據(jù)集，令M為原始數(shù)據(jù)矩陣，其中Mij為用戶i對(duì)第j個(gè)笑話的評(píng)分；Γ為Mij中已知元素的索引集.采用歸一化平均絕對(duì)誤差(NMAE)來(lái)衡量矩陣填充算法的質(zhì)量，公式為

式中：Xij為用戶i對(duì)笑話j的預(yù)測(cè)評(píng)分；rmax、rmin分別為評(píng)分的上界和下界.在試驗(yàn)過(guò)程中，令rmax=10，rmin=?10，結(jié)果見(jiàn)表1.

表1 矩陣填充問(wèn)題的比較Table 1 Comparison of matrix completion problems

從結(jié)果觀察到，對(duì)于這3 個(gè)數(shù)據(jù)集IALMSPRSVD 實(shí)現(xiàn)了與其他方法幾乎相同的可恢復(fù)性，并且效率比IALM-LANSVD 提高了兩倍左右，與IALM-SVDS 相比，提高程度也接近30%.

5 結(jié)語(yǔ)

本研究基于隨機(jī)算法提出了IALM-SPRSVD算法，改進(jìn)了原有IALM 算法在求解矩陣填充問(wèn)題上的效率.由于實(shí)際的數(shù)據(jù)集通常具有稀疏性，本研究將在現(xiàn)有研究基礎(chǔ)上，在后續(xù)工作中研究適應(yīng)數(shù)據(jù)集稀疏性的算法.