基于社交網絡中雙重好友及用戶偏好的協同過濾推薦

胡致杰,　印　鑒

(1.廣東理工學院 信息工程系， 廣東 肇慶　526100;2.中山大學 數據科學與計算機學院， 廣東 廣州　510006)

?

基于社交網絡中雙重好友及用戶偏好的協同過濾推薦

胡致杰1,印鑒2*

(1.廣東理工學院 信息工程系， 廣東 肇慶526100;2.中山大學 數據科學與計算機學院， 廣東 廣州510006)

摘要：針對目前基于社交網絡的協同過濾推薦算法只融入直接好友信息且不能有效防御概貌注入攻擊等問題，提出一種融合雙重好友及用戶偏好的協同過濾推薦算法，通過設置合適的熟悉度閾值在社交網絡的直接好友、間接好友中選取可信好友用戶集作為目標用戶K近鄰候選集，在共同評分項目數的基礎上，采用用戶偏好相似度與評分相似度的加權相似度作為尋找近鄰用戶的標準，完成目標用戶項目評分預測。在數據集Flixster上的實驗結果表明，融合雙重好友關系及用戶偏好的推薦算法不僅具有較好的推薦準確率，還具有較強的抗概貌注入攻擊能力。

關鍵詞：協同過濾; 社交網絡; 雙重好友; 用戶偏好; 概貌注入攻擊

0引言

大數據時代，如何讓人們在海量數據中尋找需要的信息變得越來越難，為此各類個性化推薦系統應運而生，其中協同過濾推薦是應用最廣、最成功的推薦方法之一。其基本思想是：系統中的用戶、項目不是孤立存在，而是彼此間具有一定相似性，利用相似用戶或相似項目即可實現評分預測或項目推薦。常用的協同過濾推薦為兩大類：基于內存的協同過濾和基于模型的協同過濾[1]。基于內存的協同過濾是根據用戶項目評分矩陣選取相似度高的用戶作為近鄰用戶，并依據近鄰來完成評分預測或項目推薦；基于模型的協同過濾則是對用戶評分數據進行數學建模，用以表示用戶的行為和興趣偏好，再通過模型求解實現評分預測或項目推薦。

1相關工作

協同過濾推薦雖能產生高質量的推薦，但存在數據稀疏、冷啟動及擴展性三大固有問題，許多學者對此展開了研究，并提出了多種解決方法。如文獻[2]提出不確定近鄰的協同過濾方法，自適應地選擇預測目標的近鄰對象，對預測結果進行平衡推薦。文獻[3]提出一種并行化的隱式反饋推薦模型p-IFRM，通過將用戶及產品隨機分桶并重構優化更新序列，達到了并行優化的目的。文獻[4]通過矩陣分解填補用戶評分，再利用填補后的稠密矩陣直接預測用戶評分，較好地解決了數據稀疏性問題。文獻[5]提出概率推理模型，通過貝葉斯、高斯概率推理預測用戶評分，可一定程度上提高推薦準確度。

在社交網絡普遍應用、社交信息極大豐富的背景下，融入社交信息的推薦系統越來越受到人們關注。文獻[6]提出一種融合用戶社交網絡信息的協同過濾方法，通過融入社交網絡中關系用戶的偏好特征進行矩陣分解產生推薦，實驗表明，算法能提高推薦準確度以及緩解數據稀疏性和冷啟動問題。文獻[7]采用基于隨機梯度矩陣分解的社會網絡推薦算法，一定程度上緩解了數據的稀疏性問題。文獻[8]將社交網絡中的信任關系融入協同過濾，通過計算信任網絡的信任度來選取最近鄰，推薦準確度有較高提升。文獻[9]提出利用信任傳播的方法，計算加權平均信任度估計值的方法。文獻[10]提出結合評分與信任的協同推薦算法，綜合了用戶相似度與信任度，提高了推薦精度和評分覆蓋率。文獻[11]提出基于雙重鄰居選取策略的推薦方法，將用戶相似度和信任度作為選取近鄰的雙重標準，有效提高了推薦質量。

以上融合社交網絡的推薦算法都能一定程度上提高推薦準確度，緩解數據稀疏性與冷啟動，但仍存在一些不足：

1)在融合社交信息時較多考慮的是目標用戶的直接好友，而用戶的潛在好友則少有考慮。

