0 引言

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

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

1 用戶信任度計算

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

    定義1（社交網絡S）設U表示S中用戶節點集合，E表示S中用戶間的直接信任關系集合，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有直接聯系，則u對v有直接信任關系，并用直接信任度T進行度量。

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

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

1.2 間接信任度計算

    若u對v有間接信任關系，則可用間接信任度T′進行度量。

    定義3（間接信任度T′）若在S中至少存在一條從u到v的路徑，則u對v有間接信任關系，又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)。

    另外，根據小世界理論設置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]的研究表明用戶間共有的朋友數越多，其社交、興趣、偏好越相似。因此，用戶間共有的朋友數也是一個影響社交網絡個性化推薦的重要因素，文中用社會相似度定量其影響程度。

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

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

3 UTSSCF算法

3.1 用戶相似度計算

    計算用戶相似度是為了尋找興趣偏好相似的用戶，從而據此產生推薦結果。設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 用戶相似度、用戶信任度和社會相似度的融合

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

    設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 產生推薦結果

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

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

3.4 算法描述

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

    算法1 UTSSCF算法

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

    輸出：給u的推薦結果Re。

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

    步驟2：根據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)。然后，根據We(u，v)為u選取最近鄰集N_s；

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

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

4 實驗設計與分析

4.1 實驗數據來源

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

4.2 實驗評價標準

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

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

4.3 實驗結果與分析

    為驗證UTSSCF算法的推薦精度，隨機將Epinion數據集的80%作為訓練集，剩余的20%作為測試集。訓練集用來訓練或者學習算法中的相關參數，測試集用來驗證推薦結果的精度。

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

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

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

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

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

5 結論

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

參考文獻

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

[2] 王玉祥，喬秀全，李曉峰，等.上下文感知的移動社交網絡服務選擇機制研究[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] 王立才，孟祥武，張玉潔.上下文感知推薦系統[J].軟件學報，2012，23(1)：1-20.

[5] 朱強，孫玉強.一種基于信任度的協同過濾推薦方法[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] 榮輝桂，火生旭，胡春華，等.基于用戶相似度的協同過濾推薦算法[J].通信學報，2014，35(2)：16-24.