0 引言

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

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

1 用戶信任度計算

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

    定義1（社交網(wǎng)絡S）設U表示S中用戶節(jié)點集合,，E表示S中用戶間的直接信任關(guān)系集合,，W表示S中用戶間的直接信任度T的集合，S則可用三元組表示成S(U,，E,，W)。其中,，U={u₁,，u₂，…，u_n},，|U|=n,；E={<u，v>|u,，v∈U},；W={T(u，v)|u,，v∈U},。

1.1 直接信任度計算

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

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

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

1.2 間接信任度計算

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

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

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

1.3 用戶信任度計算

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

2 社會相似度計算

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

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

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

3 UTSSCF算法

3.1 用戶相似度計算

    計算用戶相似度是為了尋找興趣偏好相似的用戶，從而據(jù)此產(chǎn)生推薦結(jié)果,。設S中u和v已評價項目并集為I_uv=I_u∪I_v,，則u和v的用戶相似度計算如式(4)所示。

其中,，r_u,，i和r_v,，i分別表示u和v對i的評分，R_u和R_v分別表示u和v對I_uv中所有項目評分的平均值,。

3.2 用戶相似度,、用戶信任度和社會相似度的融合

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

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

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

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

    計算出We(u,，v)后,，選擇We(u，v)最大的l個用戶作為u的最近鄰集Ns,。根據(jù)Ns中的用戶評分數(shù)據(jù)預測u對未評價項目I的評分P_u,，I，并將預測評分最高的k個項目推薦給u,。預測評分的計算如式(6)所示,。

其中，R_u和R_v分別表示u和v對所有項目評分的平均值,，r_v,，I表示v對I的評分。

3.4 算法描述

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

    算法1 UTSSCF算法

    輸入：用戶-項目矩陣UI，社交網(wǎng)絡S,，目標用戶u,，其它用戶v，推薦項目的個數(shù)k,，待推薦的項目集合I_r,。

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

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

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

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

    步驟4：對于Ir中的每個項目I，根據(jù)式(6)計算u對I的P_u,，I,；

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

4 實驗設計與分析

4.1 實驗數(shù)據(jù)來源

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

4.2 實驗評價標準

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

其中，n為評分的總數(shù),，p_i,，j代表用戶i對項目j的預測評分，r_i,，j代表用戶i對項目j的實際評分,，MAE值和RMSE值越小表示推薦精度越高。

4.3 實驗結(jié)果與分析

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

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

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

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

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

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

5 結(jié)論

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

參考文獻

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

[2] 王玉祥，喬秀全,，李曉峰,，等.上下文感知的移動社交網(wǎng)絡服務選擇機制研究[J].計算機學報，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].軟件學報，2012,，23(1)：1-20.

[5] 朱強,，孫玉強.一種基于信任度的協(xié)同過濾推薦方法[J].清華大學學報：自然科學版，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é)同過濾推薦算法[J].通信學報,，2014，35(2)：16-24.