2)好友關系是一種社會關系，個人偏好則是用戶對不同項目好惡的體現，二者之間呈完全正相關性，但真實情況下二者不具有完全正相關性。

3)一些惡意用戶為實現自己的項目被優先推薦，常常會進行概貌注入攻擊，對此文獻少有考慮。

為此，文中提出融合社交網絡中雙重好友及用戶偏好的協同過濾推薦算法(CollaborativeFilteringRecommendationBasedonDoubleFriendandPreference，CF-DFP)，算法基于社交網絡中雙重好友關系尋找目標用戶可信好友用戶集，通過可信好友用戶的偏好相似度與評分相似度得到加權相似度，然后選取加權相似度最高的前K個用戶作為目標用戶的最近鄰以完成項目評分預測，實驗表明，算法能獲得較高的推薦準確度，也能一定程度上防御惡意用戶的概貌注入攻擊。

2基于社交網絡中雙重好友及用戶偏好的協同過濾推薦

2.1問題定義

在社交網絡中，基于“好友推薦的可信度更高”的認知觀將社交網絡中的好友關系融入推薦算法，更符合現實應用情況，但社交網絡中的好友包含直接好友和潛在好友，同時不同類型好友個人偏好不同。如何在協同過濾推薦算法中既融入社交網絡的好友關系，又考慮好友的個人偏好是文中研究的主題。

2.2基于社交網絡的雙重好友及熟悉度

推薦系統一般包含用戶集、項目集和用戶項目評分矩陣，假設U= {u1，u2，…，um}表示用戶集，I={i1，i2，…，in}表示項目集，R=[Ru,i]m×n表示用戶項目評分矩陣，其中Ru,i表示用戶u對項目i的評分，通常R是一個極其稀疏的矩陣。

在社交網絡中,用戶之間的關系可以抽象表示為一個無向有權圖

式中:U----用戶節點集;

E----直接好友關系集;

W----E中直接好友關系權重集，這里表示用戶之間的熟悉度，值越大表示熟悉度越高，關系越親密。

在構建的好友關系網絡中，可以定義直接好友、潛在好友及好友間的權重，如圖1所示。

圖1　好友關系網及權重

定義1好友關系網絡中，直接相連的兩個用戶稱為直接好友，用戶ui的直接好友集記為Ud(ui)，圖1中(ui,uj)，(uj,uk)，(uj,um)互為直接好友。

定義2好友關系網絡中，通過相同直接好友相連,但彼此不直接相連的兩個用戶稱為潛在好友，用戶ui的潛在好友集記為Up(ui)，圖1中(ui,uk)，(ui,um)，(um,uk)互為潛在好友。

定義3直接好友間的熟悉度即為直接好友間的權重，可表示為:

(1)

式中:familarityd(ui,uj)----用戶ui，uj的熟悉度；

wi,j----用戶ui，uj之間的權重；

Ud(ui)----用戶ui的直接好友集。

定義4通過共同直接好友傳遞的熟悉度即為潛在好友間的熟悉度，抽象表示如下:

(2)

式中：U+----用戶ui，uk共同直接好友集。

2.3可信好友用戶集的選取

在社交網絡中，如果兩個用戶之間越熟悉，則兩者之間進行的推薦越可信，因此，可選取與目標用戶熟悉度較大的直接好友或潛在好友作為可信好友，并依據可信好友用戶項目評分預測目標用戶項目評分，既可獲得較高的推薦質量，也可排除用戶惡意注入的評分記錄。

定義5可信好友用戶集S，給定好友熟悉度閾值θ，目標用戶ui∈U，如下面兩式成立，則uj，uk∈S(ui)。

(3)

(4)

構造目標用戶可信好友用戶集的算法描述如下：

算法1可信好友用戶集構造算法。

輸入：目標用戶ui，好友關系圖G，熟悉度閾值θ；

輸出：目標用戶ui的可信好友用戶集S(ui)。

Begin

①A1←G//構造社交網絡的鄰接矩陣

②wi,j←A1，式(1)、式(2) //根據鄰接矩陣計算直接好友、潛在好友間的權重

③A2←wi,j//構造權重鄰接矩陣

④S(ui)←ui，θ，A2

End

