引入時(shí)間效應(yīng)的SVD++線性回歸推薦算法

蘇 慶,章靜芳,李小妹

(廣東工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院,廣州 510006)

0 概述

隨著互聯(lián)網(wǎng)技術(shù)的飛速發(fā)展,各類信息容量劇增導(dǎo)致嚴(yán)重的“信息過(guò)載”問(wèn)題[1],一方面用戶從海量數(shù)據(jù)中獲取感興趣的信息變得越來(lái)越困難,另一方面服務(wù)方難以從海量數(shù)據(jù)中抽象出個(gè)性化的用戶需求。推薦系統(tǒng)作為一種信息過(guò)濾系統(tǒng),能有效解決上述問(wèn)題。在推薦系統(tǒng)中廣泛使用的是基于協(xié)同過(guò)濾(Collaborative Filtering,CF)[2]的推薦算法。該類算法基于用戶對(duì)商品的評(píng)分或其他行為模式為用戶提供個(gè)性化的推薦。目前協(xié)同過(guò)濾采用的主要技術(shù)包括基于鄰域的方法[3]和隱語(yǔ)義模型,其中,基于矩陣分解的隱語(yǔ)義模型[4]具有較好的預(yù)測(cè)穩(wěn)定性以及精確度。

文獻(xiàn)[5]利用奇異值分解(Singular Value Decomposition,SVD)進(jìn)行矩陣分解,其主要缺點(diǎn)在于一開(kāi)始就需要補(bǔ)全評(píng)分矩陣的缺失值,即將一個(gè)稀疏矩陣轉(zhuǎn)化為一個(gè)稠密矩陣后再進(jìn)行分解。然而對(duì)高維稠密矩陣進(jìn)行SVD分解的時(shí)間復(fù)雜度和空間復(fù)雜度都非常高。因此,文獻(xiàn)[6-7]分別提出基于正則化的矩陣分解(Regularized SVD,RSVD)模型和非對(duì)稱矩陣分解模型(Asymmetric SVD,ASVD),通過(guò)充分的正則化來(lái)避免過(guò)擬合,且取得了較好的預(yù)測(cè)準(zhǔn)確性。文獻(xiàn)[8]提出基于信任的正則化分解模型TrustSVD,將社會(huì)信任關(guān)系融入到推薦模型中,有效提高了模型預(yù)測(cè)結(jié)果的準(zhǔn)確度。文獻(xiàn)[9]提出一種聯(lián)合正則化的矩陣分解(Co-Regularized Matrix Factorization,CRMF)推薦模型,將關(guān)聯(lián)關(guān)系與社會(huì)關(guān)系相融合,有效緩解用戶的冷啟動(dòng)問(wèn)題。SVD++模型[7]在RSVD模型基礎(chǔ)上融合隱式反饋信息使得預(yù)測(cè)的準(zhǔn)確度進(jìn)一步提高。

上述算法模型忽略了一個(gè)重要影響因素:用戶的偏好和物品的流行度都可能會(huì)隨著時(shí)間變化而改變。文獻(xiàn)[10]提出一個(gè)基于時(shí)間依賴模型的推薦系統(tǒng),將時(shí)間因子引入到協(xié)同過(guò)濾算法中,有效提高了推薦系統(tǒng)的預(yù)測(cè)準(zhǔn)確度。但是,在該模型引入的時(shí)間因子中,物品偏置只與物品相關(guān),用戶偏置只與用戶相關(guān),導(dǎo)致推薦結(jié)果穩(wěn)定性較差。

本文提出一種引入時(shí)間效應(yīng)的SVD++線性回歸推薦算法timeSVD++LR,在SVD++模型的基礎(chǔ)上引入時(shí)間效應(yīng)屬性,通過(guò)對(duì)時(shí)間效應(yīng)建模進(jìn)一步提高預(yù)測(cè)結(jié)果的準(zhǔn)確度,同時(shí)根據(jù)初始預(yù)測(cè)評(píng)分構(gòu)造特征向量Xk,將原始訓(xùn)練數(shù)據(jù)作為線性回歸模型[11]的輸入,使用梯度下降算法[12]優(yōu)化最終代價(jià)函數(shù),生成一組參數(shù)θ=(θ0,θ1,…,θn)T使得代價(jià)函數(shù)值最小,并利用預(yù)測(cè)函數(shù)模型hθ(Xk)=θTXk求得測(cè)試集上的預(yù)測(cè)評(píng)分,從整體上提高用戶預(yù)測(cè)評(píng)分的準(zhǔn)確性。

