基于增強相似度和隱含信任的推薦算法①

鄭 鵬, 王應明

(福州大學 經濟與管理學院,福州 350108)

引言

互聯網的高速發展以及電子商務的迅速崛起,有力地促進了推薦系統的研究發展. 其中,協同過濾(Collaborative Filtering,CF)推薦算法是推薦系統中應用最廣泛、最成功的推薦技術之一[1]. 雖然協同過濾推薦算法取得了一些成果,但是它同時也存在數據稀疏性、冷啟動和擴展性等一系列問題[2].

現實生活中,人們更愿意相信好友推薦的物品,因此推薦系統如果結合用戶的信任關系信息,則能夠進一步提高推薦精度. 隨著在線社會網絡的普及,利用社會網絡中用戶之間的信任關系來緩解傳統協同推薦存在問題的信任感知推薦系統(TARS)成為推薦領域新的研究熱點[3-5]. Massa等[6]提出使用信任度取代相似度的TARS系統,根據信任網絡傳播來估計一個信任度的權值,該方法增加了覆蓋范圍(可預測的評分總數),并未降低精確度(預測誤差),但需要用戶的顯式信任聲明. Yuan等[7]根據隱含信任網絡的小世界特性,提出一種基于用戶相似度的隱含信任感知推薦系統(ITARS),該方法雖然不需要用戶提前對自己在整個信任網絡中的信任關系做出聲明,但是該方法需要根據用戶之間的相似度構建隱含的信任網絡,并估算信任網絡的平均路徑長度. 郭艷紅等[8]提出以用戶的評價個數和為他人提供推薦的次數為要素的可計算的信任模型推薦算法. 該算法改變傳統推薦過程中,用戶之間的相似度唯一決定預測結果的現狀,提高了推薦的精度,但該算法無法對沒有鄰居的用戶做出推薦. 杜永萍等[9]在傳統基于用戶的協同過濾推薦算法的基礎上,引入信任關系計算,設計并構建一個集用戶聲望信任和用戶局部信任的混和信任網絡,實現了對協同過濾推薦算法稀疏性問題的優化,但該方法未考慮用戶的全局信任值. 張俊等[10]提出一種融合用戶興趣相似性和評分相似性的協同過濾推薦算法,該算法引入興趣度進行相似度計算,并通過引入專家信任度的概念對用戶未評分項目進行評分預測填充,但該算法需要進行惡意用戶檢測,算法復雜度較大. 楊秀梅等[11]提出融合用戶信任模型的協同過濾推薦算法,該算法考慮用戶評分相似性和用戶之間信任關系對推薦結果的影響,利用層次分析法實現用戶信任模型的構建. 但該算法在計算用戶信任度過程中引入信息過少,導致用戶信任模型過于簡單. 陳婷等[12]提出一種可信推薦模型(Trust-PMF),該算法首先結合全局信任和局部信任,利用信任的傳播性質對信任關系進行建模. 然后,設置推薦權重,綜合考慮相似度和信任度來構建用戶間的偏好關系,篩選出鄰居. 最后,將基于記憶的協同過濾思想和社交網絡的信任關系融入概率矩陣分解模型,但該算法同樣需要用戶提供信任聲明. 王瑞琴等[13]提出一種基于多元社交信任的協同過濾推薦算法,該算法借鑒社會心理學中的信任產生原理,提出基于多個信任要素的信任度計算方法,基于用戶間的綜合信任度選取可信鄰居,完成對目標用戶的個性化推薦,但該算法的時間復雜度較高. 針對上述問題,本文提出一種基于增強相似度和隱含信任的協同過濾算法(ETCF),在考慮用戶興趣度的同時,不需要用戶提供顯式聲明,該算法不僅提高了推薦準確度和覆蓋率,而且彌補了傳統算法的不足,有效緩解了數據稀疏性問題.

1 基于增強相似度和隱含信任的協同過濾推薦算法

協同過濾算法的關鍵在于用戶之間的相似度測量,但是由于數據稀疏性問題的存在,使得傳統的相似度測量方法都存在著缺陷. 本文的基本思路是將傳統的相似度度量方法和信任結合,采用增強的用戶相似度和隱含信任來計算用戶之間的相似度.

1.1 增強的用戶相似度

計算用戶相似度的方法有很多,比較傳統的方法有皮爾遜相關(PCC)、受約束的皮爾遜相關(CPC)、均方偏差(MSD)和Jaccard相似度. 本文使用均方偏差和Jaccard相似度進行用戶相似度的度量.

