一種改進(jìn)的FunkSVD算法

岳小琛,劉其成,牟春曉

(煙臺(tái)大學(xué)計(jì)算機(jī)控制與工程學(xué)院,山東 煙臺(tái) 264005)

隨著大數(shù)據(jù)時(shí)代的發(fā)展,各平臺(tái)的數(shù)據(jù)信息量越來越多,導(dǎo)致用戶難以從海量數(shù)據(jù)中獲取自己感興趣的內(nèi)容。因此,推薦系統(tǒng)應(yīng)運(yùn)而生,在電子商務(wù)、電影視頻、社交網(wǎng)絡(luò)、閱讀、基于位置服務(wù)(外賣、打車)、個(gè)性化郵件、個(gè)性化廣告等方面都發(fā)揮著重要作用[1-3]。推薦算法主要有基于內(nèi)容的推薦算法、協(xié)同過濾的推薦算法、混合推薦算法三類,其中協(xié)同過濾推薦算法應(yīng)用最為廣泛[4]。

協(xié)同過濾推薦算法主要分為基于用戶(user-based)的協(xié)同過濾[5]、基于項(xiàng)目(item-based)的協(xié)同過濾[6]以及基于模型(model based)的協(xié)同過濾[7]?；谀Ｐ偷膮f(xié)同過濾算法主要通過機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘模型的思想來建模解決,逐漸成為當(dāng)前研究的熱點(diǎn)方向[8]。文獻(xiàn)[9]提出了一種基于用戶播放行為序列的個(gè)性化推薦策略,實(shí)現(xiàn)了視頻網(wǎng)站的個(gè)性化推薦。

隨著基于模型的推薦算法進(jìn)一步發(fā)展,FunkSVD算法在推薦系統(tǒng)的研究中得到了廣泛的應(yīng)用[10],該算法解決了傳統(tǒng)SVD算法計(jì)算速率慢以及需要手動(dòng)補(bǔ)全缺失的值的問題。為了提高FunkSVD算法的準(zhǔn)確率,文獻(xiàn)[11]基于FunkSVD提出了一種矩陣因子分解的體系結(jié)構(gòu)和方法,為矩陣中每項(xiàng)預(yù)測(cè)提供可靠性值,提高了算法的準(zhǔn)確率,然而對(duì)于稀疏的矩陣效果不佳。文獻(xiàn)[12]提出一種基于FunkSVD矩陣分解和相似度矩陣的推薦算法,提高了算法的準(zhǔn)確率,但該算法有可能產(chǎn)生迭代振蕩現(xiàn)象,陷入局部最優(yōu)解,而非全局最優(yōu)解。文獻(xiàn)[13]提出了一種將用戶社會(huì)關(guān)系信息和項(xiàng)目信息融合在一起的改進(jìn)FunkSVD算法,提高了算法的準(zhǔn)確率,然而存在數(shù)據(jù)稀疏的問題,亟待解決。

針對(duì)上述問題,本文提出了一種基于深度學(xué)習(xí)的推薦算法,以提高FunkSVD推薦算法的準(zhǔn)確率。利用深度學(xué)習(xí)中的RMSProp算法對(duì)傳統(tǒng)FunkSVD進(jìn)行改進(jìn),避免陷入局部最優(yōu)解的困境,解決了迭代振蕩以及數(shù)據(jù)稀疏影響算法準(zhǔn)確率的問題,從而提高了推薦的準(zhǔn)確率。經(jīng)民宿數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果表明,本文提出的算法較傳統(tǒng)算法有更高的準(zhǔn)確率。

1 相關(guān)概念

1.1 傳統(tǒng)FunkSVD算法

FunkSVD算法是在傳統(tǒng)SVD算法面臨計(jì)算效率問題時(shí)提出來的,解決了SVD算法中需要補(bǔ)全缺失的值的問題,思想簡(jiǎn)單,效果好,將基于模型中矩陣分解的推薦算法推到了新的高度,該算法在實(shí)際應(yīng)用中使用也非常廣泛。

