基于用戶綜合信任度與社區(qū)信任傳播的推薦算法

周 婭,柴 旺,韓君陽,張國梁

(桂林電子科技大學(xué) 計算機與信息安全學(xué)院,廣西 桂林 541004)

0 概述

基于協(xié)同過濾的推薦算法具有從用戶角度進(jìn)行推薦的特性,符合目前重視個性化以及社會化發(fā)展的需要。但是,該算法在一定程度上存在數(shù)據(jù)稀疏性、用戶冷啟動等問題,降低了推薦的質(zhì)量。為此,一些研究者將信任機制引入到推薦中。

依據(jù)信任度獲取方式,可以將基于信任機制的推薦系統(tǒng)分為基于顯性信任的推薦和基于隱性信任的推薦。其中TidalTrust模型[1]和MoleTrust模型[2]是比較經(jīng)典的2種顯性信任模型,均以用戶的信任標(biāo)記作為直接信任度。但是在信任傳播的有效路徑選擇上,MoleTrust模型沒有設(shè)置信任閾值,使大量低可信度短路徑得以保留,而TidalTrust模型以最短路徑作為信任的最長傳遞距離,剔除了高可信度長路徑。文獻(xiàn)[3]比較并評估了信任傳播有效路徑長度對預(yù)測準(zhǔn)確性的影響,然后提出最佳策略來最大化預(yù)測的準(zhǔn)確性。在基于隱性信任的推薦中,文獻(xiàn)[4]依據(jù)用戶之間的交互關(guān)系構(gòu)建了MarkovTrust模型,文獻(xiàn)[5]將用戶之間的相似度作為隱性信任度,但是這2種方法都沒有考慮用戶評分及交互時間間隔對用戶信任度的影響,因為人在不同的時期有著不同的興趣,并不能認(rèn)為興趣具有不變性。文獻(xiàn)[6]指出綜合信任評價更優(yōu)于單一信任的評價,文獻(xiàn)[7-8]則在推薦中綜合考慮了顯性信任和隱性信任。

文獻(xiàn)[1-4]使信任在整個復(fù)雜網(wǎng)絡(luò)中進(jìn)行傳播,但是該過程存在無關(guān)節(jié)點多、遍歷范圍廣、計算量大等問題,導(dǎo)致信任傳播的時間成本過高。文獻(xiàn)[5]指出,除用戶之間的信任關(guān)系外,還應(yīng)考慮社群關(guān)系。在復(fù)雜網(wǎng)絡(luò)中,一群個體相互之間相似,而與其他個體不相似,則這些個體能構(gòu)成一個社區(qū),稱為虛擬社區(qū)[9]。用戶在復(fù)雜網(wǎng)絡(luò)中的唯一性,注定了每個用戶都擁有自己的專屬社區(qū)。文獻(xiàn)[10]將信任傳播與LPA算法加以融合,文獻(xiàn)[11-12]則在進(jìn)行信任傳播之前對用戶進(jìn)行聚類,從而使信任在用戶專屬社區(qū)進(jìn)行傳播,但僅能為用戶發(fā)現(xiàn)一個社區(qū)結(jié)構(gòu)。文獻(xiàn)[13]提出一種重疊社區(qū)發(fā)現(xiàn)算法COPRA,該算法能夠為用戶同時挖掘出多個虛擬社區(qū),并標(biāo)記出用戶對每個社區(qū)的從屬系數(shù)。文獻(xiàn)[12]指出在復(fù)雜網(wǎng)絡(luò)中對用戶進(jìn)行社區(qū)劃分可以解決用戶的冷啟動問題,文獻(xiàn)[14-15]則指出可以利用用戶間的信任關(guān)系來解決用戶冷啟動問題。

本文提出一種基于用戶綜合信任度與社區(qū)信任傳播的推薦算法VCTrust,旨在解決數(shù)據(jù)稀疏性和用戶冷啟動問題,降低信任傳播計算的時間成本,提高推薦質(zhì)量。首先綜合考慮顯性和隱性2種直接信任度,將評分時間間隔作為計算隱性直接信任度的一個影響因素,得到直接綜合信任度并以此構(gòu)建用戶信任網(wǎng)絡(luò);然后使用重疊社區(qū)發(fā)現(xiàn)算法為用戶劃分專屬虛擬社區(qū);最后在信任傳播有效信任路徑的選擇上剔除低可信度短路徑,保留高可信度長路徑,優(yōu)化信任衰減方式。

1 VCTrust算法

1.1 算法流程