1 SVD++模型

SVD++模型在RSVD模型基礎(chǔ)上融合隱式反饋信息,使得預(yù)測(cè)的準(zhǔn)確度進(jìn)一步提高。SVD++模型的核心思想是通過(guò)隱含特征關(guān)系聯(lián)系用戶興趣和項(xiàng)目,將用戶和項(xiàng)目?jī)煞矫娴男畔⑷诤想[式反饋信息映射到一個(gè)因子維度[13]為f的聯(lián)合隱語(yǔ)義空間,用戶-項(xiàng)目之間的交互作用被建模為該空間中的內(nèi)積。

(1)

(2)

2 線性回歸模型

線性回歸是按照給定的特征,對(duì)其和實(shí)際值之間的組合關(guān)系進(jìn)行分析,并通過(guò)線性組合的方式來(lái)擬合真實(shí)值。對(duì)于每一條評(píng)分記錄(樣本k),預(yù)測(cè)評(píng)分函數(shù)模型如式(3)所示。

(3)

其中,n表示特征個(gè)數(shù),x(k)表示樣本k的特征向量。最終代價(jià)函數(shù)如式(4)所示。

(4)

其中,J(θ0,θ1,…,θn)表示誤差平方和,y(k)表示真實(shí)值,m表示訓(xùn)練集的評(píng)論數(shù)總和(樣本數(shù))。代價(jià)函數(shù)用于計(jì)算參數(shù)θ=(θ0,θ1,…,θn)T。利用梯度下降法優(yōu)化代價(jià)函數(shù)J(θ0,θ1,…,θn)并求解最小值,對(duì)θ進(jìn)行求偏導(dǎo)操作,解出求導(dǎo)部分如式(5)所示。

(5)

3 timeSVD++LR推薦算法

3.1 算法原理

SVD++模型適用于對(duì)時(shí)間因子建模。通過(guò)將評(píng)分分解為各個(gè)不同項(xiàng),分別對(duì)應(yīng)于不同方面的時(shí)序影響,定義隨時(shí)間變化的偏置因子[14]:用戶偏置bu(t)和物品偏置bi(t)。用戶偏置bu(t)體現(xiàn)為隨著時(shí)間的變化,用戶可能會(huì)改變他們的基準(zhǔn)評(píng)分,例如某位過(guò)去傾向于對(duì)電影評(píng)分為3星的用戶可能現(xiàn)在給出的評(píng)分為4星;物品偏置bi(t)體現(xiàn)為物品的流行度或許隨時(shí)間變化,例如在最新一部電影里某位演員的出現(xiàn)或許會(huì)導(dǎo)致該電影的流行或過(guò)時(shí)。在第tui天,用戶u對(duì)物品i的評(píng)分如式(6)所示。

bui=μ+bu(tui)+bi(tui)

(6)

其中,bu(tui)和bi(tui)是隨時(shí)間變化的實(shí)數(shù)函數(shù),分別代表用戶偏置bu(t)和物品偏置bi(t)。

bi(t)=(bi+bi·Sng(t))wu(tui)

(7)

(8)

(9)

wu(tui)表示物品偏置與時(shí)間相關(guān)的擴(kuò)展特征,zi(tui)表示用戶偏置與時(shí)間相關(guān)的擴(kuò)展特征,增加參數(shù)zi(tui)和wu(tui)以改善由于引入時(shí)間因子帶來(lái)的預(yù)測(cè)結(jié)果欠缺穩(wěn)定性的問(wèn)題。

wu(tui)=wu+wu,t,zi(tui)=zi+zi,t

(10)

其中wu和zi是穩(wěn)定部分,wu,t和zi,t代表特定天的變化。

物品偏置bi(t)和用戶偏置bu(t)可被分為一個(gè)固定部分和一個(gè)隨時(shí)間變化的部分。通過(guò)使用隨機(jī)梯度下降算法來(lái)最小化數(shù)據(jù)集上相關(guān)的平方誤差函數(shù)來(lái)完成學(xué)習(xí)過(guò)程,在SVD++算法中引入時(shí)間效應(yīng)屬性構(gòu)造推薦模型,用戶u對(duì)物品i的初始預(yù)測(cè)評(píng)分用式(11)表示。

(11)

圖1 timeSVD++LR推薦算法流程

3.2 算法構(gòu)建

timeSVD++LR算法的構(gòu)造步驟如下:

步驟1計(jì)算項(xiàng)目偏置項(xiàng)bi和用戶偏置bu。

(12)

(13)

其中,R(i)表示評(píng)分了的物品i的所有用戶列表,R(u)表示用戶u給予評(píng)分的所有物品列表,λ2=25,λ3=10,全局平均數(shù)μ表示訓(xùn)練集的平均評(píng)分。

(14)

步驟3在矩陣因子分解方法中分別對(duì)項(xiàng)目偏置bi和用戶偏置bu均加上時(shí)間效應(yīng)屬性,如式(7)和式(8)所示,用戶u對(duì)物品i的初始預(yù)測(cè)評(píng)分如式(15)所示。

(15)

為了學(xué)習(xí)模型中的參數(shù)bi(t)、bu(t)、pu、qi,需要最小化相關(guān)聯(lián)的正則化平方誤差函數(shù),如式(16)和式(17)所示。

(16)

(17)

bu(t)←bu(t)+γ·(eu,i-λ5·bu(t))

(18)

bi(t)←bi(t)+γ·(eu,i-λ5·bi(t))

(19)

(20)

(21)

通過(guò)為每類待學(xué)習(xí)參數(shù)選擇學(xué)習(xí)率γ和正則化因子λ來(lái)提高預(yù)測(cè)準(zhǔn)確度,本文設(shè)置γ=0.02,λ6=0.015,λ5=0.005。

hθ(X)=θTX=θ0x0+θ1x1+…+θnxn

(22)

(23)

timeSVD++LR算法構(gòu)造部分用到多個(gè)常量值,針對(duì)SVD++算法,當(dāng)λ2=25,λ3=10,λ4=0.02,λ5=0.005,λ6=0.015時(shí)[15],推薦算法的預(yù)測(cè)效果最好,考慮到本文提出的算法與SVD++算法的相關(guān)性,故選取相同的正則化參數(shù)值,并且當(dāng)學(xué)習(xí)率γ=0.02時(shí),在MovieLens數(shù)據(jù)集上進(jìn)行測(cè)試預(yù)測(cè)結(jié)果最穩(wěn)定。

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

4.1 實(shí)驗(yàn)設(shè)置

為測(cè)試timeSVD++LR算法的準(zhǔn)確性,本文將其與RSVD、SVD++、timeSVD++算法進(jìn)行比較。實(shí)驗(yàn)采用MovieLens數(shù)據(jù)集[16]中的MovieLens_100k數(shù)據(jù)集,包含943名用戶對(duì)1 682部電影的約100 000條評(píng)分信息(評(píng)分密度約為6.3%),記為MovieLens_LR數(shù)據(jù)集。文獻(xiàn)[17]對(duì)推薦系統(tǒng)領(lǐng)域內(nèi)的各種不同的評(píng)價(jià)標(biāo)準(zhǔn)做了總結(jié),本文將采用檢驗(yàn)推薦算法最常用的平均絕對(duì)誤差(Mean Absolute Deviation,MAE)、均方根誤差(Root Mean Square Error,RMSE)作為評(píng)價(jià)指標(biāo)[18]。

(24)

(25)

其中,Xi表示timeSVD++LR算法對(duì)項(xiàng)目的最終預(yù)測(cè)評(píng)分,Yi表示用戶的實(shí)際評(píng)分,N表示項(xiàng)目的數(shù)量。MAE和RMSE的值越小,表示算法性能越好。

(26)

(27)

(28)

(29)

其中,μ為全局平均數(shù),σ1=0.000 05、σ2=-0.000 05為調(diào)節(jié)因子,其作用主要是為穩(wěn)定特征向量值的變化,對(duì)整體特征向量值影響不大。

4.2 結(jié)果分析

實(shí)驗(yàn)1在MovieLens_LR數(shù)據(jù)集上測(cè)試不同最大迭代次數(shù)下算法的表現(xiàn)。為減弱學(xué)習(xí)率γ和因子維度f(wàn)帶來(lái)的影響,令γ=0.002,f=20。在設(shè)置的最大迭代次數(shù)內(nèi),將損失函數(shù)J(θ)所能達(dá)到的最小值對(duì)應(yīng)的一組θ=(θ0,θ1,θ2,θ3,θ4)T值作為預(yù)測(cè)函數(shù)hθ(Xk)的參數(shù),求出最終的預(yù)測(cè)分?jǐn)?shù)。實(shí)驗(yàn)1的結(jié)果如圖2和表1所示。在表1中,加粗?jǐn)?shù)據(jù)為各算法的最優(yōu)MAE/RMSE值。從圖2可以看出,timeSVD++LR算法的MAE、RMSE值均較其他3種算法小,其MAE值在0.68附近波動(dòng),RMSE值保持在0.86左右。timeSVD++算法僅在SVD++算法基礎(chǔ)上引入時(shí)間效應(yīng)屬性,未進(jìn)行線性回歸操作,故其MAE和RMSE值較為不穩(wěn)定,但最大迭代次數(shù)小于70左右時(shí),相較于RSVD和SVD++算法,其MAE和RMSE值均相對(duì)較小,說(shuō)明在timeSVD++中引入時(shí)間效應(yīng)屬性在能有效提高推薦算法的預(yù)測(cè)精度。TimeSVD++LR在TimeSVD++基礎(chǔ)上又引入線性回歸操作,還能進(jìn)一步提高推薦算法穩(wěn)定性。特別地,當(dāng)最大迭代次數(shù)為80時(shí),timeSVD++LR算法模型的MAE值最小,約為0.673 6;當(dāng)最大迭代次數(shù)為50時(shí),timeSVD++LR算法模型的RMSE值最小,約為0.857 2。

