劉 云,張 軼,鄭文鳳

(昆明理工大學(xué) 信息工程與自動化學(xué)院，云南 昆明 650500)

基于用戶動態(tài)偏好的推薦算法,推薦系統(tǒng)(recommender system,RS)利用有關(guān)用戶、項目或用戶項目交互歷史數(shù)據(jù)中記錄的經(jīng)驗知識和信息向目標(biāo)用戶生成建議。由于用戶興趣和項目偏好是隨時間動態(tài)變化的,隨著新用戶和項目數(shù)據(jù)的不斷生成,導(dǎo)致用戶和推薦項目之間呈現(xiàn)更復(fù)雜的非線性關(guān)系。最新的研究表明,在推薦算法中引入不同的特征提取機制，構(gòu)建有效的模型,可以分析用戶興趣和項目偏好特征之間的關(guān)聯(lián)關(guān)系,學(xué)習(xí)用戶偏好的動態(tài)變化給出準(zhǔn)確的個性化推薦結(jié)果[1-2]。

為了從動態(tài)用戶的偏好變化中捕獲用戶興趣和項目偏好特征的概念漂移，構(gòu)建個性化推薦系統(tǒng),本文提出特征漂移約束(feature drift constraint，F(xiàn)DC)算法。首先，基于輸入樣本構(gòu)建評級矩陣的時間序列,分解評級矩陣為用戶特征矩陣和項目特征矩陣[7];其次,用戶興趣隨著時間推移變化,通過計算隱藏特征向量的標(biāo)準(zhǔn)偏差，與上一時間點相比來表征概念漂移;再根據(jù)概念漂移的大小動態(tài)更新用戶興趣和項目偏好特征向量,從而更新推薦模型;最后，計算用戶和項目特征向量的內(nèi)積，得到預(yù)測的項目評級,實現(xiàn)項目推薦[8-9]。仿真結(jié)果表明,相比于基線算法，F(xiàn)DC算法的推薦準(zhǔn)確性和魯棒性有所提升。

1 算法模型

1.1 推薦系統(tǒng)模型

推薦系統(tǒng)基于用戶與系統(tǒng)進行交互期間收集的行為和反饋信息,利用用戶動態(tài)偏好的推薦算法學(xué)習(xí)目標(biāo)用戶的偏好變化,向其提供個性化的項目建議，解決信息過載問題[10]。

推薦方法通常分為4類:基于內(nèi)容、協(xié)同過濾、基于知識和混合推薦方法。其中，協(xié)同過濾方法基于“偏好和興趣相似的用戶在未來會盡可能更多地呈現(xiàn)出相關(guān)性”這種假設(shè)而提出,從而依據(jù)用戶的歷史偏好和興趣為用戶生成推薦。本文采用協(xié)同過濾中的矩陣分解推薦方法[11],標(biāo)準(zhǔn)模型如圖1所示。

圖1 推薦系統(tǒng)模型Fig.1 Recommender system model

如圖1所示,常用的推薦模型由3個階段構(gòu)成,輸入數(shù)據(jù)階段包含用戶集和項目集和與其相關(guān)信息的輸入。預(yù)測階段通過建模提取輸入數(shù)據(jù)的特征,采用不同的方法計算效用函數(shù)F:Users×Items→F0，衡量推薦結(jié)果針對一個用戶u∈Users和一個項目i∈Items的匹配程度[9]，F(xiàn)0表示由用戶特征和項目特征計算得到的推薦評分。推薦階段是預(yù)測階段的擴展,選取最合適的項目支持用戶的決策，并向目標(biāo)用戶推薦具有最高預(yù)測評分的項目集。

1.2 矩陣分解(MF)

矩陣分解方法通過隱藏特征來表示單個用戶和項目,這些隱藏特征從歷史評級矩陣R中表征用戶和項目的交互作用[12]。其基本方法是將評級矩陣R分解為用戶特征矩陣P和項目特征矩陣Q。P和Q分別是m×k和n×k的矩陣，且秩為k，k≤min{m,n}。Pi代表P中的第i列元素，稱為用戶興趣特征向量，Qj代表Q中的第j列元素，稱為項目偏好特征向量。

