一種融合本地社交網絡的輕量級可信服務推薦方法

朱文強,鐘元生,徐 軍,李普聰

1(江西財經大學 軟件與通信工程學院,南昌 330013) 2(江西財經大學 現代經濟管理學院,南昌 330013) E-mail:stbrook@aliyun.com

1 引 言

移動通信技術和在線支付技術的成熟發展,促進線上與線下服務高度融合,能滿足用戶各種需求的服務大量涌現.人們可以通過智能手機訂購和使用各種服務,如人們可以通過百度外賣訂購自己喜歡的餐飲;通過e袋洗獲得自己所需要的洗衣服務;通過滴滴打車獲得方便的出行服務.

然而,這些線下服務提供方的規模一般較小,缺乏科學管理制度,因此常常會發生各種服務質量問題1.如2016年的315晚會,便重點曝光了服務平臺“餓了么”的線下餐飲商家所存在的衛生及經營誠信問題1.面對線上服務平臺提供的海量服務,人們在信息不對稱的情況下,常常難以做出正確的選擇,面臨各種風險.因此,出現了大量的服務推薦系統,以幫助人們作出正確的決策.

目前的服務推薦方法可以分為以下幾類,基于內容的推薦方法、協同過濾推薦方法和混合推薦方法[2,3].

其中, 基于

2http://www.advogato.org/

內容的推薦方法是根據用戶的歷史交易信息,推測出用戶感興趣的服務,然后選出相似服務推薦給目標用戶.協同過濾推薦方法則是基于用戶服務評分矩陣,對目標用戶的興趣偏好進行推理,選出偏好相似的用戶作為目標用戶的近鄰,將近鄰感興趣但目標用戶尚未選取的服務推薦給目標用戶.混合推薦方法則是將前兩種方法進行融合,以獲取它們的優勢,彌補其存在的不足.

然而伴隨著服務推薦系統的出現,也出現了針對推薦系統的惡意攻擊行為,如托攻擊,惡意用戶通過復制目標用戶的歷史交易行為及服務評價來提高自身與目標用戶的相似性,然后對某些服務進行惡意評價,即對符合自己利益的服務進行高分評價,而對競爭對手的服務給予低分評價,以達到非法獲利目的[4].

面對服務商家的不誠信行為,以及推薦系統中存在的惡意攻擊,人們常常咨詢其個人社交網絡,以幫助自己選出可靠且優質的服務.目前移動社交軟件的發展,為人們提供了這一基礎.因此,有必要在對推薦方法進行研究時,將用戶的個人社交網絡作為一個重要的參考因素進行考慮.

針對上述問題,本文提出了一種融合用戶本地社交網絡的輕量級可信服務推薦方法,該方法首先對Advogato信任模型進行擴展,構建目標用戶的本地信任網絡,并考慮用戶間的社交圈子相似度、互動程度,計算用戶的局部信任權重,然后融合局部信任權重和用戶的服務評價相似性,進行目標用戶的服務評分預測.基于真實數據集與其他推薦方法的對比實驗表明,該方法不僅具有更高的評分預測精度,還能更有效對抗惡意用戶的托攻擊行為,同時,該方法具有更低的計算復雜度.

本文第2節為相關研究的分析和討論;第3節對Advogato信任模型進行了簡述;第4節提出了用戶本地信任模型(SEMBA)的構建;第5節提出了本文的推薦方法(ComSEMBA);第6節進行了實驗對比、分析和討論;第7節為本文工作的總結.

2 相關研究

現有的服務推薦技術大多采用協同過濾推薦方法、基于內容的推薦方法或混合推薦方法對服務推薦進行研究.從研究角度分析,可以分為以下三個研究角度.

1)根據用戶和服務的空間關系,對用戶進行位置相關的服務推薦.HaKan等人[5]使用無向連通圖對用戶的訪問位置點進行建模,然后基于該無向連通圖執行修改后的隨機游走算法,并參考用戶在當前位置的歷史訪問足跡,朋友的歷史訪問足跡和專家的歷史訪問足跡,來為目標用戶進行興趣點的推薦.該隨機游走算法為專家節點和親密朋友節點給予了較高的權重,因此,會造成越流行的位置點,越容易被推薦,而降低了用戶的個人興趣偏好的作用.Jianxun Liu等人[6]將地理范圍分為AS、Country、Global三個層次,以這三層地理范圍建立相似用戶和相似服務的計算,在為用戶進行Web服務推薦時,首先搜索小范圍的相似用戶和相似服務,如果近鄰用戶數量不足,再將范圍擴展至上一層次,最后進行服務推薦.Weimin Li等人[7]對服務的可靠性及用戶的關系進行分析,提出了一種可靠的位置服務推薦方法,但該方法在考慮用戶的關系時,只考慮了朋友關系,且關系路徑權重設置得相對較大,難以符合實際的推薦情境.

