喬永衛(wèi)，張宇翔，肖春景,3

(1.中國民航大學(xué) 工程技術(shù)訓(xùn)練中心，天津 300300； 2.中國民航大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，天津 300300；3.河北工業(yè)大學(xué) 電子信息工程學(xué)院，天津 300401)(*通信作者電子郵箱qiaoyongwei76@126.com)

0 引言

如何從混雜無序的信息中過濾出人們最關(guān)心的信息，成為“信息過載”背景下的重要任務(wù)。推薦系統(tǒng)通過挖掘用戶交互歷史分析用戶的偏好和潛在興趣，主動向用戶推薦項目或服務(wù)。協(xié)同過濾 (Collaborative Filtering, CF)[ 1-2 ]是目前最流行的推薦技術(shù)，但由于數(shù)據(jù)稀疏使得它不能挖掘用戶的真正的相似關(guān)系，推薦準(zhǔn)確度降低。為了改善基本CF方法，研究人員在推薦過程中考慮用戶興趣漂移的問題，以提高精度。最流行的基于會話的協(xié)同過濾(Session-based CF)方法將用戶的交互歷史劃分成不同階段，利用隱含狄利克雷分布(Latent Dirichlet Allocation，LDA)將其偏好表示成這些階段的時序序列表示[3-6]。這些方法在一定程度上提高了推薦精度，但不僅沒緩解數(shù)據(jù)稀疏性問題，反而由于將交互劃分成不同階段，導(dǎo)致某些階段內(nèi)很少甚至沒有交互行為而加劇了數(shù)據(jù)稀疏。

目前,為了緩解數(shù)據(jù)稀疏主要有三類方法：1)通過設(shè)計更好的相似性度量來識別更相似的近鄰,或利用更合理的集成策略去集成近鄰用戶項目評分[7-9]。2)通過機器學(xué)習(xí)方法，如貝葉斯網(wǎng)絡(luò)[10]、奇異值分解[11]、潛在因素模型[12]、矩陣分解[13-14]等，訓(xùn)練一個預(yù)定義的模型，并用它來預(yù)測新項目的評分。3)近幾年出現(xiàn)的數(shù)據(jù)填充方法[15]，這些方法從評分矩陣中選擇一些缺失值并在評分預(yù)測前填充這些缺失值[16-19]。Park等[16]利用綜合特征工程進行了數(shù)據(jù)填充；Xue等[18]用機器學(xué)習(xí)方法平滑評分矩陣中所有的空值來提高推薦精度；Ma等[19]通過設(shè)置一個填充閾值來決定是否為用戶和項目填充缺失值，如果閾值設(shè)置合適會得到較好的填充效果；文獻[20]能自動識別帶缺失值的項目關(guān)鍵集合，并利用基于用戶的協(xié)同過濾進行自動填充；袁衛(wèi)華等[21]利用非負(fù)矩陣分解重構(gòu)矩陣來填充原始矩陣的缺失值，通過塊模型劃分用戶-興趣子集和物品-特征子集，最終完成TOP-N推薦；文獻[22]中通過構(gòu)建近鄰的K層網(wǎng)絡(luò)填充缺失值來提高預(yù)測精度；文獻[23]中通過經(jīng)典乘法更新規(guī)則填充評分以提高矩陣分解的性能；文獻[24]中研究了如何降低在矩陣分解“軟填充”中時間復(fù)雜度的問題。這些模型在一定程度上緩解了數(shù)據(jù)稀疏，但它們只考慮了評分信息，沒有考慮捕獲用戶動態(tài)偏好的時間上下文。成韻姿等[25]提出了基于云填充和混合相似性的協(xié)同過濾推薦算法，它利用云模型填充評分矩陣，將用戶間的時序影響融合到Jaccard系數(shù)相似性中；Hong等[8]提出了新的時間感知相似性挖掘間接近鄰；李燦等[26]利用非精確增廣拉格朗日乘子法對評分時間矩陣進行填充，并利用填充可信度和指數(shù)遺忘函數(shù)對填充評分進行加權(quán)修正。這些模型在填充或推薦過程中考慮了時序上下文，但它們只是將時間信息作為傳統(tǒng)相似度的權(quán)值，沒有考慮用戶興趣的漂移。文獻[5]中提出了一個基于交叉領(lǐng)域CF的評分矩陣生成模型來填補現(xiàn)有和新用戶的缺失評分，但相關(guān)領(lǐng)域共享知識往往隱蔽且不易獲得。