FunkSVD算法不再是分解為三個(gè)矩陣,而是將期望矩陣R分解為兩個(gè)低秩的用戶矩陣P和物品矩陣Q,把用戶和物品都映射到一個(gè)k維空間中,這個(gè)k維空間對(duì)應(yīng)著k個(gè)隱因子。即將期望矩陣R如下進(jìn)行分解:

(1)

對(duì)于分解評(píng)分矩陣,實(shí)際上是應(yīng)用線性回歸的思想,用均方差作為目標(biāo)函數(shù),來尋找P和Q的最優(yōu)值。然而,在實(shí)際中,為了防止過擬合,通常加上一個(gè)正則化項(xiàng),針對(duì)已有的評(píng)分樣本,可得到以下?lián)p失函數(shù):

(2)

式中:rij為R中元素值,pik,qkj分別為P、Q中的元素值,λ為正則化系數(shù)。

傳統(tǒng)FunkSVD算法采用梯度下降法求解損失函數(shù)。

首先對(duì)公式(2)中的P、Q求偏導(dǎo)可得

λpik=-2eijqkj+λpik,

(3)

λqkj=-2eijpkj+λqkj。

(4)

隨后,根據(jù)梯度下降法更新初始P、Q,得到最優(yōu)用戶矩陣P以及最優(yōu)物品矩陣Q。最后通過笛卡爾積計(jì)算得到更新后的評(píng)分矩陣。

1.2RMSProp算法

RMSProp算法是一種深度學(xué)習(xí)優(yōu)化算法。該算法是梯度下降法的一種改進(jìn),它根據(jù)自變量在每個(gè)維度的梯度值的大小來調(diào)整各個(gè)維度上的學(xué)習(xí)率,對(duì)低頻的參數(shù)做較大的更新,對(duì)高頻的參數(shù)做較小的更新,因此,對(duì)稀疏的數(shù)據(jù)表現(xiàn)很好[14]。RMSProp算法的梯度動(dòng)量E[g2]是對(duì)平方項(xiàng)gt2的指數(shù)加權(quán)移動(dòng)平均值,保證了各維度導(dǎo)數(shù)都在一個(gè)量級(jí),也因此減小了梯度下降法的迭代振蕩[15]。具體來說,給定超參數(shù)0≤γ<1、 迭代次數(shù)t>0時(shí)計(jì)算指數(shù)衰減平均值,如式(5):

(5)

其中:t為迭代次數(shù),E[g2]t為損失函數(shù)在t時(shí)刻的累積的梯度動(dòng)量,γ為衰減指數(shù),gt為t時(shí)刻參數(shù)的梯度值。

RMSProp算法將目標(biāo)函數(shù)自變量中每個(gè)元素的學(xué)習(xí)率按元素運(yùn)算重新調(diào)整,然后更新自變量,如式(6):

(6)

其中:θ為參數(shù)值,η為學(xué)習(xí)率,ε是為了維持?jǐn)?shù)值穩(wěn)定性而添加的常數(shù),如10-6。

2 基于RMSProp算法改進(jìn)的FunkS- VD算法

2.1 算法優(yōu)化

針對(duì)傳統(tǒng)FunkSVD算法準(zhǔn)確率較低的問題,利用深度學(xué)習(xí)優(yōu)化算法RMSProp對(duì)傳統(tǒng)算法進(jìn)行改進(jìn),改進(jìn)后的算法對(duì)稀疏數(shù)據(jù)效果好,減小了迭代過程中振蕩,提高了傳統(tǒng)算法的準(zhǔn)確率。

本文算法具體步驟如下:

(1) 準(zhǔn)備好用戶物品的評(píng)分矩陣R,每一條評(píng)分?jǐn)?shù)據(jù)看作一條訓(xùn)練樣本;

(2) 按照公式(1)將評(píng)分矩陣R分解為用戶矩陣P和物品矩陣Q;

(4) 利用RMSProp算法取代梯度下降法更新P、Q中的元素值,具體步驟如下:

(7)

(8)

最后,將公式(3)、(4)計(jì)算結(jié)果以及公式(7)、(8)中求得的p、q指數(shù)衰減平均值代入公式(6)更新P、Q矩陣每個(gè)元素值,更新規(guī)則如式(9)、式(10):

(9)

(10)

(6) 將上一步最終得到的最優(yōu)矩陣P、Q的參數(shù)值pt、qt代入到公式(11)中,得到更新后的評(píng)分Ti。

(11)

2.2 算法設(shè)計(jì)

本文算法設(shè)計(jì)主要分為三部分:求解損失函數(shù)、更新迭代、評(píng)分預(yù)測(cè)。迭代更新是該算法的核心部分,在此過程中尋優(yōu)找到P、Q最優(yōu)值,進(jìn)而進(jìn)行評(píng)分預(yù)測(cè)。

上述算法偽代碼如算法1。

算法1 迭代更新

輸入: 損失函數(shù)e, 衰減指數(shù)γ, 學(xué)習(xí)率η, 常數(shù)ε,極小值β。

輸出: 最優(yōu)值pt,qt。

for each value do

Δp=-2eq+λp

Δq=-2ep+λq

Ep=γEp+(1-γ)(Δp)2

Eq=γEq+(1-γ)(Δq)2

end for

for each value do

end for

end while

2.2.3 評(píng)分預(yù)測(cè) 利用上一步中最后得到的最優(yōu)值進(jìn)行評(píng)分預(yù)測(cè),如公式(11),計(jì)算出最終的評(píng)分,最終輸出評(píng)分矩陣Ti。

3 實(shí)驗(yàn)及結(jié)果分析

3.1 實(shí)驗(yàn)數(shù)據(jù)

本實(shí)驗(yàn)所用數(shù)據(jù)為網(wǎng)上下載的三個(gè)公開推薦算法數(shù)據(jù)集Movielens、OpenStreetMap和Last.fm,數(shù)據(jù)集的稀疏程度依次增大,都包括Item、User以及Rating。具體如表1。

表1 實(shí)驗(yàn)數(shù)據(jù)集

3.2 評(píng)價(jià)指標(biāo)

評(píng)價(jià)一個(gè)推薦系統(tǒng)有多種指標(biāo),本文采用平均絕對(duì)誤差(Mean Absolute Error, MAE)和均方根誤差(Root Mean Square Error, RMSE),兩種評(píng)價(jià)指標(biāo)衡量算法的優(yōu)劣。

MAE越小,說明預(yù)測(cè)值與真實(shí)值的差距越小,推薦精度越高,公式如下:

(12)

式中:rui′表示用戶u對(duì)物品i的預(yù)測(cè)評(píng)分,rui表示用戶u對(duì)物品i的實(shí)際評(píng)分,n為評(píng)分個(gè)數(shù)。

RMSE越小,推薦的準(zhǔn)確率越高,公式如下:

(13)

式中:sui′表示用戶u對(duì)物品i的預(yù)測(cè)評(píng)分,sui表示用戶u對(duì)物品i的實(shí)際評(píng)分,n為評(píng)分個(gè)數(shù)。

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

3.3.1 參數(shù)定義 本文算法參數(shù)較多,其中公式(1)中的k為特征數(shù),通常為用戶自定義[10];公式(2)中的λ為正則化參數(shù),本文算法設(shè)為0.2[16];公式(5)中的衰減速率γ通常設(shè)為0.9,公式(6)中的學(xué)習(xí)率η通常設(shè)為0.000 1[15]。

3.3.2 參數(shù)調(diào)整 本文算法最主要的參數(shù)為公式(5)中的衰減速率γ。發(fā)現(xiàn)γ的取值為0.5時(shí)改進(jìn)算法具有更高的準(zhǔn)確率。采用Movielens數(shù)據(jù)集,迭代次數(shù)為10、20、30時(shí),不同參數(shù)值的RMSE與MAE變化如圖1。當(dāng)?shù)螖?shù)為30,采用不同數(shù)據(jù)集時(shí),不同參數(shù)值的RMSE與MAE變化如表2。

