孔 麟，黃 俊，馬 浩，鄭小楠

(重慶郵電大學 通信與信息工程學院，重慶 400065)

0 引 言

協(xié)同過濾算法作為當前大數(shù)據(jù)背景下處理“信息過載”的有效技術(shù)手段，使其成為當下使用最為廣泛的推薦技術(shù)之一[1]。但隨著研究的深入，發(fā)現(xiàn)傳統(tǒng)的協(xié)同過濾算法仍存在較多有待改進的問題[2]。數(shù)據(jù)稀疏性問題作為最顯著的問題之一，為此，眾多專家學者提出了許多算法改進的方法，文獻[3,4]引入相關(guān)性權(quán)重系數(shù)提升了算法有效性；文獻[5]將Jaccard相似性系數(shù)結(jié)合評分修正公式減少了項目非相關(guān)性的影響；文獻[6,7]提出通過挖掘評分用戶之間潛在關(guān)系，使得推薦結(jié)果更加可靠；文獻[8]引入了項目相關(guān)性系數(shù)，根據(jù)項目類型和評分計算用戶相似度；文獻[9]在計算用戶偏好時，在評分相似度的基礎(chǔ)上引入時間權(quán)重函數(shù)；文獻[10]通過綜合分析用戶歷史行為和物品標簽信息，實現(xiàn)了在不依賴用戶項目評分的基礎(chǔ)上對標簽概率進行推薦；文獻[11]利用置信度函數(shù)將用戶隱性反饋映射為置信概率，基于隨機梯度下降提出了異構(gòu)置信度優(yōu)化算法。以上算法雖然對算法的有效性做了一定的優(yōu)化，但存在數(shù)據(jù)稀疏性情況下算法準確度仍有待提高、用戶相似度衡量因素較為簡單以及用戶之間潛在關(guān)系挖掘不夠深入等問題。針對以上問題，本文提出了融合多層相似度與信任機制的協(xié)同過濾算法。

1 相關(guān)定義

傳統(tǒng)協(xié)同過濾算法利用相似度大小的計算，構(gòu)建出與目標用戶最為相似的鄰居集合，并根據(jù)鄰居集合產(chǎn)生推薦結(jié)果，其算法流程如下：

(1)首先分析用戶的歷史評分數(shù)據(jù)，生成項目-評分矩陣Rm×n，記錄了m個用戶對n個物品所產(chǎn)生過的歷史評分數(shù)據(jù)。其中的Ric,代表用戶i對物品c的評分，對未有過歷史評分的項目記為0

(1)

(2)利用用戶間的歷史評分信息計算這n個用戶中兩兩用戶之間的相似度，并將用戶之間相似度計算結(jié)果按由大到小順序排列，取出前k個相似度最高的用戶組成鄰居集合。傳統(tǒng)協(xié)同過濾算法的公式如下

(2)

(3)

(4)

其中，sim(i,j)cos表示余弦相似度，sim(i,j)Adcos表示修正余弦相似度，sim(i,j)Pcc表示皮爾遜相似度。關(guān)于上述傳統(tǒng)協(xié)同過濾算法的定義請參見文獻[6]。

(3)根據(jù)求得的鄰居集合，計算得到目標用戶的項目預測評分

(5)

式中：Pi,c表示目標用戶i對項目c的預測評分，j表示鄰居集合中的任意用戶。

2 本文的算法

2.1 修正評分相似度

在推薦系統(tǒng)中，項目的評分在一定程度上反映了用戶對該項目的偏好度，此時偏好度的衡量由用戶評分值決定，但評分形式并不能準確表現(xiàn)用戶的喜愛程度。例如，某電影評分為5分制，假設(shè)用戶i給出的評分為4分，此時用戶對于電影的偏好程度就不能以數(shù)值形式準確地量化，只能粗略地預測用戶i喜歡該電影的概率較高。為解決此情況下偏好程度的度量問題，本文采用模糊邏輯法[12]，對單一數(shù)值評分進行數(shù)值豐富化處理，從而得到用戶偏好度的數(shù)值量化。

定義1 設(shè)U是一個論域，給定一個映射關(guān)系：μA:U→[0,1],x→μA(x)∈[0,1]，其中，映射μA稱為模糊集A的隸屬函數(shù)，μA表示x對模糊集A的隸屬度。根據(jù)以上定義，評分三角模糊集隸屬函數(shù)定義如圖1所示。