為了緩解數(shù)據(jù)稀疏，本文提出基于時序相似性的矩陣分解數(shù)據(jù)填充(Data Imputation by Matrix Factorization, DIMF)方法。首先，提出基于會話的時序相似性來識別用戶的近鄰，它不僅考慮評分模式，而且還考慮了時間信息，以捕獲用戶間的實際相似關(guān)系；其次，自動抽取待填充的關(guān)鍵項目集合評分子矩陣并通過矩陣分解自動重構(gòu)缺失值，更好地利用了影響用戶和項目的潛在因素；接著，利用隱含狄利克雷分布(Latent Dirichlet Allocation， LDA)和時間懲罰權(quán)值建立用戶動態(tài)模型，并完成基于用戶的協(xié)同過濾(User-based Collaborative Filtering, UCF)推薦。實驗結(jié)果表明，與其他數(shù)據(jù)填充方法相比，本文方法降低了平均絕對誤差(Mean Absolute Error， MAE)，取得了更好性能。

1 問題定義及整體流程

1.1 問題定義

1.2 算法整體框架

基于矩陣分解的數(shù)據(jù)填充整體上分為三步：先對用戶交互歷史進行劃分并計算用戶間的基于會話的時序相似性；接著抽取用戶關(guān)鍵項目集合并利用矩陣分解進行填充；最后利用LDA建立用戶興趣模型并完成基于用戶的協(xié)同過濾推薦。具體的過程如算法1所示。

算法1 基于矩陣分解的數(shù)據(jù)填充方法。

輸入 評分矩陣，時間窗大小，相似性參數(shù)，待填充評分子矩陣用戶和項目數(shù)，近鄰數(shù)；

輸出 每個用戶填充矩陣及評分預(yù)測矩陣。

1)

For 每個用戶

2)

3)

End for

4)

For 每個用戶

5)

計算用戶間相似性，得到待填充關(guān)鍵項目集合，利用矩陣分解進行填充；

6)

利用LDA及時間懲罰函數(shù)得到用戶興趣漂移模型，預(yù)測用戶下一階段概率主題分布

7)

End for

8)

For 每個用戶

9)

利用預(yù)測概率主題分布計算用戶相似性，得到預(yù)測評分矩陣

10)

返回每個用戶的填充的評分子矩陣和預(yù)測評分矩陣

11)

End for

2 基于會話的時序相似性

2.1 傳統(tǒng)相似性缺陷分析

基于會話的CF方法通過建立用戶偏好的漂移模型來提高推薦結(jié)果，但也加劇了數(shù)據(jù)稀疏，導(dǎo)致了由于相似性度量的失效而不能找到真正的近鄰。

如圖1所示，ij(rij)代表用戶ui對項目ij評分rij,hl是用戶交互歷史用時間窗劃分后的第l階段，—表示這個階段用戶沒有評分。假設(shè)u1是目標(biāo)用戶，u1與u2,u3的基于余弦或皮爾遜的相似性相同，因此i4將被推薦給u1。u1和u2的評分模式和隨時間偏好的變化趨勢是相似的，但是u1的偏好變化趨勢則與u3正相反。因此傳統(tǒng)的相似性能度量用戶間評分模式的相似性，卻不能度量偏好的變化趨勢。

h1h2h3…h(huán)tu1i1(2);i2(4)——…i3(3)u2i1(2);i2(4)——…i3(3);i4(5)u3i3(3);i4(5)——…i1(2);i2(4)u4i1(2);i2(4)i6(3);i7(5)i8(3);i9(5)…i3(3);i4(5);i5(3)u5i1(2);i2(4);i11(3)i6(3);i7(3)i8(4);i10(2)…i3(3);i4(5)u6i1(2);i2(4)i6(3);i7(5)—…i3(3);i4(5);i5(3)

