一種基于矩陣分解的電影推薦算法

聶常超

（南京理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，江蘇 南京210014）

一種基于矩陣分解的電影推薦算法

聶常超

（南京理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，江蘇 南京210014）

針對目前的電影推薦算法中，傳統(tǒng)的矩陣分解算法對于用戶的離散型評分?jǐn)?shù)據(jù)集的數(shù)據(jù)利用率不高的問題，提出基于二項(xiàng)分布的矩陣分解算法的模型，在假定用戶的評分?jǐn)?shù)據(jù)是服從二項(xiàng)分布的前提下，利用最大后驗(yàn)估計(jì)學(xué)習(xí)得出損失函數(shù)，將用戶的興趣度作為影響因子，加入項(xiàng)目之間的鄰域影響，其后利用隨機(jī)梯度下降法針對問題求解。通過在MovieLens數(shù)據(jù)集上與傳統(tǒng)的矩陣分解算法的對比實(shí)驗(yàn)，結(jié)果表明，提出的算法可以有效的提高推薦精度，表現(xiàn)出良好的穩(wěn)定性。

推薦算法；二項(xiàng)分布；隨機(jī)梯度下降；矩陣分解

飛速發(fā)展的互聯(lián)網(wǎng)是現(xiàn)代社會(huì)人們獲得信息的重要途徑，與此同時(shí)，信息過載問題已經(jīng)是網(wǎng)民必須要面對的一個(gè)問題。推薦系統(tǒng)就是為了解決信息過載問題［1］而提出的強(qiáng)有力的工具，同時(shí)也是目前學(xué)術(shù)界和互聯(lián)網(wǎng)企業(yè)大力研究的熱門問題。協(xié)同過濾推薦算法［2］在目前是使用最廣泛的推薦算法，近些年來基于矩陣分解的推薦算法［3］越來越引起人們的重視。

目前的推薦系統(tǒng)中，用戶對于電影的實(shí)際評分?jǐn)?shù)據(jù)都是正整數(shù)，傳統(tǒng)的矩陣分解算法不能對這些信息進(jìn)行有效的利用，有鑒于此，提出了一種假設(shè)，即用戶的評分?jǐn)?shù)據(jù)服從二項(xiàng)分布。在此前提之下，從概率論的角度，假設(shè)模型中的參數(shù)都服從一定的分布模型，從機(jī)器學(xué)習(xí)的角度用最大后驗(yàn)估計(jì)［4］進(jìn)行模型的推導(dǎo)，并將項(xiàng)目之間的相互作用加入到模型之中，矩陣分解模型因此更加健壯，具備更好的可解釋性。

在MovieLens電影數(shù)據(jù)集上，對提出的算法和傳統(tǒng)的矩陣分解算法進(jìn)行實(shí)驗(yàn)對比的結(jié)果表明，所提出推薦算法可以有效提高推薦精度，并表現(xiàn)出較高的穩(wěn)定性。

1　二項(xiàng)矩陣分解算法

傳統(tǒng)的矩陣分解模型對于用戶的評分并沒有特別要求，因此有文獻(xiàn)提出用戶評分服從正態(tài)分布的矩陣分解（PMF）模型［5］。但在現(xiàn)實(shí)的評分系統(tǒng)中，用戶的評分基本都是整數(shù)。因此，用戶的評分服從正態(tài)分布的假定是不成立的。提出一種合理的假設(shè)，即用戶的評分服從二項(xiàng)分布。并由此引出的二項(xiàng)分布矩陣分解模型［6］。

1.1二項(xiàng)分布模型

假設(shè)用戶評分服從下面公式中的二項(xiàng)分布：

其中βu，i表示用戶u對于項(xiàng)目i的評分概率。pu，qi分別滿足正態(tài)分布并且相互獨(dú)立。進(jìn)一步假設(shè)在該二項(xiàng)分布中，對于不同u或i是相互之間獨(dú)立的。因此，整個(gè)二項(xiàng)分布模型可以用如下形式表示：

1.2最大后驗(yàn)估計(jì)學(xué)習(xí)