算法主要包含兩部分：一是依據社交網絡關系圖構造鄰接矩陣，利用鄰接矩陣計算直接好友與潛在好友間的熟悉度，并構造社交網絡的權重鄰接矩陣；二是利用權重鄰接矩陣和熟悉度閾值選擇目標用戶ui的可信好友用戶集S(ui)。

2.4可信好友用戶的偏好相似度與評分相似度

在協同過濾推薦中，為目標用戶選取理想的近鄰用戶是保障推薦質量的關鍵，傳統方法僅根據用戶評分相似度確定近鄰進行推薦的質量往往不高。因此，我們提出在目標用戶的可信好友用戶集中綜合用戶的偏好相似度及評分相似度來選取近鄰用戶。

偏好度是用戶對不同項目喜好程度的一種體現，對應用戶評分矩陣，如果兩個用戶共同評分的項目數越多，表明他們的個人偏好越接近，偏好相似度就越高，用戶的偏好相似度可用如下公式計算:

(5)

式中:sim′(ui,uj)----用戶ui，uj的偏好相似度，sim′(ui,uj)∈[0,1];

I(ui)----用戶ui的評分項目集。

在協同過濾算法中，用戶相似性可根據用戶項目評分矩陣進行計算，常用的相似度包括余弦相似性、改進的余弦相似性和Pearson相似性，文獻[12]用實驗證明Pearson相似性更適于度量用戶間的相似度，因此，這里采用Pearson相似性作為用戶相似度的度量方法，具體計算公式如下：

(6)

式中：sim″(ui,uj)----用戶ui，uj的評分相似度，sim″(ui,uj)∈[0,1]；

Rui,c----用戶ui對項目c的評分；

Iij----用戶ui，uj共同評分項目集。

2.5用戶加權相似度及推薦

對用戶偏好相似度與評分相似度進行線性組合可得用戶加權相似度，并根據加權相似度選取近鄰用戶完成評分預測或項目推薦，加權相似度計算公式如下：

(7)

式中:sim(ui,uj)----用戶ui，uj的加權相似度；

α----調和參數，用于調節用戶偏好相似度與評分相似度，α∈[0,1]。

根據式(7)計算得到目標用戶與可信好友用戶之間的加權相似度，并依據加權相似度大小選取目標用戶的K近鄰，再結合用戶評分矩陣完成目標用戶對目標項目的評分預測，預測評分計算公式如下：

(8)

Uk----用戶ui的K近鄰。

基于可信好友用戶偏好度和相似度的推薦算法描述如下：

算法2基于可信好友用戶偏好度和相似度推薦算法。

輸入：目標用戶ui，可信好友用戶集S(ui)，用戶項目評分矩陣R，最近鄰用戶數K；

Begin

①R+←S(ui)，R；//構造可信好友用戶評分矩陣

②sim′(ui,uj)←R+，公式(5)；//使用公式(5)在R+上計算用戶偏好度

③sim″(ui,uj)←R+，公式(6)；

④sim(ui,uj)←α，公式(7)；//使用公式(7)計算用戶加權相似度

⑤Uk←加權相似度最大的前K個用戶

End

2.6算法復雜度分析

3實驗結果及分析

3.1實驗數據集及評價指標

實驗采用來自Flixster網站的數據集作為實驗數據集，該網站是一電影社交網站，用戶可以分享電影評價及推薦新電影，也可通過電影認識愛好相同的人。數據集包含用戶對電影的評分以及用戶間的好友信息，包含481 189個用戶， 18 760部電影，450 297 863條用戶評分記錄， 4 197 338條好友關系，用戶平均好友數約為8.72，評分數據的稀疏度為95.01%。

實驗隨機抽取2 000個用戶的好友信息及評分數據作為樣本數據，并將其中的80%作為訓練集，20%作為測試集。

平均絕對誤差(Mean Absolute Error， MAE)是較直觀、常用的推薦系統評價指標，通過計算項目的預測評分與實際評分之間的偏差來估算推薦的準確度，MAE值越小,表示推薦的準確度越高，MAE計算公式如下[13]：

(9)

式中pi----推薦系統預測的目標用戶對項目i的評分；

ri----目標用戶對項目i的實際評分；

n----預測評分的項目數。

3.2θ對MAE的影響