2)將可信計算理論與服務推薦相結合,為用戶推薦可信的服務.王海艷等人[8]對推薦用戶的正確推薦次數和錯誤推薦次數進行分析,使用Beta概率模型來計算推薦用戶的直接推薦信任,根據信任鏈路上的用戶共同使用服務數量來計算推薦用戶的間接信任,最后與用戶評價相似度進行融合,產生推薦用戶的綜合信任權重,并建立可信用戶聯盟,為目標用戶進行服務推薦.張燕平等人[9]對目前電子商務推薦系統面臨的托攻擊進行研究,利用用戶的歷史交易記錄建立用戶的聲譽,并結合協同過濾領域內的隱語義模型,提出融合用戶聲譽和隱語義模型的協同推薦算法,以提高推薦系統抵御托攻擊的能力.文獻[10]針對現有推薦系統面臨的信任安全問題,提出了一種基于信任的協同推薦方法,具備一定的抗惡意攻擊能力,且能夠一定程度緩解數據稀疏和冷啟動問題.

3)將社交網絡理論與服務推薦相融合,利用社交網絡為用戶的服務推薦提供支持.Yan Wang等人[11]將用戶的個人偏好和領域熟悉度作為獨立的社交上下文,將用戶間的信任、社交親密度和交互上下文作為依賴社交上下文,提出了一種新的概率方法來計算用戶間的上下文信任度,然后進行服務推薦,并根據推薦結果來更新用戶社交網絡的信任數據和偏好數據.Magdalini Eirinaki[12]等人基于友誼、信任、不信任因素來計算用戶間的直接聯系,而利用用戶評論、興趣和不感興趣等因素來計算用戶間的隱含聯系,綜合生成用戶的個性化聲譽及信任值,最后為目標用戶進行服務推薦.Shuiguang Deng等人[13]利用矩陣分解方法來計算社會網絡中的用戶信任程度,然后采用擴展的隨機游走算法來為目標用戶進行服務推薦.

綜合分析,現有的服務推薦方法存在以下問題:

1) 在利用社交網絡進行信任計算時,采用的是全局信任計算方法,而實際上用戶間的信任常常是主觀的、本地的.

2) 基于整個用戶-服務評價矩陣計算用戶間的相似性,然后進行推薦,計算工作量大.

3) 未深入研究服務推薦方法的魯棒性,不能有效抵御惡意用戶的托攻擊行為.

3 Advogato信任模型概述

Advogato是一個著名的自由軟件開發者社區2,其所采用的Advogato信任模型,在防止垃圾郵件攻擊方面尤為有效[14].

Advogato信任模型的構建涉及兩個重要概念.一個是信任容量(Trust Capacity),代表源節點(Seed)所擁有的信任能力,信任容量大的節點,其構建信任網絡的能力也越強.第二個是信任流量,是源節點根據對其他節點的信任強度分配到信任邊上的信任權重.信任權重越大,分配到信任邊上的信任流量越多,相關節點所獲得的信任容量也越大.

Advogato信任模型的構建分為三個步驟.首先,根據節點與源節點的距離,采用廣度優先搜索方法,為信任網絡中的每個節點分配信任容量.后續節點的信任容量采用公式(1)計算,等于前節點的信任容量除以前節點的出度值.

(1)

第二步,將第一步計算得到的信任網絡(圖1(a))轉化為Advogato信任網絡(圖1(c)).轉化步驟如下:首先,將信任網絡中的每個節點分解為正節點和負節點(圖1(b)).然后將節點的信任容量轉移到負節點通往正節點的信任鏈路上使之成為信任流量,再抽取信任流量1共同注入superlink節點(流量匯點)上(圖1(c)).最后,采用Fold-Fulkerson算法[15]對源節點的信任網絡進行網絡最大流增量路徑查找,直到不再有增量路徑為止.

圖1 信任網絡轉化為Advogato信任網絡結構的步驟Fig.1 Transforming steps of a trust network into Advogato structrue

在Advogato信任模型的基礎上,我們提出了SEMBA信任模型,其與Advogato模型的區別如表1所示.