圖1 基于交互歷史劃分的用戶-項目評分矩陣

Fig. 1 User-item rating matrix based on session

2.2 基于會話的時序相似性定義

針對傳統(tǒng)相似性度量方法的不足，本文提出了一種基于會話的時序相似性度量方法，該方法不僅衡量用戶間的評分模式的一致性，也反映了用戶偏好隨時間的漂移趨勢。

定義1 時序相似性。它是每個階段的評分模式和整個交互歷史用戶偏好變化趨勢的綜合度量，定義如式(1)：

(1)

定義2 時序相異度。它是目標(biāo)用戶沒有交互的每個階段的差異度和整個交互歷史中用戶偏好差異的綜合衡量，定義如式(2)：

(2)

在圖1中，u1和u2、u4、u5、u6在h1,h|H|有極大相似，因此u1和u2、u4、u5、u6是時序相似的。但如果近鄰與目標(biāo)用戶行為太一致，需要為目標(biāo)用戶填充數(shù)據(jù)的會話里近鄰也沒有交互行為，例如u2,因此應(yīng)選取與目標(biāo)用戶有交互行為的會話保持一致，而與目標(biāo)用戶沒有交互行為的會話保持相異性的那些用戶作為近鄰能更好地完成數(shù)據(jù)填充，如u4和u5。

結(jié)合時序相似性和時序相異性，定義基于會話的時序相似性如式(3)所示：

Sim(ui,uk)=γSim_T(ui,uk)+(1-γ)DSim_T(ui,uk)

(3)

其中γ∈[0,1] 用于調(diào)整時序相似性和相異性比率。 如果γ=0,目標(biāo)用戶與近鄰時序相似性差別最大，但目標(biāo)用戶交互行為會話可參考填充數(shù)據(jù)是最豐富的；如果γ=1,目標(biāo)用戶與近鄰時序相似性最一致，但數(shù)據(jù)填充是困難的。因此選取合適的γ值對發(fā)現(xiàn)近鄰去填充缺失值至關(guān)重要。

3 基于矩陣分解的數(shù)據(jù)填充

3.1 利用矩陣分解填充關(guān)鍵項目集合評分子矩陣

(4)

(5)

(6)

(7)

(8)

3.2 評分沖突解決

(9)

4 用戶漂移模型的建立和項目推薦

4.1 利用LDA建立用戶動態(tài)漂移模型

用戶目前偏好更依賴于它最近喜好，也就是說在預(yù)測用戶當(dāng)前偏好時，用戶越久遠(yuǎn)的喜好貢獻越小[7]。因此，用戶ui的偏好模型可表示為：

(10)

其中f(·)為指數(shù)衰減函數(shù)(范圍從1到0)，定義如下：

(11)

4.2 項目推薦

使用余弦相似度通過預(yù)測的概率主題分布計算所有用戶間的相似性并選擇用戶ui的n個近鄰。利用式(12)基于用戶CF的集成近鄰的評分完成預(yù)測。

(12)

5 實驗與分析

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

實驗使用的數(shù)據(jù)集是推薦系統(tǒng)流行的MovieLens數(shù)據(jù)集(https://grouplens.org/datasets/movielens/)，包含從2008年9月7日到2009年1月5日間共1 200位用戶對3 526部電影以0.5為步長的157 961個評分(分值為1～5)。其中每個用戶至少評過30部電影，每個項目至少被10個用戶評分過，用戶項矩陣的數(shù)據(jù)稀疏性為96.27%。實驗中建立了幾種不同的形式來評估算法，分別選擇300、600、900位用戶作為訓(xùn)練集，命名為M300、M600和M900，其余300位用戶作為測試集，為每個用戶選取項目評分?jǐn)?shù)分別為10、20、30，即Given10，Given20和Given30。

5.2 評估度量

為了與其他工作一致，使用平均絕對誤差作為度量標(biāo)準(zhǔn)，定義如下：

(13)

5.3 參數(shù)訓(xùn)練

5.3.1 時間窗口T

時間窗T的大小對鄰居選擇和推薦精度至關(guān)重要。T值如果太小，用戶在階段內(nèi)穩(wěn)定偏好不能形成；如果太大，某一階段內(nèi)的偏好可能已經(jīng)遷移。為了觀察時間窗T的大小對推薦精度的影響，T值從20變化到60在不同的訓(xùn)練集的性能如圖2所示，該圖表示在訓(xùn)練集為M300、M600、M900，評分分別為10, 20, 30時T如何影響MAE。由于數(shù)據(jù)的極度稀疏，在不同訓(xùn)練集下Given10的推薦結(jié)果都差于Given20和Given30。隨著T的增加，MAE先下降后增加，因此需要選擇適當(dāng)?shù)腡值平衡用戶偏好的穩(wěn)定和遷移得到較好的推薦性能。在M300Given10、M300Given20和M300Given30中分別選擇60、50、40，而在M600和M900中分別選60、50、50和40、60、60。