虛擬社區(qū)信任模型是VCTrust的核心,包括用戶直接綜合信任度的計算、用戶虛擬社區(qū)的劃分、用戶信任的傳播計算3個部分。其中用戶直接綜合信任度的計算是模型的基礎(chǔ),決定了用戶間信任度的準(zhǔn)確性與合理性,該過程獲取用戶直接綜合信任度并以此構(gòu)建用戶信任網(wǎng)絡(luò)。為避免在信任的傳播過程中消耗大量時間,同時也為解決用戶冷啟動問題,模型使用重疊社區(qū)發(fā)現(xiàn)算法對用戶信任網(wǎng)絡(luò)進(jìn)行虛擬社區(qū)的劃分,使每個用戶都擁有自己的專屬虛擬社區(qū)。信任僅在用戶的專屬虛擬社區(qū)內(nèi)進(jìn)行傳播,新用戶可以通過選擇自己感興趣的社區(qū)來獲得初始的推薦結(jié)果。用戶信任的傳播計算是模擬用戶在社區(qū)中的社會行為,利用信任的方向性和傳遞性獲得用戶對非直接聯(lián)系用戶的信任值,即間接信任度,在用戶信任網(wǎng)絡(luò)中,直接信任用戶往往是稀疏的,通過對用戶間接信任度的獲取可以緩解數(shù)據(jù)的稀疏性。

VCTrust算法流程如圖1所示。該算法將用戶之間信任標(biāo)記數(shù)據(jù)、用戶對項目的評分?jǐn)?shù)據(jù)以及目標(biāo)用戶作為算法的輸入,其中用戶對項目的評分?jǐn)?shù)據(jù)包括評分值和評分時間,算法根據(jù)目標(biāo)用戶是否為新用戶給出不同的處理方式。

圖1 VCTrust算法流程

1.2 用戶直接綜合信任度計算

在計算用戶的直接信任度時綜合考慮顯性和隱性直接信任度,得到用戶直接綜合信任度。顯性直接信任是由一個用戶直接標(biāo)記對另一個用戶是否信任,設(shè)定該信任標(biāo)記為t,t=1,若t存在則表示存在顯性直接信任度;若t不存在,則需要獲取隱性直接信任度。利用用戶的歷史評分?jǐn)?shù)據(jù)得到用戶之間的綜合相似度sim(u,v)并認(rèn)為該相似度的值即為隱性直接信任度的值。有信任標(biāo)記的用戶間并不一定具有高相似度,而相似度高的用戶往往有著不錯的推薦效果,因此,本文將t和用戶綜合相似度sim(u,v)調(diào)和處理得到用戶顯性直接信任度。直接綜合信任度、顯性直接信任度、隱性直接信任度分別如式(1)～式(3)所示,其中α是權(quán)重因子。

(1)

(2)

(3)

本文在計算用戶綜合相似度sim(u,v)時主要考慮了3種影響因素:1)用戶間共同評分項目的數(shù)量;2)用戶對同一項目的評分時間間隔;3)用戶對共同評分項目的評分誤差。用戶間共同評分?jǐn)?shù)量越多,評分時間間隔和共同項目評分誤差越小,用戶的相似度也就越高。用戶u和v的綜合相似度如式(4)所示。

sim(u,v)=βsimtimeNum(u,v)+(1-β)simratingError(u,v)

(4)

其中,simtimeNum(u,v)是用戶u和v基于時間間隔與共同評分?jǐn)?shù)量的相似度,simratingError(u,v)是用戶u和v基于共同評分誤差的相似度,β是一個權(quán)重因子,取值范圍為(0,1)。

計算simtimeNum(u,v)時將Salton系數(shù)和時間衰減函數(shù)f(x)相結(jié)合。f(x)是一個指數(shù)衰減函數(shù),具有值域為(0,1]、隨x的增大值先快后慢逐漸衰減并趨于0的特性。

使用皮爾遜相似度計算simratingError(u,v),皮爾遜相似度可以很好地反映出用戶之間不同打分值的差異,并且能夠考慮到項目平均分值不同所帶來的影響。

f(x)、simtimeNum(u,v)和simratingError(u,v)分別如式(5)～式(7)所示。

f(x)=e-λx

(5)

(6)

(7)

1.3 用戶虛擬社區(qū)劃分

本文使用COPRA算法進(jìn)行用戶虛擬社區(qū)的劃分,以用戶直接綜合信任度作為劃分的依據(jù)。該算法能夠為節(jié)點用戶同時挖掘出多個社區(qū),社區(qū)個數(shù)范圍是[1,n],其中n是事先設(shè)定的用戶所能擁有的社區(qū)個數(shù)最大值,還能標(biāo)記出用戶與每個社區(qū)的從屬系數(shù)b(0≤b≤1),b的值越接近于1,表明用戶對該社區(qū)的從屬性也就越強。

