聶常超

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

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

聶常超

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

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

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

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

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

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

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

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

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

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

其中βu，i表示用戶u對(duì)于項(xiàng)目i的評(píng)分概率。pu，qi分別滿足正態(tài)分布并且相互獨(dú)立。進(jìn)一步假設(shè)在該二項(xiàng)分布中，對(duì)于不同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ù)來(lái)獲取難以觀測(cè)到的變量的點(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ù)可以用下式表示：

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

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

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

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

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

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

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

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

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

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

7）對(duì)均方根誤差RMSE進(jìn)行計(jì)算，如果本次計(jì)算結(jié)果與上次結(jié)果之差的絕對(duì)值小于某一特定閾值，則迭代結(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è)用戶針對(duì)1682個(gè)商品進(jìn)行的100 000條評(píng)分信息，MovieLens-1m數(shù)據(jù)集則包含了6 040個(gè)用戶針對(duì)3 900個(gè)商品的1 000 209條評(píng)分記錄，每個(gè)用戶對(duì)20或20部以上的電影進(jìn)行過(guò)評(píng)分，用戶對(duì)每部電影的評(píng)分為5個(gè)等級(jí)（1到5分）。除了有評(píng)分信息之外，數(shù)據(jù)集中還包含有用戶信息，電影信息，對(duì)電影評(píng)分的時(shí)戳等信息。即便如此，數(shù)據(jù)依然非常稀疏，在用戶-項(xiàng)目的評(píng)分矩陣中，評(píng)分信息只有6.3%。

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

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

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

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

為了比較傳統(tǒng)的矩陣分解算法與所提出的二項(xiàng)矩陣分解算法的異同，這里提出3種方法來(lái)進(jìn)行對(duì)照實(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的不同對(duì)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值對(duì)于推薦結(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é)束語(yǔ)

隨著近年來(lái)對(duì)于推薦算法的研究逐漸深入，越來(lái)越多的研究者開始關(guān)注矩陣分解算法。但是基于矩陣分解的推薦算法依然存在一些不足，如算法復(fù)雜度高，對(duì)用戶數(shù)據(jù)利用率低等。針對(duì)現(xiàn)實(shí)中用戶評(píng)分普遍具有離散性的特點(diǎn)，提出基于二項(xiàng)分布的矩陣分解算法和改進(jìn)，在二項(xiàng)分布中考慮了鄰域的影響，從概率方面對(duì)傳統(tǒng)的矩陣分解方法進(jìn)行改進(jìn)。在MovieLens數(shù)據(jù)集下，對(duì)提出的算法和傳統(tǒng)的矩陣分解算法進(jìn)行了對(duì)比分析。實(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é)同過(guò)濾推薦算法研究［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ó)，陳靜，吳金龍.基于關(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é)同過(guò)濾推薦算法［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.

馬琳，王直杰，朱曉明，等 .基于灰度共生矩陣的注塑模具瑕疵檢測(cè)［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.

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

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

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

徐彬，張建明.基于標(biāo)簽與協(xié)同過(guò)濾算法的淘書吧應(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é)同過(guò)濾技術(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稿件編號(hào)：201510147

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