一種融合近鄰用戶影響力的矩陣分解推薦算法

李昆侖，郭昌隆，關(guān)立偉

(河北大學(xué) 電子信息工程學(xué)院，河北 保定 071000)

1 引 言

隨著互聯(lián)網(wǎng)經(jīng)濟的高速發(fā)展，商品種類與數(shù)量均呈爆發(fā)式增長.在此情況下，能夠利用各種已知信息刻畫出用戶喜好并為之推送感興趣內(nèi)容，進而將潛在購買力轉(zhuǎn)化為實際購買力的推薦算法受到了越來越多的重視.它在幫助用戶從海量商品中快速準(zhǔn)確發(fā)現(xiàn)感興趣商品的同時也極大地提高了網(wǎng)站的銷售額與用戶忠誠度.

推薦系統(tǒng)的概念最初由斯坦福大學(xué)MarkoBalabanovic等人提出.其主要分為兩大類：基于內(nèi)容的推薦以及基于協(xié)同過濾的推薦[1].基于內(nèi)容的推薦建立在項目內(nèi)容的相似性上，通過比較用戶喜好物品與推薦物品的相似性來產(chǎn)生推薦.例如在文本推薦中，TF-IDF算法通過計算文章中某些關(guān)鍵字所對應(yīng)的權(quán)重，進而將有著相似的關(guān)鍵字權(quán)重的文章推薦給讀者.而基于協(xié)同過濾的推薦建立在相似用戶(或項目)對于相似項目的評分也是相似的這一假設(shè)之上.例如基于用戶的top-N算法[2-5]，首先根據(jù)用戶相似性得到與目標(biāo)用戶最為相似的N個用戶，其后從這N個用戶中尋找評分最高的商品推薦給目標(biāo)用戶；同理基于項目的推薦則是尋找用戶評分較高的項目，并將與之類似的項目推薦給用戶.

矩陣分解算法近來已經(jīng)逐漸應(yīng)用于推薦系統(tǒng)中.傳統(tǒng)的矩陣分解算法包括奇異值分解[6](Singular Value Decompostion)，QR分解(QR Factorization)，三角分解法(Triangular Factoriz-ation)等等.隨著研究的深入，針對SVD分解出現(xiàn)負(fù)值的問題提出了非負(fù)矩陣分解[7，8]的方法，增加了推薦結(jié)果的可解釋性；Parivash等人利用矩陣分解算法對用戶對相似度矩陣進行填充以此改善數(shù)據(jù)稀疏問題[9]；Mnih等人以SVD為基礎(chǔ)，假設(shè)用戶與物品的隱式特征符合高斯分布進而得到最有可能的用戶與商品信息矩陣[10].但以上方法均試圖將高維數(shù)據(jù)分解為低維數(shù)據(jù)，僅考慮了用戶與商品各自的屬性問題，并未意識到用戶之間也蘊含著復(fù)雜的關(guān)系.因此本文針對此問題從鄰近用戶對目標(biāo)用戶的影響出發(fā)，提出了一種融合近鄰用戶影響力的矩陣分解推薦算法，在考慮用戶信息與評分信息的同時，將近鄰用戶的影響力融入到矩陣分解模型中并通過優(yōu)化目標(biāo)函數(shù)訓(xùn)練此模型，之后利用此模型對用戶的評分進行預(yù)測.實驗結(jié)果表明本文算法相較傳統(tǒng)推薦算法其推薦精度有明顯提高.

2 相關(guān)工作

2.1 近鄰用戶的相似性度量

用戶間的影響相當(dāng)復(fù)雜，僅通過用戶間有無共同評分項來判斷兩者之間有無影響是不準(zhǔn)確的.例如作為目標(biāo)用戶的家人、老師等，可能因年齡段等問題其共同購買或評價的商品很少，但依舊能通過一些日常行為影響到用戶對某些商品的評價.而采用傳統(tǒng)的如余弦相似度和皮爾遜相似度等方式在尋找用戶近鄰時可能會面臨共同評分項極少甚至無共同評分項的情形，導(dǎo)致其效果很差，嚴(yán)重影響目標(biāo)用戶近鄰的確定.考慮到共同評分項很少或無共同評分項的用戶之間其評分趨勢是相似的這一事實，我們采用一種基于Cloud-model[11]的相似度計算方法，從統(tǒng)計學(xué)意義上考慮用戶間評分的相似性.