圖2是用戶虛擬社區(qū)劃分示意圖,其中(e,2/3)表示節(jié)點從屬于社區(qū)f的從屬系數(shù)強度為2/3。

圖2 虛擬社區(qū)劃分示意圖

1.4 用戶信任傳播計算

1.4.1 有效路徑的選擇

虛擬社區(qū)信任模型在有效路徑選擇上遵循以下原則:1)去除社區(qū)信任網(wǎng)絡(luò)中存在的環(huán)結(jié)構(gòu),避免對節(jié)點的重復(fù)訪問;2)設(shè)定動態(tài)的信任閾值,使路徑的選擇更合理;3)優(yōu)先選擇高可信度短路徑,保留高可信度長路徑,去除低可信度短路徑。

模型利用廣度優(yōu)先搜索算法對社區(qū)信任網(wǎng)絡(luò)進(jìn)行規(guī)范化處理,去除不必要的環(huán)結(jié)構(gòu),并用標(biāo)簽(vertex,depth,children)對節(jié)點進(jìn)行標(biāo)記。其中,vertex表示節(jié)點,depth是步長,表示當(dāng)前節(jié)點距離源節(jié)點的最短距離,children是節(jié)點vertex的子節(jié)點集合,步長相同的節(jié)點可以有共同的子節(jié)點,目標(biāo)節(jié)點沒有子節(jié)點,其步長也是不定的。

最短路徑shortPath(u,v)是從節(jié)點u到v的最快路徑。根據(jù)“六度空間理論”,任何2個人可以通過6個人取得聯(lián)系,因此,本文給定一個建議最大步長suggestDepth=6。信任在社區(qū)信任網(wǎng)絡(luò)中最大傳遞距離L(u,v)取shortPath(u,v)和suggestDepth中的較大值,如式(8)所示。

L(u,v)=max(shortPath(u,v),suggestDepth)

(8)

在信任閾值的設(shè)定上取所有傳遞距離不大于L(u,v)的路徑,在路徑上取目標(biāo)節(jié)點的鄰接節(jié)點,認(rèn)為鄰接節(jié)點信任強度最大值為信任閾值,如式(9)和式(10)所示。

thread(u,v)= max(strength(x1),

strength(x2),…,strength(xn))

(9)

strength(x)= max(min(strength(p1),trust(p1,x)),

min(strength(p2),trust(p2,x)),…)

(10)

其中,thread(u,v)表示從源節(jié)點u到目標(biāo)節(jié)點v的信任閾值,x1,x2,…,xn是目標(biāo)節(jié)點v的鄰接節(jié)點,strength(x)是節(jié)點x的信任強度,源節(jié)點的信任強度為1,p1是節(jié)點x的父節(jié)點。

從源節(jié)點u到目標(biāo)節(jié)點v的有效路徑需要滿足路徑長度不超過L(u,v)路徑中任意2個節(jié)點的直接綜合信任度不小于thread(u,v)的條件。

1.4.2 信任的傳遞與用戶綜合信任度的計算

信任在傳遞過程中會隨傳遞步數(shù)的增加而減弱。根據(jù)三度影響力理論,源節(jié)點對三步以內(nèi)的節(jié)點具有強關(guān)系而對三步之外的節(jié)點具有弱關(guān)系,也就是說信任在三步以內(nèi)傳遞時的衰減是微弱的,但是在三步以外的衰減相對來說是比較迅速的。這一信任衰減過程可用式(11)表示,D(x)表示信任傳遞x步時信任的衰減度,源節(jié)點對子節(jié)點的信任不會衰減,即x=1時D(x)=1。

(11)

計算用戶的綜合信任度需要從目標(biāo)用戶節(jié)點v向源用戶節(jié)點u回溯計算有效路徑上的中間節(jié)點對目標(biāo)節(jié)點的信任值,最后對源節(jié)點的子節(jié)點加權(quán)平均得到源節(jié)點u對目標(biāo)節(jié)點v的信任度。若目標(biāo)節(jié)點是源節(jié)點的子節(jié)點,則綜合信任度為直接綜合信任度,用戶綜合信任度如式(12)所示。

(12)

其中,N(u)表示源節(jié)點u的子節(jié)點集合,xd表示節(jié)點x的步數(shù)。

1.5 項目的預(yù)測評分與推薦

