一種帶偏置的非負矩陣分解推薦算法

王建芳,劉冉東,劉永利

(河南理工大學 計算機科學與技術學院,河南 焦作 454000)

1 引 言

推薦系統[1]的一個基本功能是利用用戶-項目評分矩陣中已知評分預測未知評分,將預測評分高的項目推薦給用戶,但是在研究過程中面臨著諸多難題,其中最為典型的就是由數據的高維稀疏性帶來的對稀疏用戶(評價項目較少的用戶)評分預測準確度不高的問題.

在現代化推薦系統中,用戶、項目的數量通常都是呈指數級.隨著項目數量的增加,用戶評價的項目在總項目中所占比例越來越小,如果仍然采用適用于低維數據的相似性度量方法[2]度量用戶、項目之間的相似性[3],計算得到用戶之間的相似區分度較低,隨著數據量的增加,相似度的計算量將成指數增長.針對稀疏矩陣中評分預測問題,近年來研究者們采用了各種各樣的方式,Koren Y[4]提出把矩陣分解技術[5]應用到推薦系統中,文中把用戶-項目評分矩陣Rm×n分解為兩個K(K≤m,n)維的用戶-隱因子矩陣Pm×k和項目-隱因子矩陣qk×n,利用分解后的隱因子矩陣預測評分,該算法與傳統的協同過濾推薦算法相比預測準確度上有比較大的提升,但是在分解后的矩陣中出現的負值與用戶-隱因子、項目-隱因子原理不符.Lin C[6]提出利用每一個不為零的評分更新Pm×k、qk×n的NMF(Non-negative Matrix Factorization,NMF)算法.NMF算法在充分擬合已知評分的基礎上對用戶評分預測具有以下特點:

1)相似用戶m、t分解后對應的行向量Pm,·與qt,·相似度比較高.

2)相似用戶m、t分解后對應的列向量q·,m與q·,t相似度比較高.

由以上分析可知NMF算法有助于提高相似用戶的預測準確性,但在對稀疏用戶評分預測方面表現一般,為了解決這一問題,本文在NMF算法的基礎上,提出一種由SVD[7]初始化,融合用戶和項目偏執信息的非負矩陣分解算法,稱為RBNMF(Recommend with Bias Information NMF,RBNMF)算法,與傳統矩陣分解算法相比RBNMF算法的稀疏用戶預測準確性有較大提高.

2 相關工作

2.1 矩陣分解

矩陣分解模型[8]假設用戶對項目的評分受到若干隱因子[9]的影響,將用戶和項目映射到一個共同的隱因子空間中,這種情況在實際工作中具體表現為:如果用戶喜歡《c語言程序設計》這本書,背后的原因可能是用戶喜歡編程、用戶喜歡譚浩強本人或用戶對c語言比較感興趣等,這背后的原因就稱為隱因子.但是在矩陣分解的過程中有些隱因子不能給出明確的解釋,所以矩陣分解模型又稱為隱語義模型.

矩陣算法是將用戶-項目評分矩陣Rm×n分解成兩個低維度的矩陣乘積,如公式(1)所示:

Rm×n≈Pm×k×qk×n

(1)

其中,m表示用戶的個數,n表示項目的個數,k<

(2)

其中,K表示已知評分,Pu,·表示Rm×n分解后Pm×k中的行向量,q·,i表示Rm×n分解后qk×n中的列向量,λ表示正則化因子.基于矩陣分解的算法由于隱因子k<

2.2 奇異值矩陣

在推薦系統中,SVD[12]作為一種矩陣分解技術,通過分解產生低秩矩陣[13]近似逼近原始矩陣.在一個給定的矩陣A中奇異值分解可由公式(3)表示.

A=U×S×VT

(3)

其中,U∈Rm×m,V∈Rn×n,S∈Rm×n,矩陣U和V是正交矩陣,矩陣的列分別是AAT、 ATA的特征向量.矩陣S=diag(σ1,…,σr),σ1≥σ2≥…≥σr≥0,其中r是矩陣R的秩;σr是R的奇異值.

SVD算法可以分解為三個矩陣相乘對原始矩陣A進行最優逼近,通過將矩陣S保留前K個最大的奇異值進行化簡得到更新后的對角矩陣,其中k<

(4)

2.3 Baseline 預測

測試算法性能好壞,往往需要建立一個對比基線[14],在對比的基礎上觀察后續試驗效果的變化.觀測到的評分數據有一些和用戶無關的因素產生的效果,即一部分因素是和用戶對物品的喜好無關而只取決于用戶或物品本身的特性,例如,樂觀的用戶對于一些項目的評分普遍較高,而悲觀的用戶對項目的評分普遍較低,也就是說即使這兩類用戶對同一項目的評分相同,但是對物品的喜好程度確是不一樣的.對于項目來說道理是一樣的,受用戶歡迎的項目評分普遍較高,不受用戶歡迎的項目評分較低,加入偏執信息的評分預測公式如公式(5)表示:

R*(i,j)=μ+bu(i)+bi(j)

(5)

其中,R*(i,j) 表示用戶i對項目j的預測評分,μ為數據集的總體偏置信息,bu(i)表示用戶i的偏置信息,bi(j) 表示項目j的偏置信息.假如項目η的總體偏置為a,項目η的口碑普遍高于其它項目的值為b,如果用戶U1是悲觀嚴謹的,其bu(i)值為c,那么U1對項目η的預測值為a+b-c.

在計算偏置信息時,求解bu(i) 和bi(j)的值如公式(6)所示.

(6)

其中,μ表示所有已被評價項目的總體偏置,u表示用戶,i表示項目,I表示用戶u評價過的項目集合,|I| 表示集合的個數,Ui表示評價過項目i的用戶集合,|Ui|表示集合的個數,參數λ1,λ2需要實驗時確定.

2.4 NMF算法

對于現代化推薦系統來講需要處理的數據量非常龐大,在現有矩陣分解的基礎上Lin C提出了一種時間復雜度比較低的NMF[15]算法,該算法利用每一個已知評分項更新分解后的用戶-隱因子矩陣Pm×k和項目-隱因子矩陣qk×n.在Lin C算法的基礎上,為了防止分解后的矩陣出現過擬合[16],加入正則項的乘性迭代如公式(7)所示.

(7)

3 RBNMF算法

3.1 理論的分析

為了更好利用NMF算法提升對稀疏用戶評分的預測準確度,本文在誤差函數中把用戶、項目的偏置信息與用戶-隱因子矩陣Pm×k和項目-隱因子矩陣qk×n相結合,為了防止Pm×k、qk×n在訓開始階段陷入局部最優解,利用SVD算法初始化Pm×k、qk×n.由上文可知融入了用戶、項目偏置的損失函數可用公式(8)表示:

(8)

其中,μ表示項目的總體偏置,bu表示用戶的偏置,bi表示項目i的偏置,Pm×k、qk×n是分解后的與用戶和項目相關的矩陣,λp,λq,是正則化因子,Rk表示不為零評分項的集合,由公式(8)可以得出Pm×k、qk×n的更新方式如公式(9)所示.

(9)

其中,ηu,k,ηk,i,,表示每次更新步長,為了使用使分解后的矩陣符合隱因子原理,本文采用乘性迭代保證每次迭代的值都為正,對公式(9)進行如下改進:

1)把公式(9)簡化為公式(10).

2)為了迭代過程中出現乘性迭代,對于參數選擇的主要目的是消掉相加的第一項,經過化簡得到ηu,k,ηk,i,如公式(11)所示.

(10)

(11)

其中,上式中Ui表示評價過項目的用戶集合,Iu表示被用戶評價過的項目集合,將式(11)、代入(10)得到pu,k,qk,i的乘性迭代公式如公式(12)、(13)所示.

(12)

(13)

評分形成有四部分構成,數據集總體偏置、用戶偏置、項目偏置、預測值.具體可用公式(14)表示:

(14)

3.2 RBNMF算法流程

輸入:用戶項目評分矩陣Rm×n,初始用戶隱因子矩陣Pm×k,初始項目隱因子矩陣qk×n,訓練次數Round=1000次,初始化用戶偏置向量bum和項目偏置向量bin,初始正則化因子λp,λq.初始化中間計算過渡矩陣UP,UD,IP,ID.

輸出:用戶隱因子矩陣Pm×k,項目隱因子矩陣qk×n,μ,bum,bin.

算法基本流程如下:

步驟2.利用初始化的Pm×k、Qk×n計算μ,由此利用公式(6)計算出bum,bin.

步驟3.利用每一個不為零的評分項訓練出中間矩陣值.

for (Ri,j≠0) do

將過渡矩陣UP,UD,IP,ID初始化為0矩陣.

for (f=1;f

end

end

for (每一個用戶)

for (f=1;f

Pm,f=Pm,f·UPm,f∕UDm,f;

end

end

for (每一個項目)

for (f=1;f

Qf,n=Qf,n·IPf,n∕IDf,n;

end

end

步驟4.利用測試集測試及一次訓練生成的Pm×k、Qk×n、bum、bin及公式(15)計算RMSE值.

if 前一次得到的RMSE值大于這次的值,

進入下一次訓練;

else

記錄當前參數值;

end

步驟5.返回最優參數值及Pm×k、Qk×n、μ、bum、bin.

4 實驗分析

在本節中,首先介紹實驗數據集的來源,然后介紹實驗參數的確定,最后進行對比試驗并分析實驗結果.

本文進行的實驗主要解決以下幾個問題:

1)偏置參數的確定.

2)潛在因子維度對推薦質量的影響.

3)本算法與NMF與RBNMF推薦算法對稀疏用戶評分預測比較.