表1 SEMBA與Advogato信任模型的區別
Table 1 Difference between SEMBA and Advogato trust model

模型名稱圖類型信任特征信任容量分配規則輸出內容Advogato有向無權連通圖全局信任根據距離分配非嚴格順序可信群體列表SEMBA有向加權連通圖本地信任根據信任強度分配N位有序可信用戶列表

4 SEMBA信任模型

根據Mark Granovetter[16]的社會網絡理論,社會網絡關系可以分為強關系和弱關系兩種,強關系用于表達個人的社交圈子,通過血緣、感情、興趣、地域等因素進行連接;而弱關系則是強關系的擴展,將不同的社交網絡圈子進行連接.強關系強調用戶的同質性,而弱關系則更關注聯系之間的異質性.因此,我們認為用戶的個人社交網絡屬于社會網絡強關系圈子,并且包含以下幾個因素.

1)距離因素,這里的距離可以是地域距離、血緣距離及熟悉度距離等,當用戶間的距離越近,其可信程度越高.

2)相似度因素,相似度因素可以分為兩類,一類是社交圈子相似性,代表了用戶的社交圈子重合程度;另一類是興趣相似性,即用戶所選擇服務相似,并給出相似的服務評價.相似性越高的用戶,其可信程度也越高[17].

3)互動程度,已有的研究表明,互動程度越高的用戶,其可信程度也越高[18].

綜合上述分析,我們對Advogato模型進行擴展,將距離因素、相似度因素及互動程度等考慮進來,提出了SEMBA信任模型,為目標用戶構建其本地信任網絡.

4.1 SEMBA信任模型的形式化

定義1.信任網絡.我們用G=(V,E)代表一個面向服務的具有信任關系的社交網絡,其中,V為節點集,代表社交網絡中的用戶;E為節點間信任邊的集合,邊上的權重代表信任的強度,E∈V×V.信任網絡G=(V,E)的構建由用戶的信任關系鄰接矩陣M生成.

定義2.源節點與源節點的本地信任網絡.給定節點u,設GLu=(VLu,ELu)為信任網絡G的一個子圖,其中,VLu?V,代表從節點u出發可以到達的節點集合;ELu?E,代表從節點u出發到達所有VLu的邊的集合,那么我們稱節點u為源節點,GLu=(VLu,ELu)為源節點u的本地信任網絡.

定義3.m跳連接和m跳朋友.在源節點u的本地信任網絡GLu=(VLu,ELu)中,假定存在一條從節點Vu到Vm的路徑,該路徑由節點序列Vu,V1,…,Vm-1,Vm組成,?Vi∈VLu(i=u,1,…,m),如果Vu到Vi中間沒有其他節點,那么我們稱Vu到Vi為1跳連接,否則我們稱其為m跳連接.對應的,稱V1為源節點u的1跳朋友,稱Vm為源節點u的m跳朋友.

定義4.可信節點識別.給定一個源節點u,根據他的本地信任網絡GLu=(VLu,ELu),按照一定的信任規則,找出所有滿足該信任規則的節點集合VTu,并排序輸出.

定義5.信任容量.給定一個源節點u,用信任容量Capu代表其構建個人本地信任網絡能力,源節點u的社交網絡關系越多,傾向于信任樂觀時,其信任容量就越大.

定義6.信任流量.給定一個源節點u和它的1跳朋友Vk,源節點u對k的信任強度稱為源節點u到k的信任流量,用Wu,k表示,其值越大,節點k分配得到的信任容量就越多.

4.2 本地信任網絡的構建

用戶的社交網絡關系存在很多類別,如朋友、親戚、鄰居、同事等社交關系,不同的社交關系具有不同的信任程度.很多情況下,用戶不愿對社交關系進行標注,而且用戶間的社交關系信息也常常難以獲得.為了識別出用戶社交網絡中的可信用戶群體,我們需要對用戶的個人社交網絡進行重構,對網絡中用戶的信任度進行區分.

為了構建目標用戶的本地信任網絡,我們首先要為目標用戶信任容量分配.為了方便處理,本文將源節點的信任容量設為1.用戶節點間的信任強度采用公式(2)計算.

(2)

(3)

(4)

其中,JaSimi,j為節點i與j基于Jaccard系數的社交圈子重合程度,avg(JaSim)為整個社會網絡中的平均社交圈子重合度.So(i)、So(j)為節點i與j的社交關系集合,包括節點自身.公式(3)反映了用戶i與j的社交圈子相似程度.

