基于用戶信任及推薦反饋機制的社會網絡推薦模型

翟 鶴 劉柏嵩

(寧波大學信息科學與工程學院 浙江 寧波 315211)

?

基于用戶信任及推薦反饋機制的社會網絡推薦模型

翟 鶴 劉柏嵩

(寧波大學信息科學與工程學院 浙江 寧波 315211)

社會網絡包括以興趣為核心的興趣網絡和以信任為核心的信任網絡。如何利用社會網絡中用戶信任與興趣相似的好友的項目數據來擴展用戶本身的項目數據集，緩解用戶數據稀疏性，利用目標用戶的好友的項目評分數據為其產生推薦，是研究的重點。和傳統的推薦方法相比，提出一種改進模型SIMTM(Similar and Trust Model)來提供用戶更加高效的推薦體驗。該模型融合用戶興趣度和信任度作為初始親密程度，根據融合后的好友網絡進行推薦，同時根據推薦反饋，來不斷地優化用戶的項目評分數據集，使得親密的用戶好友更加親密，過濾掉用戶的普通好友，優化用戶之間的興趣和信任關聯；并重新計算用戶之間的親密程度形成融合用戶與其好友的融合網絡，直至前后兩次根據親密程度得到的推薦結果相近，根據得到的最優的親密程度構建融合網絡來進行推薦。實驗結果表明，該模型在數據稀疏的情況下，能有效提高用戶推薦的準確率和覆蓋率。

社會網絡 興趣網絡 信任網絡 融合網絡 推薦反饋 信任更新

0 引 言

隨著現代科技及互聯網技術的發展，人與人之間的原有的物理活動，逐漸向互聯網等虛擬空間發展，人與人的社交活動也全面帶入了在線社交時代。在線社交網絡已經成為了人與人交往的必不可少的手段，也衍生了很多很優秀的在線社交平臺，如Facebook、Twitter、國內的QQ和新浪微博等。在這種背景下，基于社交網絡的個性化推薦，已成了傳統的推薦方法的有效補充，也引起廣大的研究人員的關注。在現實社會中，人們更相信來自自己身邊的人，自己好友的推薦，人們也會在社交網絡中，更多的與自己信任的人，或者與自己興趣相同的人進行交流。如何將社交網絡引入到個性化推薦當中，為用戶提供基于社交網絡的推薦，以便提高推薦結果的質量，是社交網絡個性化推薦方法研究的熱點和難點。

基于社交網絡的推薦可以分為兩類：基于信任的推薦和基于信任及興趣的推薦。而絕大部分的推薦，都是純粹的基于信任的傳遞。基于信任的傳遞又可以在信任傳遞、信任提取兩個方面進行改進。在信任傳遞方面，2004年，Massa等[1]首先將信任引入到推薦系統當中，提出利用用戶信任關系的傳遞，從而為用戶匹配更多的鄰居，一定程度上解決了協同過濾出推薦中存在的數據稀疏性問題，并提出了信任感知的推薦系統框架。將信任傳播模型引用到協同過濾中。由于信任度傳遞，提高了用戶預測的精確度和覆蓋率，并在一定程度上解決了冷啟動的問題[2]。胡福華提出一種基于可信相似度傳遞的協同過濾算法,該算法在用戶相似度傳遞過程中，考慮用戶之間信任度，可以提高用戶相似度傳遞過程中推薦的準確度。但是，由于考慮的是興趣在信任中傳遞，所以導致很多高信任的用戶在傳遞過程中遺失，而事實上，基于信任的推薦比基于興趣的推薦更可靠[9]。在信任提取方面，Golbeck用信任關系來定量分析社交網絡中的社會關系，提出了信任網絡，開發了個性化的電影評論網FilmTrust，利用社會網絡中的信任關系作為電影評分的權值，從而為用戶提供更加準確可信的電影推薦，但是由于未考慮用戶之間的興趣關聯，因此，用戶的推薦體驗較差[3-5]。郭艷紅等采用用戶評價個數和對其他用戶的推薦次數建立信任模型，并將此模型應用到協同過濾推薦算法中，提高了推薦算法的準確率，而在實際應用中，由于用戶對商品的評價數據非常稀少，因此該方法的推薦結果不夠精確[6]。Bedi等人根據蟻群算法中信息素更新算法提出了用戶間信任值的動態更新算法，但是這種方法的信任初始值是通過用戶之間的興趣度和雙方共同評價數獲取到的，在用戶數據稀疏的情況下，這種方法存在嚴重的缺陷[8]。王英等人提出利用社會學理論的社會等級理論和同質性理論構建信任關系預測模型。該方法有效地解決了數據稀疏性問題,還針對用戶所屬的不同領域實現了信任關系的預測。和其他方法相比，此方法具有較高的信任關系預測精度，但是由于算法的時間復雜度和空間復雜度較大，無法大規模應用到推薦領域[10]。上述的方法都是基于信任的推薦，沒有考慮用戶之間的興趣關聯，無法保障為用戶提供有效的、感興趣的商品。而綜合考慮信任和興趣的推薦，Gao等融合社交網絡和改進CF算法，提出一個混合型推薦系統，用戶間直接信任值由用戶自身給出，間接信任值由基于信任傳遞距離和最長傳遞距離的公式加權算得[7]。這種信任計算方式比較主觀，用戶之間的直接信任關系是通過用戶直接給出的，但是在現實的電商平臺，電影播放領域，以及音樂推薦領域中，用戶直接給出直接信任值的情況是非常稀少的，該方法實用性不足。張富國對基于社交網絡的推薦進行了系統性的闡述[11]。