4.1 實驗數據集

本實驗分別在Epinion、Ciao、Movielens三個數據集進行,這三個數據集都包含了用戶對項目的評分且分值分為1-5的離散值,數據集的具體信息如表1所示.

表1 數據集簡介
Table 1 Introduction of data sets

數據集用戶數目項目數目評分數稀疏度Movielens6040370610002094．47%Ciao7375997462784830．0379%Epinion401631397386648240．0118%

4.2 實驗評價標準

為了檢驗本文提出算法的推薦質量,本實驗采用均方根誤差RMSE(Root Mean Square Error,RMSE)作為度量標準[16],通過計算預測值與實際值之間的RMSE來表示預測的準確性,RMSE值越小,推薦質量就越好.

(15)

其中,xi是代表預測值,x0代表與預測值對應的真實值.

4.3 實驗結果及分析

BaseLine預測

首先將數據集的90%作為訓練集,其余的10%作為測試集,其次選擇BaseLine預測的目的在于該算法的訓練時間短,預測精度高,可以通過實驗訓練得到最優參數.

如圖1是在Movielens數據集上做的Baseline預測,經實驗發現當λ1=3,λ2=6,RMSE達到最優,最小為值為0.961.

如圖2是在Ciao數據集上做的Baseline預測,經實驗發現當λ1=58,λ2=41,RMSE達到最優,最小為值0.976.

如圖3是在Epinions數據集上的Baseline預測,經實驗發現當λ1=55,λ2=45,RMSE達到最優,最小為值0.998.

圖1 MovieLens1m數據集Baseline預測Fig.1 Baseline prediction of MovieLens 1M dataSets

圖2 Ciao數據集Baseline預測Fig.2 Baseline prediction of Ciao dataSets

圖3 Epinion數據集Baseline預測Fig.3 Baseline prediction of Epinion dataSets

由以上實驗確定了參數值之后,在MovieLens 1M數據集上通過多次實驗參數λ1=3,λ2=6,λp=1.35,λq=0.96時RMSE表現最優,此時對比NMF算法與本文提出的RBNMF算法在不同的維度上RMSE值如圖4所示;在Ciao數據集上通過多次實驗參數λ1=58,λ2=41,λp=1.62,λq=1.06時RMSE表現最優,此時對比NMF算法與本文提出的RBNMF算法在不同的維度上RMSE值如圖5所示;在Epinion數據集上通過多次實驗參數λ1=55,λ2=45,λp=1.73,λq=0.786時RMSE表現最優,此時對比NMF算法與本文提出的RBNMF算法在不同的維度上RMSE值如圖6所示.有以下三個圖可以明顯看出,NMF算法的RMSE值隨著分解維度的增加,變化幅度與本文提出的算法相比變化范圍較大.這說明了本文提出的RBNMF算法在訓練過程中對分解維度的要求弱于NMF算法,也恰恰證明了本文添加用戶、項目偏置信息,有力的改善了對于一些難以通過實驗確定最佳分解維度的用戶評分預測.當分解維度到達一定值時在不同數據集上兩種算法的最優RMSE基本相等,如果分解維度繼續增加,NMF算法及RBNMF算法都會顯示出預測精確度下降的趨勢,但是本文提出的算法改變幅度較小,原因是一旦隱因子數量超過一定范圍,相對多增加的隱因子會在一定程度上削弱最佳隱因子(也即RMSE對應最低的維度數)對預測值的影響,實際表現就是預測精度的降低.

圖4 MovieLens 1M數據集分解不同維度RMSE對比Fig.4 RMSE of MovieLens 1M decomposed of different dimension

圖5 Ciao數據集分解不同維度RMSE對比Fig.5 RMSE of Ciao decomposed of different dimension

圖6 Epinion數據集分解不同維度RMSE對比Fig.6 RMSE of Epinion decomposed of different dimension

對于大型數據集,稀疏用戶的數量比較大,圖7表示出MovieLens 1M數據集、Ciao數據集、Epinion數據集的用戶評價項數量分布,從圖7可以看出稀疏用戶(四類中的第一類)占全部用戶的比例較大.