均方偏差(MSD)的公式如下：

JMSD相比傳統的皮爾遜相關系數(PCC)、余弦相似(Cosine)、調整的余弦相似度(Adjusted Cosine)具有明顯的優勢,但是還是存在著一個問題,那就是沒有考慮用戶的評分偏好. 假如現在有三個用戶,他們對四項物品的評分值分別為U1(4,3,3,4),U2(2,1,-,-),U3(4,2,-,-),這時候使用JSMD計算出的相似度,用戶U1和U3的相似度小于U2和U3的相似度,這顯然不符合實際情況,主要的原因就是沒有考慮用戶的評分偏好問題. 有的用戶喜歡打高分,有的用戶喜歡打低分. 考慮到這個問題,本文引入了一種偏好相似度,其公式為：

基于以上的情況,本文提出一種新的基于用戶的相似性度量方法,公式如下：

1.2 隱含信任

在實際的數據集中兩個用戶之間可能不存在共同評分的項目,這種情況下使用傳統的相似性度量方法顯然不可行,本文引入信任機制來解決用戶之間沒有共同評分項的問題.

1.2.1 信任機制

信任在人們的日常生活中占據著舉足輕重的地位,但它是一個相對模糊的概念,涉及到的方面很多,以至于至今都未能給出一個令人信服的定義. 雖然信任的定義難以確定,但目前信任有一些公認的特性,包括主觀性、不對稱性、傳遞性、動態性等,這些屬性彼此之間是相互關聯的,所以它們之間出現交叉或沖突等情況是正常現象

下文將給出本文對信任的定義.

定義1. 信任是指接受推薦者對提供推薦者特定行為的主觀可能性預測,它是一種單向、相對、局限在一定范圍內的主觀反映.

定義2. 直接信任是指兩個用戶根據曾經直接交往的經驗建立的信任關系.

定義3. 間接信任是指兩個用戶通過第三方的推薦建立的信任關系.

定義4. 信任度是根據用戶所處的情境以及信任的屬性,量化用戶間信任程度后的信任值.

1.2.2 用戶之間的直接信任

直接信任度來源于兩個用戶曾經交互的經驗積累,本文的直接信任度通過活動用戶相似度來度量,例如,如果用戶a和用戶b的相似度比較大,那么我們可以認為二者屬于同一類,是可以相互信任的. 對用戶的信任推導,我們使用JMSD,也就是說用戶之間的直接信任度：

從中可以很容易的看出如果兩個用戶之間的共同評分項非空,二者之間的直接信任度非零,否則二者之間的信任度為零. 在現實生活中,人們之間的信任程度受到交互經驗的影響,推薦系統中用戶間的信任度也會隨著項目交互結果的變化而逐漸變化. 本文根據用戶評分的均值將用戶評分分成兩類,即積極評分和消極評分. 如果評分值不小于用戶的評分均值就被認為是積極評分,相反則被認為是消極評分. 當用戶u和v對項目i的評分同為消極評分或積極評分時,交互是成功的,反之是失敗的：

公式中1表示交互成功,0表示交互失敗. 交互成功和失敗分別用sus和fal表示若交互成功則sus+1,否則fal+1. 結合了用戶交互經驗的直接信任度計算公式如下：

1.2.3 間接信任的計算

在社會信任網絡中,當2個用戶之間沒有直接的信任關系時,就需要通過信任傳播從信任網絡中推斷出用戶之間的間接信任關系. 例如,假定用戶a信任用戶b,并且用戶b信任用戶c,通過使用信任傳播矩陣,可以推導出用戶a在某種程度上信任用戶c,在中間用戶多于一個的情況下,就需要使用信任聚合方法來合并不同的信任. 一般的信任聚合方法有： 最大值、最小值、均值. 其中加權平均聚合方法相比其他方法被認為具有更好的性能[15],加權平均聚合的基本思想是確保距離源用戶比較近的信任路徑上的信任值獲得比較大的權值. 對任意的用戶u,v,w,間接信任計算公式如下：

綜合公式(8)和公式(9),可以得到兩個用戶之間的信任值,該信任值是通過評分矩陣計算得出來的,不同于TARS中用戶的顯式聲明,被稱為隱含信任. 表示為,公式如下：

1.2.4 選擇鄰居

對于鄰居的選擇過程,根據上一步計算得到的用戶相似度和間接信任度,采用Top-N方法選擇活動用戶最信任或者與用戶相似的前N個鄰居.