1 模型構建

用戶往往選擇自己信任的，或者與自己興趣相關的社交團體，社交團體中的用戶往往相互影響。并且由于推薦系統的局限性，如何緩解用戶數據稀疏性一直都是推薦系統的熱點和難點。而如何利用社交網絡來緩解推薦系統的數據稀疏性，并利用好友的項目評分數據來對用戶進行推薦，是本文考慮的重點。

本文提出一種同時考慮用戶的興趣相似度和信任關系的模型SIMTM。該模型融合用戶的興趣網絡和信任網絡,作為衡量用戶親密程度的標志；同時在興趣網絡中，采用共同項目評分個數作為調和權重，校正用戶之間的興趣度；對信任度采用迭代的方式進行推薦反饋，得到一個最終的融合用戶興趣及信任的，有效表達用戶之間親密程度的融合網絡，而信任度的初始值，是通過隱形方式獲得，符合絕大部分的電商平臺以及其他的相應的推薦領域。通過這樣一種方式，提高對目標用戶推薦結果的精確度和覆蓋度。

在推薦系統中，用戶集U={u1,u2,…,un}，項目集I={i1,i2,…,im}，每一個用戶u對項目集的項目進行評分，得到用戶項目評分用rui表示，rui一般用1～5表示。在基于信任的推薦系統中，用戶與用戶之間構建一個信任網絡，用tuv表示用戶u對用戶v的信任度。信任度的取值范圍一般在[0,1]。社交網絡融合信任網絡和興趣網絡，可以用圖表示：G=,其中，TS={(u, v),u∈U, v∈V},其中，u表示用戶節點，v表示用戶與用戶之間的融合信任與興趣的關聯關系。

1.1 融合網絡

從社會學理論出發，任何一個單純的信任網絡或者興趣網絡都不是一個完整的社交網絡。在現實世界中，人與人之間的社交圈應包括興趣關聯和信任關聯兩部分，因此，只有融合了信任關系和興趣關系，才更符合現實世界中的社交網絡。

在本文中采用兩種方式計算融合兩種關聯之后的親密程度，親密程度用Itc表示，興趣度用sim表示，信任度用tru表示。

方法一簡單的線性加權

其公式為：

Itc(u,v)=αsim(u,v)+(1-α)tru(u,v)

(1)

當α=0，Itc(u,v)=sim(u,v)；當α=1；Itc(u,v)=tru(u,v)。

方法二通過用戶信任放大用戶偏好

當在用戶的信任網絡中，其信任的用戶同時與其具有相似的興趣偏好，則強化用戶對該用戶的信任。

其公式為：

Itc(u,v)=max{sim(u,v)·(1+tru(u,v)),tru(u,v)}

(2)

對于冷啟動用戶，和其他用戶的興趣偏好為0,此時只考慮用戶之間信任度。

其中，sim(u,v)采用皮爾遜相關系數計算用戶之間的興趣度，并采用校正系數校正用戶之間的興趣度。其公式為：