根據(jù)上述定義可以用每對用戶和項目特征向量的點積近似計算每一個評級，

(1)

矩陣分解方法考慮式(1)中P和Q的優(yōu)化問題如下，

(2)

優(yōu)化P和Q可以通過SGD算法進行學(xué)習(xí),該算法遍歷訓(xùn)練集中的所有評分。對每個訓(xùn)練樣本Rij,計算相應(yīng)的預(yù)測誤差為

(3)

接著對每個循環(huán)進行評分，特征向量Pi和Qj采用與梯度相反的方向更新如下，

Pi←Pi+α(eijQj-λPi)，

(4)

Qj←Qj+α(eijPi-λQj)。

(5)

其中，α和λ分別是學(xué)習(xí)參數(shù)和調(diào)節(jié)器參數(shù)。在實際推薦應(yīng)用中,數(shù)據(jù)分布隨時間的變化降低了學(xué)習(xí)算法對新數(shù)據(jù)或?qū)崟r數(shù)據(jù)的泛化能力。

1.3 概念漂移檢測

為了學(xué)習(xí)隨時間變化的用戶興趣和項目偏好,提取目標(biāo)用戶的個性化喜好特征，采用概念漂移檢測方法學(xué)習(xí)用戶偏好行為變化的特征漂移,更新提高推薦系統(tǒng)的有效性。Hellinger距離測度通過計算新分布和基線分布之間Hellinger距離變化的幅度判斷是否發(fā)生特征漂移，每次檢測到漂移時都會更新模型。Hellinger距離是分布散度的度量[13],使推薦算法能夠檢測兩個后續(xù)時間戳在數(shù)據(jù)分布之間的變化。

δH(t)=

(6)

其中：d是數(shù)據(jù)的維度；Li,k和Mi,k分別是特征k對應(yīng)直方圖L和M中堆棧i的頻率計數(shù)。將當(dāng)前距離與先前距離之間的差異與閾值進行比較,以確定變化是否足夠大而產(chǎn)生概念漂移。

針對用戶喜好特征的動態(tài)變化,基于時間的協(xié)同過濾方法結(jié)合概念漂移檢測在矩陣分解推薦中解釋隱藏特征的概念漂移,提出特征漂移約束算法優(yōu)化推薦系統(tǒng)模型。

2 特征漂移約束(FDC)算法

基于時間矩陣分解的基本模型,針對用戶興趣和項目偏好特征向量的概念漂移建模，改進動態(tài)推薦系統(tǒng)。通過跟蹤用戶興趣或項目偏好特征漂移表示推薦系統(tǒng)中用戶興趣和項目吸引力的變化,模型如圖2所示。

圖2 特征漂移約束算法模型Fig.2 Feature drift constraint algorithm model

算法主要步驟如下:

Step1利用訓(xùn)練集的評級反饋構(gòu)造m×n階評級矩陣的時間序列R(t),t=1,2,…,T-1;

Step2基于評級矩陣的時間序列R(t)學(xué)習(xí)用戶興趣特征向量的時間序列Pi(t)，以及項目偏好特征向量Qj(t);

Step3利用用戶興趣特征向量的時間序列Pi(t)和項目偏好特征向量的時間序列Qj(t)計算每個用戶i以及每個項目j中的概念漂移;

Step4基于步驟3中獲得的特征漂移計算加權(quán)的用戶興趣和項目偏好向量,更新模型;

Step5使用T時預(yù)測的用戶興趣特征矩陣P(T)和項目偏好特征矩陣Q(T)的乘積預(yù)測評分矩陣的缺失值。

推薦模型的目標(biāo)是研究每個用戶潛在向量中可能的漂移。概念漂移表示用戶對k個項目偏好特征向量的變化,代表了單個項目與k個特征的關(guān)聯(lián)關(guān)系?？紤]到用戶-項目交互的關(guān)聯(lián)時間信息,將用戶評價矩陣表示為4元組(user,item,rating,time)。

當(dāng)評價矩陣的時間標(biāo)簽被刪除時,評級用m×n大小的矩陣表示,元素Rij表示真實評價下用戶i對項目j的評價,相反，如果用戶沒有進行評價，則Rij被稱為缺失評級。在實際應(yīng)用中,矩陣R是一個存在許多缺失值的稀疏矩陣。