圖1 評分三角模糊集隸屬函數(shù)

(6)

μbad(x)=(5-x)/4; 1≤x≤5

(7)

例如，對某5分制的電影，某用戶對該電影的評分為4分，利用式(6)、式(7)對評分數(shù)據(jù)進行豐富化處理，得到該用戶對該項目的模糊偏好度為(0.75,0.25)，其中，0.75和0.25分別表示用戶對項目喜好程度和不喜好程度的數(shù)值量化，其計算過程如下

μgood=(4-1)/4=0.75

(8)

μbad=(5-4)/4=0.25

(9)

任意兩個用戶之間偏好差異度的計算依賴于二者對于共同評分項目的評分差異，評分差異越大，則說明他們之間所存在的偏好差異程度也越大，偏好差異度可通過式(6)、式(7)計算得到?；诖送普?，對于任意兩個用戶采用公共項目計算得到的偏好相似度用Ps(i,j)來表示，可由式(10)～式(12)計算得到

(10)

(11)

(12)

在對用戶評分相似度sim(i,j)a的計算時，將引入模糊映射關(guān)系修正后的用戶偏好與修正評分Jaccard相似度[5]結(jié)合，以平衡用戶對項目量綱和用戶間公共評分項目占比關(guān)系，最后基于用戶修正余弦相似度，計算出用戶的評分相似度

sima(i,j) =sim(i,j)Adcos×Ps(i,j)×Jaccard

(13)

Jaccard=|Ii∩Ij|/|Ii∪Ij|

(14)

其中，Ii和Ij表示用戶i和j的評分項目集合。

2.2 用戶興趣相似度

傳統(tǒng)的協(xié)同過濾算法只考慮了用戶的項目評分值，忽略了對用戶針對不同項目類型的興趣相似度，而往往用戶的興趣相似度在很大程度上影響了項目的推薦精度。在數(shù)據(jù)較為稀疏的情況下，用戶之間公共評分項較少，甚至為零，此時，基于項目類型所評估的用戶興趣相似度即可很大程度上彌補數(shù)據(jù)稀疏帶來的影響。

用戶的興趣度計算受到不同項目類型評分值以及數(shù)量占比關(guān)系的影響。例如，通過分析計算某用戶的電影觀看歷史記錄，得知該用戶對喜劇和愛情類的電影感興趣，那么當出現(xiàn)某部相關(guān)類型的電影時，則可以推測該用戶有較大可能性喜歡這部電影?；谝陨贤普摚瑢τ脩襞d趣向量interesti,j的定義為：用戶對不同類型項目的偏好程度，興趣向量的組成包括各個項目類型的評分值的占比和評分數(shù)量的占比

(15)

(16)

其中，avgi(t)表示某類型項目的評分均值，Ri,c表示對某類型項目的評分，It表示對該類項目評分次數(shù)，T表示所有類型項目的集合，Nt表示t類型項目的評分統(tǒng)計次數(shù)，N表示所有評分的數(shù)量，α表示興趣權(quán)重。

例如，根據(jù)以上公式分析計算某用戶的歷史評分記錄，對計算得到的興趣向量進行歸一化處理，得到用戶對動作、冒險、愛情、科幻類等電影的興趣權(quán)重占比為25%、20%、15%、13%……，由此可以看出，該用戶對動作類和冒險類電影比較偏愛。同時，利用用戶的興趣向量結(jié)合余弦相似度計算公式，對于任意兩個用戶i、j而言，可以計算得到用戶興趣相似度

(17)

式中：T表示所有項目類型的集合。

2.3 用戶混合相似度

綜上所述，將二者所得到的相似度進行融合，得到用戶混合相似度?？紤]到兩種相似度的計算受到數(shù)據(jù)稀疏性影響的程度不同：在公共評分數(shù)量較少時，評分尺度的度量易受評分峰值的影響，導致計算結(jié)果存在較大誤差，相對而言，基于項目類型得到的興趣相似度受評分峰值影響較小，故此時應提高后者權(quán)重；當公共評分項數(shù)量較多時，基于用戶評分計算得到的推薦結(jié)果精度更高，故此時應增大評分相似度占比。故而通過設(shè)定公共評分數(shù)量閥值d1，根據(jù)d1大小調(diào)整二者在不同數(shù)據(jù)稀疏性情況下的平衡分布權(quán)重，確保算法的精度和靈活度。計算公式如下

