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）設(shè)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ù)小世界理論設(shè)置max(k+1)為6。若S中u到v的max(k+1)大于6，則T′(u，v)=0。

1.3 用戶信任度計算

    如上所述，文中把用戶信任度分為直接信任度和間接信任度，故用戶信任度是它們的綜合值。設(shè)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é)果。設(shè)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ù)稀疏的問題。

    設(shè)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 實驗設(shè)計與分析

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ù)設(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.