圖1 不同迭代次數(shù)下不同參數(shù)值的RMSE和MAE

表2 不同數(shù)據(jù)集下不同參數(shù)的RMSE、MAE

由圖1、表2可見,無論是數(shù)據(jù)集不變,改變迭代次數(shù)的情況下,還是迭代次數(shù)不變,改變數(shù)據(jù)集的情況下,參數(shù)值為0.5時(shí)算法的準(zhǔn)確率更高。

3.4 算法對(duì)比

3.4.1 迭代次數(shù) 本文算法通過減輕傳統(tǒng)FunkSVD算法中迭代振蕩現(xiàn)象來提高算法的準(zhǔn)確率,因此實(shí)驗(yàn)通過改變迭代次數(shù)將本文提出的算法與傳統(tǒng)FunkSVD算法以及文獻(xiàn)[11-12]中提出的改進(jìn)算法進(jìn)行對(duì)比,實(shí)驗(yàn)數(shù)據(jù)為Movielens,迭代次數(shù)為10、20、30。不同算法的RMSE和MAE變化如圖2。

圖2 不同算法的RMSE和MAE對(duì)比

由圖2可見,在不同迭代次數(shù)下,本文算法較其他三種算法,準(zhǔn)確率得到了提高。

3.4.2 數(shù)據(jù)稀疏性 本文提出的改進(jìn)算法對(duì)稀疏的數(shù)據(jù)效果表現(xiàn)良好,在此基礎(chǔ)上能夠提高算法的準(zhǔn)確率。因此,對(duì)不同稀疏程度的數(shù)據(jù)集進(jìn)行了實(shí)驗(yàn)對(duì)比。Movielens、OpenStreetMap、Last.fm數(shù)據(jù)集稀疏程度依次增大。迭代次數(shù)取值為30。實(shí)驗(yàn)對(duì)比情況如圖3。

由圖3可知,隨著數(shù)據(jù)集的稀疏性增大,四種算法的準(zhǔn)確率均有所下降,然而本文算法準(zhǔn)確率顯著高于其他三種算法。因此,可以認(rèn)為本文算法在處理稀疏數(shù)據(jù)時(shí)優(yōu)于其他三種算法。

圖3 不同稀疏度下RMSE和MAE對(duì)比

綜上,結(jié)合分析實(shí)驗(yàn)結(jié)果表明,本文算法較傳統(tǒng)FunkSVD算法、文獻(xiàn)[11]改進(jìn)算法、文獻(xiàn)[12]改進(jìn)算法具有更高的準(zhǔn)確率,說明在提高準(zhǔn)確率方面,通過改進(jìn)數(shù)據(jù)稀疏以及迭代振蕩是有效的,并且公式(5)中的參數(shù)取值為0.5、迭代次數(shù)為30時(shí)本文算法達(dá)到最優(yōu)。

4 結(jié)束語

推薦系統(tǒng)的應(yīng)用越來越廣泛,基于模型的推薦算法也逐漸成為較為流行的算法之一,將深度學(xué)習(xí)與模型結(jié)合的推薦算法的研究也越來越多。本文為了提高傳統(tǒng)FunkSVD算法的準(zhǔn)確率,在數(shù)據(jù)稀疏以及迭代振蕩方面用深度學(xué)習(xí)優(yōu)化算法RMSProp對(duì)其進(jìn)行了改進(jìn)。實(shí)驗(yàn)結(jié)果表明,本文提出的算法的準(zhǔn)確率有所提高,優(yōu)于傳統(tǒng)算法。

然而,本文算法在運(yùn)行時(shí)間上較傳統(tǒng)算法更慢,因此下一步的研究方向就是解決速率問題,以及如何將本文算法與其他算法結(jié)合使用,將其應(yīng)用于更多實(shí)際問題上,實(shí)現(xiàn)更加有效的推薦算法。