(18)

式中：simt(i,j)表示用戶混合相似度，count表示用戶評分數(shù)量，β為融合因子。

2.4 用戶間的信任度

分析發(fā)現(xiàn)，用戶間的信任關(guān)系在日常生活中占據(jù)著至關(guān)重要的作用，涉及到方方面面。但關(guān)于信任的描述是一個相對模糊的概念，對其的認知包括了主觀性、不對稱性、動態(tài)性等。傳統(tǒng)推薦算法僅從評分角度考慮，但在現(xiàn)實生活中，僅以此得到的推薦精度難以保證，例如，存在一些商家為了使自己的產(chǎn)品得到更多推薦而偽造評分數(shù)據(jù)的情況。為了降低推薦結(jié)果對評分數(shù)據(jù)準確性問題帶來的影響，本文引入用戶間的信任機制，當用戶間的可信度越高，那么由他所產(chǎn)生的推薦數(shù)據(jù)可靠性也相對更高。

推薦系統(tǒng)中兩兩用戶之間的信任度受用戶間交互關(guān)系的影響，所經(jīng)歷過共同的歷史行為越多，那么所累積的信任度也越高。用戶間每發(fā)生過一次相同項目的評分行為則認為產(chǎn)生過一次交互，根據(jù)交互次數(shù)與自身歷史評分次數(shù)的占比關(guān)系，得到用戶間的交互關(guān)系

IT(i,j)=|Ii∩Ij|/|Ii|

(19)

式中：Ii和Ij分別表示用戶i和j的評分項目集合，|Ii|、|Ij|表示集合的勢。

用戶之間的信任度受交互關(guān)系影響的同時，也受交互狀態(tài)的影響，成功的交互狀態(tài)必然會加強用戶間的信任度，同樣，失敗的交互狀態(tài)也會削弱用戶之間的信任度。將用戶滿意度狀態(tài)作為衡量交互成功與否的標準：如果兩個用戶同時表現(xiàn)出對某項目的滿意或者不滿意，那么認為二者的交互狀態(tài)是成功的，如果兩個用戶對共同評價的項目持不同的滿意度，那么認為二者的交互狀態(tài)是失敗的。滿意度的計算通過比較兩個用戶共同項目的評分與各自的平均評分，評分高于自身平均分即代表滿意，反之則代表不滿意。

綜上所述，用戶之間的交互狀態(tài)如下

(20)

式中：sus表示成功交互的統(tǒng)計次數(shù)，每交互成功一次記sus+1；fal表示失敗交互的統(tǒng)計次數(shù)，每交互失敗一次記fal+1。結(jié)合式(19)計算用戶間的交互關(guān)系，得到用戶信任度

(21)

在上式中，對交互的成功與否，都認為兩者對信任度的影響程度相同，但實際情況有所不同。在交互失敗時兩個用戶的評分差值遠大于交互成功時的評分差值，則說明此時兩個用戶對公共評分項的滿意度存在較大分歧，因此可以認為失敗交互所帶來的負面影響更大。在對信任度進行修正時，加入評分差值作為影響交互平衡的懲罰權(quán)重，以加強失敗交互帶來的消極影響，改進后的用戶間信任度如下

(22)

式中：IDP(i,j)表示用戶i對用戶j的信任度，Isus表示交互成功的集合，Ifal表示交互失敗的集合，ric和rjc分別表示用戶i和用戶j對項目c的評分，式(22)滿足信任度的不對稱原則，即IDP(i,j)≠IDP(j,i)。

3 UPTCF算法描述

將上述所建立的修正評分相似度、用戶興趣相似度以及用戶間的信任度進行動態(tài)融合，得到融合多層相似度與信任機制的協(xié)同過濾算法UPTCF，UPTCF的具體描述如下：

步驟1 根據(jù)用戶項目-評分矩陣Rm×n，將矩陣中所有用戶、項目以及評分數(shù)據(jù)進行標記提??；

步驟2 通過引入模糊邏輯法，對用戶間的評分差值進行豐富化處理得到用戶的模糊偏好，再基于模糊偏好差異對評分相似度進行修正，結(jié)合Jaccard相似性系數(shù)得到用戶修正評分相似度sima(i,j)；