圖2 不同迭代次數(shù)下各算法MAE、RMSE值的比較

Fig.2 Comparison of MAE and RMSE values of different algorithms under different iterations

表1 不同最大迭代次數(shù)下各算法MAE、RMSE值的比較結(jié)果

實(shí)驗(yàn)2在同一數(shù)據(jù)集上測(cè)試不同因子維度f(wàn)下算法的表現(xiàn)。4種算法模型的學(xué)習(xí)率均取γ=0.002。從表1可知,RSVD、SVD++、timeSVD++和timeSVD++LR算法最佳最大迭代次數(shù)依次為150、150、50和80,故在實(shí)驗(yàn)2中設(shè)置最大迭代次數(shù)為最佳迭代次數(shù),結(jié)果如圖3和表2所示。在表2中,加粗?jǐn)?shù)據(jù)為各算法的最優(yōu)MAE/RMSE值。從圖3可看出,在一定范圍內(nèi)隨著因子維度的增大,4種算法的MAE和RMSE值均逐漸減小。這說(shuō)明在一定范圍內(nèi)因子維度的增大可提高算法的預(yù)測(cè)準(zhǔn)確度。從表2可看出,當(dāng)因子維度為200時(shí),timeSVD++LR算法的RMSE值最小,約為0.858 3,此時(shí) MAE值約為0.669 1,其結(jié)果均小于其他3種算法的最小RMSE和最小MAE值。

