何 利,胡 飄
(重慶郵電大學(xué) 計算機科學(xué)與技術(shù)學(xué)院, 重慶 400065)
大數(shù)據(jù)時代帶來的信息過載問題日漸突出,使得人們從海量信息中找到對自己有效的信息變得愈發(fā)困難。推薦算法(recommendation algorithm,RA)是有效解決信息過載問題的重要方式,而且與人們的日常生活息息相關(guān)。推薦算法是指應(yīng)用知識發(fā)現(xiàn)技術(shù)產(chǎn)生個性化推薦,從而幫助用戶在大量的文章、產(chǎn)品、電影、音樂、網(wǎng)頁等中篩選出有用的信息[1-2]。
協(xié)同過濾(collaborative filtering ,CF)[3]是推薦算法中整體性能最佳的技術(shù)之一,與傳統(tǒng)推薦算法相比,其使用用戶的歷史交互信息得出用戶的興趣偏好信息,從而為用戶給出推薦,可以避免由于不完全或不精確特征抽取而產(chǎn)生的不準(zhǔn)確推薦[4]。當(dāng)用戶評分信息較少時,傳統(tǒng)協(xié)同過濾卻面臨推薦服務(wù)質(zhì)量低的問題,即用戶冷啟動(cold start)、數(shù)據(jù)稀疏(data sparsity)問題[5]。
圍繞用戶冷啟動問題,近年來引入用戶的輔助信息來緩解冷啟動問題的方法得到了諸多學(xué)者的廣泛研究。這些輔助信息包括統(tǒng)計信息[6]、會員信息和社交信任[7-8]等。其中,由于社交信任信息比會員信息和統(tǒng)計信息等更加可靠和明確,所以,引入信任信息已然成為目前解決用戶冷啟動問題的有效手段之一。該類方法在一定程度上緩解了傳統(tǒng)推薦系統(tǒng)中的數(shù)據(jù)稀疏和用戶冷啟動等問題,提高了推薦算法的準(zhǔn)確性;但現(xiàn)有的基于信任的推薦技術(shù)多數(shù)僅簡單使用用戶的二值信任來尋找可信好友,未考慮用戶間信任傳遞問題以及用戶間隱含的信任信息,使得用戶間信任估計精度低,導(dǎo)致對冷啟動用戶的推薦質(zhì)量不高。
目前,引入信任關(guān)系是解決協(xié)同過濾中用戶冷啟動問題的有效手段,并且已經(jīng)取得部分成果:在采用聚類分析和概率矩陣分解方法來利用引入的信任信息方面,Moradi等[9]將用戶評分相似作為用戶間的信任值,并結(jié)合用戶的社交拓?fù)鋱D對用戶進行K-Means聚類分析。而Ullah等[10]和Guo等[11]采用社區(qū)檢測聚類算法,通過用戶興趣對用戶信任進行加權(quán),使多個初始簇中擁有較高用戶興趣和信任相似的用戶分配到同一社區(qū)聚類中。Guo等[12]提出一種結(jié)合信任的多視圖聚類的方法,從評分和信任這2個關(guān)系視圖對用戶進行K-Mediods交叉聚類來擴大冷啟動用戶的鄰居集,從而在一定程度上緩解了用戶數(shù)據(jù)稀疏的問題。該類方法并未考慮信任傳遞的方向性對用戶信任的影響以及忽視了用戶在社交關(guān)系中存在的信任信息、用戶對間接用戶信任強度的差異。
潘一騰等[13]和Zhang等[14]通過貝葉斯概率矩陣分解(Bayes probabilistic matrix factorization,BPMF)社交信任矩陣,并利用梯度下降法得到信任關(guān)系隱含相似度,放大用戶間信任程度細(xì)微的差異,從而選出更加可信的鄰居好友。Li等[15]則采用矩陣奇異值分解(singular value decomposition,SVD)和信任傳播相結(jié)合的方法來最大化地挖掘評分信息和信任信息中的潛在有效信息,提高冷用戶的推薦質(zhì)量。為了解決傳統(tǒng)矩陣分解無法建立潛在因素與項目顯示屬性間的關(guān)聯(lián)關(guān)系,Zhao等[16]提出一種混合矩陣分解(hybrid matrix factorization,HMF)方法,通過結(jié)合隱式和顯示屬性并利用顯示屬性間的關(guān)聯(lián)關(guān)系對因素矩陣進行約束,緩解矩陣分解中的過擬合問題。但由于矩陣分解采用的是數(shù)據(jù)降維處理,當(dāng)矩陣數(shù)據(jù)甚少時,矩陣分解難以得到更加準(zhǔn)確的隱含信任關(guān)系甚至?xí)箖H有的有效信息丟失。
在信任傳播尋找用戶的鄰居好友方面,Massa等[17]提出的moletrust模型利用信任傳播理論評估信任的手段,提高了引入信任網(wǎng)絡(luò)進行推薦的準(zhǔn)確性和覆蓋率。Guo等[18]提出一種“融合”[14]方法,將評分信息和社交信任值有效整合,并在信任傳播中運用六度空間理論有效縮小了信任傳播的路徑長度,提高信任傳播的傳播效率。Ma等[19]和Lee等[20]考慮到不可信任傳播的存在,通過在傳統(tǒng)社會化推薦算法[13]中加入不可信任關(guān)系矩陣,并基于奇異值分解的聚類算法來處理信任和不信任關(guān)系矩陣,以使冷用戶更容易發(fā)現(xiàn)信任社區(qū)[10]。但不可信任信息較二值信任信息更難獲取,并且信任與不可信任關(guān)系存在著重疊的可能性,這也會使部分用戶的信任估計被放大導(dǎo)致相似計算準(zhǔn)確度較低。Kala?等[21]和Liu等[22]則基于專家協(xié)商機制,通過設(shè)置某個信任閾值,檢測不同層次好友中的最值得信賴的好友或?qū)<业男湃渭墑e,并使用好友或?qū)<业臍v史信息為用戶提供服務(wù)推薦。該方法在一定程度上可以減少冷用戶匹配好友群或?qū)<胰旱臅r間,但也可能使用戶的直接信任好友被忽視,用戶間的信任估計較片面。
上述研究并沒有考慮到用戶信任關(guān)系的復(fù)雜性以及信任信息的丟失問題,尤其是沒有從多方面考慮影響用戶信任的因素而僅從單一維度衡量用戶信任,導(dǎo)致用戶間信任計算精度低的問題。
針對冷用戶信任度計算問題[23],本文通過深入分析用戶在社交網(wǎng)絡(luò)中的信任機制[24-25],用戶信任關(guān)系必須含有直接信任關(guān)系和間接信任關(guān)系,并且用戶信任受所處社交網(wǎng)絡(luò)中的局部和全局因素的影響。本文從多角度考慮影響用戶信任的隱含因素,提出一種多維度信任度量模型,得到用戶綜合信任,將用戶綜合信任按照一定的權(quán)重與用戶評分相似進行有效融合得到基于用戶多維度信任的冷啟動推薦算法(user multidimensional trust-based cold-start recommendation algorithm,UMTCRA),通過提高用戶綜合相似精度來提高對冷啟動用戶推薦的質(zhì)量。
用戶間信任度量的準(zhǔn)確度會影響基于信任的協(xié)同過濾算法對冷啟動用戶的推薦質(zhì)量。信任度量越準(zhǔn)確,協(xié)同過濾算法對冷啟動用戶的個性化服務(wù)質(zhì)量就越高;否則就難以保證對冷啟動用戶的高質(zhì)量推薦。本文提出的多維度信任度量模型中,用戶信任包括間接信任和直接信任,并且從信任傳遞的方向性和用戶的全局聲望2個維度量化分析其對用戶信任的影響。由此,本文得到用戶的局部可被信任概率和全局可被信任概率;并分別使用局部可被信任概率和全局可被信任概率對直接信任和間接信任進行線性加權(quán)處理,得到用戶的綜合信任度。
用戶間的信任度指一個用戶對另一個用戶的信任程度,同時信任度分為直接信任度和間接信任度。圖1表示目標(biāo)用戶U1所處社交網(wǎng)絡(luò)中用戶間的信任關(guān)系,其中,節(jié)點U1-U2代表用戶,圖1中的有向邊表示用戶間存在著直接信任關(guān)系,且箭頭所指的用戶為該信任關(guān)系中受托人(Trustee[7]),與箭頭尾部連接的用戶為該信任關(guān)系中的信托人(Truster[7])。
圖1 用戶間的信任關(guān)系Fig.1 Trust relationship among users
直接信任度Dt(u,v)表示存在著直接信任關(guān)系的用戶u和用戶v之間的信任度。如圖1中用戶U1和用戶U2間的信任度即為直接信任度。在本文中,直接信任值由用戶的社交信任數(shù)據(jù)轉(zhuǎn)換得到,構(gòu)成用戶間的有向鄰接矩陣UU。表1表示由圖1中的用戶信任關(guān)系轉(zhuǎn)換得到的用戶間的有向鄰接矩陣。在表1中,數(shù)值0或1表示用戶間是否存在著直接信任關(guān)系,如用戶U1與用戶U2存在直接信任關(guān)系,故Dt(U1,U2)=1;用戶U1與用戶U4不存在直接信任關(guān)系,故Dt(U1,U4)=0。其中,用戶是相信自己本身,故對角線值應(yīng)該為1。
表1 有向鄰接矩陣
信任度量局部可被信任概率l(u,v)表示當(dāng)用戶u和用戶v間存在直接信任關(guān)系時,用戶v被用戶u直接信任的概率,即用戶u直接信任用戶v的概率。Jaccard相似系數(shù)可計算存在直接聯(lián)系的用戶間的局部可被信任概率,但未考慮用戶間信任的非對稱性。因此,本文的局部可被信任概率由兩直接聯(lián)系用戶的共同直接好友數(shù)占信托人好友總數(shù)的比例得到。為避免兩直接聯(lián)系的用戶間的局部可被信任概率為零導(dǎo)致用戶間信任值可能為零的問題,本文假設(shè)用戶本身也是自己的一個好友;故本文的局部可被信任概率被定義為
(1)
(1)式中:Fu表示用戶u的直接信任好友;Fv表示用戶v的直接信任好友;Fu∩Fv表示用戶u和用戶v的共同直接信任好友。
間接信任度IDt(u,v)表示若用戶u和用戶v間存在著可達路徑,如path=(u,m1,m2,…,mn,v),其中,m1,m2,…,mn表示該可達路徑的中間用戶,且可達路徑的長度d至少為2時,則稱用戶u和用戶v間存在的間接信任關(guān)系,用戶u和用戶v間的信任度為用戶的間接信任度。依據(jù)社交網(wǎng)絡(luò)中的信任傳播與信任機制的相關(guān)研究可知,用戶間的信任強度會隨著傳播路徑的增長而衰減,即用戶間的間接信任與可達路徑的長度成反比關(guān)系。本文利用如下公式計算用戶間的間接信任度
(2)
當(dāng)用戶與鄰居用戶存在著多條可達路徑時,用戶間的間接信任度為
(3)
(3)式中:N表示用戶u與用戶v的可達路徑的總數(shù)目。
全局可被信任概率g(u,v)表示用戶v在目標(biāo)用戶u所處的信任關(guān)系圖中可被其他用戶信任的概率。依據(jù)社會學(xué)中有關(guān)聲望機制的研究可知,在某個社會群體中,若一個人被信任的次數(shù)越多,其被其他人信任的概率越大;那么在某信任關(guān)系圖中,一個用戶的信任入度(信任該用戶的用戶數(shù)目)越大,則其可被信任的概率也就越大。因此,用戶v全局可被信任概率為
(4)
如上所述,本文將用戶信任分為直接信任和間接信任,并針對用戶在直接信任關(guān)系和間接信任關(guān)系中處于信任關(guān)系圖中的局部與全局位置,提出用戶在信任關(guān)系圖局部與全局可被信任的概率。故利用局部可被信任概率和全局可被信任概率分別對直接信任與間接信任加權(quán)融合,用戶u對用戶v的綜合信任度為
T(u,v)=l(u,v)·Dt(u,v)+g(u,v)·IDt(u,v)
(5)
由于冷啟動用戶評分的項目數(shù)甚少,直接使用用戶的評分?jǐn)?shù)據(jù)來計算用戶評分相似準(zhǔn)確度低。故本文從計數(shù)、占比、均值、加權(quán)等角度分析用戶-項目矩陣UI中的評分?jǐn)?shù)據(jù),提取出每個用戶的行為特征。據(jù)此得到每個用戶的特征向量,如F1=(f11,f12,…,f1n)表示用戶1的n維特征向量(其中,f11等表示前面提取出的行為特征值),最終獲取到m個用戶的特征向量集合F={F1,F2,…,Fm}。據(jù)此,用戶u與用戶v的評分相似度為
(6)
(6)式中,(fu1,fu2,…,fun)和(fv1,fv2,…,fvn)分別表示用戶u與用戶v的n維特征向量。
由于用戶評分相似與社交信任都能在一定程度上反映出用戶間的行為偏好相似,所以,本文將得到的綜合信任度和用戶評分相似進行線性加權(quán)融合,得到用戶間的綜合相似度為
CS(u,v)=α·T(u,v)+β·S(u,v)
(7)
(7)式中:CS(u,v)為用戶間的綜合相似度;α,β分別表示T(u,v)和S(u,v)的權(quán)重系數(shù),且滿足α+β=1。
(8)
(8)式中,r(v,i)表示用戶v對項目i的真實評分。
UMTCRA算法主要針對冷啟動用戶做出個性化推薦,該算法的實現(xiàn)過程主要分為5個步驟:①用戶綜合相似計算;②用戶評分相似計算;③用戶綜合相似計算;④最近可信鄰居選擇;⑤評分預(yù)測。以下為該算法的具體實施步驟。
輸入:目標(biāo)用戶u,其他用戶v,有向鄰接矩陣UU,用戶-項目矩陣UI,用戶特征向量集合F,最近可信鄰居集合TNu,可信鄰居好友的個數(shù)k;
步驟1依據(jù)有向鄰接矩陣UU,采用公式(5)計算用戶u與v的綜合信任度T(u,v);
步驟2依據(jù)用戶-項目矩陣UI提取得到的用戶特征向量集合F,采用公式(6)計算用戶u與v的評分相似S(u,v);
步驟3對步驟1和2得到的T(u,v)和S(u,v),采用公式(7)得到用戶u與v的綜合相似度CS(u,v);
步驟4對步驟3得到的CS(u,v)進行從高到低排序,選擇相似性最大的前k個用戶作為目標(biāo)用戶u最近可信鄰居好友TNu;
實驗使用Epinions(http://www.epinions.com)真實數(shù)據(jù)集對本文提出的方法進行驗證。epinions是一個大眾消費點評網(wǎng)站,用戶可以在該網(wǎng)站上通過評分表達自己對物品的喜好程度,也可以將其他人添加到自己的信任列表中作為好友。Epinions數(shù)據(jù)集包含用戶對項目的評分信息和用戶信任列表中的信任關(guān)系信息,其中,用戶評分是從1到5的整數(shù)評分,信任值是0或1(1表示信任,0表示不信任)。關(guān)于該數(shù)據(jù)集的具體信息如表2所示。
表2 Epinions數(shù)據(jù)集信息
從Epinions數(shù)據(jù)集的統(tǒng)計信息中可以看出,該數(shù)據(jù)集數(shù)據(jù)量大且非常稀疏。如圖2,圖3所示,在該數(shù)據(jù)集中,冷啟動用戶[17]有16 910個,占整個用戶數(shù)的34.3%。其中,大部分冷啟動用戶的直接信任好友數(shù)和評論過物品數(shù)非常少,冷啟動用戶集的數(shù)據(jù)極其稀疏。綜上所述,該數(shù)據(jù)集完全符合本實驗對冷啟動用戶推薦效果驗證的要求。
本文采用評估預(yù)測中廣泛使用的留一法對數(shù)據(jù)集進行劃分并預(yù)測評分,即保留冷用戶的一條評分信息,用其余的所有信息預(yù)測該評分。故測試集為所有保留一條評分信息的冷用戶,訓(xùn)練集為非冷啟動用戶以及剔除一條保留的評分信息后的冷用戶。
圖2 擁有不同直接好友數(shù)的冷用戶的數(shù)目Fig.2 Number of cold users with different direct friends
圖3 不同已評項目數(shù)的冷用戶的數(shù)目Fig.3 Number of cold users with different rated items
1)實驗采用平均絕對誤差(mean absolute error,MAE)作為評估預(yù)測評分與真實評分接近程度的重要指標(biāo),該指標(biāo)在大多數(shù)研究中被采用。
(9)
2)評分覆蓋率(rating coverage, RC)可以評估預(yù)測出的評分?jǐn)?shù)占測試集評分?jǐn)?shù)的比例為
(10)
(10)式中,M和N分別表示預(yù)測出評分的項目數(shù)與測試集中已評分的項目數(shù)。
3)魯棒性(F-measure,F1)通過綜合考慮評分準(zhǔn)確度和評分覆蓋率來評估推薦方法的整體性能平衡性和穩(wěn)定性。評分準(zhǔn)確度iMAE和F1分別為
(11)
(12)
為評估本文UMTCRA算法對冷啟動用戶的推薦效果,將Epinions中的所有冷啟動用戶作為實驗的測試數(shù)據(jù)集。在通過信任傳播尋找冷啟動用戶的可信好友時,為了避免無意義的搜索和減少計算開銷,將可達路徑d的最大值嚴(yán)格設(shè)置為3。同時,在選取冷啟動用戶的最近可信鄰居用戶時,為了便于對參數(shù)α的調(diào)節(jié)和由于d的嚴(yán)格控制導(dǎo)致評分預(yù)測時有效可信鄰居用戶的數(shù)目較少,因此,實驗不對k進行設(shè)置,直接使用所有相似用戶作為目標(biāo)用戶最近可信鄰居用戶。
實驗1(α的選擇)。因為α+β=1,所以僅需通過調(diào)節(jié)α或β的值來驗證UMTCRA算法的性能。由于本文通過融合用戶的評分信息和信任關(guān)系信息來緩解冷啟動用戶的數(shù)據(jù)稀疏問題,單獨使用評分信息或信任關(guān)系信息對冷啟動用戶進行推薦很明顯會使冷啟動用戶再次面臨原有的數(shù)據(jù)稀疏問題。因此,實驗將α的初始值設(shè)置為0.1,最高取值為0.9,且α以0.1為增量逐級遞增;α的值越大表明基于用戶信任預(yù)測的評分值的占比越大。
通過實驗得到α分別對UMTCRA算法的評估指標(biāo)MAE,RC,F(xiàn)1的影響,如圖4—圖6所示。其中,圖4顯示隨著α的增長,MAE整體呈現(xiàn)先增大后減小,并且當(dāng)α取值為[0.1,0.4]時,MAE值的上下波動較為明顯,尤其,α取值為0.2時,該算法的平均絕對誤差最小;而當(dāng)α取值為[0.4,0.9]時,MAE值波動較為平穩(wěn)。圖5顯示RC隨著α的增長整體呈現(xiàn)先增大后減小,在α取值為[0.2,0.7]時,RC值較為平穩(wěn),其中,當(dāng)α在[0.2,0.5]時,該算法有最好的覆蓋率;圖6顯示,F(xiàn)1隨著α的增長整體呈現(xiàn)先增大后減小,當(dāng)α取值為[0.1,0.3]時,F(xiàn)1值上下波動較為明顯,α在[0.3,0.7]時,F1值波動較為平穩(wěn),且在[0.4,0.55]時有最好的穩(wěn)定性。綜上所述,當(dāng)α取值為0.5時,該算法表現(xiàn)出最佳的推薦效果。除此之外,實驗結(jié)果表明,當(dāng)用戶綜合相似度中的權(quán)重分配過于偏向綜合信任和評分相似時,算法推薦性能不穩(wěn)定,所以在對冷啟動用戶預(yù)測評分時需要平衡倆者之間的權(quán)重,也說明人們與其信任的好友和評分相似的鄰居之間的偏好相似程度相當(dāng)。
圖4 權(quán)重系數(shù)α對MAE的影響Fig.4 Influence of weight coefficient α on MAE
圖5 權(quán)重系數(shù)α對RC的影響Fig.5 Influence of weight coefficient α on RC
圖6 權(quán)重系數(shù)α對F1的影響Fig.6 Influence of weight coefficient α on F1
實驗2(不同算法推薦效果對比)。為了驗證本文提出的UMTCRA算法對冷啟動用戶的推薦效果,在所有冷啟動用戶作為測試數(shù)據(jù)集下,與以下3種方法進行比較分析:UBCF(user-based collaborative filter),Mole(moletrust)和Merger3[18]。其中,UBCF為使用Pearson系數(shù)計算用戶相似的傳統(tǒng)協(xié)同過濾算法,相似度閾值設(shè)置為0;Mole為MoleTrust信任增強模型的實現(xiàn)算法,在信任網(wǎng)絡(luò)中信任傳播的長度設(shè)置為3,僅將被信任的鄰居用于項目的評分預(yù)測;Merger3為Guo等[18]提出的針對用戶冷啟動推薦的方法,信任傳播的長度設(shè)置為3。最后,UMTCRA算法中的α為0.5。
通過實驗得到UMTCRA與其他3種方法對冷啟動用戶推薦的對比結(jié)果,如圖7所示。在這4種方法中,除UBCF僅使用評分信息尋找最近鄰給用戶做出推薦外,其他3種方法均引入了用戶的信任關(guān)系信息。由于引入了用戶間的信任關(guān)系,除UBCF外的3種方法均可以在一定程度上緩解冷啟動用戶的數(shù)據(jù)稀疏問題,并且在冷啟動用戶集中相比UBCF有著明顯的提高。從實驗結(jié)果中可以觀察到UMTCRA在MAE方面,MAE值越低表明算法預(yù)測出的評分與真實評分的誤差越小,算法評分預(yù)測越精確。圖7中, UBCF算法的MAE值最低,后3種算法的MAE明顯降低;其中,本文的UMTCRA的評分誤差最低,相較于Merge3的評分絕對誤差減少了6.29%,表明本文算法提高了對冷用戶進行評分預(yù)測的準(zhǔn)確度;在RC方面,RC越高表明預(yù)測出的評分?jǐn)?shù)占測試集評分?jǐn)?shù)的比例。如圖7所示,4種算法的評分覆蓋率依次升高,UBCF評分覆蓋率最低,本文算法的評分覆蓋率最高,且為87.05%,相較于Merge3的52.66%顯著提高了34.39%,表明本算法在對冷用戶的推薦面更廣;在F1方面,F(xiàn)1越高表明算法的穩(wěn)定性越好,能越好地對冷用戶進行個性化推薦。如圖7所示,4種算法的F1逐漸提高,其中,UBCF的推薦性能最低,后3種算法較UNCF有了明顯提高,并且本文算法相對于Merge3算法在F1上提高了32.12%,表明本文算法在對冷用戶推薦上的穩(wěn)定性更好。因此,本文提出的UMTCRA在冷啟動用戶集下的推薦效果優(yōu)于其他對比算法。
圖7 不同推薦算法的實驗結(jié)果對比Fig.7 Comparison of experimental results of different recommendation algorithms
引入信任關(guān)系是目前解決傳統(tǒng)協(xié)同過濾算法中用戶冷啟動問題行之有效的方法,而僅使用二值信任或僅從單一方面估計用戶信任大大降低了信任估計的準(zhǔn)確度,導(dǎo)致對冷啟動用戶的推薦效果不佳。鑒于此,本文提出多維度信任度量模型用于量化用戶信任,該模型以用戶的直接信任和間接信任為信任估計的基礎(chǔ),考慮用戶在信任關(guān)系圖局部非對稱信任和全局聲望對用戶信任的影響,得到用戶的綜合信任度;并將其與傳統(tǒng)協(xié)同過濾中的用戶評分相似線性融合。試圖通過提高用戶信任估計的準(zhǔn)確度來提高算法對冷啟動用戶的推薦質(zhì)量。實驗表明,該算法提高了對冷啟動用戶的推薦精度和覆蓋率,整體性能表現(xiàn)穩(wěn)定,明顯改善了對冷啟動用戶個性化推薦的質(zhì)量。本文在計算用戶信任時,未考慮到時間因素對用戶間信任關(guān)系的影響,用戶間的信任值會隨著時間發(fā)生波動。因此,引入時間函數(shù)到信任度量中提高用戶間信任估計的準(zhǔn)確度將是我們未來的工作。