(3)

其中：

(4)

采用校正系數是為了避免由于用戶共同項目數差距比較大而造成的相似度的不準確性。

得到興趣度后，計算用戶對項目的預測評分，其公式為：

(5)

對于式(2)中的tru(u,v)表示用戶之間的信任度。由于用戶之間的信任度大多數情況下無法直接從用戶中獲取，本文采用隱式的方法來獲取用戶之間的信任度。直接信任度的計算公式為：

(6)

其中，SuccessSet(u,v)表示用戶u對用戶v的推薦成功數，RecommandSet(u,v)表示用戶u對用戶v的推薦總次數。ru,v表示用戶u對用戶v的推薦總次數，而ru,max表示用戶u向其好友網絡中的好友的最大推薦次數。

推薦成功的定義為：

(7)

間接信任度分為單路徑下間接信任度和多路徑下間接信任度。在本文中，單路徑下的信任傳遞信任度，采用直接信任度相乘的方式得到。假設用戶u和用戶v存在n個用戶，當信任傳遞距離小于閾值δ，則得到的單路徑下的間接信任度為：

Tu,v=Tu,s1·Ts1,s2,…,Tsn-1,sn·Tsn,v

(8)

當用戶之間存在多條路徑，多中間節點的情況下，對并聯信任傳遞的間接信任計算公式為：

(9)

其中，a表示用戶u和v的中間節點。

當用戶與好友之間同時具有直接信任關系和間接信任關系時，以直接信任關系為準。

得到最終的融合用戶信任和興趣關聯的親密程度之后，篩選前K個值最高的用戶，形成鄰居集合，并根據親密程度進行推薦，推薦公式為：

(10)

SIMTM是融合興趣關聯和信任關聯來模擬現實世界中的好友關系，并產生推薦。初始親密程度Itc(u,v)采用式(1)或式(2)計算得到，并將篩選取到的K個值，得到以目標用戶為中心的融合網絡，并計算目標用戶的直接節點的融合網絡，以此類推，得到以目標用戶為核心的、用戶資源豐富的融合網絡，并在此融合網絡上，進行個性化推薦。

1.2 算法描述

由于數據的稀疏性，單純從現有的數據中計算得到用戶的興趣度很小，不足以呈現出用戶的興趣關聯，而由此得到的信任關聯也不能真實有效地體現用戶之間的信任關系。而且，用戶之間的信任關系，并不是一成不變的，而是會隨著推薦結果的反饋而進行動態更新，因此，本文中，引入了推薦反饋這個概念。

定義1親密程度是指融合了用戶信任和興趣關聯的，用來衡量用戶與其好友之間的友好程度的指標。

定義2推薦反饋是指所有向u推薦的用戶中，若用戶v向用戶u推薦成功，則把用戶v的項目評分通過用戶u及用戶v的親密程度作為權重，擴展到用戶u的項目評分集，并重新計算用戶v對用戶u的親密程度。

本文中，根據得到的初始親密程度進行推薦，并根據推薦成功率進行反饋。設置閾值δ，取推薦成功率大于δ的進行反饋。

由于ACM的國際大學生程序競賽，提出的社交網絡中距離大于2的節點之間的關系對于鏈接預測的影響很小。而且在以前的基于信任的推薦算法中，證明了這一點，因此，本文中的好友距離默認為2。

好友之間的興趣度往往是十分相似的，因此通過推薦反饋來填充用戶的項目評分矩陣，來緩解用戶項目評分數據的稀疏性。根據填充后的用戶評分矩陣，重新計算用戶之間的興趣度、信任度及親密程度。直至兩次親密程度相差不大為止，即：

(11)

系統框架如圖1所示。

圖1 系統架構圖

算法根據上述算法思想，設u為目標用戶，U為用戶集合，I為項目集合，U_I為用戶項目評分集合。整個算法計算流程如下：

1) 從用戶集合U中查找目標用戶u的好友集合；

2) 遍歷好友集合，去數據集中查找每個好友的直接好友集合；

3) 根據步驟1)和步驟2)得到的好友集合，構建目標用戶u的好友網絡；

4) 計算好友網絡中，任意兩個直接相連的節點的興趣度；

5) 根據計算得到的興趣度，按式(5)產生推薦；

