楊海月，朱玉婷，施化吉，徐　慧

（1.江蘇大學(xué) 計(jì)算機(jī)科學(xué)與通信工程學(xué)院，江蘇 鎮(zhèn)江212013；2.大全集團(tuán)，江蘇 揚(yáng)中 212211）

基于用戶信任度和社會(huì)相似度的協(xié)作過(guò)濾算法*

楊海月1，朱玉婷1，施化吉1，徐慧2

（1.江蘇大學(xué) 計(jì)算機(jī)科學(xué)與通信工程學(xué)院，江蘇 鎮(zhèn)江212013；2.大全集團(tuán)，江蘇 揚(yáng)中 212211）

個(gè)性化推薦算法是解決社交網(wǎng)絡(luò)中信息過(guò)載問(wèn)題的一種有效方法，已成為社交網(wǎng)絡(luò)中的研究熱點(diǎn)。協(xié)作過(guò)濾算法是被廣泛應(yīng)用的個(gè)性化推薦算法，但由于未考慮社交網(wǎng)絡(luò)的一些重要社交信息及數(shù)據(jù)稀疏問(wèn)題，故其在解決社交網(wǎng)絡(luò)的推薦問(wèn)題時(shí)推薦效果不佳。為此，提出一個(gè)基于用戶信任度和社會(huì)相似度的協(xié)作過(guò)濾算法。首先根據(jù)用戶-項(xiàng)目矩陣計(jì)算用戶相似度，然后通過(guò)社交網(wǎng)絡(luò)計(jì)算用戶信任度和社會(huì)相似度并將三者融合，最后根據(jù)融合后的值形成最近鄰集，并據(jù)此產(chǎn)生推薦結(jié)果。經(jīng)實(shí)驗(yàn)分析，文中提出的算法較其他算法在解決社交網(wǎng)絡(luò)的推薦問(wèn)題時(shí)有更高的推薦精度。

協(xié)作過(guò)濾；數(shù)據(jù)稀疏；用戶信任度；社會(huì)相似度；社交網(wǎng)絡(luò)

0　引言

隨著社交網(wǎng)絡(luò)的迅猛發(fā)展，網(wǎng)絡(luò)上的信息呈爆炸式增長(zhǎng)，出現(xiàn)了“信息過(guò)載”問(wèn)題。個(gè)性化推薦被認(rèn)為是解決該問(wèn)題最有效的方法[1]，常用的個(gè)性化推薦算法主要有協(xié)作過(guò)濾[2]、基于內(nèi)容推薦[3]、混合推薦[4]等，協(xié)作過(guò)濾算法是其中的研究熱點(diǎn)[5]。

協(xié)作過(guò)濾算法在解決社交網(wǎng)絡(luò)的推薦問(wèn)題時(shí)因未考慮社交網(wǎng)絡(luò)的一些重要社交信息及數(shù)據(jù)稀疏問(wèn)題，故其推薦效果不佳。文獻(xiàn)[6]提出的方法在一定程度上緩解了數(shù)據(jù)稀疏問(wèn)題，對(duì)冷啟動(dòng)用戶的推薦精度有一定提高，但對(duì)所有用戶的推薦精度不高。文獻(xiàn)[7]提出方法僅考慮了朋友關(guān)系這一社交信息而忽略了用戶相似度的影響，故推薦精度也不高。文獻(xiàn)[8]提出的方法研究了用戶項(xiàng)目間的信任關(guān)系，但未考慮用戶間信任關(guān)系，故未能緩解數(shù)據(jù)稀疏問(wèn)題。這些研究表明社交網(wǎng)絡(luò)中個(gè)性化推薦的精度有待提高且數(shù)據(jù)稀疏問(wèn)題也沒(méi)有得到很好的解決。為此，提出一個(gè)基于用戶信任度和社會(huì)相似度的協(xié)作過(guò)濾算法（User Trust and Social Similarity-based Collaborative Filtering Algorithm，UTSSCF）。首先根據(jù)用戶-項(xiàng)目矩陣計(jì)算用戶相似度，然后通過(guò)社交網(wǎng)絡(luò)計(jì)算用戶信任度和社會(huì)相似度并將三者融合，最后根據(jù)融合后的值形成最近鄰集，并據(jù)此產(chǎn)生推薦結(jié)果。

1　用戶信任度計(jì)算