在統(tǒng)計(jì)學(xué)理論中，最大后驗(yàn)（MAP）估計(jì)方法是根據(jù)經(jīng)驗(yàn)數(shù)據(jù)來獲取難以觀測到的變量的點(diǎn)估計(jì)，這在統(tǒng)計(jì)學(xué)中是一種比較常用的估計(jì)方法。最大后驗(yàn)估計(jì)與最大似然估計(jì)中的Fisher方法有密切的聯(lián)系，但是最大后驗(yàn)估計(jì)使用了增大的優(yōu)化目標(biāo)，它將被估計(jì)量先驗(yàn)分布融合其中，據(jù)此，最大后驗(yàn)估計(jì)可被看作規(guī)則化的最大似然估計(jì)。

假定x是獨(dú)立同分布的樣本，θ為模型的調(diào)整參數(shù)，f是的模型，后驗(yàn)分布函數(shù)可以用下式表示：

通過以上對最大后驗(yàn)估計(jì)的初步介紹，現(xiàn)在對式（2）求最大后驗(yàn)估計(jì)（MAP），將式（3）和式（4）代入得到：

令μ=θ=0，將式（3）和式（4）代入，并加上ci，j的規(guī)則化項(xiàng)用以防止過度擬合，得到最后的目標(biāo)函數(shù)如下：

1.3隨機(jī)梯度下降法

隨機(jī)梯度下降法（SGD），在最優(yōu)化理論中是最基礎(chǔ)的算法之一。這種算法通過對參數(shù)求導(dǎo)的方法來找到目標(biāo)函數(shù)的參數(shù)下降最快的方向，然后通過迭代求解來使目標(biāo)函數(shù)逐步收斂。

對于式（7）中的目標(biāo)函數(shù)，可以通過使用隨機(jī)梯度下降法來進(jìn)行求解。具體算法如下：

輸入：用戶評分矩陣R，隱含類別個(gè)數(shù)K。

輸出：用戶興趣度矩陣P，項(xiàng)目隱類矩陣Q以及興趣度偏移矩陣c。

（1）把實(shí)驗(yàn)數(shù)據(jù)集按照M:1的比例采用隨機(jī)分配的方法分成訓(xùn)練集和測試集。

（2）選擇合適的常量α，學(xué)習(xí)率η，以及正則化參數(shù)λ1，λ2的值，對用戶興趣矩陣P，項(xiàng)目隱類矩陣Q，興趣度偏移矩陣c進(jìn)行初始化。

6）根據(jù)公式（7）對P，Q，c分別求偏導(dǎo)得到更新規(guī)則，按如下方式分別更新P，Q，c矩陣：

7）對均方根誤差RMSE進(jìn)行計(jì)算，如果本次計(jì)算結(jié)果與上次結(jié)果之差的絕對值小于某一特定閾值，則迭代結(jié)束；否則，轉(zhuǎn)到步驟3）。

2　實(shí)驗(yàn)與結(jié)果分析

2.1M ovieLens數(shù)據(jù)集

本實(shí)驗(yàn)所采用的數(shù)據(jù)集是GroupLens研究小組 （明尼蘇達(dá)大學(xué)）提供的，包括MovieLens-100k以及MovieLens-1m兩個(gè)數(shù)據(jù)集。MovieLens-100k數(shù)據(jù)集包括943個(gè)用戶針對1682個(gè)商品進(jìn)行的100 000條評分信息，MovieLens-1m數(shù)據(jù)集則包含了6 040個(gè)用戶針對3 900個(gè)商品的1 000 209條評分記錄，每個(gè)用戶對20或20部以上的電影進(jìn)行過評分，用戶對每部電影的評分為5個(gè)等級（1到5分）。除了有評分信息之外，數(shù)據(jù)集中還包含有用戶信息，電影信息，對電影評分的時(shí)戳等信息。即便如此，數(shù)據(jù)依然非常稀疏，在用戶-項(xiàng)目的評分矩陣中，評分信息只有6.3%。

本實(shí)驗(yàn)中，會(huì)把數(shù)據(jù)集隨機(jī)分成M份，把其中的一份作為測試集來用，另外M-1份則作為訓(xùn)練集。訓(xùn)練集用來進(jìn)行相應(yīng)的實(shí)驗(yàn)，測試集用來統(tǒng)計(jì)相應(yīng)的評價(jià)指標(biāo)。實(shí)驗(yàn)一共進(jìn)行M次，M次實(shí)驗(yàn)結(jié)果的平均值將作為最終的評測指標(biāo)，這樣可以防止評價(jià)結(jié)果過擬合。