6) 根據推薦結果和式(6)計算節點之間的信任度；

7) 根據計算得到的信任和興趣度，采用式(1)和式(2)，計算融合二者關系的親密程度；

8) 選擇topK的親密程度，擴展好友網絡中相應好友的用戶項目評分數據，并去除掉未選擇的親密程度的好友的邊，重新回到公式步驟4)進行計算；

9) 前后兩次計算得到親密程度的差的絕對值。若小于閾值，則迭代結束；否則繼續回到步驟4)進行計算；

10) 根據最終得到的最優親密程度，采用式(10)進行推薦，選擇topK個評分，推薦給目標用戶。

上述算法中，首先得到用戶u的直接好友集，并分別得到好友集中的每個用戶的直接好友集，并由此得到以用戶u為核心的好友網絡，此時得到的網絡是一個有向有環圖，對應步驟為1)-3)；在好友網絡中，分別計算任意兩個好友之間的興趣度，并根據得到的用戶項目評分做出推薦并計算任意好友之間的信任度，對應步驟為4)-6)；得到興趣度和信任度后計算親密程度，得到親密程度后選取topK，去除未選擇的親密程度的好友之間的邊，并根據親密程度填充好友網絡中的用戶項目將評分，重新回到式(4)計算，直到兩次親密程度差值小于某個范圍，則親密程度計算完成，并根據親密程度產生推薦。

本方法中，通過好友之間的興趣擴展，有效地緩解了用戶項目評分的數據稀疏性。與傳統的推薦方法相比，本文中由于加入了動態更新的迭代方法，因此，該算法的時間復雜度更高，但是也正是由于動態更新，該方法有效地保證推薦結果的準確性。

2 實驗結果與分析

2.1 數據集

本文采用Epinions數據集來驗證本次模型的可用性。Epinisons數據集是目前公開可用的、為數不多的既包含用戶好友關系、又含有用戶項目評分數據的數據集[15]。Epinions數據集是來源于Epinions網站的真實數據。該數據集中包含兩個文件，第一個為用戶評分文件，包含49 289個用戶對139 738個商品的664 825個評分。另一個為好友關系文件，包含了49 289個用戶間487 181個信任關系。為了避免由于冗余數據而造成的數據孤點，本文選取評分分布與全體用戶評分分布大致一致的用戶、評分人數分布與全部商品評分人數分布大致一致的商品作為實驗數據集。將實驗數據集的80%設置為訓練數據，余下的20%為測試數據。

2.2 評價指標

為了驗證本文中提出的模型，本文采用推薦準確率和覆蓋率作為評測指標。

2.2.1 準確率

平均絕對誤差(MAE)是推薦系統或者推薦算法最常用的評價指標之一，用來度量為用戶預測行為的能力。MAE是通過計算項目的預測評分值和項目實際評分的差值的絕對值的平均得到。MAE越小，表示算法的推薦結果越好。MAE的計算公式為：

(12)

其中，Ri表示用戶u對項目i的推薦評分，Pi表示項目的實際評分，n表示項目的預測個數。

2.2.2 覆蓋度

覆蓋率是描述一個推薦系統對物品長尾的挖掘能力。簡而言之，是推薦系統能夠推薦出來的物品占所有物品的比例。推薦系統，目的是為了給用戶推薦用戶感興趣的商品，而不是所有商品。因此，在本文中，對覆蓋率公式進行調整，其分母調整為用戶與其所有好友的項目評分數據取并集，用Nall表示。修改后的公式為：

(13)

其中，NIR表示用戶的推薦項目集個數，Nall表示用戶與其所有好友的所有項目的個數。

2.3 實驗及實驗結果

本文實驗分為兩個部分，第一個實驗用于確定式(12)的α的值；第二個實驗用于比較本文改進的推薦算法和傳統的協同過濾算法以及基于信任的協同過濾算法的平均絕對誤差，在實驗之前，需先對數據集的評分數據進行歸一化處理。

2.3.1 融合系數α確定

本實驗目的在于通過同一個用戶的不同鄰居數在得到最優的α值，設置鄰居個數分別為5、10、20。通過調整后的鄰居個數重新計算推薦算法的平均絕對誤差，根據MAE來選擇最優值，得到的結果如圖2所示。

圖2 不同α值不同好友數下的MAE對比