步驟3 通過分別計算各種類型項目的評分均值與所有項目評分均值之和的占比關(guān)系，以及各類項目評分次數(shù)與項目總評分次數(shù)比值，計算二者之和，得到用戶的興趣向量，結(jié)合余弦相似度，計算出用戶興趣相似度simb(i,j)；

步驟4 將步驟2和步驟3基于不同因素計算得到的相似度，結(jié)合式(18)進行權(quán)值融合，得到混合相似度simt(i,j)。考慮到僅利用simt(i,j)產(chǎn)生的預測評分進行項目推薦可能會導致推薦因素單一、推薦精度較差的問題，故在此基礎(chǔ)上引入用戶間的信任度關(guān)系。若目標用戶i與目標用戶j之間的混合相似度越高，同時i覺得j值得信任，那么i就更可能采納j的建議。因此，在建立鄰居用戶集合Us時，將混合相似度以及信任度按照取值大小倒序排列，取出綜合值最高的前k個用戶建立鄰居用戶集合，并生成預測評分Pi,c

(23)

式中：δ的取值采用自適應模型[13]確定，δ取值范圍為[0,1]

(24)

步驟5 將得到的預測評分Pi,c進行降序排列，針對目標用戶未評分的項目，將預測評分最高的前N個項目推薦給目標用戶。

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

4.1 實驗數(shù)據(jù)

實驗數(shù)據(jù)集為MovieLen(ml-100k)公用數(shù)據(jù)集，數(shù)據(jù)集中包含了943個用戶對1682部電影的100 000個評分信息。將該數(shù)據(jù)集按照8∶2隨機進行劃分，將80%的評分信息作為訓練集，將20%的評分信息作為測試集，前者用于構(gòu)造推薦模型，并將產(chǎn)生的預測評分與后者的真實評分進行差值比較，訓練集和測試集的數(shù)據(jù)稀疏性都為93.6%，根據(jù)對數(shù)據(jù)集中用戶評分次數(shù)進行統(tǒng)計分析，評分次數(shù)小于15的用戶數(shù)量與評分次數(shù)大于15的用戶數(shù)量差值最大，此時在計算用戶混合相似度的過程中，兩種相似度的計算精度受到數(shù)據(jù)稀疏性差異的影響最大，故本文取d1=15進行以下實驗，完成未知參數(shù)的取值。

4.2 評價標準

對推薦系統(tǒng)的準確度的評價指標分為很多種，本文采用MAE(mean absolute error)作為算法準確度的評估指標，平均絕對誤差的計算公式如下

(25)

式中：reali表示實際評分，prei表示預測評分，n表示預測評分數(shù)量。

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

本文實驗利用IDEA完成算法的運行實現(xiàn)以及實驗結(jié)果的統(tǒng)計分析，IDEA全稱IntelliJ IDEA，是編程語言開發(fā)的集成環(huán)境。實驗一完成未知參數(shù)α和β的確定，采用十折交叉法，在MAE值最小時完成參數(shù)值的確定；實驗二采用對照實驗驗證本文算法的有效性。

實驗一:未知參數(shù)的確定

(1)興趣向量權(quán)重α的確定

項目類型偏好權(quán)重α主要用于調(diào)節(jié)對基于不同類型項目與總評分值的比值，以及不同類型項目數(shù)量與總評分項目數(shù)量的比值，通過調(diào)節(jié)二者占比，得到不同的興趣向量interesti,j，再根據(jù)興趣向量結(jié)合式(17)計算用戶之間的興趣相似度simb(i,j)。實驗過程中α以0.1為步長遞增，取值范圍為[0,1]，鄰居集合k以10為步長，取值范圍為[10,60]。根據(jù)計算生成多組預測評分，得到對應的真實評分與預測評分的MAE，統(tǒng)計結(jié)果如圖2所示。

圖2 偏好權(quán)重α的確定

從圖2中可以看出，MAE隨著鄰居集合數(shù)量的增加呈下降趨勢，說明推薦精度受到數(shù)據(jù)稀疏性的影響較為明顯。觀察圖2可知，在k=60，α=0.7時，此時預測評分與真實評分的平均絕對誤差最小，達到最優(yōu)值，故未知參數(shù)α的取值為0.7。

(2)融合因子β的確定