2.1 FDC算法實現(xiàn)

通過對原始評級矩陣進行排序，構(gòu)建評級矩陣時間序列R(t)，使項目時間標(biāo)簽在相同的尺度上平均劃分評級矩陣。為了避免生成更稀疏的數(shù)據(jù),采用基于分區(qū)的方法保證了數(shù)據(jù)的生成。又選取滑動窗口的方法,將多個連續(xù)切片中的評級組合成單個時間步長。

用戶興趣的特征漂移隨著時間變化,當(dāng)在t時收到一組新的評級時,得到更多的關(guān)于扭曲用戶興趣預(yù)測模型的信息，因此,必須調(diào)整參考模型。為了分析各個用戶的用戶興趣特征向量的時間序列,在t=1時，對評級矩陣進行分解,確定用戶特征矩陣和項目特征矩陣與時間步長有關(guān)[6]。對于每個時間段的用戶項目交互，基于FDC算法定義如下，

(7)

其中：Pi(t)和Qj(t)分別為原始用戶Pi和項目Qj的特征向量。使用該時間步長上觀察的評級分別學(xué)習(xí)Pi(t)和Qj(t)。收到新的評級后,迭代訓(xùn)練模型獲得更新的用戶興趣和項目偏好特征向量Pi(t+1)和Qj(t+1),但不是永久更新。為了解決優(yōu)化問題,采用隨機梯度下降(SGD)方法[14]獲得優(yōu)化的學(xué)習(xí)參數(shù)。

(8)

Pi(t)←Pi(t)+α(eij(t)Qj(t)-λPi(t))，

(9)

Qj(t)←Qj(t)+α(eij(t)Pi(t)-λQj(t))。

(10)

每一次新的評級,都會獲得有關(guān)用戶偏好的新信息,從而基于新的評級更新用戶和項目相關(guān)的特征向量。此方法保持了舊偏好和新偏好之間的平衡,并確保特征向量中的概念漂移得到及時處理。

在真實的推薦系統(tǒng)中,單個用戶會在不同的時間點發(fā)生興趣漂移。學(xué)習(xí)關(guān)于這些動態(tài)變化的模型都會扭曲預(yù)測模型的精度,為了學(xué)習(xí)偏好的變化,衡量Pi(t+1)與前一時間點Pi(t)相比隱藏特征發(fā)生了多少變化,采用Hellinger距離度量計算相似性得分。Hellinger距離測度是一種基于特征的漂移檢測方法[13],適應(yīng)數(shù)據(jù)分布中逐漸變化和突然變化的概念漂移,表示為

h(Pi(t+1),Pi(t))=

(11)

漂移分數(shù)表征用戶興趣是否發(fā)生變化或項目內(nèi)容是否隨時間變化。漂移分數(shù)越低,發(fā)生概念漂移的可能性就越大。通過計算標(biāo)準(zhǔn)偏差SD(h(Pi(t+1,Pi(t))，研究與上一個時間點相比興趣特征發(fā)生了多少變化。在這種情況下,如果滿足以下不等式,則發(fā)生更新。

h(Pi(t+1),Pi(t))>αSD(h(Pi(t+1),

Pi(t)))。

(12)

其中：參數(shù)α控制遺忘舊偏好的敏感性,在每種情況下,α的選擇都是特定的,必須通過實驗確定。相同的方法也適用于計算項目偏好特征向量Qi(t+1)和Qi(t)的概念漂移。

分析了用戶興趣特征向量Pi和項目偏好特征向量Qj在兩個時間點之間的變化后,分別調(diào)整用戶和項目特征模型。如果新的評級與該用戶的興趣保持一致,則特征向量Pi(t)和Pi(t+1)之間的預(yù)期變化最小。如果在對新評級進行訓(xùn)練后影藏向量發(fā)生較大變化,則表明用戶興趣已經(jīng)發(fā)生了偏移。針對這種情況,通過乘以一個指數(shù)函數(shù)更新用戶興趣模型,該指數(shù)函數(shù)的值取決于用戶興趣的變化率,計算如下，

Pi(t+1)=α-SD(h(Pi(t+1),Pi(t)))Pi(t)，

(13)

Qj(t+1)=α-SD(h(Qj(t+1),Qj(t)))Qj(t)。

(14)

該指數(shù)函數(shù)控制懲罰項的程度,當(dāng)α>1時，該函數(shù)值域為[0,1]。針對高值漂移,指數(shù)函數(shù)產(chǎn)生較低的值,對歷史興趣的懲罰較高。

時間周期T-1內(nèi)的用戶和項目特征向量已經(jīng)獲得,對T時刻的偏好特征向量預(yù)測如下，

Pi(T)=α-SD(h(Pi(t+1),Pi(t)))Pi(T-1)，

(15)

Qj(T)=α-SD(h(Qj(t+1),Qj(t)))Qj(T-1)。

(16)

經(jīng)過時間T時特征向量P和Q的學(xué)習(xí),使用特征向量Pi(T)和Qj(T)的內(nèi)積預(yù)測推薦項目的未來預(yù)測，

(17)

2.2 FDC算法分析

迭代算法解決推薦問題的偽代碼如下，此過程迭代進行直到變量收斂為止。

算法1：特征漂移約束算法(FDC)

輸入：

1)用戶-項目評級矩陣R

初始化：

2)用戶興趣特征向量Pi(t)，項目偏好特征向量Qj(t)