從圖2可以看出，隨著鄰居數的增加，MAE變小，這表明用戶好友越多，其推薦結果越準確。并且可以看出，當α=0.4的時候，計算得到的平均絕對誤差最小，得到最后的推薦效果。

2.3.2 推薦結果比對

為了驗證本文提出的改進算法的有效性，本文采用對比本文的改進算法和基于用戶的協同過濾算法以及基于信任的協同過濾算法的平均絕對誤差和覆蓋率來驗證算法優劣。其中，UCF和TrustD的實驗數據通過相應的算法在Epinions數據集上計算所得，部分實驗結果記錄在表1中。

表1 不同好友數下的三種算法效率對比

在不同的好友數下驗證三個算法的時效性，其MAE數據對比用柱狀圖表示，如圖3所示。

圖3 不同好友數下的三種算法MAE對比

從圖3可以看出，隨著用戶好友數的增加，三個算法的MAE逐漸下降，并且本文提出的改進算法的MAE一直小于另兩個算法。當用戶的好友數超過20以后，算法的MAE逐漸趨于平緩。這是因為數據的稀疏性，目標用戶的好友用戶較少，導致得到的用戶的相似用戶較少，構建的鄰域集合較小，因此無法得到足夠的評分數據來進行預測。在本文中，通過迭代，得到最終的融合后的親密程度，并且把好友用戶的一些評分數據通過親密程度作為權重添加到目標用戶的評分集中，擴展了用戶的數據，極大地緩解了推薦系統數據稀疏性的問題。隨著好友數的增加，通過迭代擴展的數據集也越來越豐富，得到的推薦效果也越來越好。當好友數大于某一范圍后，用戶的評分集飽滿，因此得到的MAE也趨于平緩。

覆蓋率結果用柱狀圖表示，其結果如圖4所示。從圖4可以看出，隨著用戶好友數的增加，推薦結果的覆蓋率隨之上升，這是因為當用戶的好友數增多，得到的用戶的相似用戶就隨之增多，從而使得構建的鄰域集合增大，對用戶推薦的項目也隨之增多。當用戶增加到一定數量以后，覆蓋率的增加隨之平緩。因為用戶及用戶好友的項目，隨著人數的增多，用戶的項目集趨于飽和，因此覆蓋率隨之平緩。因此，本文提出的改進算法明顯優于另兩種算法，這是因為采用本文提出的算法擴展了用戶的項目集，擴展后的項目集包含了其他好友的項目。隨著好友的增加，SIMTM的覆蓋率增加的斜率也比另兩種算法更大。

圖4 不同好友數下的三種算法的覆蓋率對比

從覆蓋率和MAE的結果圖可知，本文提出的改進算法SIMTM明顯優于另兩種算法。和傳統的UCF相比，本文考慮用戶的社交網絡，有效縮小了用戶的好友數，避免用戶過多而造成的時間復雜度和空間復雜度過大。和純粹的基于信任的推薦算法相比，本文考慮用戶之間的興趣度，選取那些與目標用戶既信任又興趣一致的用戶進行推薦，明顯優于只考慮信任的推薦算反。并且，本文采用了推薦反饋來進行動態更新用戶的項目評分數據集，很好地緩解了數據稀疏性的問題，而且在覆蓋率方面，本文提出的算法明顯優于另兩種算法，在解決長尾問題上，有明顯優勢。

3 結 語

社交網絡包括由興趣建立的興趣網絡和由信任構建的信任網絡兩方面，本文提出一種改進的推薦算法SIMTM。該算法融合了用戶興趣度和信任度，并根據融合的親密程度對用戶評分數據進行更新，通過不斷的迭代過程，得到最優的親密程度，并根據親密程度進行推薦。根據實驗結果顯示，該算法在推薦結果上，明顯優于傳統的基于用戶的協同過濾算法和純粹的基于信任的推薦算法，并且很好地解決了用戶評分數據稀疏的問題及長尾，也證明了當用戶好友數足夠的情況下，能得到最優的推薦結果。該算法沒有考慮到用戶之間的不信任因素以及信任的時間衰減等因素，并且由于該算法采用了一種迭代的計算過程，所以算法時間復雜度偏大。而且由于本算法是采用的融合社會網絡中好友的一些評分數據，因此在用戶數據隱私性問題上，也需多加考慮。在后續的工作中，會重點處理這些問題，爭取進一步完善算法。