2.1.1Cloud-model

Cloud-model最初是李德毅在解決概率論和模糊數(shù)學(xué)等問題時提出的一種進行定量與定性之間轉(zhuǎn)換的數(shù)學(xué)模型[11].模型用Ex(期望)，En(熵)，He(超熵)三個參數(shù)來表征一個模糊的概念，從而將事物的模糊性與隨機性有機結(jié)合在一起.在某個數(shù)域空間中，模型中的數(shù)值點(云滴)在如上三個參數(shù)控制下選取和產(chǎn)生，其產(chǎn)生的數(shù)值點(云滴)構(gòu)成了整個模型(Cloud-model).因其在三維空間中成云狀，因此也稱其模型為云模型.其模型定義如下：

定義：云和云滴：設(shè)U為某個模糊集合，C是U上的定性概念.若數(shù)值a∈U是C上的一次隨機實現(xiàn)，A對于C的確定度y(a)∈[0，1]是有穩(wěn)定傾向的隨機數(shù)且y：Y→[0，1] ?a∈Y a→y(x)，則所有的a在模糊域U上的分布可稱為云.而云中的每個數(shù)值a可稱作云滴.其中Ex表示a在模糊域U上分布的期望，En表示C的可度量性，且En的大小與其C的模糊性呈正比.He表示熵的不確定性，由熵的隨機性和模糊度共同確定[12].

如將每位用戶U視為一個Cloud-model，則其對物品的評分值r為隸屬于云U上的云滴，用戶所有的評分項構(gòu)成用戶U的Cloud-model.若用戶之間的評分趨勢相似，則其構(gòu)成的Cloud-model也將是相似的.由此通過比較兩者模型即可得到用戶間的相似度，進而避免了余弦相似度等傳統(tǒng)方法在面臨共同評分項較少時誤差較大的缺點.

2.1.2 逆向云算法

若用戶間的Cloud-model是相似的，則控制其云滴(評分)產(chǎn)生的三個參數(shù)Ex(期望)，En(熵)，He(超熵)所構(gòu)成的三維向量也應(yīng)是相似的.本文通過逆向云算法求取上述三個參數(shù).此算法是基于數(shù)理統(tǒng)計的樣本均值和樣本方差的均值算法，也可以稱其為均值法.其步驟如下：

輸入：n個云滴(評分值){r1，r2，r3，…rn-2，rn-1，rn}

輸出：控制云滴產(chǎn)生的三個參數(shù)Ex，En，He

步驟：

1)①計算云滴的樣本均值：

(1)

②計算云滴的一階樣本絕對中心距：

(2)

③計算云滴的方差：

(3)

2)根據(jù)(1)、(2)和(3)式得到其模型的Ex，En，He：

(4)

(5)

(6)

2.1.3 基于Cloud-model的相似度計算

每位用戶的Cloud-model用向量(Ex，En，He)表示，則比較用戶相似度時只需比較代表其Cloud-model的向量相似度即可.但僅用Ex，En，He三者構(gòu)成的向量在計算相似度時面臨一個問題：假設(shè)U(Eau，Enu，Heu)與V(Eav，Env，Hev)兩者均與歐式空間中某條直線平行，若采用余弦相似度等方法得到其相似度定為1，但兩者所代表的Cloud-model顯然不同.在計算向量相似度時一般認(rèn)為兩者的距離與其相似度成反比，于是得到向量U與V的距離表達(dá)式：

(7)

同時引入一個單調(diào)遞減的指數(shù)函數(shù)，將距離標(biāo)準(zhǔn)化到(0，1)之間：