由信任模型可以獲得目標(biāo)用戶與其他用戶的綜合信任度,選取與目標(biāo)用戶u綜合信任度最高的前n個用戶作為最近鄰居集合NN(u),然后利用式(13)進(jìn)行評分預(yù)測,選取預(yù)測評分最高的前k個項目推薦給目標(biāo)用戶。

(13)

1.6 算法實現(xiàn)

VCTrust推薦算法的主要步驟如下:

輸入用戶信任標(biāo)記數(shù)據(jù),用戶項目評分?jǐn)?shù)據(jù),目標(biāo)用戶

輸出目標(biāo)用戶的推薦項目集合

步驟1由用戶信任標(biāo)記數(shù)據(jù)和用戶項目評分?jǐn)?shù)據(jù)計算出用戶間的直接綜合信任度,并生成用戶信任網(wǎng)絡(luò)。

步驟2用COPRA算法對用戶信任網(wǎng)絡(luò)進(jìn)行虛擬社區(qū)的劃分,使每個用戶都有其專屬虛擬社區(qū)。

步驟3若目標(biāo)用戶不是新用戶,則獲取目標(biāo)用戶專屬虛擬社區(qū)。

步驟4若目標(biāo)用戶是新用戶,則選擇其感興趣的社區(qū),并指定社區(qū)內(nèi)度數(shù)最高的用戶為參照用戶,執(zhí)行步驟3。

步驟5通過用戶信任的傳播計算得到其他用戶與目標(biāo)用戶的綜合信任度。

步驟6選擇與目標(biāo)用戶綜合信任度最高的前n個用戶,使用式(15)進(jìn)行項目評分預(yù)測。

步驟7選擇預(yù)測評分最高的前k個項目作為推薦項目集合,推薦給目標(biāo)用戶。

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

2.1 實驗數(shù)據(jù)集

實驗采用的數(shù)據(jù)集來自Epinions (http://www.trustlet.org/epinions.html),是由Epinions工作人員提供給Massa的120 492個用戶對755 760篇文章三年內(nèi)的評分?jǐn)?shù)據(jù),以及717 667條用戶之間的信任標(biāo)記,其中88 180個用戶至少有一次信任標(biāo)記,數(shù)據(jù)的稀疏度達(dá)到99.984%,若認(rèn)為評分項目數(shù)低于3個的用戶為新用戶,則在該數(shù)據(jù)集中近35%的用戶存在冷啟動問題。數(shù)據(jù)集的具體格式如表1和表2所示。實驗中隨機選取70%的數(shù)據(jù)作為訓(xùn)練集,30%的數(shù)據(jù)作為測試集,用Java語言實現(xiàn)所有算法。

表1 用戶項目評分表

表2 用戶信任標(biāo)記表

2.2 算法評價標(biāo)準(zhǔn)

使用均方根誤差(RMSE)和平均絕對誤差(MAE)來計算評分預(yù)測準(zhǔn)確度,它們的值表示預(yù)測的結(jié)果與實際情況的偏差,值越小偏差越小,值越大偏差也就越大。

本文使用召回率和覆蓋率衡量推薦預(yù)測準(zhǔn)確度。召回率為能夠準(zhǔn)確推薦出的項目個數(shù)與測試集中所有項目個數(shù)的比值,當(dāng)條件相同時比值越大,說明推薦的效果越好。覆蓋率體現(xiàn)的是算法對項目的發(fā)掘能力,其值越大,說明發(fā)掘出的項目范圍越廣。

(14)

為更好地衡量推薦效果,引入Influence指標(biāo),如式(15)所示,該指標(biāo)是MAE和RMSE的調(diào)和值,值越小表示推薦的效果越好。

(15)

2.3 結(jié)果分析

對比實驗中所使用的算法及描述如下:

1)VCTrust:基于用戶綜合信任度與社區(qū)信任傳播的推薦算法。

2)VCT-kmeans:在VCTrust算法中利用k-means算法進(jìn)行虛擬社區(qū)劃分的算法。

3)TidalTrust:基于TidalTrust信任模型的推薦算法。

4)BUCF:基于用戶的協(xié)同過濾推薦算法。

2.3.1 權(quán)重因子對VCTrust的影響

在計算用戶顯性直接信任度時,使用權(quán)重因子α確定用戶間信任標(biāo)記t和用戶間綜合相似度sim(u,v)的權(quán)重分配,使用權(quán)重因子β衡量計算sim(u,v)時simtimeNum(u,v)和simratingError(u,v)的權(quán)重值。圖3顯示的是保持VCTrust其他變量保持不變,分別改變權(quán)重因子α和β所得到的Influence的值,以此來衡量α和β對VCTrust的影響。

圖3 α和β對VCTrust算法的影響