信任流量的傳遞涉及2個因素,前節點信任容量的大小及信任流量的大小.后續節點的信任容量采用公式(5)進行計算.

Capv=Capk×Wk,v

(5)

其中,Capv代表后續節點v的信任容量,Wk,v為節點k到v的信任強度,即信任流量.如果源節點u到v大于1跳距離,則采用文獻[15]FordFulkerson算法的思想,選擇一條信任流量最大的路徑進行信任流量傳遞,得到節點v的信任容量.

圖2 信任流量傳遞中的路徑選擇Fig.2 Path choice in trust flow transiting process

在圖2中,源節點u的信任容量為1,源節點u到節點A的信任權重Wu,A為0.67,則節點A的信任容量CapA=1×0.67=0.67.在對節點G進行信任容量計算時,因為存在兩條信任流量傳播路徑,需要分別計算Pathu,B,G和Pathu,C,G的信任流量傳播結果,并選擇一條信任流量最大的傳播路徑.其中,Pathu,B,G的計算結果為0.5612,而Pathu,C,G的計算結果為0.748,因此,節點G的信任容量為0.748.根據文獻[19]的小世界理論分析,任意兩個用戶的人際關系距離不超過6,因此,本文將信任流量的最大傳播路徑深度設置為6.

4.3 信任容量優先最大流搜索方法

在本節中,我們對Advogato的可信用戶識別搜索方法進行修改,提出了信任容量優先最大流搜索方法(Capacity-first maximum flow search-CFMS),來對源節點本地信任網絡的可信用戶進行識別、搜索和排序,并返回前N個用戶.

算法1.信任容量優先最大流搜索算法.

輸入:節點u,u的本地信任網絡鄰接矩陣M,M中所有節點的信任容量表CM,u的信任閾值Thu,u的候選朋友集CFM,需返回的可信用戶數量N值

輸出:u的有序可信用戶列表TruNListSorted

1. i=0,U0=u,CFM←getNeighbour(U0),n=N

2. while ((CFM is not empty) && i

3. TruList[i]=getMax(CFM,CM)

4. i++

5. CFM←CFM+getNeighbour(TruList[i])

6. TruList[i].Cap= TruList[i].Cap-Thu

7. setRelation(M,U0,TruList[i])

8. CFM←delete(CFM,TruList[i])

9. EndWhile

10. doQuickSorting(TruList)

11. For i=1 to n

12. TruNListSorted [i]=TruList[i]

13. EndFor

14. return TruNListSorted

其中,getNeighbour(U0)方法用來獲取U0在信任網絡鄰接矩陣M中的所有1跳朋友節點,getMax(CFM)用來獲得候選朋友集CFM中信任容量最大的節點,setRelation(M,U0,TruList[i])方法用來在信任網絡鄰接矩陣M中建立U0與TruList[i]的信任邊,delete(CFM,TruList[i])方法則在候選朋友集CFM刪除TruList[i]節點.通過偽代碼2-9行,便可以獲得一個基本排好序的可信用戶列表TruList,然后,我們采用快速排序方法doQuickSorting(TruList)來對其進行重新排序,以提高排序的效率.最后返回包含N個有序可信用戶的列表TruNListSorted.

圖3 采用CFMS方法對圖2的信任網絡進行可信用戶識別和搜索Fig.3 Using CFMS method to identifying and searching the trustworthy users in Fig.2

通過CFMS方法,我們對圖2的本地信任網絡的可信用戶進行識別和排序,并將其轉化為改進后的SEMBA信任網絡結構.最終得到源節點u的有序可信用戶列表:B、C、G、A、D、H、E、F(這里的Thu=0.1,限于篇幅,E,F節點沒有畫出).

5 基于用戶本地社交網絡的輕量級可信服務推薦方法(ComSEMBA)

通過SEMBA模型,我們為目標用戶構建了本地信任網絡,并使用信任容量優先最大流搜索方法CFMS,將目標用戶的可信用戶進行識別、排序輸出.對于目標用戶的信任閾值Thu的設置,當M及RM的數據較為稀疏時,可以將Thu設置得較小,以保證有較多的用戶進入目標用戶的候選朋友集CFM,為產生一定數量的近鄰提供基礎.而當M及RM的數據較為稠密時,則需要將Thu設置大些,以減少算法的運行時間,提高算法的運行效率.在目標用戶有特殊需要的情況下,也可由目標用戶設定Thu值.

5.1 目標用戶的服務評分預測

以目標用戶的可信用戶列表TruNListSorted為基礎,便可以計算TruNListSorted中的N個用戶與目標用戶的評分相似度.采用Pearson相似度進行計算,如公式(6)所示.

(6)

獲得了目標用戶u與TruNListSorted中用戶的評分相似度后,便可以選取TruNListSorted中的top-K個用戶,來為目標用戶進行服務評分預測,采用公式(7)進行計算.

(7)

其中,PRu,s為目標用戶u對服務S的評分預測,Capu,j為采用公式(5)和Ford Fulkerson算法計算得到的用戶j在目標用戶u的本地信任網絡中的信任容量,UC為目標用戶u的近鄰用戶集,即TruNListSorted中的top-K個用戶.

5.2 ComSEMBA推薦方法

ComSEMBA推薦方法的步驟如下.

1)選定目標用戶u,基于u的信任鄰接矩陣M,采用SEMBA信任模型的公式2、3、4、5計算節點間的信任流量及節點的信任容量,采用Fold-Fulkerson算法,建立目標用戶u的本地信任網絡;