1.2.5 計算加權評分

評分預測是推薦系統中最重要的步驟,本文的評分預測采取融合信任度與相似度的方式進行加權,計算公式如公式(11)：

2 算法流程

將上述所建立的用戶增強相似度以及用戶隱含信任度相結合,形成了本文新的協同過濾算法. 算法的具體步驟如下文.式(1)(2)(3)計算用戶的相似度JMSD,建立用戶相似度矩陣,根據公式(4)計算用戶的偏好相似度,最后根據公式(5)計算用戶的增強相似度

步驟2. 根據公式(7)計算用戶的交互成功和失敗項目集合,并根據公式(8)建立用戶的直接信任矩陣

步驟3. 根據用戶直接信任矩陣,利用公式(9)計算用戶的傳播信任,并根據公式(10)計算用戶的隱含信任,建立隱含信任矩陣.

步驟4. 確定用戶的鄰居數目N,根據公式(11)計算用戶的預測評分值進行降序排列,將前N個項目推薦給用戶.

3 實驗與分析

3.1 實驗數據集

本實驗基于目前推薦系統研究中經常使用的由美國Minnesota大學的GroupLens研究小組提供的MovieLens100 k(943個用戶、1682部電影、100 000條評分)和Epinions(49 290個用戶、139 738個項目、664 824條評分)數據集作為測試數據集. 兩個數據集的數據稀疏性(未評分過的項目數占整個數據集的比例)分別為93.7%和99.9%. 兩個數據集評分范圍為1-5. 實驗中將數據集按照1：4的比例劃分成兩個部分：前者作為測試集合,測試模型的性能,后者作為訓練集.

3.2.1 平均絕對誤差

本實驗采用當前被廣泛使用的平均絕對誤差(Mean Absolute Error,MAE)度量推薦算法的性能,它屬于統計精度方法. 它的原理是通過對比用戶對項目預測評分與用戶對項目實際評分的偏差,進行算法預測準確性的度量. 公式如下：

其中Pi為用戶對目標的預測評分,Ri為實際評分,n代表預測評分的次數. 從公式(12)可以看出,MAE值越小,算法預測的精確性越高.

3.2.2 覆蓋率

覆蓋率(Coverage)用來衡量一個算法能夠預測的項目占所有項目的百分比,在推薦系統中Coverage衡量的是推薦系統為用戶推薦的項目集對用戶興趣的覆蓋范圍,Coverage值越大,算法的全面性越好,Coverage的公式如下：

其中P(u)代表推薦系統為用戶u推薦的項目集合,R(u)代表用戶u在測試集上的評分集合.

3.3 實驗結果分析

3.3.1 參數 λ對MAE的影響

圖1 不同的λ值下算法的精確度變化 (MovieLens100k)

3.3.2 近鄰數對算法精確度影響

為了進一步驗證所提出的ETCF算法的有效性,2種傳統的算法和兩種改進的傳統算法被選作比較對象： 基于PCC的協同過濾算法,基于Cosine的協同過濾算法,基于SPCC的協同過濾算法以及基于JMSD的協同過濾算法,近鄰數K的取值為10-90. 從圖3可以看出,在MovieLens100k數據集下,隨著鄰居數K的增加,五種算法的精確度都逐漸提高,之后稍有下降,但是從整體上看本文提出的ETCF算法的精確度一直優于其他4種算法. 從圖4可以看出在Epinions數據集下隨著K增加,JMSD、Cosine、PCC三種算法的精確度都逐漸降低,接著逐漸升高,最后趨于穩定. SPCC的精確度隨著K的增加先下降然后逐漸上升. 本文所提出的ETCF算法隨著K的增加逐漸降低,隨后逐漸升高. 但從整體上看,本文提出的ETCF算法的精確度一直優于其他4種算法.

圖2 不同的λ值下算法的精確度變化 (Epinions)

圖3 近鄰數對算法精確度的影響 (MovieLens100k)

3.3.2 近鄰數對算法覆蓋率的影響

圖5和圖6分別為MovieLens100k和Epinions數據集下算法的覆蓋率隨鄰居數k的變化情況,隨著鄰居數K的增加,在兩個數據集下算法的覆蓋率都逐漸提升,但本文的ETCF算法覆蓋率一直優與其他4種算法.

圖4 近鄰數對算法精確度的影響 (Epinions)

圖5 近鄰數對算法覆蓋率的影響 (MovieLens100k)

圖6 近鄰數對算法覆蓋率的影響 (Epinions)