文獻(xiàn)[9]的研究表明社交網(wǎng)絡(luò)中的用戶更傾向于采納信任的人的推薦。因此，用戶信任對(duì)社交網(wǎng)絡(luò)的個(gè)性化推薦有著重要影響。在社交網(wǎng)絡(luò)中，若A和B有直接聯(lián)系（如A關(guān)注B），則A對(duì)B有直接信任關(guān)系；若A對(duì)B且B對(duì)C有直接信任關(guān)系，則A對(duì)C有間接信任關(guān)系。文中把社交網(wǎng)絡(luò)中用戶信任關(guān)系劃分為直接信任關(guān)系和間接信任關(guān)系，分別以直接信任度和間接信任度進(jìn)行度量。

定義1（社交網(wǎng)絡(luò)S）設(shè)U表示S中用戶節(jié)點(diǎn)集合，E表示S中用戶間的直接信任關(guān)系集合，W表示S中用戶間的直接信任度T的集合，S則可用三元組表示成S(U，E，W)。其中，U={u1，u2，…，un}，|U|=n；E={＜u，v＞|u，v∈U}；W={T(u，v)|u，v∈U}。

1.1直接信任度計(jì)算

在S中若u和v有直接聯(lián)系，則u對(duì)v有直接信任關(guān)系，并用直接信任度T進(jìn)行度量。

定義2（直接信任度T）若S中有一條從u指向v的邊，則u對(duì)v的直接信任度T(u，v)為1，否則，為0。

考慮到后文選取的用戶相似度度量方法(見(jiàn)4.1節(jié))的取值范圍是[-1，1]，故要對(duì) T進(jìn)行歸一化處理，使得歸一化的直接信任度tr取值限定在[0，1]。歸一化處理后得到的直接信任度如式(1)所示。

1.2間接信任度計(jì)算

若u對(duì)v有間接信任關(guān)系，則可用間接信任度T′進(jìn)行度量。

定義3（間接信任度T′）若在S中至少存在一條從u到v的路徑，則u對(duì)v有間接信任關(guān)系，又u到v的最短路徑為 path={＜u，u1，u2，…，uk，v＞|min(k+1)∧u，v，ux∈U，1≤x≤k}，則u對(duì)v的間接信任度T′(u，v)=(tr(u，u1) +tr(u1，u2)+…+tr(uk，v))/(k+1)。

另外，根據(jù)小世界理論設(shè)置max(k+1)為6。若S中u到v的max(k+1)大于6，則T′(u，v)=0。

1.3用戶信任度計(jì)算

如上所述，文中把用戶信任度分為直接信任度和間接信任度，故用戶信任度是它們的綜合值。設(shè)Tr(u，v)表示u對(duì)v的用戶信任度，A表示tr(u，v)，B表示T′(u，v)，則用戶信任度的計(jì)算如式(2)所示。

2　社會(huì)相似度計(jì)算

文獻(xiàn)[10]的研究表明用戶間共有的朋友數(shù)越多，其社交、興趣、偏好越相似。因此，用戶間共有的朋友數(shù)也是一個(gè)影響社交網(wǎng)絡(luò)個(gè)性化推薦的重要因素，文中用社會(huì)相似度定量其影響程度。

定義 4（社會(huì)相似度 Ss）Ss(u，v)指 S中任意兩個(gè)直接相連的用戶節(jié)點(diǎn)u和v間共有的朋友數(shù)占它們總朋友數(shù)的比值，則其計(jì)算如式(3)所示。

其中，F(xiàn)(u)={u′|＜u，u′＞∈E∧u，u′∈U}(F(v)同理)，表示從u和v共同指向的用戶節(jié)點(diǎn)數(shù)，表示從u及v指向的用戶節(jié)點(diǎn)數(shù)之和。

3　UTSSCF算法

3.1用戶相似度計(jì)算

計(jì)算用戶相似度是為了尋找興趣偏好相似的用戶，從而據(jù)此產(chǎn)生推薦結(jié)果。設(shè)S中u和v已評(píng)價(jià)項(xiàng)目并集為 Iuv=Iu∪Iv，則 u和v的用戶相似度計(jì)算如式(4)所示。

其中，ru，i和rv，i分別表示u和v對(duì)i的評(píng)分，Ru和Rv分別表示u和v對(duì)Iuv中所有項(xiàng)目評(píng)分的平均值。

3.2用戶相似度、用戶信任度和社會(huì)相似度的融合

由于社交網(wǎng)絡(luò)中用戶-項(xiàng)目矩陣很稀疏，故將用戶相似度、用戶信任度和社會(huì)相似度進(jìn)行融合以緩解數(shù)據(jù)稀疏的問(wèn)題。

設(shè) We(u，v)表示 Si(u，v)、Tr(u，v)和 Ss(u，v)融合后的值，則We(u，v)的計(jì)算如式(5)所示。