2)基于目標用戶的本地信任網絡,采用信任容量優先最大流搜索方法CFMS,獲得目標用戶的可信用戶列表TruList,并使用快速排序方法對其進行排序得到包含了N個用戶的有序可信用戶列表TruNListSorted;

3)根據公式(6),計算目標用戶u與TruNListSorted中的N個用戶的評分相似性;

4)選取與目標用戶u最相似的top-K個用戶作為目標用戶的近鄰;

5)根據公式(7),預測目標用戶的未知項目評分.

5.3 ComSEMBA推薦方法的復雜度分析

6 實驗與分析

6.1 實驗數據集

目前可用于推薦系統的數據集較多,其中,HetRec 2011的子數據集hetrec2011-lastfm-2k來自于在線音樂網站www.last.fm,包括了用戶的社交網絡關系,用戶對藝術家的標簽,用戶對藝術家的聆聽次數等數據,且因為在線音樂本身即屬于服務,具有較為明顯的用戶興趣偏好特征[20].因此,本文將hetrec2011-lastfm-2k作為實驗數據集.

表2 hetrec2011-lastfm數據集的統計信息
Table 2 Statistics of the hetrec2011-lastfm dataset

ParameterValueUsers1892Artists17632Friendrelations25434Avgfriendrelationsperuser13.443User-listenedartistrelations92834

在hetrec2011-lastfm-2k數據集中,并沒有用戶對藝術家的評分數據,因此,我們將用戶對藝術家的聆聽次數作為用戶對藝術家的評分,并將其映射到[0,5]的評分區間內.采用公式(8)計算.

(8)

其中,Listeningcountu,s表示用戶u對藝術家s的聆聽次數,Listeningcountmax為最大的用戶聆聽次數.由于在hetrec2011-lastfm-2k數據集中,也沒有用戶的交互數據,因此,我們將用戶共同聆聽過的藝術家數量作為用戶的交互次數.在得到了用戶對藝術家的評分和交互數據后,我們隨機選擇500個用戶作為源節點,分別構建其本地信任網絡.然后將這500個源節點的評分數據的80%作為訓練集,20%作為測試集.

6.2 實驗評價方法

我們采用推薦方法中普遍采用的MAE及RMSE兩個評價指標來對推薦方法的評分預測精度進行評價.其計算方式分別如公式(9)和公式(10)所示.

(9)

(10)

其中,PRi,s為目標用戶i對藝術家s的評分預測,Ri,s為目標用戶i對藝術家s的實際評分.MAE及RMSE分別被稱為平均絕對誤差和均方根誤差,是推薦系統中常用的兩個評價指標,其值越小,代表推薦方法評分預測越準確.

6.3 實驗結果與分析

6.3.1 實驗參數設置

在ComSEMBA方法中,有3個參數需要考慮,包括信任閾值參數Thu,TruNListSorted可信用戶列表中N的大小,top-K近鄰用戶數量K值的大小.其中,參數Thu用于控制目標用戶本地信任網絡的大小,而可信用戶列表中的N為top-K近鄰用戶K值的基數,N越大,近鄰用戶可選擇的范圍越廣.因為數據集hetrec2011-lastfm-2k的用戶數量較小,我們將Thu設置為0.通過實驗驗證N值與K值的關系.