2.2實(shí)驗(yàn)分析

本實(shí)驗(yàn)采用RMSE（RootMean Square Error，即均方根誤差）作為評價(jià)推薦系統(tǒng)的指標(biāo)。均方根誤差計(jì)算評分和實(shí)際評分之間誤差的平方和的均值的平方根。RMSE的值如果越小，則說明精度越高。RMSE的計(jì)算公式如下：

其中ru，i表示的是用戶u對于項(xiàng)目i的真實(shí)評分，表示的是預(yù)測評分，T表示測試集，表示測試集的大小。

為了比較傳統(tǒng)的矩陣分解算法與所提出的二項(xiàng)矩陣分解算法的異同，這里提出3種方法來進(jìn)行對照實(shí)驗(yàn)：

1）規(guī)范化矩陣奇異值分解Funk-SVD

2）非負(fù)矩陣分解NMF

3）改進(jìn)的二項(xiàng)矩陣分解BMF

其中第三種是提出的方法。

首先在MovieLens-100k數(shù)據(jù)集上調(diào)整隱含因子的個(gè)數(shù)，比較隱含因子數(shù)K的不同對BMF和傳統(tǒng)的矩陣分解算法的推薦效果。這里令學(xué)習(xí)速率η=0.01，正則化參數(shù)λ1=λ2=0.05，令α=0.5，將迭代學(xué)習(xí)率每次按照0.99倍的速度遞減。讓K的值分別取10、20、50、100、150、200、250、300、350、400、500等值，觀察不同的K值對于推薦結(jié)果的影響。

圖1　3種算法隨隱含因子數(shù)不同的RMSE值

圖1中展示了3種不同的矩陣分解算法在隱含因子數(shù)K取值不同的情況下RMSE的情況。由圖中可看出，當(dāng)隱含因子數(shù)取200左右時(shí)，幾種算法的結(jié)果最為理想。而當(dāng)K值取更大時(shí)，計(jì)算復(fù)雜度隨之增加，但是精度方面卻沒有明顯改變。由圖中還可看出，BMF具有良好的穩(wěn)定性，當(dāng)隱含因子數(shù)K改變時(shí)波動(dòng)不大，在推薦精度方面，BMF要好于Funk-SVD、NMF，最好情況下，RMSE達(dá)到0.923 4。

表1中列出了幾種算法在K=200的情況下在MovieLens-1m這個(gè)更大的數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果。從表中可看出BMF在學(xué)習(xí)率取值0.01的情況下，只需55次迭代就能達(dá)到最優(yōu)值，RMSE最低達(dá)0.845 0。該實(shí)驗(yàn)表明，當(dāng)數(shù)據(jù)集更大時(shí)，BMF優(yōu)于其他兩種矩陣分解算法。

表1　在MovieLens-1m數(shù)據(jù)集下3種算法的迭代次數(shù)和RMSE

3　結(jié)束語

隨著近年來對于推薦算法的研究逐漸深入，越來越多的研究者開始關(guān)注矩陣分解算法。但是基于矩陣分解的推薦算法依然存在一些不足，如算法復(fù)雜度高，對用戶數(shù)據(jù)利用率低等。針對現(xiàn)實(shí)中用戶評分普遍具有離散性的特點(diǎn)，提出基于二項(xiàng)分布的矩陣分解算法和改進(jìn)，在二項(xiàng)分布中考慮了鄰域的影響，從概率方面對傳統(tǒng)的矩陣分解方法進(jìn)行改進(jìn)。在MovieLens數(shù)據(jù)集下，對提出的算法和傳統(tǒng)的矩陣分解算法進(jìn)行了對比分析。實(shí)驗(yàn)表明，這種基于二項(xiàng)分布的矩陣分解推薦算法能夠有效的提高推薦精度，具有較好的穩(wěn)定性。

［1］許海玲，李曉東，吳瀟.互聯(lián)網(wǎng)推薦系統(tǒng)比較研究［J］.軟件學(xué)報(bào)，2009，20（2）：74-80.

［2］周靜.基于信任的協(xié)同過濾推薦算法研究［D］.秦皇島：燕山大學(xué)，2013.