θ是目標用戶與好友用戶之間熟悉度的閾值，主要用于確定目標用戶的可信好友用戶集，值的大小直接決定可信好友的數量及評分數量，因此需對θ作調優實驗。實驗參數設置為：α=0.7，K=50，設置θ從0.1變化到1.0，每次變化增量為0.1，依次統計每次改變時的MAE值，實驗結果如圖2所示。

圖2　θ對MAE的影響

從圖2中可知，θ=0時，是將所有用戶都作為目標用戶的可信好友，這與傳統的協同過濾相同；θ=1時,是將與目標用戶具有完全相同好友關系的用戶作為可信好友用戶，將導致可信好友用戶數量極少，推薦質量較差。實驗表明,θ在0.6左右取值MAE較小，這也比較符合社交網絡中的好友關系圖譜。

3.3α對MAE的影響

α是對可信好友用戶的偏好相似度與評分相似度進行調和的參數，通過α調和得到用于推薦的加權相似度，因此α對推薦準確度有較大影響。實驗參數設置為：θ=0.6，K=50，設置α從0.1變化到1.0，每次變化增量為0.1，依次統計每次改變時的MAE值，實驗結果如圖3所示。

圖3　α對MAE的影響

實驗結果表明，綜合用戶偏好相似度與評分相似度的推薦效果比只使用其中一種相似度的推薦效果要好，準確度要高。當α=0.7時，MAE值最小，推薦質量最高。

3.4推薦質量對比

為評判算法的推薦質量，將文中提出的融合社交網絡中雙重好友及用戶偏好的協同過濾推薦算法(CF-DFP)、傳統的基于用戶的協同過濾推薦算法(UserCF)、融合社交網絡信息的協同過濾方法(SocialRec)[6]、結合時間權重與信任關系的協同過濾推薦算法(TTCF)[14]的推薦質量進行對比。實驗參數設置為：θ=0.6，α=0.7，4種推薦算法的MAE值對比如圖4所示。

圖4　推薦算法質量對比

從圖4可以看出，在鄰居數量較少時，TTCF算法的MAE值最小，推薦質量最高；隨著鄰居數量的增加，4種算法的MAE值都呈現出先降后升的趨勢，但當最近鄰數大于30后,文中的CF-DFP算法能獲得比其它3種算法更低的MAE值，并在近鄰數為[50,60]區間MAE值最小。因此，推薦算法整體上具有較高的推薦準確度。

3.5抗概貌注入攻擊對比

為評判算法的抗攻擊能力，分別向實驗數據集中注入2%、4%、6%、8%、10%的概貌入侵記錄，設置θ=0.6，α=0.7，K=50，上述4種算法的MAE值對比結果如圖5所示。

圖5　抗概貌入侵對比

從圖5可以得出，文中的CF-DFP算法不僅具有較強的抗概貌入侵能力，還具有良好的平穩性。而其它3種算法抗概貌入侵性能較差，隨著攻擊規模的增大，MAE值都呈現快速上升趨勢，推薦準確度急劇下降。

4結語

針對協同過濾推薦算法的推薦準確度和抗攻擊能力進行了探索，將社交網絡中的直接好友、潛在好友及用戶偏好融入推薦算法，算法在用戶的直接好友、潛在好友中選取可信好友用戶，在可信好友用戶集中將用戶的偏好相似度與評分相似度作為目標用戶K近鄰的雙重選取依據。實驗證明，利用社交關系和用戶偏好能極大提高用戶預測評分的精確度，同時具有良好的抗概貌注入攻擊能力。在社交網絡應用日益廣泛、信息日益豐富的背景下，如果在推薦系統中更多地融入社交網絡信息以改善協同過濾推薦的三大固有問題是未來研究的熱點。后續的工作主要包括以下兩個方面：一是算法進一步融合社交網絡中的隱形好友關系----“可能感興趣的人”；二是在大數據背景下，如何用并行化來實現可信好友用戶集的計算。

參考文獻：

[1]許海玲,吳瀟,李曉東,等.互聯網推薦系統比較研究[J].軟件學報，2009，20(2):350-362.

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

[3]印鑒,王智圣,李琪,等.基于大規模隱式反饋的個性化推薦[J].軟件學報,2014,25(9):1953-1966.