圖2 時間窗口T對MAE的影響

5.3.2 相似性度量參數(shù)α,β,γ

對基于會話時序相似性中三個參數(shù)α、β、γ進行了幾個實驗來確定它們對最終結(jié)果影響。具體來說，α、β、γ以0.1步長從0.1變化到0.9，結(jié)果分別如圖3～5所示。

圖3 α對MAE的影響

圖4 β對MAE的影響

圖3和圖4表明時序相似性和時序相異性階段數(shù)目對評分模型同等重要，因為當(dāng)α和β為最大值和最小值時MAE沒有明顯變化，并且在不同訓(xùn)練集上的趨勢是相同的。隨著訓(xùn)練用戶和評分?jǐn)?shù)的增加，相比會話數(shù)，每個會話內(nèi)評分模式更能顯著提高性能，并且α比β更明顯。例如圖3的M900訓(xùn)練集，在α=0.1時算法性能好于α=0.9性能，但是在M300和M600訓(xùn)練集上差別不大。它說明當(dāng)數(shù)據(jù)稀疏時，時序相似性/相異性會話數(shù)目對尋找近鄰是重要的,也表明基于會話時序相似性更適用于稀疏數(shù)據(jù)。

圖5 γ對MAE的影響

從圖5可知，M300Given10、M600Given10和M900所有三種情況在γ最大值和最小值時的MAE沒有明顯變化，因此時序相異性和時序相似性同等重要。但是其他訓(xùn)練集在γ=0.1的性能明顯優(yōu)于γ=0.9時的性能，這表明時序相異性在較小的訓(xùn)練集對發(fā)現(xiàn)近鄰?fù)瓿蓴?shù)據(jù)填充至關(guān)重要。

5.3.3 待填充項目集合評分子矩陣用戶和項目數(shù)s,d

在數(shù)據(jù)填充過程中，s和d起著非常重要的作用，它們直接決定著選擇多少近鄰和多少缺失數(shù)據(jù)被填充。s和d如果太大，每個目標(biāo)用戶會有太多近鄰和待填充數(shù)據(jù)，導(dǎo)致計算不準(zhǔn)確、計算開銷增大；如果太小，又會導(dǎo)致可利用的信息仍然很少。當(dāng)它們的值從10增長到100時，MAE先降低后增長，如圖6和圖7所示。

圖6 待填充矩陣最大用戶數(shù)對MAE的影響

從圖6可知，隨著訓(xùn)練集用戶和評分?jǐn)?shù)的增加，近鄰的最佳數(shù)目降低。例如在M300訓(xùn)練集，在Given10、Given20和Given30最佳性能時近鄰分別為90、40、40。 相似地，在圖7中隨著訓(xùn)練用戶和評分的增加，最佳的填充項目數(shù)也在減少。這主要是因為隨著越來越多可用信息，可選擇較少近鄰和項目進行數(shù)據(jù)填充。

5.3.4 近鄰數(shù)n

基于近鄰的推薦算法，近鄰數(shù)目n是關(guān)鍵。n從10變化到100的預(yù)測性能如圖8所示。

圖7 待填充項目數(shù)對MAE的影響

圖8 近鄰數(shù)n對MAE的影響