3)隱藏特征數(shù)k，學(xué)習(xí)率α，調(diào)節(jié)器參數(shù)λ

4)whilePi(t)，Qj(t)不收斂do

迭代計算：

5)根據(jù)式(12)計算用戶興趣特征向量和項目偏好特征向量的概念漂移

6)更新特征矩陣

Pi(t)←Pi(t)+α(eij(t)Qj(t)-λPi(t))

Qj(t)←Qj(t)+α(eij(t)Pi(t)-λQj(t))

7)end while

8)for每個用戶udo

9)計算T時刻的特征向量預(yù)測

10)根據(jù)式(17)計算用戶對未來項目的預(yù)測評級。

11)end for

輸出：

13)使用預(yù)測評級為用戶提供項目評分。

在此方法的每個步驟中，所有變量均根據(jù)其相應(yīng)公式進行更新。為了證明推薦系統(tǒng)的有效性,通過將評級矩陣劃分為訓(xùn)練集和測試集來評估預(yù)測算法的性能。采用時間平均均方根誤差(time-averaged root mean square error,TRMSE)衡量所提出方法的性能,TRMSE是基于RMSE的評估時間推薦算法的基準(zhǔn)指標(biāo)[15],根據(jù)在某一特定時間點之前的評級計算如下，

(18)

3 仿真分析

3.1 數(shù)據(jù)集及仿真環(huán)境

與類似算法仿真一致,仿真分析采用Ciao和Epinions兩個真實數(shù)據(jù)集評估所提方法的性能[16]。這兩個數(shù)據(jù)集是基于帶有時間標(biāo)簽信息選擇,并廣泛用于協(xié)作過濾研究項目中,用于在推薦系統(tǒng)中跟蹤概念漂移的動態(tài)。數(shù)據(jù)集提供了有關(guān)用戶、項目、用戶偏好評級以及相關(guān)的時間標(biāo)簽信息,數(shù)據(jù)集的統(tǒng)計信息如表1所示。

表1 數(shù)據(jù)集信息Tab.1 Data set information

為了能夠正確檢測特征漂移,刪除在數(shù)據(jù)集中出現(xiàn)次數(shù)少于20次的用戶或項目,并將重點放在現(xiàn)有用戶和項目上,用于學(xué)習(xí)隱藏向量的變化。運行環(huán)境為Windows 10,2.6 GHz CPU,8GB內(nèi)存,Python 3.7。基于時間感知RMSE調(diào)整參數(shù),用隨機梯度下降算法對所有模型進行訓(xùn)練,至少50次迭代直到收斂。

3.2 時間平均均方根誤差分析

為了評估推薦算法預(yù)測結(jié)果的準(zhǔn)確性,對時間平均均方根誤差(TRMSE)進行分析，在Ciao和Epinions數(shù)據(jù)集中評估FDC算法與MF、TSVD++、TMF和MCFTT算法的推薦準(zhǔn)確性結(jié)果,仿真如圖3所示。