[4]ShanH,BanerjeeA.Generalizedprobabilisticmatrixfactorizationsforcollaborativefiltering[C].//Proceedingsof2010IEEE10thInternationalConferenceonDatamining.Piscataway:IEEEPress,2010:1025-1030.

[5]ThakurSS,SingJK.Onlineproductpredictionandrecommendationusingprobabilitygraphicalmodelandcollaborativefiltering:Anewapproach[C].//Proceedingsof2011RecentAdvancesinIntelligentComputationalSystems.Piscataway:IEEEPress,2011:151-156.

[6]賀超波,湯庸,傅城州,等. 融合社交網絡信息的協同過濾方法[J].暨南大學學報:自然科學版,2013,34(3):243-248.

[7]李衛平,楊杰.基于隨機梯度矩陣分解的社會網絡推薦算法[J].計算機應用研究,2014,31(6):1654-1656.

[8]LiYM,WuCT,LaiCY.Asocialrecommendermech-anismfore-commerce:combiningsimilarity,trust,andrelationship[J].DecisionSupportSystems，2013，55(3):740-752.

[9]韓麗.社交網絡中的信任推薦和好友搜索過濾算法研究[D].秦皇島:燕山大學,2012.

[10]秦繼偉,鄭慶華,鄭德立,等.結合評分和信任的協同推薦算法[J].西安交通大學學報,2013,47(4):100-104.

[11]賈冬艷,張付志.基于雙重鄰居選取策略的協同過濾推薦算法[J].計算機研究與發展,2013,50(5):1076-1084.

[12]BreeseJS,HeckermanD,KadieC.Empiricalanalysisofpredictivealgorithmsforcollaborativefiltering[C]//ProceedingsoftheFourteenthConferenceonUncertaintyinArtificialIntelligence.MorganKaufmannPublishersInc.,1998:43-52.

[13]RicciF,RokachL，ShapiraB,etal.Recommendersystemsandbook[M].Berlin:Springer,2011:145-186.

[14]趙海燕,候景德,陳慶奎.結合時間權重與信任關系的協同過濾推薦算法[J].計算機應用研究，2015,32(5):157-162.

Collaborativefilteringrecommendationalgorithmbasedondoublefriendsrelationshipsanduserspreferences

HUZhijie1，YINJian2*

(1.DepartmentofInformationEngineering，GuangdongPolytechnicCollege，Zhaoqing526100,China;2.SchoolofDataandComputerScience，SunYat-SenUniversity，Guangzhou510006,China)

Abstract：Collaborativefilteringrecommendationbasedonsocialnetworksuffersthefollowingproblems:directfriendsinformationisconsideredonly,weakercapabilityofprofileinjectionattackresistance.Toaddresstheproblem,acollaborativefilteringrecommendationalgorithmbasedondoublefriends’relationshipsandusers’preferences(CF-DFP)isproposed.ThetrustyfriendsetisselectedfromdirectfriendsandpotentialfriendsinsocialnetworkbyproperfamiliaritythresholdandisconsideredasKnearestneighborcandidates(KNNC).Meanwhile,weightedsimilaritycombiningusers’preferencesandratingsisusedtofindKNNinKNNCandpredictratingsforusers.RelatedexperimentresultsonFlixsterdatasetshowthattheproposedalgorithmcannotonlyimprovetheaccuracyofcollaborativefiltering,butalsoresiststheprofileinjectionattackeffectively.

Keywords：collaborativefiltering;socialnetwork;doublefriends’relationship;userpreference;profileinjectionattack.

收稿日期：2016-03-11

基金項目：國家自然科學基金資助項目(61033010，61472453)； 廣東省自然科學基金資助項目(S2013020012865)； 廣東省科技計劃項目(2013B090200006)

作者簡介：胡致杰(1974-)，男，漢族，湖北蘄春人，廣東理工學院講師，碩士，主要從事數據挖掘、推薦系統方向研究,E-mail:gl_hzj@foxmail.com. *通訊作者：印鑒(1968-)，男，漢族，湖北仙桃人，中山大學教授，博士生導師，主要從事大數據、數據挖掘方向研究,E-mail:issjyin@mail.sysu.edu.cn.

DOI:10.15923/j.cnki.cn22-1382/t.2016.3.05

中圖分類號：TP393

文獻標志碼：A

文章編號：1674-1374(2016)03-0230-06