圖3 不同因子維度下各算法MAE、RMSE值的比較

表2 不同因子維度下各算法MAE、RMSE值的比較結(jié)果

通過(guò)2組實(shí)驗(yàn)對(duì)比可知,在4種算法中,timeSVD++LR算法的穩(wěn)定性和預(yù)測(cè)精度較好。

5 結(jié)束語(yǔ)

本文提出一種引入時(shí)間效應(yīng)的推薦算法timeSVD++LR。在SVD++模型基礎(chǔ)上引入時(shí)間效應(yīng)屬性,根據(jù)預(yù)測(cè)評(píng)分構(gòu)造特征向量。將原始訓(xùn)練數(shù)據(jù)作為線性回歸模型的輸入,采用隨機(jī)梯度下降算法優(yōu)化代價(jià)函數(shù),使得代價(jià)函數(shù)值最小,生成回歸參數(shù),并根據(jù)特征向量和回歸參數(shù)求得預(yù)測(cè)評(píng)分。實(shí)驗(yàn)結(jié)果表明,timeSVD++LR算法的推薦準(zhǔn)確性較RSVD、SVD++、timeSVD++算法有顯著提高且推薦結(jié)果較為穩(wěn)定,同時(shí)還能較好地改善評(píng)分矩陣稀疏和擴(kuò)展性弱等問(wèn)題。下一步將在本文算法的基礎(chǔ)上研究其他分類算法對(duì)推薦系統(tǒng)的影響。