基于上下文與馬爾科夫矩陣分解的流式推薦算法

紀(jì)淑娟,申彥博,王 振

(山東科技大學(xué) 計算機(jī)科學(xué)與工程學(xué)院，山東 青島 266590)

近年來，用戶所處上下文環(huán)境信息更加容易獲得，基于上下文的推薦算法逐漸成為備受關(guān)注的研究課題。Lombardi等通過對上下文信息降維，對上下文信息進(jìn)行預(yù)處理，使得預(yù)處理后的上下文信息可以運用在任意一個傳統(tǒng)的推薦算法上[1]。Baltrunas等則是通過項目分解的方式，對上下文信息進(jìn)行預(yù)處理，同樣地，預(yù)處理后的上下文信息可以運用在任意一個傳統(tǒng)的推薦算法上[2]。上述兩個算法都是通過在傳統(tǒng)的推薦算法中融入預(yù)處理后的上下文信息，從而獲得滿足用戶偏好并契合上下文要求的推薦列表，但這類方法普遍存在時間成本高且推薦準(zhǔn)確率低的問題。Karatzoglou等在協(xié)同過濾模型的基礎(chǔ)上，提出了一種基于張量分解的上下文推薦算法，該算法通過多維度上下文信息和正則化來構(gòu)建目標(biāo)函數(shù)，并且采用迭代學(xué)習(xí)的措施得到最終結(jié)果[3]。Oku等引入一種上下文信息支持向量機(jī)的思想，該算法考慮多維空間中的支持向量，并找到分離超平面[4]。Kim等提出了一種并行張量分解算法，加速大型數(shù)據(jù)集的張量分解以支持上下文推薦[5]。Wu等利用回歸樹進(jìn)行上下文特征選擇，解決了上下文特性選擇問題[6]。

自1998年Henzinger等首次提出數(shù)據(jù)流式處理方法以來[7]，數(shù)據(jù)流式處理逐漸成為熱門研究領(lǐng)域，而推薦系統(tǒng)中的推薦算法是其中最熱門的研究對象[8-9]。大量處理流式數(shù)據(jù)的算法被提出[10-11]，用以提高推薦系統(tǒng)的推薦性能。

為了使推薦系統(tǒng)具備處理流式數(shù)據(jù)的能力，一些推薦系統(tǒng)采用在線學(xué)習(xí)的方式，克服了推薦系統(tǒng)中算法模型必須實時更新的難題。其中，文獻(xiàn)[12-14]在基于內(nèi)存的推薦算法基礎(chǔ)上，在推薦算法中融合解決增量更新的措施，由于此類增量更新方法主要采用相似度計算進(jìn)行更新，其計算耗時與數(shù)量成正比，無法克服流式數(shù)據(jù)環(huán)境下無法實時更新的問題。

在動態(tài)矩陣分解算法中， Zhang等提出了基于矩陣過程的馬爾科夫分解(Markovian factorization of matrix process, MFMP)的電影推薦算法，該算法將矩陣分解技術(shù)與馬爾科夫相關(guān)知識相結(jié)合[15]。一方面， MFMP算法能夠捕獲數(shù)據(jù)集中的時間動態(tài)；另一方面，算法將輸入數(shù)據(jù)轉(zhuǎn)換為流式數(shù)據(jù)，能夠更好地捕獲時間動態(tài)下用戶的興趣愛好變化，從而在不同時間為用戶進(jìn)行相應(yīng)推薦。

在真實推薦系統(tǒng)中，用戶對項目進(jìn)行評分時所處的上下文環(huán)境也會對用戶的偏好產(chǎn)生影響，而且隨著時間變更的不僅是用戶和項目的隱特征向量，用戶所處的上下文環(huán)境也會改變。為了表現(xiàn)出上下文環(huán)境對用戶偏好的影響，本文在iMFMP(i Markovian factorization of matrix processes)算法[16]的基礎(chǔ)上，在流式推薦算法中考慮上下文因素，將矩陣分解技術(shù)、馬爾科夫過程以及動態(tài)變化的上下文環(huán)境融合在一起，提出了一種基于上下文的流式推薦算法。

1 相關(guān)理論

定義1信息熵表示信息隨機(jī)變量的混亂程度。隨機(jī)變量越混亂，信息熵越大。假設(shè)X是一個有限的離散隨機(jī)變量，其概率分布為

P(X={xi})={p(xi)},i=1,2,…,n。

那么隨機(jī)變量X的信息熵為

(1)

式中n為隨機(jī)變量的總個數(shù)。

