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

李昆侖，郭昌隆，關立偉

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

1 引 言

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

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

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

2 相關工作

2.1 近鄰用戶的相似性度量

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

2.1.1Cloud-model

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

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

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

2.1.2 逆向云算法

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

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

輸出：控制云滴產生的三個參數Ex，En，He

步驟：

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

(1)

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

(2)

③計算云滴的方差：

(3)

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

(4)

(5)

(6)

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

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

(7)

同時引入一個單調遞減的指數函數，將距離標準化到(0，1)之間：

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

(8)

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

2.2 矩陣分解

矩陣分解模型

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

(9)

(10)

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

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

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

(11)

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

(12)

設損失函數為SSE，表示所有誤差的平方和：

(13)

(14)

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

α←α+Δα

(15)

(16)

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

(17)

其中η為更新步長.

實驗步驟：

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

輸出：用戶U對項目i的預測評分

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

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

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

Step4.根據評分模型對預測矩陣進行參數訓練：

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

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

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

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

5：更新各項參數

6： end

7： end

8：end

4 實驗及分析

4.1 數據集

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

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

4.2 度量標準

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

4.3 實驗結果及分析

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

4.3.1 不同近鄰個數對本文算法的影響

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結論和未來工作

本文針對用戶間的影響力作用提出的基于近鄰用戶影響力的矩陣分解推薦算法，與傳統矩陣分解推薦算法相比在考慮用戶與商品各自隱含信息的同時還綜合考慮了用戶間的隱含聯系，并將其融入到了矩陣分解中去.通過實驗表明，相較于傳統基于用戶相似度的推薦算法以及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，Feng 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.

附中文參考文獻：

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

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