其中，α、β、γ分別表示 Si(u，v)、Tr(u，v)、Ss(u，v)所占的比重，且α+β+γ=1。

3.3產(chǎn)生推薦結(jié)果

計(jì)算出We(u，v)后，選擇We(u，v)最大的l個(gè)用戶作為u的最近鄰集Ns。根據(jù)Ns中的用戶評(píng)分?jǐn)?shù)據(jù)預(yù)測(cè)u對(duì)未評(píng)價(jià)項(xiàng)目I的評(píng)分Pu，I，并將預(yù)測(cè)評(píng)分最高的 k個(gè)項(xiàng)目推薦給u。預(yù)測(cè)評(píng)分的計(jì)算如式(6)所示。

其中，Ru和Rv分別表示u和v對(duì)所有項(xiàng)目評(píng)分的平均值，rv，I表示 v對(duì) I的評(píng)分。

3.4算法描述

UTSSCF算法的推薦步驟可分為用戶相似度計(jì)算、用戶信任度和社會(huì)相似度計(jì)算、形成最近鄰集、預(yù)測(cè)評(píng)分、產(chǎn)生推薦結(jié)果5個(gè)階段。算法1為UTSSCF算法的具體實(shí)現(xiàn)步驟。

算法1 UTSSCF算法

輸入：用戶-項(xiàng)目矩陣 UI，社交網(wǎng)絡(luò) S，目標(biāo)用戶 u，其它用戶 v，推薦項(xiàng)目的個(gè)數(shù) k，待推薦的項(xiàng)目集合Ir。

輸出：給u的推薦結(jié)果Re。

步驟1：根據(jù)UI，利用式(4)計(jì)算u與v的Si(u，v)；

步驟2：根據(jù)S，先按定義2得到u對(duì)v的T(u，v)，并按式(1)計(jì)算出 tr(u，v)，然后按定義 3計(jì)算 u對(duì) v的T′(u，v)，接著按式(2)計(jì)算 u對(duì) v的 Tr(u，v)，最后按式(3)計(jì)算u對(duì)v的Ss(u，v)；

步驟 3：對(duì)步驟 1和步驟 2得到的 Si(u，v)、Tr(u，v)和Ss(u，v)利用式(5)計(jì)算出We(u，v)。然后，根據(jù)We(u，v)為u選取最近鄰集Ns；

步驟 4：對(duì)于 Ir中的每個(gè)項(xiàng)目 I，根據(jù)式(6)計(jì)算 u對(duì)I的 Pu，I；

步驟5：根據(jù)步驟4得到的Pu，I，將 Ir中的所有I進(jìn)行排序，選擇前top-k個(gè)I作為給u的Re。

4　實(shí)驗(yàn)設(shè)計(jì)與分析

4.1實(shí)驗(yàn)數(shù)據(jù)來(lái)源

實(shí)驗(yàn)采用的數(shù)據(jù)集是目前在度量算法推薦精度中較常用的Epinion1數(shù)據(jù)集，由49 290個(gè)用戶、139 738個(gè)項(xiàng)目、664 824個(gè)評(píng)分和487 182條信任聲明組成。其中評(píng)分是從1到5的整數(shù)，信任值是0或者1（0表示不信任，1表示信任）。

4.2實(shí)驗(yàn)評(píng)價(jià)標(biāo)準(zhǔn)

實(shí)驗(yàn)采用平均絕對(duì)誤差MAE(Mean Absolute Error)和均方根誤差RMSE(Root Mean Square Error)衡量算法的推薦精度。MAE和RMSE的計(jì)算分別如式(7)和式(8)所示。

其中，n為評(píng)分的總數(shù)，pi，j代表用戶 i對(duì)項(xiàng)目 j的預(yù)測(cè)評(píng)分，ri，j代表用戶 i對(duì)項(xiàng)目 j的實(shí)際評(píng)分，MAE值和RMSE值越小表示推薦精度越高。

4.3實(shí)驗(yàn)結(jié)果與分析

為驗(yàn)證 UTSSCF算法的推薦精度，隨機(jī)將 Epinion數(shù)據(jù)集的80%作為訓(xùn)練集，剩余的20%作為測(cè)試集。訓(xùn)練集用來(lái)訓(xùn)練或者學(xué)習(xí)算法中的相關(guān)參數(shù)，測(cè)試集用來(lái)驗(yàn)證推薦結(jié)果的精度。