定義2條件熵表示在一定條件下隨機(jī)變量分布的混亂程度。假設(shè)兩個事件用隨機(jī)變量X與Y表示，X={x1,x2,…,xn},Y={y1,y2,…,ym}，則在隨機(jī)變量X發(fā)生的條件下，Y分布的混亂程度即條件熵為

(2)

定義3信息增益是一種權(quán)衡樣本特征重要性的方法。假設(shè)某個狀態(tài)下系統(tǒng)的信息熵為H(Y)，特征X給定條件下系統(tǒng)的條件熵為H(Y|X)，特征X對系統(tǒng)的信息增益為

G(Y|X)=H(Y)-H(Y|X)。

(3)

2 基于上下文的馬爾科夫矩陣分解方法

在真實的推薦系統(tǒng)中，用戶評分時所處的上下文環(huán)境、上下文類型、上下文變化以及時刻變化都會對用戶產(chǎn)生影響。根據(jù)文獻(xiàn)[17]對上下文信息的建模，上下文環(huán)境會影響用戶對項目的偏好。在iMFMP算法[16]的基礎(chǔ)上，本文將矩陣分解技術(shù)、馬爾科夫矩陣分解相關(guān)知識以及動態(tài)變化的上下文環(huán)境融合在一起，提出了一種基于上下文的流式推薦算法(streaming recommendation algorithm based on context, C-SRA)。

2.1 基于信息增益的上下文信息與評分相關(guān)性分析方法

為了引出C-SRA算法，首先介紹一種基于信息增益的上下文信息與評分相關(guān)性分析方法。在推薦系統(tǒng)中，用戶在對項目進(jìn)行評分時所處的上下文環(huán)境往往是嘈雜的。為了從嘈雜的上下文環(huán)境中選取有價值的上下文信息，下面給出基于信息增益的上下文信息與評分相關(guān)性分析方法的步驟。

第一步，首先對數(shù)據(jù)進(jìn)行統(tǒng)計與分析，統(tǒng)計不同評分下，上下文信息的分布情況。

第二步，根據(jù)公式(1)，計算數(shù)據(jù)集上相同評分上下文信息的信息熵。

第三步，根據(jù)公式(2)，計算相同評分上下文信息的條件熵。

第四步，根據(jù)公式(3)，計算該數(shù)據(jù)集所有上下文的信息增益值。

然后,根據(jù)信息增益值的大小去除無用的上下文信息，保留有價值的上下文信息，并將保留下來的上下文信息集合記作CA。

以上步驟通過計算各上下文信息增益，可以將數(shù)據(jù)集中無用的上下文信息剔除，從而得到與評分相關(guān)性大的上下文信息。其時間復(fù)雜度為O(r×c)，其中r是級別的數(shù)目，c是上下文信息的數(shù)目。

2.2 C-SRA算法

根據(jù)心理學(xué)上“積極情緒產(chǎn)生正面影響、消極情緒產(chǎn)生負(fù)面影響”以及Zheng等提出的兩個時刻評分的相關(guān)性計算方法[17]，本節(jié)將兩類上下文信息融入流式推薦算法之中，提出了基于上下文的流式推薦算法。

根據(jù)前面提出的基于信息增益的上下文信息與評分相關(guān)性分析方法，可以得到與評分相關(guān)性大的上下文信息集合。將心理學(xué)上“可以受人的主觀意識影響的上下文信息”如人的情緒、心情等，記作主觀上下文信息；將“客觀存在于真實世界的上下文信息”如時間、地點等，記作客觀上下文信息。下面將詳細(xì)介紹如何將上下文信息有效地與流式推薦系統(tǒng)相結(jié)合，進(jìn)一步提高推薦性能，算法模型如圖1所示。

圖1 C-SRA算法模型圖

對于主觀上下文信息，本文根據(jù)心理學(xué)上“積極的情緒會給用戶帶來正面的影響、消極的情緒會給用戶帶來負(fù)面的影響”這一認(rèn)知，如果用戶i在t時刻較(t-1)時刻情緒存在積極變化，則用戶i對任意一個項目的評分在t時刻較(t-1)時刻會產(chǎn)生正相關(guān)變化；相反，如果用戶i在t時刻較(t-1)時刻情緒存在消極變化，則用戶i對任意一個項目的評分在t時刻較(t-1)時刻會產(chǎn)生負(fù)相關(guān)變化。本文通過計算情緒變化因子(pE)來判斷情緒的積極變化(pE>0)和消極變化(pE<0)。

(4)