D(dis(U，V))=e-dis(U，V)

(8)

顯然此函數(shù)與距離成反比，當(dāng)距離為0時函數(shù)值為1，表示兩者相似度最大，當(dāng)距離為無窮時函數(shù)值為0，表示兩者相似度最小.

2.2 矩陣分解

矩陣分解模型

矩陣分解其目的是將高維的戶-項目評分矩陣分解為低維的用戶隱含信息矩陣和物品隱含信息矩陣.其算法涉及三個矩陣：用戶信息矩陣P：{u1，…，um}，物品信息矩陣Q：{i1，…，in}，以及評分矩陣R.其原理是由兩個低秩矩陣P，Q構(gòu)造的預(yù)測矩陣相乘逐漸逼近原評分矩陣R(訓(xùn)練集)進而進行參數(shù)訓(xùn)練，并將訓(xùn)練完畢后的各參數(shù)應(yīng)用到推薦模型之中.即：

(9)

(10)

其中μ為所有項目評分的平均值，bu為用戶偏置矩陣，bi為項目偏置矩陣.bu表示某用戶的平均評分，用戶的bu大(小)表明此用戶評分普遍偏高(低).同樣某項目的bi大(小)表明整體用戶對此項目的評分普遍偏高(低).

3 基于近鄰用戶影響力的矩陣分解模型

為了反映出近鄰用戶對目標(biāo)用戶的影響，本文提出的一種基于近鄰用戶影響力的矩陣分解算法將近鄰用戶對目標(biāo)用戶的的影響力融入到矩陣分解模型中去.假設(shè)近鄰用戶對目標(biāo)用戶產(chǎn)生的影響力用W表示，則N個近鄰用戶對目標(biāo)用戶的影響力可以表示為：

(11)

其中T(a)表示近鄰用戶的集合，wf代表每位近鄰用戶產(chǎn)生的影響力的隱式反饋.于是得到一個如下所示的新的評分模型：

(12)

設(shè)損失函數(shù)為SSE，表示所有誤差的平方和：

(13)

(14)

采用隨機梯度下降法最小化損失函數(shù)，設(shè)α為損失函數(shù)中需要更新的參數(shù)，則在任意一次更新中的任意參數(shù)的更新式為：

α←α+Δα

(15)

(16)

根據(jù)(15)式，將(11)，(12)，(13)，(14)式帶入(16)式中，則得到各參數(shù)的如下更新式：

(17)

其中η為更新步長.

實驗步驟：

輸入：用戶與項目所組成的評分矩陣，過擬合因子λ，更新步長η，最大迭代次數(shù)N以及最小提升閾值M.

輸出：用戶U對項目i的預(yù)測評分

Step1.根據(jù)評分矩陣得到用戶的Cloud-model，利用逆向云算法得到用戶的Ex，En，He值.

Step2.用向量(Ex，En，He)表示每位用戶的評分模型，通過比較向量的相似性得到與目標(biāo)用戶相似的N個近鄰用戶.

Step3.構(gòu)造近鄰用戶的影響力模型W，將其融入矩陣分解模型中得到新的評分模型：

Step4.根據(jù)評分模型對預(yù)測矩陣進行參數(shù)訓(xùn)練：

1：for(最大迭代次數(shù)或者最小提升閾值)

2： for(循環(huán)遍歷每一名用戶)：

3： for(循環(huán)遍歷每一個項目)：

4： (計算用戶對此項目的預(yù)測評分以及與真實評分的誤差e

5：更新各項參數(shù)

6： end

7： end

8：end

4 實驗及分析

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

為驗證本文算法的有效性，實驗采用由Minnesota大學(xué)的Grouplens項目組提供的Movielens數(shù)據(jù)集，記錄了943位用戶對1682部電影共計10萬條的評分記錄.用戶評分值在1-5分之間.分?jǐn)?shù)低(高)代表用戶對電影不滿意(滿意).在整個實驗中，每次隨機抽取20%的用戶作為測試集，另外80%作為訓(xùn)練集.