實驗結果分析： 由于Movielens數據集和Epinions數據集的稀疏性比較高,用戶之間的共同評分項較少.Cosine和PCC都是基于用戶之間的共同評分項來計算相似系數,所以性能比較差,SPCC和JMSD考慮了用戶之間共同評分項較少的問題,公式中引入了用戶之間的共同評分作為參考項,因此和傳統的算法比性能上有了一定的提升,但是這兩種算法同樣存在著缺陷,首先沒有考慮用戶評分的興趣度問題,其次沒有考慮兩個用戶沒有共同評分項的問題. 本文提出的EFCF算法在一定程度上解決了上述問題,因此具有較好的性能.

4 結束語

針對推薦系統中的數據稀疏性問題,本文提出基于增強相似度和隱含信任的協同過濾算法,首先對傳統的相似性度量方法進行改進,引入了一種基于用戶偏好和JMSD的增強相似度. 其次,考慮到兩個用戶之間可能沒有共同評分項的問題,提出了一種基于隱含信任的信任傳播模型,在直接信任的計算過程了融入了用戶的交互經驗,然后根據直接信任提出了一種間接信任的計算方法. 最后將用戶增強相似度和信任度分別進行近鄰選擇,然后進行融合. 實驗表明,本文提出的ETCF算法相比傳統算法在推薦精度上和覆蓋率上有明顯的提升,然而該算法傳統相似度和用戶信任度融合的比例問題還需要進一步的探討.

1王立才,孟祥武,張玉潔. 上下文感知推薦系統. 軟件學報,2012,23(1)： 1-20.

2黃創光,印鑒,汪靜,等. 不確定近鄰的協同過濾推薦算法.計算機學報,2010,33(8)： 1369-1377.

3徐守坤,孫德超,李寧,等. 一種結合語義Web和用戶信任網絡的協同過濾推薦模型. 計算機應用研究,2014,31(6)：1714-1718.

4Eirinaki M,Louta MD,Varlamis I. A trust-aware system for personalized user recommendations in social networks. IEEE Transactions on Systems,Man,and Cybernetics： Systems,2014,44(4)： 409-421. [doi： 10.1109/TSMC.2013.2263128]

5Abbas A,Zhang LM,Khan SU. A survey on context-aware recommender systems based on computational intelligence techniques. Computing,2015,97(7)： 667-690. [doi： 10.1007/s00607-015-0448-7]

6Massa P,Avesani P. Trust-aware recommender systems.Proceedings of the 2007 ACM Conference on Recommender Systems. Minneapolis,MN,USA. 2007. 17-24.

7Yuan W,Shu L,Chao HC,et al. ITARS： Trust-aware recommender system using implicit trust networks. IET Communications,2010,4(14)： 1709-1721. [doi： 10.1049/ietcom.2009.0733]

8郭艷紅,鄧貴仕,雒春雨. 基于信任因子的協同過濾推薦算法. 計 算 機 工 程,2008,34(20)： 1-3. [doi： 10.3778/j.issn.1002-8331.2008.20.001]

9杜永萍,黃亮,何明. 融合信任計算的協同過濾推薦方法.模式識別與人工智能,2014,27(5)： 417-425.

10張俊,劉滿,彭維平,等. 融合興趣和評分的協同過濾推薦算法. 小型微型計算機系統,2017,38(2)： 357-362.

11楊秀梅,孫詠,王丹妮,等. 融合用戶信任模型的協同過濾推薦算法. 計算機系統應用,2016,25(7)： 165-170. [doi：10.15888/ j.cnki.csa.005229]

12陳婷,朱青,周夢溪,等. 社交網絡環境下基于信任的推薦算法. 軟件學報,2017,28(3)： 721-731. [doi： 10.13328/j.cnki.jos.005159]

13王瑞琴,蔣云良,李一嘯,等. 一種基于多元社交信任的協同過濾推薦算法. 計算機研究與發展,2016,53(6)：1389-1399. [doi： 10.7544/issn1000-1239.2016.20150307]

14Bobadilla J,Serradilla F,Bernal J. A new collaborative filtering metric that improves the behavior of recommender systems. Knowledge-Based Systems,2010,23(6)： 520-528.[doi： 10.1016/j.knosys.2010.03.009]

15Loll F,Pinkwart N. Using collaborative filtering algorithms as elearning tools. Proceedings of 42nd Hawaii International Conference on System Sciences. Big Island,HI,USA. 2009.1-10.