本文采用線性回歸算法計算上述主觀上下文信息對情緒變化因子的影響，并利用批量梯度下降(batch gradient decent, BGD)算法對權(quán)重系數(shù)w進(jìn)行迭代訓(xùn)練。

情緒變化因子pE的損失函數(shù)如(5)式所示,然后利用(6)式對權(quán)重系數(shù)w進(jìn)行批量梯度訓(xùn)練。

(5)

?

(6)

對于客觀上下文信息，通過建模兩個時刻上下文信息的相關(guān)性，可以計算兩個時刻用戶對項目偏好的相似性[17]。通過計算關(guān)聯(lián)系數(shù)的方法，將客觀上下文信息融入本文所提算法模型當(dāng)中。

(7)

1)在時間t=0時，對于歷史上第一個用戶和項目的更新規(guī)則如下：

(8)

2)對于在(t-τ)時刻存在當(dāng)前t時刻依然存在的用戶和項目的更新規(guī)則如式(9)所示。

3)對于在t時刻新產(chǎn)生用戶的更新規(guī)則如式(10)所示。

4)t時刻新產(chǎn)生項目的更新規(guī)則如式(11)所示。

5)最終的評分預(yù)測公式如式(12)所示。

(9)

(10)

(11)

(12)

(13)

綜合以上內(nèi)容得到的C-SRA算法如下。

算法1C-SRA算法

輸入：t時刻用戶-項目評分矩陣Rt，正則化參數(shù)λ，特征矩陣訓(xùn)練學(xué)習(xí)率η，終止時間T，上下文信息集合CA，項目相似度閾值ρ，權(quán)重系數(shù)w,訓(xùn)練學(xué)習(xí)率δ。

用隨機(jī)值初始化Ui和Vj

fort=0,t<=T,t+=τ

for (i,j)∈Rt

ift=0

else ift≤T

if用戶i已經(jīng)存在

最后，科學(xué)合理地安排英語閱讀時間。要根據(jù)學(xué)生的平時英語閱讀習(xí)慣，來有針對性地安排課外閱讀的時間，并對其課外閱讀學(xué)習(xí)進(jìn)行指導(dǎo)，鼓勵學(xué)生養(yǎng)成收集英語閱讀材料的好習(xí)慣，提高學(xué)生英語閱讀的自覺性，并給予學(xué)生足夠的時間進(jìn)行集體閱讀。相比較而言可以適當(dāng)?shù)販p少英語其他方面的作業(yè)布置時間。

if項目j已經(jīng)存在

else if用戶i是新用戶

else if項目j是新項目

end if

end for

end for

經(jīng)過分析，本算法時間復(fù)雜度為O(T×N×M)。

3 實驗及結(jié)果分析

為了驗證本文提出的基于上下文的流式推薦算法(C-SRA算法)的有效性，將C-SRA算法在LDOS-CoMoDa數(shù)據(jù)集上與其他現(xiàn)存算法進(jìn)行對比實驗。下面將對實驗數(shù)據(jù)集、評價指標(biāo)以及實驗結(jié)果進(jìn)行詳細(xì)介紹。

3.1 數(shù)據(jù)集

為了充分論證C-SRA算法的有效性，本節(jié)實驗選取LDOS-CoMoDa公開數(shù)據(jù)集進(jìn)行實驗。對數(shù)據(jù)集的介紹詳見表1～2。

表1詳細(xì)說明了LDOS-CoMoDa數(shù)據(jù)集的評分?jǐn)?shù)、評分形式、用戶數(shù)、物品數(shù)、物品類型以及上下文信息個數(shù)和物品特征數(shù)。表2是對LDOS-CoMoDa數(shù)據(jù)集中上下文的詳細(xì)介紹。

表1 LDOS-CoMoDa數(shù)據(jù)集

表2 LDOS-CoMoDa數(shù)據(jù)集上下文

3.2 評價指標(biāo)

為驗證本文算法的有效性，選用均方根誤差(root mean squared error, RMSE)、精確率(precision)以及召回率(recall)作為實驗的評價指標(biāo)，其中均方根誤差用來評價C-SRA算法在評分預(yù)測方面的性能，精確率和召回率用來評價C-SRA算法在推薦方面的性能。均方根誤差、精確率以及召回率的具體計算方法如下所示。

均方根誤差(RMSE,式中簡記為ERMS)用來衡量預(yù)測值與真實值之間的偏差，即

(14)

精確率表示用戶看過的電影出現(xiàn)在TOP-N推薦列表中的數(shù)量占推薦列表長度的百分比，即

