胡致杰,　印　鑒

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

?

基于社交網(wǎng)絡中雙重好友及用戶偏好的協(xié)同過濾推薦

胡致杰1,印鑒2*

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

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

關鍵詞：協(xié)同過濾; 社交網(wǎng)絡; 雙重好友; 用戶偏好; 概貌注入攻擊

0引言

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

1相關工作

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

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

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

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

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

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

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

2基于社交網(wǎng)絡中雙重好友及用戶偏好的協(xié)同過濾推薦

2.1問題定義

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

2.2基于社交網(wǎng)絡的雙重好友及熟悉度

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

在社交網(wǎng)絡中,用戶之間的關系可以抽象表示為一個無向有權(quán)圖

式中:U----用戶節(jié)點集;

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

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

在構(gòu)建的好友關系網(wǎng)絡中，可以定義直接好友、潛在好友及好友間的權(quán)重，如圖1所示。

圖1　好友關系網(wǎng)及權(quán)重

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

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

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

(1)

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

wi,j----用戶ui，uj之間的權(quán)重；

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

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

(2)

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

2.3可信好友用戶集的選取

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

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

(3)

(4)

構(gòu)造目標用戶可信好友用戶集的算法描述如下：

算法1可信好友用戶集構(gòu)造算法。

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

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

Begin

①A1←G//構(gòu)造社交網(wǎng)絡的鄰接矩陣

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

③A2←wi,j//構(gòu)造權(quán)重鄰接矩陣

④S(ui)←ui，θ，A2

End

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

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

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

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

(5)

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

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

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

(6)

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

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

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

2.5用戶加權(quán)相似度及推薦

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

(7)

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

α----調(diào)和參數(shù)，用于調(diào)節(jié)用戶偏好相似度與評分相似度，α∈[0,1]。

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

(8)

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

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

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

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

Begin

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

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

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

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

⑤Uk←加權(quán)相似度最大的前K個用戶

End

2.6算法復雜度分析

3實驗結(jié)果及分析

3.1實驗數(shù)據(jù)集及評價指標

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

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

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

(9)

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

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

n----預測評分的項目數(shù)。

3.2θ對MAE的影響

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

圖2　θ對MAE的影響

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

3.3α對MAE的影響

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

圖3　α對MAE的影響

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

3.4推薦質(zhì)量對比

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

圖4　推薦算法質(zhì)量對比

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

3.5抗概貌注入攻擊對比

為評判算法的抗攻擊能力，分別向?qū)嶒灁?shù)據(jù)集中注入2%、4%、6%、8%、10%的概貌入侵記錄，設置θ=0.6，α=0.7，K=50，上述4種算法的MAE值對比結(jié)果如圖5所示。

圖5　抗概貌入侵對比

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

4結(jié)語

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

參考文獻：

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

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

[3]印鑒,王智圣,李琪,等.基于大規(guī)模隱式反饋的個性化推薦[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]賀超波,湯庸,傅城州,等. 融合社交網(wǎng)絡信息的協(xié)同過濾方法[J].暨南大學學報:自然科學版,2013,34(3):243-248.

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

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

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

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

[11]賈冬艷,張付志.基于雙重鄰居選取策略的協(xié)同過濾推薦算法[J].計算機研究與發(fā)展,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]趙海燕,候景德,陳慶奎.結(jié)合時間權(quán)重與信任關系的協(xié)同過濾推薦算法[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-)，男，漢族，湖北蘄春人，廣東理工學院講師，碩士，主要從事數(shù)據(jù)挖掘、推薦系統(tǒng)方向研究,E-mail:gl_hzj@foxmail.com. *通訊作者：印鑒(1968-)，男，漢族，湖北仙桃人，中山大學教授，博士生導師，主要從事大數(shù)據(jù)、數(shù)據(jù)挖掘方向研究,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