圖3顯示了5種算法算法在兩種數(shù)據(jù)集中的性能,5種算法的TRMSE值隨迭代次數(shù)的增加都逐漸減小,最終趨于平穩(wěn)點。但是,不同基準(zhǔn)算法的性能在數(shù)據(jù)集中有所不同,在兩種數(shù)據(jù)集中，F(xiàn)DC和TMF算法對比TSVD++、MF和MCFTT算法表現(xiàn)良好,這表明了相對非時間模型,時間模型因其較長的時間跨度以及對動態(tài)偏好的敏感性在推薦系統(tǒng)中存在優(yōu)勢。

另一方面,FDC算法在Ciao數(shù)據(jù)集中獲得了14%的性能改善,而在Epinions數(shù)據(jù)集中獲得了10%的性能改善,與基線算法相比,實現(xiàn)了最佳性能改進。結(jié)合Ciao和Epinions兩種數(shù)據(jù)集仿真分析,雖然FDC的初始推薦準(zhǔn)確性低于同類算法,但基于時間矩陣分解模型的FDC算法引入概念漂移檢測組件,跟蹤用戶動態(tài)偏好特征漂移,使偏好特征提取更接近用戶行為存在的穩(wěn)定結(jié)構(gòu)和不變特征,隨著模型學(xué)習(xí)訓(xùn)練均能獲得更低的TRMSE值,表現(xiàn)出更為優(yōu)異的推薦準(zhǔn)確性。

圖3 迭代訓(xùn)練對推薦準(zhǔn)確性影響分析Fig.3 Analysis of the influence of iterative training on recommendation accuracy

3.3 用戶興趣特征漂移檢測有效性分析

對Ciao數(shù)據(jù)集中的用戶63,仿真研究FDC算法相較基線算法對用戶興趣特征變化的概念漂移捕捉的有效性。一方面驗證用戶興趣特征向量隨時間發(fā)生特征漂移的變化,結(jié)果如表2所示。另一方面驗證FDC算法與對比算法提取的用戶興趣特征向量同原始用戶興趣特征向量的擬合情況,仿真結(jié)果如圖4所示。 仿真實驗中隱藏特征數(shù)k=40, 學(xué)習(xí)率α=0.003, 調(diào)節(jié)器參數(shù)λ=0.01。執(zhí)行50次SGD迭代捕獲每個時間段的特征向量,計算每個時間段的用戶興趣特征向量，參數(shù)設(shè)置為與基線相同。

表2記錄了前5個時間段用戶63的5個潛在興趣特征向量的變化情況,以及預(yù)測的下一時間段用戶63的興趣特征向量Pi(6)。對于用戶63,FDC預(yù)測的用戶興趣特征向量隨時間推移發(fā)生變化，綜合5個特征的變化情況，第4個時間段的用戶興趣特征向量同時間段1的初始用戶興趣特向量相比差異明顯，表明用戶在第4個時間步長后興趣偏好發(fā)生較大變化。這表明用戶傾向于以不同的方式改變自己的行為偏好,即使用戶在一段時間內(nèi)傾向于相同項目,也可能在未來的某個時間改變自己的興趣偏好,FDC算法能夠基于概念漂移檢測不斷更新用戶行為信息,跟蹤用戶興趣特征向量的動態(tài)變化。

表2 前5個特征下Ciao數(shù)據(jù)集中用戶63的興趣特征向量變化

Tab.2 User 63 interest characteristics for the first five features in the Ciao dataset

用戶興趣特征向量特征1特征2特征3特征4特征5Pi0.484 70.346 80.486 90.408 50.367 0Pi(1)0.507 80.446 80.576 90.488 50.467 0Pi(2)0.467 80.380 20.579 10.404 30.393 5Pi(3)0.483 50.393 40.445 50.381 30.423 6Pi(4)0.494 80.344 70.474 80.369 90.388 7Pi(5)0.434 40.378 50.569 30.389 50.370 3Pi(6)0.474 00.420 70.558 00.471 10.457 5