本實驗中,我們將top-K的K值分別設為5至40,步長為5,將TruNListSorted中可信用戶數量N設為K的1至6倍,用1K、…、6K表示,驗證在不同N值情況下ComSEMBA方法的評分預測精度.實驗結果如圖4所示.

圖4 不同N值下ComSEMBA推薦方法的MAE曲線圖Fig.4 MAE curve of ComSEMBA method while under different N

以下為圖4所示實驗結果的分析.

1)隨著N/K值比例的增加,ComSEMBA方法的評分預測精度越來越高.這與我們的期望是相符的,TruNListSorted中可信用戶數量越多,top-K近鄰的選擇基數越大,越能夠選出與目標用戶相似度更高的近鄰,從而服務的評分預測越精確.

2)N為1K時,ComSEMBA方法的預測效果最差,這時推薦方法的top-K等于N,意味著只能將TruNListSorted中的N個可信用戶作為近鄰,因此預測效果最差.

3)當N值從1K增至6K時,推薦方法的評分預測精度提高的效果在逐漸減弱.其中,N從1K增長至2K時,推薦方法的預測精度提高最快,5K至6K時的預測精度提高最不明顯.

4)隨著目標用戶的近鄰數量增加,推薦方法的評分預測精度在逐步提高.當N為1K至3K時,趨勢最為明顯.而當N等于5K、6K時,近鄰數量增加至30時,已經不能明顯改善推薦方法的預測精度,這說明ComSEMBA方法已經提取了目標用戶的絕大部分有效近鄰,這時增加近鄰數量并不能明顯改善推薦方法的預測精度.

6.3.2 實驗對比方法

為了對本文提出的推薦方法效果進行驗證,我們對本文提出的推薦方法進行區分,將不考慮用戶互動因素的推薦方法稱為SimSEMBA,即只采用SoSimi,j來表示Wi,j.然后將SimSEMBA、ComSEMBA與以下幾個方法進行對比.

1)User-based CF,傳統的Pearson協同過濾方法[21].

2)TARS,文獻[22]提出的基于蟻群算法動態更新用戶間信任值,為目標用戶選出優質可信用戶,然后進行服務評分預測的推薦方法.

3)Nikolaos,該方法依據用戶間共同評價服務數量及評分相似性設置不同等級閾值,等級閾值越高的近鄰用戶,在進行評分預測時,分配的推薦權重越高[23].

6.3.3 預測精度對比

本實驗將N設置為6K,將top-K的K值分別設為5至40,步長為5,來觀察這5個推薦方法的MAE及RMSE值,對比它們的評分預測精度.實驗結果如圖5和圖6所示.

圖5 5種推薦方法的MAE曲線圖Fig.5 MAE curve of the five comparing methods

以下為圖5、圖6所示實驗結果的分析.

1)隨著目標用戶的近鄰增加,這5個推薦方法的預測精度都得到了提高.這證明近鄰用戶數量的增多,能有效提高評分預測的精度.但近鄰用戶增加至35以上時,TARS、Nikolaos及ComSEMBA方法的預測精度改善效果不明顯,主要因為后面的近鄰相似度更低,對評分預測精度的提高效用不大.

圖6 5種推薦方法的RMSE曲線圖Fig.6 RMSE curve of the five comparing methods

2)通過SimSEMBA方法與User-based CF的對比可以看出,同時考慮節點間的社交圈子相似度、評價相似度比只考慮用戶評價相似度的預測效果更好.提高社交圈子相似度高的用戶在評分預測中的權重,有助于提高推薦方法的評分預測精確度.

3)SimSEMBA與ComSEMBA方法對比,其評分預測精度不如后者,說明綜合考慮社交圈子相似度、用戶互動程度和評分相似性,比僅考慮社交圈子相似性和用戶評分相似性效果更好,因此互動程度因素在評分預測時是有效的.

4)TARS比SimSEMBA方法的預測效果更好,但次于Nikolaos方法和ComSEMBA方法.這是因為TARS方法基于蟻群算法對目標用戶的評分進行預測,近鄰用戶對某項服務的評價越多,將導致該項服務累積的信息素越多,會提高該項服務在評分預測時的權重,從而導致越受用戶歡迎的服務,越有可能被推薦給目標用戶.但其不足是會使目標用戶的個性化偏好作用減弱,從而導致TARS的預測精度不如Nikolaos方法和ComSEMBA方法.