實(shí)驗(yàn)1（參數(shù) α、β、γ的學(xué)習(xí)）：因?yàn)?α+β+γ=1，所以只需要對(duì)任意2個(gè)參數(shù)進(jìn)行學(xué)習(xí)即可。實(shí)驗(yàn)中分別考慮當(dāng)α=0.1、β從0.1到0.8變化時(shí)，及當(dāng)α每增加0.1直到0.8、β從0.1到0.8變化時(shí)對(duì)推薦精度的影響。經(jīng)實(shí)驗(yàn)發(fā)現(xiàn)，當(dāng)α=0.2、β=0.4、γ=0.4時(shí)是最優(yōu)值。

實(shí)驗(yàn) 2（鄰居數(shù)的影響）：實(shí)驗(yàn) 2是觀察 UTSSCF算法的MAE值和RMSE值隨鄰居數(shù)變化而變化的情況。當(dāng)鄰居數(shù)分別取 5、10、15、20、25、30、35、40時(shí)，實(shí)驗(yàn)結(jié)果如圖1所示。

圖1　鄰居數(shù)對(duì)MAE值和RMSE值的影響

從圖1可以看出UTSSCF算法的MAE值和RMSE值隨著鄰居數(shù)的增加先逐漸減小再逐漸增加。在鄰居數(shù)為30時(shí)，UTSSCF算法的MAE值和RMSE值均達(dá)到最小值。這說(shuō)明當(dāng)鄰居數(shù)為30時(shí)，UTSSCF算法的推薦精度最高。

實(shí)驗(yàn)3（USTTCF算法與其他算法的比較）：實(shí)驗(yàn)3的目的是比較UTSSCF算法與其他算法的推薦精度。實(shí)驗(yàn)3中參數(shù)設(shè)置為 α=0.2，β=0.4，γ=0.4，鄰居數(shù)為 30，實(shí)驗(yàn)結(jié)果如圖2所示。實(shí)驗(yàn)中選擇以下算法與UTSSCF算法進(jìn)行對(duì)比：(1)協(xié)作過(guò)濾推薦算法（Collaborative Filtering Recommendation Algorithm，CF）；(2)基于用戶相似度的協(xié)作過(guò)濾推薦算法[11]（User Similarity-based Collaborative Filtering Recommendation Algorithm，USCF）；(3)基于綜合信任度的協(xié)作過(guò)濾推薦算法[5]（Comprehensive Trust-based Collaborative Filtering Recommendation Algorithm，CTCF）。

圖2　各類算法的比較

從圖2可以看出USCF算法優(yōu)于CF算法，CTCF算法優(yōu)于USCF算法，而UTSSCF算法又優(yōu)于CTCF算法。USCF算法優(yōu)于 CF算法是因?yàn)?USCF算法針對(duì)社會(huì)網(wǎng)絡(luò)對(duì)用戶相似度進(jìn)行重新定義，所以USCF算法在該實(shí)驗(yàn)數(shù)據(jù)集上取得了比CF算法更好的實(shí)驗(yàn)結(jié)果。CTCF算法優(yōu)于USCF算法是因?yàn)镃TCF算法考慮了用戶信任關(guān)系，由此可見(jiàn)，考慮用戶信任關(guān)系確實(shí)有助于提高算法的推薦精度。UTSSCF算法優(yōu)于 CTCF算法是因?yàn)閁TSSCF不僅考慮了用戶信任關(guān)系，還有社會(huì)相似度。此外，在圖2所示的整個(gè)變化過(guò)程中，UTSSCF算法的MAE值和RMSE值比其它算法都低，這說(shuō)明UTSSCF算法能夠提高推薦精度。

5　結(jié)論

針對(duì)社交網(wǎng)絡(luò)中個(gè)性化推薦精度不高和數(shù)據(jù)稀疏的問(wèn)題，提出了一個(gè)基于用戶信任度和社會(huì)相似度的協(xié)作過(guò)濾算法。首先根據(jù)用戶-項(xiàng)目矩陣計(jì)算用戶相似度，然后通過(guò)社交網(wǎng)絡(luò)計(jì)算用戶信任度和社會(huì)相似度并將三者融合，最后根據(jù)融合后的值形成最近鄰集，并據(jù)此產(chǎn)生推薦結(jié)果。經(jīng)實(shí)驗(yàn)分析，UTSSCF算法較其他算法在解決社交網(wǎng)絡(luò)的推薦問(wèn)題時(shí)有更高的推薦精度。UTSSCF算法只考慮了用戶信任度和社會(huì)相似度，而社交網(wǎng)絡(luò)中的社交信息還有很多，如社區(qū)、上下文信息、主題等。在協(xié)作過(guò)濾算法中引入更多社交信息是后續(xù)要研究的內(nèi)容。