實驗環(huán)境：CPU 為Intel(R)-Core(TM) i5-2450M @ 2.50GHz、內(nèi)存為6GB的微機；軟件為Python2.73.

4.2 度量標(biāo)準(zhǔn)

本文采用均方根誤差(RMSE)作為度量標(biāo)準(zhǔn).RMSE的值越小證明算法的準(zhǔn)確度越高.

4.3 實驗結(jié)果及分析

實驗將從如下幾方面來驗證本文算法的有效性：不同近鄰個數(shù)對本文算法(NUISVD)的影響；不同隱因子個數(shù)對本文算法的影響；不同正則化系數(shù)對本文算法的影響；對比本文算法與BSVD在不同隱因子個數(shù)條件下的差別；采用余弦相似度與Cloud-model在獲取近鄰用戶時對本文算法的影響；對比本文算法與BSVD算法在相同學(xué)習(xí)率、正則化系數(shù)以及隱因子個數(shù)情況下的收斂速度.

4.3.1 不同近鄰個數(shù)對本文算法的影響

如表1所示，在保持其他參數(shù)不變的情況下，選取不同數(shù)量的近鄰個數(shù)，驗證不同近鄰個數(shù)對本文算法以及傳統(tǒng)的基于用戶相似度(UBCF)的推薦算法的影響.

表1 不同近鄰個數(shù)對本文算法的影響Table 1 Influence of different nearest numbers

圖1為上述兩算法在表1所給出的各項參數(shù)下所獲得的結(jié)果.

圖1 不同近鄰個數(shù)對本文算法的影響Fig.1 Influence of different nearest numbers

如圖1所示，顯示了傳統(tǒng)的基于用戶相似度的推薦算法(UBCF)與本文算法在表1各參數(shù)下所獲得的推薦精度.可看出本文算法在近鄰個數(shù)為60時取得結(jié)果約為0.90，且在近鄰個數(shù)為10-100的情況下，本文算法所獲得的精度均遠(yuǎn)遠(yuǎn)高于UBCF.但無論是傳統(tǒng)的基于用戶相似度的推薦算法還是本文算法，其精度均不會隨著近鄰個數(shù)的增加而持續(xù)提高.

4.3.2 不同正則化系數(shù)對本文算法的影響

如表2所示，在保持學(xué)習(xí)率，隱因子個數(shù)，迭代次數(shù)不變的情況下，給定不同正則化系數(shù)，驗證不同正則化系數(shù)對本文算法的影響.

表2 正則化系數(shù)對本文算法影響Table 2 Influence of regularization parameter on NUISVD

圖2為在表2所給出的各項參數(shù)下，本文算法所得到的推薦精度.

圖2 不同正則化系數(shù)對本文算法的影響Fig.2 Influence of regul-arization parameter on NUISVD

如圖2所示，可以看出算法在迭代20次左右時趨于穩(wěn)定，在迭代次數(shù)為5-10時，正則化系數(shù)為0.145的曲線所對應(yīng)的RMSE最小且下降最快，但在迭代次數(shù)約為15次之后，正則化系數(shù)為0.160的曲線所對應(yīng)的RMSE最小.可見正則化系數(shù)小，則RMSE下降快，但過小的正則化系數(shù)有可能會造成算法的過擬合現(xiàn)象進而影響算法精度.可正則化系數(shù)過大時，則又會導(dǎo)致RMSE下降速度過慢，增加了算法的迭代次數(shù)以及計算成本.

4.3.3 本文算法與BSVD算法在不同隱因子個數(shù)下的對比

如表3所示，在保持學(xué)習(xí)率，正則化系數(shù)，迭代停止條件以及次數(shù)不變的情況下，驗證不同隱因子個數(shù)對本文算法以及BSVD算法的影響.

表3 本文算法與BSVD算法在不同隱因子個數(shù)下的對比Table 3 NUISVD and BSVD in different latent factors

圖3為本文算法與BSVD算法在表3所給出的各項參數(shù)下得到的結(jié)果.