如圖8所示,選擇三種數據集的稀疏用戶(圖7中每種數據集的第一類用戶)作為測試集,從上述實驗中選取三種不同數據集達到最優的λ1、λ2、λp、λq.從圖中可以看出在實驗開始階段,三種數據集在分解維度數相同時,本文提出的RBNMF算法的預測準確度優于NMF算法.針對稀疏性較大的Ciao和Epinion數據集的預測準確性,分解維度數為20時,相比于稀疏性較低的MovieLens數據集展現出比較大的優勢,更加明確的說明了用戶-項目偏置對稀疏用的評分預測準確性有較大提升,隨著分解維度的增加三種算法的預測準確性有明顯提高,原因是隱因子模型隨著挖掘的潛在因素的增加預測值趨于更加合理化.隨著分解維度的進一步增加,相比各個數據集中全部用戶,稀疏用戶的預測準確度下降并不明顯,原因是稀疏用戶評價項目較少,約束隱因子條件較少,不能確定最優分解維數(如Movielens 數據集中最優維度數可以為50,…,100的任何一種).

圖7 用戶評價項目數量分布圖Fig.7 Distribution of users who evaluate items

圖8 稀疏用戶的RMSE三種算法對比Fig.8 Sparse user RMSE use three algorithm

5 結束語

本文研究了非負矩陣分解算法在推薦系統中的應用,RBNMF在NMF的基礎上加入了獨立于觀測的評分數據和用戶無關的偏置信息.實驗表明,對比傳統的矩陣分解算法,本文提出的算法針對稀疏用戶評分預測精確性有較大的提高.但是,在算法的改進過程中充分利用已知評分的機制還不夠完善,進一步研究的重點應該放在不同用戶之間信任的建立、傳播,把信任機制引入到矩陣分解算法中.

[1] Herlocker J L,Konstan J A,Riedl J,et al.Explaining collaborative filtering recommendations[C].ACM Conference on Computer Supported Cooperative Work,Proceedings of America,2001:5-53.

[2] Deshpande M,Karypis G.Item-based top- N recommendation algorithms[J].ACM Transactions on Information Systems,2004,22(1):143-177.

[3] Cheung K W,Tian L F.Learning user similarity and rating style for collaborative recommendation[J].Information Retrieval Journal,2004,7(3):395-410.

[4] Koren Y,Bell R,Volinsky C.Matrix factorization techniques for recommender systems[J].Computer,2009,42(8):30-37.

[5] Hoyer P O.Non-negative matrix factorization with sparseness constraints[J].Journal of Machine Learning Research,2004,5(1):1457-1469.

[6] Lin C.Projected gradient methods for nonnegative matrix factorization[J].Neural Computation,2007,19(10):2756-2779.

[7] Aharon M,Elad M,Bruckstein A.An algorithm for designing overcomplete dictionaries for sparse representation[J].IEEE Transactions on Signal Processing,2006,54(11):4311-4322.

[8] Koren Y,Bell R,Volinsky C.Matrix factorization techniques for recommender systems[J].IEEE,Computer Journal,2009,42(8):30-37.

[9] Xia Ye-mao,Gou Jian-wei,Liu Ying-an.Semi parametric Bias analysis of hidden Markov model[J].Journal of Applied Mathematics,2015,30(1):17-30.

[10]Miller F P,Vandome A F,Mcbrewster J.Gradient descent[J].Alphascript Publishing,2010,20(4):235-242.

[11]Osher S,Yin W,Goldfarb D,et al.An iterative regularization method for total variation-based image restoration[J].Siam Journal on Multiscale Modeling & Simulation,2005,4(2):460-489.

[12]Dan K.A singularly valuable decomposition:The SVD of a matrix[J].College Mathematics Journal,1996,27(1):2-23.

[13]Shi Jia-rong,Zheng Xiu-yun,Wei Zong-tian,et al.Review of low rank matrix recovery algorithm[J].Computer Application Research,2013,30(6):1601-1605.

[14]Marinho L B,Hotho A,Jaschke R,et al.Baseline techniques[M].New York:Springer US Press,2012.

[15]Tang Z,Zhang X,Zhang S.Robust perceptual image hashing based on ring partition and NMF[J].IEEE Transactions on Knowledge & Data Engineering,2014,26(3):711-724.

[16]Chen Da-wei,Yan Zhao,Liu Hao-yan.Over fitting phenomenon of SVD series algorithm in scoring prediction[J].Journal of Shandong University,2014,6(3):15-21.

附中文參考文獻：

[9] 夏業茂,勾建偉,劉應安.隱馬爾可夫因子分析模型的半參數貝葉斯分析[J].高校應用數學學報,2015,30(1):17-30.

[13] 史加榮,鄭秀云,魏宗田,等.低秩矩陣恢復算法綜述[J].計算機應用研究,2013,30(6):1601-1605.

[16] 陳大偉,閆 昭,劉昊巖.SVD系列算法在評分預測中的過擬合現象[J].山東大學學報工學版,2014,6(3):15-21.