[1]王國(guó)霞，劉賀平.個(gè)性化推薦系統(tǒng)綜述[J].計(jì)算機(jī)工程與應(yīng)用，2012，48(7)：66-76.

[2]王玉祥，喬秀全，李曉峰，等.上下文感知的移動(dòng)社交網(wǎng)絡(luò)服務(wù)選擇機(jī)制研究[J].計(jì)算機(jī)學(xué)報(bào)，2010，33(11)：2126-2135.

[3]QU W，SONG K S，ZHANG Y F，et al.A novel approach based on multi-view content analysis and semi-supervised enrichment for movie recommendation[J].Journal of Computer Science and Technology，2013，28(5)：776-787.

[4]王立才，孟祥武，張玉潔.上下文感知推薦系統(tǒng)[J].軟件學(xué)報(bào)，2012，23(1)：1-20.

[5]朱強(qiáng)，孫玉強(qiáng).一種基于信任度的協(xié)同過(guò)濾推薦方法[J].清華大學(xué)學(xué)報(bào)：自然科學(xué)版，2014，54(3)：360-365.

[6]HWANG W S，LI S，KIM S W，et al.Data imputation using a trust network for recommendation[C].Proceedings of the companion publication of the 23rd international conference on World wide web companion.International World Wide Web Conferences Steering Committee，2014：299-300.

[7]YIN C，CHU T.Improving personal product recommendation via friendships'expansion[J].Journal of Computer and Communications，2013，1(5)：1-8.

[8]DENG S G，HUANG L T，WU J，et al.Trust-based personalized service recommendation:A network perspective[J]. Journal of Computer Science and Technology，2014，29(1)：69-80.

[9]JAMALI M，ESTER M.A matrix factorization technique with trust propagation for recommendation in social networks[C]. Proceedings of the 4th ACM conference on Recommender systems.ACM，2010：135-142.

[10]GUO G，ZHANG J，THALMANN D.Merging trust in collaborative filtering to alleviate data sparsity and cold start[J].Knowledge-Based Systems，2014，57(2)：57-68.

[11]榮輝桂，火生旭，胡春華，等.基于用戶相似度的協(xié)同過(guò)濾推薦算法[J].通信學(xué)報(bào)，2014，35(2)：16-24.

Collaborative filtering algorithm based on user trust and social similarity

Yang Haiyue1，Zhu Yuting1，Shi Huaji1，Xu Hui2
(1.School of Computer Science and Telecommunication Engineering，Jiangsu University，Zhenjiang 212013，China；2.Daquan Group Company，Yangzhong 212211，China)

Personalized recommendation algorithm as an effective method to solve the information overload problem has become a research hotspot in social networks.Without considering some important social information of social networks and the data sparsity, the collaborative filtering algorithm which is a widely used personalized recommendation algorithm has poor recommendation effect for recommendation issues of social networks.Therefore,this paper proposes a collaborative filtering algorithm based on user trust and social similarity.Firstly,the algorithm calculates user similarity according to the user-item matrix and calculates user trust as well as social similarity through constructed user network.Next,the user similarity,user trust and social similarity will be merged to form a comprehensive value,which is used to produce neighbors.Accordingly,recommendations are produced.The experimental results show that the proposed algorithm has higher recommendation accuracy than other algorithms in solving the recommendation issues of social networks.

collaborative filtering；sparse data；user trust；social similarity；social networks

TP301.6

A

10.16157/j.issn.0258-7998.2016.01.026

江蘇省科技支撐計(jì)劃（BE2011156）

2015-08-18)

楊海月（1992-），通信作者，女，碩士研究生，主要研究方向：個(gè)性化服務(wù)、數(shù)據(jù)庫(kù)技術(shù)，E-mail：haiyue_yang1@163.com。

朱玉婷（1991-），女，碩士研究生，主要研究方向：社會(huì)網(wǎng)絡(luò)分析。

施化吉（1964-），男，碩士，教授，主要研究方向：智能信息處理、社會(huì)網(wǎng)絡(luò)分析。

中文引用格式：楊海月，朱玉婷，施化吉，等.基于用戶信任度和社會(huì)相似度的協(xié)作過(guò)濾算法[J].電子技術(shù)應(yīng)用，2016，42(1)：100-103.

英文引用格式：Yang Haiyue，Zhu Yuting，Shi Huaji，et al.Collaborative filtering algorithm based on user trust and social similarity [J].Application of Electronic Technique，2016，42(1)：100-103.