圖4 Ciao數(shù)據(jù)集中用戶63興趣特征向量的變化Fig.4 The changes in user interest characteristics for user 63 in Ciao dataset

從圖4可以觀察到, 相比MF和MCFTT算法, FDC算法預(yù)測的用戶隱藏向量與實時用戶隱藏向量具有更好的擬合效果, 表現(xiàn)出對概念漂移檢測的有效性。 綜合用戶興趣特征向量的兩種仿真結(jié)果, FDC算法在提取用戶興趣特征的基礎(chǔ)上， 檢測用戶興趣屬性變化的概念漂移, 基于測量的單個用戶的概念漂移更新用戶隱藏興趣特征向量, 能夠有效對抗用戶興趣漂移對推薦系統(tǒng)的影響。

3.4 項目偏好特征漂移檢測有效性分析

采用相同方法在Ciao數(shù)據(jù)集項目80情況下,項目隱藏偏好特征向量隨前5個隱藏特征的變化仿真如表3所示,另根據(jù)FDC算法預(yù)測的項目偏好特征向量變化情況仿真結(jié)果如圖4所示。

表3 前5個特征下Ciao數(shù)據(jù)集中項目80偏好特征向量變化

Tab.3 Item 80 preference characteristics for the first five features in the Ciao dataset

項目偏好特征向量特征1特征2特征3特征4特征5Qi0.523 50.703 40.725 50.711 30.523 6Qj(1)0.583 50.802 70.802 70.861 30.503 6Qj(2)0.574 80.717 40.728 40.786 90.498 7Qj(3)0.408 50.646 10.616 30.707 50.431 1Qj(4)0.402 30.617 80.730 50.723 90.485 6Qj(5)0.415 80.655 40.755 90.705 00.472 1Qj(6)0.574 80.797 40.808 40.866 90.508 7

圖5 Ciao數(shù)據(jù)集中項目80偏好特征向量的變化Fig.5 The changes in item preference characteristics for item 80 in the Ciao dataset

表3記錄了前5個時段項目80的5個潛在偏好特征向量的變化情況，以及預(yù)測的下一時間段項目80的偏好特征向量Qj(6)。從表3可以看出，F(xiàn)DC預(yù)測的項目80偏好特征向量隨時間推移發(fā)生變化。綜合5個特征的變化情況，時間段3的項目偏好特征向量同時間段1的初始項目偏好特征向量相比有顯著差異，表明在第3時間段后項目偏好發(fā)生較大改變。發(fā)生這種變化的原因是特定的因素改變了用戶對項目隱藏特征的偏好,FDC算法通過學(xué)習(xí)新項目的隱藏屬性特征來捕獲項目偏好變化的概念漂移,用于更新項目偏好特征的提取。

從圖4可以觀察到,相比基線算法,FDC算法預(yù)測的項目偏好特征向量與實時項目偏好特征向量具有更好的擬合效果。針對真實數(shù)據(jù)集中隨時間發(fā)生的項目偏好變化,FDC算法通過捕獲項目屬性變化反映出的概念漂移來跟蹤用戶針對項目偏好的改變,基于項目偏好的變化調(diào)整項目偏好模型，實現(xiàn)項目偏好特征的有效提取,提高了推薦系統(tǒng)的魯棒性。

4 結(jié)語

在時間矩陣分解推薦模型中加入概念漂移檢測方法，通過捕捉用戶興趣和項目偏好特征的變化情況可有效提升推薦性能。為此，本文提出特征漂移約束 (FDC)算法,首先,依據(jù)評級矩陣的時間序列，采用矩陣分解方法將評級矩陣分解為用戶特征矩陣和項目特征矩陣;然后，采用隨機梯度下降方法訓(xùn)練模型以獲得優(yōu)化的學(xué)習(xí)參數(shù),計算概念漂移的動態(tài)特征加權(quán)用于調(diào)整模型;最后,結(jié)合用戶興趣特征向量和項目偏好特征向量內(nèi)積，計算得到預(yù)測的項目評級,實現(xiàn)有效的推薦目標(biāo)。在下一步的工作中,面對更復(fù)雜的用戶喜好變化，需要研究實時特征漂移檢測方法來動態(tài)學(xué)習(xí)概念漂移。