從圖8可知，不同訓(xùn)練集上給定20和30評分時，由于隨著n增加，可用信息越來越豐富，因此MAE降低。但是在Given10時，由于需要填充更多缺失值，MAE先降低后升高。在M300和M600訓(xùn)練集上,Given10的最佳性能優(yōu)于Given20和 Given30的最佳性能。這表明本文方法更適合稀疏數(shù)據(jù)，可以更好地處理數(shù)據(jù)稀疏問題。

5.4 與其他方法的比較

為了驗證方法的有效性，將本文矩陣分解數(shù)據(jù)填充方法 (DIMF)與其他數(shù)據(jù)填充方法進行了比較：

1)自適應(yīng)填充 (Auto-Adaptive Imputation, AutAI)[20]：自動識別缺失數(shù)據(jù)關(guān)鍵集合并利用用戶的交互歷史進行數(shù)據(jù)填充的方法。

2)非負(fù)矩陣分解及子集劃分協(xié)同過濾 (Non-negative Matrix Completion and Subgroups Partitioning, NMCSP)[21]：利用非負(fù)矩陣分解填充原始評分矩陣空缺值，并用塊模型劃分用戶-興趣和項目-特征子集，完成TOP-N推薦。

3)基于云填充與混合相似性的協(xié)同過濾 (Cloud model Filling and Hybrid Similarity, CFHS)[25]：利用云模型進行數(shù)據(jù)填充，并利用時序信息改進了傳統(tǒng)協(xié)同過濾的相似性計算。

4)時間依賴的網(wǎng)絡(luò)服務(wù)推薦 (Time-aware Web Service Recommendation, TWSRec)[11]：結(jié)合時間信息進行相似性計算和服務(wù)質(zhì)量預(yù)測，并采用隨機游走處理數(shù)據(jù)稀疏的方法。

5)層次近鄰網(wǎng)絡(luò) (Hierarchy K-Nearest Neighbor, HKNN)[22]：建立多層的近鄰網(wǎng)絡(luò)填充數(shù)據(jù)的方法。

實驗過程中對比方法的參數(shù)都采用最佳值，本文方法的參數(shù)都采用5.3節(jié)的最優(yōu)參數(shù)，結(jié)果如表1所示。顯然，即使由于用戶交互歷史被劃分成不同會話階段加劇了數(shù)據(jù)稀疏，本文方法仍然能夠提高推薦精度，并優(yōu)于對比方法。這是因為，在利用矩陣分解填充空缺值時，本文方法在計算用戶間相似性時，不僅考慮了評分模式，也考慮到時間上下文，而其他方法只考慮兩種情況之一；此外，本文方法在用基于近鄰的協(xié)同過濾項目推薦前在填充后的評分矩陣上建立了用戶偏好的漂移模型，而其他方法都是在數(shù)據(jù)填充后直接進行項目推薦。訓(xùn)練用戶從300增加到900時，MAE降低說明所有基于填充的方法在可用信息豐富時都能產(chǎn)生較好性能。Given10的性能不低于Given20和Given30表明所有方法都能處理數(shù)據(jù)稀疏，但本文方法改善效果最明顯，這也是因為矩陣分解重構(gòu)低秩矩陣的數(shù)據(jù)填充能挖掘潛在影響因素，而其他方法僅直接利用了評分。

表1 本文方法與其他方法在MAE上的比較

6 結(jié)語

本文提出了基于會話的時序相似性度量的矩陣分解數(shù)據(jù)填充方法。該方法首先定義了基于會話時序相似性度量，它結(jié)合時間信息到評分模式捕獲用戶間的真實相似關(guān)系；采用矩陣分解重構(gòu)基于近鄰用戶自動抽取項目關(guān)鍵集合的評分子矩陣來填充缺失值緩解了數(shù)據(jù)稀疏，挖掘了用戶和項目的潛在影響因素；利用LDA和時間懲罰函數(shù)建立了用戶興趣漂移模型，捕獲了用戶興趣動態(tài)。實驗結(jié)果表明，本文方法的預(yù)測精度優(yōu)于對比的幾種填充方法。