圖3 不同隱因子個數(shù)對UNISVD和BSVD算法的影響Fig.3 NUISVD and BSVD in different number of latent factors

如圖3所示，是本文算法與BSVD算法在上述表3各項參數(shù)下所獲得的推薦精度.可以看出BSVD算法在隱因子個數(shù)為80時推薦精度趨于穩(wěn)定且取得最高的推薦高精度約為0.919，本文算法在隱因子個數(shù)為70時趨于穩(wěn)定，且在隱因子個數(shù)為90時取得的最高精度為約為0.901.且在表3各項參數(shù)下本文算法的推薦精度均高于傳統(tǒng)的BSVD算法，這是因為相較于BSVD而言，本文算法將近鄰用戶的影響力加入其中，從而提高了推薦精度.而且還可看出兩算法在隱因子個數(shù)為40至80之間時，其推薦精度呈現(xiàn)出逐漸減緩的上升趨勢，之后均趨于穩(wěn)定.證明適當(dāng)增加隱因子個數(shù)會提高算法的精確度，但隱因子個數(shù)過多時其精確度提高并不明顯，反而增加了計算的復(fù)雜度.

表4 余弦相似度與Cloud-model的對比Table 4 Comparison of Cosine similarity and Cloud-model

4.3.4 余弦相似度與Cloud-model在相同近鄰個數(shù)時的對比

如表4所示，在保持學(xué)習(xí)率、正則化系數(shù)、隱因子個數(shù)及迭代次數(shù)相同的情況下，比較余弦相似度(COS)與Cloud-model(CM)在獲取同等數(shù)量的近鄰時對算法的影響.

圖4為本文算法在上述表4中各參數(shù)情況下采用余弦相似度和Cloud-model獲取相同數(shù)目的近鄰時得到的推薦精度：

圖4 余弦相似度與Cloud-model的對比Fig.4 Comparison of cosine similarity and Cloud-model

由圖4可以看出，本文算法無論是采用余弦相似度還是Cloud-model均在近鄰個數(shù)為60時取得最高推薦精度，但相較于余弦相似度，采用Cloud-model所獲得的推薦精度要明顯高于前者.這是由于在遇到用戶間共同評分項很少甚至沒有共同評分項的極端情況時，余弦相似度得到的目標(biāo)用戶近鄰的準(zhǔn)確性較低，而Cloud-model則是從統(tǒng)計學(xué)意義上根據(jù)用戶的評分趨勢獲得目標(biāo)用戶的近鄰，從而有效避免了上述問題.

4.3.5 本文算法與BSVD算法在相同系數(shù)下的收斂速度

如表5所示，在保持各項參數(shù)相同的情況下，比較本文算法(NUISVD)與BSVD算法的收斂速度.

表5 NUISVD與BSVD的收斂速度Table 5 Convergence rates of NUISVD and BSVD

下頁圖5為本文算法與BSVD算法在相同參數(shù)下迭代300步的收斂曲線.

可看出在相同參數(shù)情況下，本文算法RMSE的下降速度明顯快于BSVD算法.

圖5 本文算法與BSVD的收斂速度Fig.5 Convergence rates of NUISVD and BSVD

這是因為在相同參數(shù)情形下，本文引入了近鄰用的影響力，考慮了更多影響推薦精度的因素，但同樣因為用戶影響力的引進也使得本文算法每一步的計算復(fù)雜度要高于傳統(tǒng)的BSVD.

5 結(jié)論和未來工作

本文針對用戶間的影響力作用提出的基于近鄰用戶影響力的矩陣分解推薦算法，與傳統(tǒng)矩陣分解推薦算法相比在考慮用戶與商品各自隱含信息的同時還綜合考慮了用戶間的隱含聯(lián)系，并將其融入到了矩陣分解中去.通過實驗表明，相較于傳統(tǒng)基于用戶相似度的推薦算法以及BSVD算法而言，本文算法在推薦精度上有較大的提高.