(15)

式中:LU表示給用戶U的推薦列表集合；BU表示用戶U在測試集評分過的項目集合。

召回率表示用戶看過的電影出現(xiàn)在TOP-N推薦列表中的數(shù)量占用戶所有看過電影數(shù)量的百分比,即

(16)

式中:LU表示給用戶U的推薦列表集合；BU表示用戶U在測試集評分過的項目集合。

3.3 數(shù)據(jù)預(yù)處理與分析

在對本文算法進(jìn)行實驗之前，首先根據(jù)基于信息增益的上下文與評分相關(guān)性分析方法對LDOS-CoMoDa數(shù)據(jù)集進(jìn)行數(shù)據(jù)預(yù)處理與分析，得到LDOS-CoMoDa數(shù)據(jù)集上不同評分下各個上下文信息的統(tǒng)計結(jié)果。然后，計算LDOS-CoMoDa數(shù)據(jù)集上各上下文的信息熵與信息增益。保留信息增值大于0.002的上下文信息，然后將上下文信息分為主觀上下文與客觀上下文兩類，具體的分類結(jié)果如表3所示。

表3 上下文分類結(jié)果

通過表3可以發(fā)現(xiàn)Mood、EndEmo以及DominantEmo這3類上下文的信息增益值要明顯大于其余7類上下文。將上述3類上下文統(tǒng)稱為主觀上下文，將剩余7類上下文統(tǒng)稱為客觀上下文。

本文假設(shè)用戶的情緒波動在一段時間內(nèi)是穩(wěn)定的，由于LDOS-CoMoDa數(shù)據(jù)集整體時間跨度較小，所以不再對LDOS-CoMoDa數(shù)據(jù)集進(jìn)行劃分。在得到表3中3類主觀上下文的基礎(chǔ)上，采用線性回歸梯度下降的方法在LDOS-CoMoDa數(shù)據(jù)集上全局靜態(tài)計算每一個用戶主觀上下文的權(quán)重系數(shù)。權(quán)重系數(shù)訓(xùn)練的學(xué)習(xí)率取值為0.02，迭代次數(shù)為50 000次，然后以EndEmo權(quán)重系數(shù)為x坐標(biāo)軸、DominantEmo權(quán)重系數(shù)為y坐標(biāo)軸、Mood權(quán)重系數(shù)作為z坐標(biāo)軸，根據(jù)最終訓(xùn)練結(jié)果構(gòu)建三維坐標(biāo)圖，其結(jié)果如圖2所示，其中每一個用戶用一個☆表示。

圖2 權(quán)重訓(xùn)練結(jié)果

由圖2可以看出，LDOS-CoMoDa數(shù)據(jù)集上大多數(shù)用戶的3個權(quán)重系數(shù)分布在0.25～0.5范圍內(nèi)。由此可知，對于大部分用戶，3類主觀上下文對用戶評分的影響相差不大，并且大多數(shù)用戶的情緒在整個時間線上是穩(wěn)定的，這與本文關(guān)于用戶情緒波動在一段時間內(nèi)是穩(wěn)定的這一假設(shè)一致。

3.4 實驗設(shè)置

為充分驗證C-SRA算法的有效性，將C-SRA算法在LDOS-CoMoDa數(shù)據(jù)集上進(jìn)行2組對比實驗。

第一組實驗以RMSE作為評價指標(biāo)，在LDOS-CoMoDa數(shù)據(jù)集上將C- SRA算法與經(jīng)典的矩陣分解算法PMF、流式矩陣分解推薦算法MFMP、iMFMP和上下文推薦算法BiasTF-RT算法作比較，旨在驗證C-SRA算法融合上下文的方法是否能夠有效提高算法在評分預(yù)測方面的性能。

第二組實驗在第一組實驗的基礎(chǔ)上，以精確率、召回率作為評價指標(biāo)，在LDOS-CoMoDa數(shù)據(jù)集上將C-SRA算法與經(jīng)典的矩陣分解算法PMF、流式矩陣分解推薦算法MFMP、iMFMP和上下文推薦算法BiasTF-RT算法作比較，旨在驗證本文提出的C-SRA算法在LDOS-CoMoDa數(shù)據(jù)集上的推薦性能。同樣地，兩組實驗均采用80%數(shù)據(jù)集作為訓(xùn)練集，20%數(shù)據(jù)集作為測試集，且學(xué)習(xí)率取值為0.02，迭代次數(shù)均為50 000次。

3.5 實驗結(jié)果與分析