[1] Massa P,Bhattacharjee B.Using Trust in Recommender Systems:An Experimental Analysis[J].Lecture Notes in Computer Science,2004:221-235.

[2] Chen X C,Liu R J,Chang H Y.Research of Collaborative Filtering Recommendation Algorithm Based on Trust Propagation Model[C]//Computer Application and System Modeling (Iccasm),2010 International Conference on.2010:V4-177-V4-183.

[3] Golbeck J.Computer Science-Waving a Web of Trust[J].Science,2008,321(5896):1640-1641.

[4] Golebec J.Computing and Applying Trust in Web-Based Social Networks[D].University of Maryland,USA,2005.

[5] Kuter U,Golebeck J.Sunny:A New Alogorithm for Turst Inference in Social Networks Using Probabilistic Confidence Models[C]//Proceedings of The 22nd National Coference on Artificial Intelligence.Coulumbla,Canada,2007:1377-1392.

[6] 郭艷紅,鄧貴仕,雒春雨.基于信任因子的協同過濾推薦算法[J].計算機工程,2008,34(20):1-3.

[7] Gao Y,Xu B,Cai H.Information Recommendation Method Research Based on Trust Network and Collaborative Filtering[C]//E-business Engineering (Icebe),2011 Ieee 8th International Conference on IEEE,2011:386-391.

[8] Bedi P,Sharma R.Trust Based Recommender System Using Ant Colony for Trust Computation[J].Expert Systems with Applications,2012,39(1):1183-1190.

[9] 胡福華.基于可信相似度傳遞的協同過濾算法研究與應用[D].浙江大學,2011.

[10] 王英,王鑫,左萬利.基于社會學理論的信任關系預測模型[J].軟件學報,2014(12):2893-2904.

[11] 張富國.基于社交網絡的個性化推薦技術[J].小型微型計算機系統,2014,35(7):1470-1476.

[12] Guo L,Ma J,Chen Z.Learning to Recommend with Multi-faceted Trust in Social Networks[C]//International Conference on World Wide Web Companion. International World Wide Web Conferences Steering Committee,2013:205-206.

[13] De Meo P,Nocera A,Terracina G,et al.Recommendation of Similar Users,Resources and Social Networks in a Social Internetworking Scenario[J].Information Sciences,2011,181(7):1285-1305.

[14] Zhang J,Cohen R.A Framework for Trust Modeling in Multiagent Electronic Marketplaces with Buying Advisors to Consider Varying Seller Behavior and the Limiting of Seller Bids[J].Acm Transactions on Intelligent Systems & Technology,2013,4(2):55-73.

SOCIAL NETWORK RECOMMENDATION MODEL BASED ON USER TRUST AND RECOMMENDATION FEEDBACK MECHANISM

Zhai He Liu Baisong

(College of Information Science and Engineering,Ningbo University,Ningbo 315211,Zhejiang,China)

Social networks include the interest network taking the interest as core and the trust network taking the trust as core. The research focus of this paper is that how to use the projects data of the friends in social networks with similar trust and interest to expand the project dataset of user’s own, to alleviate the sparsity of user data, and to use the data of project rating score of target user’s friends to generate recommendation for it. Compared with traditional recommendation methods, the paper presents an improved SIMTM(Similar and Trust Model), which can provide more efficient recommendation experience. The model fuses interest and confidence as the initial intimacy, and makes recommendation according to the fused networks of friends, at the same time it constantly optimises the project rating score dataset according to the recommended feedbacks, this makes user’s close friends be more intimate while filtering out user’s ordinary friends, and optimises the association of interest and trust between user, moreover it re-calculates the intimacy degree between users to form a fusion network which fuses the user and user’s friends until the twice recommendation results before and the after derived from intimacy degree are close, and then constructs the fusion network based on the derived optimal intimacy degree for recommendation. Experimental results show that, the model can effectively improve the accuracy and coverage of recommendation of users, especially in the case of data sparsity.

Social network Interested network Trust network Fusion network Recommendation feedback Trust update

2015-06-27。翟鶴，碩士生，主研領域：數據挖掘。劉柏嵩，研究員。

TP391

A

10.3969/j.issn.1000-386x.2016.11.060