［3］JingLong Wu.Binomial Matrix Factorization for Discrete Collaborate Filterring［C］∥.DataMining，ICDM's09.Ninth IEEE international conference.［S.I.］:IEEE，2009:262-272.

［4］丁振國，陳靜，吳金龍.基于關(guān)聯(lián)規(guī)則的個(gè)性化推薦系統(tǒng)［J］.計(jì)算機(jī)集成制造系統(tǒng)，2003，9（10）：890-894.

［5］Li Pu，F(xiàn)altings B.Understanding and Improving Relational Matrix Factorization in Recommender Systems［C］.Procee dings of the 7thACM conference on Recommender systems，New York:ACM，2013:41-48.

［6］陳天奇.基于特征的矩陣分解模型［D］.上海：上海交通大學(xué)，2013.

【相關(guān)參考文獻(xiàn)鏈接】

陳小輝，高燕，劉漢燁.基于歸一化方法的協(xié)同過濾推薦算法［J］.2014,22（14）：17-20.

魏嬋娟，張春水，劉健.一種基于Cholesky分解的快速矩陣求逆方法設(shè)計(jì)［J］.2014,22（1）：159-161,164.

曹旭東，孫敬晶，張實(shí).基于ARM及μC/OS-Ⅱ的RGB視頻矩陣設(shè)計(jì)［J］.2014,22（2）：180-184.

張祎煊，殷新社，張燚.基于耦合矩陣修正和空間映射法的濾波器設(shè)計(jì)［J］.2015,23（1）；130-133.

馬琳，王直杰，朱曉明，等 .基于灰度共生矩陣的注塑模具瑕疵檢測［J］.2015,23（7）：138-140.

張衛(wèi)華.基于矩陣的apriori算法的改進(jìn)［J］.2015,23（13）：52-54.

曾弘揚(yáng).基于Epiphany計(jì)算并行矩陣乘法的研究［J］.2015,23（24）：52-55.

路振民，王陽，陸圣宇，等.基于矩陣鍵盤和QT/E的中文輸入設(shè)計(jì)［J］.2016,24（4）：161-163.

張茗茗，周詮.基于修正正態(tài)分布的噴泉編碼［J］.2015,23（19）：89-93.

彭鑫.一種基于稀疏矩陣的指紋識別新方法 ［J］.2014,22（23）：54-55.

徐彬，張建明.基于標(biāo)簽與協(xié)同過濾算法的淘書吧應(yīng)用［J］. 2014,22（23）：21-23.

郭秀琪.基于本體的旅游資源推薦算法研究［J］.2016（6）：108-110.

袁小艷.基于情境的個(gè)性化學(xué)習(xí)云服務(wù)推薦模型研究［J］.2016（4）：39-41.

唐積益，黃樹成.優(yōu)化相似度計(jì)算在推薦系統(tǒng)中的應(yīng)用［J］. 2015（23）:46-48.

史玉珍，鄭浩.基于協(xié)同過濾技術(shù)的個(gè)性化推薦系統(tǒng)研究［J］. 2012（11）:41-44.

譚林，朱江，楊軍，等.近地應(yīng)用CCSDS標(biāo)準(zhǔn)LDPC碼動(dòng)態(tài)補(bǔ)償譯碼算法研究［J］.2011（18）:36-38.

A movie recommendation algorithm based on matrix decomposition

NIE Chang-chao
（Computer Science and Engineering，Nanjing University of Technology and Engineering，Nanjing 210014，China）

For the currentmovie recommendation algorithm，the traditionalmatrix factorization algorithm score for the user's discrete data set is not high data availability problem，matrix decomposition algorithm based on the binomialmodel，on the assumption that the user data is to obey ratings under the premise of the binomial，using themaximum a posterioriestimation loss function study results，the user's interest degree as the impact factor，join neighborhood impact between projects，followed by the use of stochastic gradient descentmethod for problem solving.By the MovieLens datasetswith conventional matrix factorization algorithm comparison test results show that the proposed algorithm can effectively improve the recommendation accuracy，showing good stability.

recommendation algorithm；binomial distribution；stochastic gradient descent；matrix factorization

TN99

A

1674-6236（2016）19-0073-03

2015-10-21稿件編號：201510147

聶常超（1986—），男，河南新鄉(xiāng)人，碩士研究生。研究方向：機(jī)器學(xué)習(xí)、計(jì)算機(jī)視覺。