5)ComSEMBA方法的預測效果最好,Nikolaos次之.Nikolaos考慮近鄰用戶與目標用戶的共同評價服務數量,推薦用戶與目標用戶的評分相似性越高,共同評價服務數量越多,在進行目標用戶的評分預測時所給予的權重越大,但卻忽略了用戶的社交網絡的重要參考作用.因為ComSEMBA方法同時考慮了用戶的社交圈子相似性和互動程度,所以其預測精度要高于Nikolaos方法.

6.3.4 抗托攻擊對比

本實驗用來對比這5個方法在托攻擊下的性能表現.我們在實驗數據集中隨機生成一定比例的惡意用戶,這些用戶通過復制目標用戶的評分,然后再生成其他服務的惡意評價,以進行托攻擊.在本實驗中,我們將目標用戶的近鄰設為40,N設置為6K,然后逐漸增加托攻擊用戶的比例.實驗結果如圖7、圖8所示.

圖7 托攻擊下推薦方法的MAE曲線圖Fig.7 MAE curve of the five comparing methods while under Shilling attacks

圖8 托攻擊下推薦方法的RMSE曲線圖Fig.8 RMSE curve of the five comparing methods while under Shilling attacks

以下為圖7、圖8所示實驗結果的分析.

1)隨著惡意用戶比例的增加,所有的推薦方法預測精度都有所下降.證明惡意用戶的托攻擊行為能夠對這些方法產生干擾,這主要是因為這5個方法在進行評分預測時,都使用了用戶評分相似性這一因素.而User-based CF方法受到的影響最大,因為它只基于用戶評分相似性進行目標用戶的評分預測,所以其實驗運行結果最差.

2)SimSEMBA與TARS方法相比,在最初階段仍然比TARS方法的預測效果要差,當惡意用戶比例超過30%時,SimSEMBA反而呈現出了一定的優勢.這是因為TARS方法采用蟻群算法作為評分預測的基礎,服務受歡迎程度越高,越容易得到推薦,而惡意用戶的托攻擊行為將對這一情況產生較大干擾.而SimSEMBA基于用戶的社交圈子相似性進行評分預測,能夠有效減緩這一攻擊行為的影響.

3)Nikolaos方法考慮了用戶間共同評價服務數量的影響,而惡意用戶是通過復制目標用戶的評分來提高自身與目標用戶的相似度,從而與目標用戶的共同評價服務數量將占據很大比例,當惡意用戶增加至20%時,Nikolaos的評分預測精度受到了很大的影響,甚至低于TARS和SimSEMBA.

4)ComSEMBA方法的抗托攻擊能力最強.因為ComSEMBA方法既考慮了用戶的社交圈子相似度,又考慮了用戶的互動程度,惡意用戶僅通過復制目標用戶的服務評分,很難提高自身在目標用戶評分預測時的權重,因此,惡意用戶的托攻擊行為對ComSEMBA方法的干擾最小.

7 總 結

移動通信技術和在線支付技術的成熟發展,促使能滿足用戶各種需求的服務大量涌現.面對海量的可用服務,用戶常常咨詢其個人移動社交網絡,以選取可靠且能滿足其需求的優質服務.目前的推薦技術大多基于用戶服務評分矩陣,采用全局相似度計算方式計算用戶間的相似度,然后進行目標用戶的服務評分預測,計算資源耗費較大,且忽略了用戶本地社交網絡的重要參考作用,同時也不能有效對抗惡意用戶的托攻擊行為.針對這一問題,本文提出了基于用戶本地社交網絡的輕量級可信服務推薦方法,該方法首先對Advogato模型進行擴展,構建目標用戶的本地信任網絡,然后在本地信任網絡的基礎上,考慮用戶間的社交圈子相似度、互動程度,計算用戶的局部信任權重,再結合信任權重和用戶的評分相似性,進行目標用戶的服務評分預測.基于真實數據集與其他推薦方法的對比實驗表明,該方法不僅具有更高的評分預測精度,還能更有效對抗惡意用戶的托攻擊行為,同時,該方法具有更低的計算復雜度.

[1] Liu Wei,Xu Peng-tao.A study on influencing factors of the helpfulness of online reviews in O2O of restaurant industry—based on tobit model[J].Chinese Journal of Management Science,2016,24(5):168-176.

[2] Verbert K,Manouselis N,Ochoa X.Context-aware recommender systems for learning:A survey and future challenges[J].IEEE Transactions on Learning Technologies,2012,5(4):318-335.

[3] Meng Xiang-wu,Liu Shu-dong,Zhang Yu-jie,et al.Research on social recommender systems[J].Journal of Software,2015,26(6):1356-1372.