影響力是具有時效性的.因此在未來研究中我們將考慮上述問題，通過建立影響力的時效性模型并嘗試將其融入到矩陣分解推薦算法中，相信可以取得更為優(yōu)異的推薦精度.

[1] Sarwar B，Karypis G，Konstan J，et al.Item-based collaborative filtering recommendation algorithms[C].Proceeding of the 10th international Conference on World Wide Web，ACM，2001：285-295.

[2] Hoens T R，Blanton M.A private and reliable recemendation system for social networks[C].Proc.of the IEEE Social Com.Washington：IEEE Computer Society，2011：816-825.

[3] Min J K，Cho S B.Mobile human network management and recommendation by probabilistic social mining[J].IEEE Trans.on Systems，Man and Cybernetics，Part B，2011，41(3)：761-771.

[4] Colombo-MendozaLO，Valencia-GarcíaR，Rodríguez-Gonzál-ez A，et al.A context-aware knowledge based mobil recommender system for movie showtimes[J].Expert Systems with Application，2015，42(3)：1202-1222.

[5] Kasap O Y,Tunga M A.A polynomial modeling based algorithm in top-N recommendation[J].Expert Systems with Applications,2017,79:313-321.http://dio.org/10.1016/j.eswa.2017.03.005

[6] Zhang X D，F(xiàn)eng X C，Wang W W.Two-direction nonlocal Model for image denoising[C].IEEE Transactions on Image Processing，2013，22(1)：408-412.

[7] San Juan P,Vidal A M,Garcia-Molla V M.Updating/downdating the NonNegative matrix factorization[J].Journal of Computational and Applied Mathematics,2017,318:59-69.http:// dio.org/10.1016/j.cam.2016.11.048.

[8] Yang Yong-sheng，Ming An-bo，Zhang You-yun.Discriminative non-negative matrix factorization (DNMF) and its application to the fault diagnosis of diesel engine[J].Mechanical Systems and Signal Processing,2017，95：158-171.

[9] Wang Xi-men，Liu Yun，Xiong Fei.Improve personalized recommendation based on a simliarity network[J].Physica(A)，2016，456：271-280.

[10] Mohsen Jamali，Mtin Ester，A matrix factorization technique with trust propagtionfor recommendation in social net work[C].ACM Recomemender System，2010：135.

[11] Zhang Guang-wei，Li De-yi，Li Peng，et al.A collaborative filtering recommendation algorothm based on cloud model[J].Journal of Software，2007，18(10)：2403-2411.

[12] Xu Xuan-hua，Wang Pei，Cai Chen-guang.Linguistic multiattribute large group decision-making method based on similarity measurement of cloud model[J].Control and Decision，2017，3(32)：459-466.

[13] Zhu X，Huang Z，Shen H T，et al.Dimensionality reduction by mixed kernel canonical correlation analysis[J].Pattern Recognition，2012，45(8)：3003-3016.

[14] Ma H，Zhou D，Liu C.Recommender system with social regularization[C].Proceedings of the 4th ACM International Conferenec on Web Search and Datam Mining,Hong Kong，China，2011：287-296.

[15] Zheng N，Qi L，Guan L.Generalized multiple maximum scatter difference feature extraction using QR decomposition[J].Journal of Visual Communication &Image Representation，2014，25(6)：140-147.

[16] Song F X，Cheng K，Yang J Y，et al .Maximum scatter difference，large margin linear projection and support vector machines[J].Acta Automatical Sinical，2004，30(6)：890-896.

[17] Gao S，Tsang I W H，Chia L T.Sparse representation with kernels[J].IEEE Transactions on Image Processing，2013，22(2)：423-434.

附中文參考文獻(xiàn)：

[11] 張光衛(wèi)，李德毅，李 鵬，等.基于云模型的協(xié)同過濾推薦算法[J].軟件學(xué)報，2007，18(10)：2403-2411.

[12] 徐選華，王 佩，蔡晨光.基于云相似度的語言偏好信息多屬性大群體決策方法[J].控制與決策，2017，3(32)：459-466.