動態(tài)融合因子β的作用是針對根據(jù)數(shù)據(jù)稀疏性的不同，動態(tài)調(diào)整兩種相似度算法在混合相似度中的占比關(guān)系。實驗通過對鄰居集合數(shù)量k以及融合因子β采取步長均勻變化取值的方法，計算出多組預測評分及其MAE的變化曲線，實驗結(jié)果如圖3所示。

圖3 動態(tài)權(quán)重β的確定

從圖3可以看出，隨著鄰居集合數(shù)的增加，MAE的差值逐漸降低，當集合數(shù)k取值為60，動態(tài)因子β的取值為0.9時，MAE取得最優(yōu)值，故本文中β=0.9。

實驗二:算法性能對比

(1)引入信任機制前后算法性能對比

算法性能的驗證采用對比實驗的方法，對比引入信任機制前后兩種算法所得的MAE的值越小，說明該算法的準確性越高。根據(jù)實驗一所取得的最優(yōu)值α=0.7，β=0.9，基于此參數(shù)，分別采用基于用戶混合相似度算法(UPCF)，以及在此基礎(chǔ)上加入信任機制的UPTCF算法，得到各自的鄰居用戶集合，并以10為步長，對鄰居集合數(shù)k進行遞增取值，計算得到兩種算法所對應的兩組MAE，其實驗結(jié)果如圖4所示。

圖4 算法引入信任機制前后MAE對比

從圖4分析可知，隨著鄰居用戶數(shù)量的增多，在引入信任機制后的UPTCF算法所得到的MAE變化趨勢相比于UPCF而言，下降趨勢呈現(xiàn)出由急變緩的趨勢，由此可知UPTCF算法在數(shù)據(jù)稀疏性較高時，相比于UPCF算法推薦準確度更高；伴隨著鄰居用戶數(shù)量k的增加，引入信任機制的UPTCF算法相比于未引入信任機制的UPCF算法而言，準確度均有一定程度的提升，由此驗證引入信任機制對算法性能的優(yōu)化。

(2)UPTCF算法與其它幾種算法準確度對比

幾種算法準確度的比較同樣采用對比實驗的方法，對比的算法包括：傳統(tǒng)余弦相似度(CSCF)、改進的余弦相似度(ACSCF)和文獻[5]中提出的基于修正相似系數(shù)Jaccard的協(xié)同過濾算法(MKJCF)，計算各種算法對應的MAE，實驗結(jié)果如圖5所示。

圖5 不同算法的MAE值比較

通過圖5分析得出，隨著k值的遞增，以上4種算法的MAE都呈現(xiàn)不同程度的下降，并最終趨于平緩，且本文所改進得到的UPTCF算法的MAE均小于其它3種算法，實驗結(jié)果分析如下。

通過引入用戶興趣度以及信任機制，使得UPTCF算法相比于其它算法而言，在數(shù)據(jù)稀疏性情況下具有明顯優(yōu)勢：在k=10時，UPTCF算法的MAE取值為0.765，相比于改進的余弦相似度算法(ACSCF)在準確度上提升了6.3%，相比于余弦相似度算法(CSCF)在精度上提升了3.8%，與改進的MKJCF算法相比，其準確度約有2.1%的提升。隨著鄰居用戶數(shù)量的增加，各算法的推薦準確度均有不同程度的提升，在鄰居集合數(shù)量k=80時，本文提出UPTCF算法的MAE取得最小值，達到了0.721，相比于余弦相似度算法(CSCF)的MAE降低了3.1%，相比于改進的余弦相似度算法(ACSCF)的MAE降低了2.9%，與改進的MKJCF算法相比，MAE降低了1.7%；綜上所述，本文改進得到的UPTCF算法相比于其它幾種協(xié)同過濾算法，其推薦準確度都有較為明顯的提升，且在數(shù)據(jù)稀疏性情況下，推薦準確度的性能提升更為明顯。

5 結(jié)束語

為了從多方面解決推薦系統(tǒng)中用戶相似度計算精度低以及數(shù)據(jù)稀疏性的問題，本文提出并實現(xiàn)了的融合多層混合相似度與信任機制的協(xié)同過濾算法，該算法在一定程度上緩解了數(shù)據(jù)稀疏性帶來的影響，尤其是在鄰居集合數(shù)量較少的情況下；同時，相比于傳統(tǒng)的余弦相似度算法以及部分改進算法，在推薦準確率方面均有較大的提升；但算法本身仍然存在冷啟動問題，因此在未來的研究工作中，仍需對啟動問題做重點研究和解決。