[4] Gunes I,Kaleli C,Bilge A,et al.Shilling attacks against recommender systems:a comprehensive survey[J].Artificial Intelligence Review,2014,42(4):767-799.

[5] Bagci H,Karagoz P.Context-aware location recommendation by using a random walk-based approach[J].Knowledge and Information Systems,2016,47(2):241-260.

[6] Liu J,Tang M,Zheng Z,et al.Location-aware and personalized collaborative filtering for web service recommendation[J].IEEE Transactions on Services Computing,2016,9(5):686-699.

[7] Li W,Yao M,Zhou X,et al.Recommendation of location-based services based on composite measures of trust degree[J].The Journal of Supercomputing,2014,69(3):1154-1165.

[8] Wang Hai-yan,Yang Wen-bin,Wang Sui-chang,et al.A service recommendation method based on trustworthy community[J].Chinese Journal of Computers,2014,37(2):301-311.

[9] Zhang Yan-ping,Zhang Shun,Qian Fu-lan,et al.Robust collaborative recommendation algorithm based on user's reputation[J].Acta Automiatica Sinica,2015,41(5):1004-1012.

[10] Liu Ying-nan,Xie Jin-kui,Zhang Jia-li,et al.Recommendation algorithm based on trust in social network [J].Journal of Chinese Computer Systems,2015,36(6):1165-1170.

[11] Wang Y,Li L,Liu G.Social context-aware trust inference for trust enhancement in social network based recommendations on service providers[J].World Wide Web,2015,18(1):159-184.

[12] Eirinaki M,Louta M D,Varlamis I.A trust-aware system for personalized user recommendations in social networks[J].IEEE Transactions on Systems Man and Cybernetics-Part A Systems and Humans,2013,44(4):409-421.

[13] Deng S,Huang L,Xu G.Social network-based service recommendation with trust enhancement[J].Expert Systems with Applications,2014,41(18):8075-8084.

[14] Al-oufi S,Kim H N,Ei Saddik A.A group trust metric for identifying people of trust in online social networks[J].Expert Systems with Applications,2012,39(18):13173-13181.

[15] Ford L R,Fulkerson D R.Maximal flow through a network[M].Classic Papers in Combinatorics，Birkhuser Boston,2009:243-248.

[16] Mark Granovetter.The strength of weak ties:a network theory revisited[J].Sociological Theory,1983,1(1):201-233.

[17] Josang A,Ismail R,Boyd C.A survey of trust and reputation systems for online service provision[J].Decision Support Systems,2007,43(2):618-644.

[18] Gilbert E,Karahalios K.Predicting tie strength with social media[C].International Conference on Human Factors in Computing Systems,ACM,Boston，2009:211-220.

[19] Kleinberg J.The small-world phenomenon:an algorithm perspective[J].Proceedings of Acm Symposium on Theory of Computing,1999,406(2):163-170.

[20] Cantador I,Brusilovsky P,Kuflik T.Second workshop on information heterogeneity and fusion in recommender systems [C].Proceedings of the 2nd International Workshop on Information Heterogeneity and Fusion in Recommender Systems(HetRec2011),2011:387-388.

[21] X Su,TM Khoshgoftaar.A survey of collaborative filtering techniques[J].Advances in Artificial Intelligence,2009,(12):189-201.

[22] Bedi P,Sharma R.Trust based recommender system using ant colony for trust computation[J].Expert Systems with Applications,2012,39(1):1183-1190.

[23] Polatidis N,Georgiadis C K.A multi-level collaborative filtering method that improves recommendations[J].Expert Systems with Applications,2016,48(2):100-110.

附中文參考文獻：

[1] 劉 偉,徐鵬濤.O2O電商平臺在線點評有用性影響因素的識別研究-以餐飲行業O2O模式為例[J].中國管理科學,2016,24(5):168-176.

[3] 孟祥武,劉樹棟,張玉潔,等.社會化推薦系統研究[J].軟件學報,2015,26(6):1356-1372.

[8] 王海艷,楊文彬,王隨昌,等.基于可信聯盟的服務推薦方法[J].計算機學報,2014,37(2):301-311.

[9] 張燕平,張 順,錢付蘭,等.基于用戶聲譽的魯棒協同推薦算法[J].自動化學報,2015,41(5):1004-1012.

[10] 劉英南,謝瑾奎,張家利,等.社交網絡中基于信任的推薦算法[J].小型微型計算機系統,2015,36(6):1165-1170.