第一組實驗對比結(jié)果如表4所示。

表4 LDOS-CoMoDa各算法RMSE對比

通過表4可以看出，C-SRA算法在LDOS-CoMoDa數(shù)據(jù)集上的RMSE值均小于其他算法，iMFMP算法次之。這一實驗結(jié)果驗證了C-SRA算法中數(shù)據(jù)預(yù)處理與參數(shù)訓(xùn)練的合理性，證實了算法融合上下文方法的有效性，證明了流式矩陣分解算法中融入上下文信息能夠有效地提升推薦系統(tǒng)在評分預(yù)測方面的性能。并且從整體結(jié)果來看，在流式矩陣分解的基礎(chǔ)上加入上下文的方法可以提高推薦系統(tǒng)的性能。

第二組實驗結(jié)果如圖3、表5所示。

圖3 LDOS-CoMoDa各算法精確率對比

表5 LDOS-CoMoDa各算法召回率對比

通過圖3可知，本文提出的C-SRA算法在精確率上的整體性能均要優(yōu)于PMF[19]、MFMP[15]以及BiasTF-RT[6]算法，并且C-SRA算法與iMFMP算法精確率均在推薦列表長度為9時達(dá)到最大值，證明了iMFMP算法處理新產(chǎn)生用戶、項目的方法的有效性，以及C-SRA算法中對數(shù)據(jù)預(yù)處理與參數(shù)訓(xùn)練的合理性，證實了C-SRA算法融合上下文方法的有效性，流式矩陣分解算法中融入上下文信息能夠有效地提升推薦系統(tǒng)的推薦精確率。PMF算法以及MFMP算法同樣在推薦列表長度為9時精確率達(dá)到最大值，BiasTF-RT算法則是在推薦列表長度為7時精確率達(dá)到最大值。從整體走勢來看，隨著推薦列表長度的增加，算法推薦精確率整體呈現(xiàn)先上升后下降的趨勢。

通過表5可以看出，本文提出的C-SRA算法在不同推薦列表長度上的召回率均要優(yōu)于PMF、MFMP、iMFMP以及BiasTF-RT算法，并且iMFMP算法的整體召回率也均優(yōu)于其余算法，再次證明了iMFMP算法處理新產(chǎn)生用戶、項目的方法的有效性，以及C-SRA算法中對數(shù)據(jù)預(yù)處理與參數(shù)訓(xùn)練的合理性，證實了C-SRA算法融合上下文方法的有效性，證明了流式矩陣分解算法中融入上下文信息能夠有效地提升推薦系統(tǒng)的推薦召回率。從整體來看，召回率與推薦列表長度正相關(guān)。

對比實驗證明，在流式推薦算法的基礎(chǔ)上考慮上下文信息可以提升算法的評分預(yù)測性能和推薦性能，從而證明了本文提出的基于信息增益的上下文與評分相關(guān)性分析方法的有效性。

4 總結(jié)與展望

本文提出了基于上下文的流式推薦算法，并提出了一種基于信息增益的上下文信息與評分相關(guān)性分析方法，詳細(xì)介紹了如何將分類的上下文有效融合到流式推薦算法之中。通過C-SRA算法在LDOS-CoMoDa數(shù)據(jù)集上的兩組實驗，驗證了本文提出的C-SRA算法無論是評分預(yù)測性能還是推薦性能均要優(yōu)于其他算法。

然而，文中給出的算法模型并沒有考慮潛在特征的突然變化，當(dāng)數(shù)據(jù)集中存在明顯的此類現(xiàn)象時，應(yīng)考慮比依賴高斯分布更一般的模型。例如，可以采用類似于貝葉斯的方法對現(xiàn)有模型進(jìn)行高參數(shù)擴(kuò)充。這種模型下的推理通常在所有模型參數(shù)設(shè)置上表現(xiàn)出平均效果，并且有利于避免過度設(shè)置。

在算法模型中，本文假設(shè)用戶的情緒波動是穩(wěn)定的，因此對主觀上下文的權(quán)重訓(xùn)練是基于全局?jǐn)?shù)據(jù)進(jìn)行的靜態(tài)訓(xùn)練。如何對主觀上下文的權(quán)重進(jìn)行實時在線訓(xùn)練將是接下來要解決的問題。并且，面對未來規(guī)模更加龐大的數(shù)據(jù)量，用戶對推薦系統(tǒng)的實時性要求將更加嚴(yán)格，如何在準(zhǔn)確推薦的同時降低算法的時間復(fù)雜度將成為下一步研究的重點。