從圖3可以看出,當(dāng)α為0.7時Influence取得最小值,其原因在于信任標(biāo)記t是用戶間真實的信任關(guān)系的反映。因此,在計算用戶直接顯性信任度時會占有較大權(quán)重。此外還可看出,當(dāng)β為0.6時Influence取得最小值。因此,在下文所敘述的實驗中將α設(shè)為0.7,β設(shè)為0.6。

2.3.2 改善數(shù)據(jù)稀疏性能力的分析

在推薦算法中,數(shù)據(jù)稀疏性通常是由用戶行為數(shù)據(jù)缺失引起的,體現(xiàn)在算法無法為用戶挖掘出足夠多的鄰居用戶。因此,可以用能夠挖掘出的鄰居用戶數(shù)量來衡量算法改善數(shù)據(jù)稀疏性的能力。表3描述的是4種算法能夠挖掘出的平均鄰居用戶數(shù)量,從中可以看出,VCTrust能夠挖掘出的用戶數(shù)量遠(yuǎn)遠(yuǎn)超過BUCF和VCT-kmeans,由此表明VCTrust算法能夠有效地緩解數(shù)據(jù)稀疏性。

表3 4種算法挖掘出的鄰居用戶數(shù)量對比

2.3.3 信任傳播計算的時間成本分析

圖4顯示的是在隨機選取5 000個用戶所構(gòu)建的信任網(wǎng)絡(luò)中,不同信任模型信任傳播計算的時間成本。可以看出VCTrust能夠明顯降低信任傳播計算的時間成本,因為COPRA算法允許用戶同時從屬于多個社區(qū),所以大于VCT-kmeans的時間成本。

圖4 信任傳播計算的時間成本比較

2.3.4 推薦質(zhì)量分析

圖5和圖6分別顯示了不同算法的平均絕對誤差和均方根誤差?？梢钥闯?VCTrust的MAE值和RMSE值明顯小于其他算法得出的相應(yīng)值,即VCTrust的評分預(yù)測準(zhǔn)確度要優(yōu)于其他算法。其中,在最近鄰居個數(shù)為10時,VCTrust和VCT-kmeans的MAE值與RMSE值最小,而BUCF在最近鄰居個數(shù)為20時MAE和RMSE取得最小值,當(dāng)最近鄰居個數(shù)為5時VCTrust和VCT-kmeans的MAE值和RMSE值相當(dāng)并且要遠(yuǎn)小于BUCF和TidalTrust,這說明基于VCTrust思想的算法在擁有較少的鄰居用戶時就有較高的評分預(yù)測準(zhǔn)確度,能夠有效地緩解數(shù)據(jù)稀疏性和用戶冷啟動問題給評分預(yù)測帶來的影響。

圖7是最近鄰居個數(shù)取不同值時VCTrust和VCT-kmeans、TidalTrust、BUCF在召回率上的比較結(jié)果?？梢钥闯鯲CTrust算法的召回率明顯優(yōu)于其他3種算法。

圖8是算法覆蓋率的比較結(jié)果,從中可以看出,VCTrust和VCT-kmeans的覆蓋率要優(yōu)于BUCF,與TidalTrust相當(dāng)。VCTrust在初始階段覆蓋率增加緩慢小于VCT-kmeans,但是之后會快速增加趨近于VCT-kmeans。因此,VCTrust在覆蓋率上還是有著不錯的表現(xiàn),能夠覆蓋到足夠多的項目。

圖5 不同算法的平均絕對誤差比較

圖6 不同算法的均方根誤差比較

圖7 不同算法的召回率比較

圖8 不同算法的覆蓋率比較

3 結(jié)束語

本文算法利用虛擬社區(qū)信任模型得到用戶綜合信任度,并將該信任度帶入?yún)f(xié)同過濾推薦算法進(jìn)行計算,從而得到推薦結(jié)果。該算法使用用戶直接綜合信任度構(gòu)建用戶信任網(wǎng)絡(luò),利用重疊社區(qū)發(fā)現(xiàn)算法為每個用戶劃分其專屬虛擬社區(qū)并進(jìn)行信任傳播計算得到用戶綜合信任度。實驗結(jié)果表明,本文算法在平均絕對誤差、均方根誤差、召回率以及覆蓋率指標(biāo)上均優(yōu)于傳統(tǒng)推薦算法,能夠有效緩解數(shù)據(jù)稀疏性和用戶冷啟動問題,降低用戶信任傳播計算的時間成本,提高推薦質(zhì)量。下一步工作將考慮項目屬性標(biāo)簽對推薦預(yù)測的影響,從而為用戶提供更個性化的推薦服務(wù)。