基于社會信任的協同過濾算法研究綜述

秦凱 吳家麗 宋益多 喬晨蕊

摘 要：隨著推薦技術的不斷發展，研究發現用戶更加偏好于相信熟人或者權威人士的推薦，因此，基于信任的推薦方法成為研究熱點。本文從社會網絡信任特征和基于信任的協同過濾算法研究情況進行分析總結，為未來對個性推薦方法和基于信任的協同過濾算法進行深入研究奠定基礎。文章最后針對目前基于信任的協同過濾算法研究現狀，對未來的發展方向進行展望。

關鍵字：個性化推薦；協同過濾；信任

中圖分類號：TP391.41 文獻標識號：A 文章編號：2095-2163（2015）04-

A Review of Collaborative Filtering Algorithm Based on Social Trust Relationships

QIN Kai， WU Jiali， SONG Yiduo， QIAO Chenrui

（School of Computer Science and Technology ，Harbin Engineering University， Harbin 150001， China ）

Abstract ：With the rapid development of recommendation technology， people have realized that users prefer to believe the recommendations from acquaintances or authorities. Recommended approaches based on social trust relationships have only recently been given research attention. This paper summarizes the feature of social trust networks and analysis collaborative filtering （CF） based social recommender systems. These lay the foundation for the research of individualization recommended technology and collaborative filtering algorithm based on social trust relationships. Facing to the research status of collaborative filtering algorithm based on social trust relationships， the paper prospects the future development directions.

Keywords： Personalized Recommendation； Collaborative Filtering； Trust

0 引 言

近年來隨著社會網絡的發展和網絡設備承載能力的提升，信息量急速增長，面對海量的數據，用戶很難在其中找到自己想要的信息，推薦系統應運而生。社會網絡的飛速興起為推薦技術發展帶來了前所未有的機遇和挑戰[1]。社會網絡促使網絡信息劇增，這使得用戶從中搜取需要的信息更加困難；另一方面，社會網絡將用戶的屬性、習慣更好地展現出來，便于從數據中挖掘出潛在的信息以用于個性化推薦，提高推薦準確度和效率。社會網絡中的用戶信任關系為個性化推薦算法研究開辟了一個新的領域[2-3]。

協同過濾算法是目前使用非常廣泛的個性化推薦算法之一。傳統的協同過濾算法主要分為兩類：基于用戶的協同過濾算法和基于項目的協同過濾算法。基于用戶的協同過濾算法是通過假設擁有相似興趣的用戶會對相似項目感興趣。例如，A和B曾經對很多相同的電影給予了相似的打分評價，那么如果A喜歡電影1，很大程度上B也可能喜歡電影1，以此為依據將電影1推薦給B。基于項目的協同過濾算法是假設同一個用戶可能會對具有相似特征的項目具有相似偏好。例如，用戶A對電影m、n、o、p、q都給予了很高的評價，其中m、n、o、p都具有外國、喜劇、滑稽的特征，那么算法將推測其偏愛外國滑稽喜劇類電影，可以將同為外國滑稽喜劇電影s推薦給A。協同過濾算法是利用集體智慧進行個性推薦的典型方法，相比于基于內容的推薦方法，解決了基于內容的推薦方法存在的特征抽取困難、過度擬合和難以跨領域等問題，但是協同過濾算法存在數據稀疏、用戶冷啟動、惡意推薦的問題，這些問題一定程度上制約著協同過濾算法的發展[2]。

社會網絡的興起、發展為協同過濾算法的發展提供了新思路。社會網絡可以提供與目標用戶有著直接或者間接社會關系的用戶信息，而用戶更傾向于相信朋友，利用這些有效的社會關系尋找目標用戶的最近鄰，可以有效緩解基于項目的協同過濾算法的冷啟動和惡意推薦問題。針對社會網絡中用戶間信任關系的傳遞性、非對稱性、主觀性等特點，學者從不同角度分析用戶間的信任關系以及信任關系對興趣相似度的相關性，以此進行結合社會信任的協同過濾算法研究[4-8]。

1 社會網絡信任和協同過濾算法

傳統協同過濾算法通過用戶-項目的歷史評分數據尋找興趣相似的用戶，根據相似用戶的選擇結果實施推薦。社會網絡信任關系為尋找相似興趣用戶提供了一個新的角度，符合用戶偏愛信任的人推薦的心理，同時也彌補了用戶-項目評分數據稀疏和選取最近鄰用戶依據單一的不足。社會網絡信任和傳統協同過濾算法是基于社會信任的協同過濾算法研究的兩個關鍵點，下面將逐一進行闡述。

1.1社會網絡信任

信任最初是一個社會學概念，描述一個主體假設另一個主體的行為與自己對其的預期剛好相同，表示第一個主體信任第二個主體。信任在不同的領域，概念稍有差別，社會網絡中的信任是指一個用戶通過依據其他用戶所做的選擇而形成占優策略的程度。在推薦系統中，可以利用信任來衡量一個用戶在多大程度上依賴其他用戶給出的推薦做出選擇[9-10]。

社會網絡中的信任具有主觀性、非對稱性、動態性、可傳遞性、自適應性等性質。信任的主觀性是指用戶對其他用戶的信任與否具有主觀性，一個用戶對不同用戶的信任評價不同，不同用戶對于同一個用戶的評價也可能存在差異。信任的非對稱性是指交互雙方的信任關系是不對稱的，用戶a對用戶b的信任和用戶b對用戶a的信任無必然聯系。信任的動態性表現在用戶之間的信任不會一成不變，會隨著時間、環境、上下文等影響變化[11]。信任還具有一定的弱傳遞性，假設a、b用戶之間存在信任關系，b、c用戶之間存在信任關系，那么a、c用戶之間可能也存在信任關系，信任的弱傳遞關系如圖1所示[12-14]。信任具有一定的自適應性，隨著信任的動態變化，其能夠自適應地更新。

圖1 信任弱傳遞關系示意圖

Fig.1 Weak trust transitive relation between nodes

根據信任的多個特性從不同角度對信任進行分類，具體描述如下：

局部信任與全局信任[14-15]：局部信任是指在系統中，目標用戶對鄰居用戶的信任度，全局信任是指用戶在整個系統中的可信度。局部信任是一個相對量，在同一個系統中，用戶之間的間接信任度是不同的，主要取決于目標用戶的位置，而每個用戶只有一個整體信任度。

初始信任與成熟信任：根據信任建立的時間，可以將信任分為初始信任和成熟信任。未進行過交互的用戶之間的信任關系稱為初始信任，用戶之間通過積累多次交互而得到的信任稱為成熟信任。

顯性信任與隱性信任[6、16]：根據信任獲取的方式的不同，信任分為顯性信任和隱性信任。用戶明確表明對其他用戶的信任聲明，這樣的信任為顯性信任，用戶之間沒有明確表明信任關系，需要通過用戶的操作行為或者交互過程得到信任來判定信任關系的則定義為隱性信任。

直接信任與間接信任[17]：根據信任的可傳遞性，可將信任分為直接信任和間接信任。直接信任是指用戶通過交互或者關注等行為建立的直接信任關系，間接信任是指用戶間的間接關聯關系，需要通過數個具有直接信任關系的用戶傳遞建立的間接信任關系。

針對基于社會信任的協同過濾算法使用的不同場景，研究者選取在該場景下對用戶間信任關系影響較大的特性進行分析研究，將相關信任特性對用戶選擇帶來的影響添加進傳統協同過濾算法中，以得到最符合算法使用場景，推薦效果更好的算法。

1.2協同過濾算法

協同過濾算法的思想是模擬現實生活中人與人之間“口口相傳”形式的信息推薦，其中假設擁有相似興趣的用戶可能會喜歡相似的項目或者用戶可能對相似的項目表現相似的偏好程度。結合信任的協同過濾算法主要是以基于用戶的協同過濾算法為基礎，故本文著重介紹基于用戶的協同過濾算法。

基于用戶的協同過濾算法一般分為三個步驟（如圖2所示）：

（1） 建立用戶模型

用戶模型是一個用戶對項目的評分矩陣，可以用Rm*n表示，其中m表示用戶數，n表示項目數。Rm*n的值表示用戶對某個項目的評分，即以評分高低描述用戶對項目的喜好程度，用戶對某些項目沒有評分則用0填充。

（2） 計算用戶相似度并尋找最近鄰

通過用戶模型計算用戶相似度一般有兩種方法：Pearson相關系數法和夾角余弦相似度法。Pearson相關系數法在計算相似性的過程中主要是以用戶平均分為標準，比較目標用戶和鄰居對項目評分偏離平均評分的程度。通過偏離程度判斷用戶相似度。夾角余弦在基于用戶的方法中，把用戶的評分看作向量，通過比較兩個向量的夾角余弦判斷用戶和鄰居的評分相似度。根據計算的相似度尋找目標用戶的最近鄰，常用的有固定值法和閾值法，選擇與目標用戶相似度較高的一部分鄰居用戶。

（3） 評分預測給出推薦列表

通過最近鄰對于項目的評分情況，預測目標用戶的評分，將評分由高到低排序，選擇評分高的項目產生推薦列表，進行推薦。

圖2 傳統協同過濾算法流程圖

Fig.2 Flow chart of traditional collaborative filtering algorithms

2 基于社會信任的協同過濾算法發展

結合信任的協同過濾算法較傳統的協同過濾算法更符合人們實際生活中的對于推薦結果的選擇規律，具有更好的推薦精確度。目前，結合信任的協同過濾算法研究從使用信任關系的角度看主要分為三類：其一是在建立用戶模型時使用信任關系，利用目標用戶與其他用戶的信任關系篩選出目標用戶的用戶-項目評分矩陣，緩解了矩陣稀疏性問題的同時降低了評分矩陣的維度，增加計算效率；其二是在計算用戶相似度和尋找最近鄰時使用信任關系，可以利用信任關系和用戶模型共同計算用戶相似度，也可以根據用戶信任關系篩選目標用戶的最近鄰；其三是綜合以上兩種方法，建立多維度的協同過濾算法。

2.1用戶模型中的信任研究

用戶模型是協同過濾算法的基礎，旨在建立一個用戶-項目評分矩陣，以便后續根據評分矩陣提供的用戶評分關系得到相似用戶。通常情況下，推薦系統中用戶和項目的數量都很龐大，然而用戶對項目的評分參與度不高，矩陣稀疏，這將導致建立用戶模型計算量較大并且有效數據量小，計算結果可用度不高。用戶模型中結合信任關系的研究是使用社會網絡中收集到的用戶信任關系圖構造用戶信任關系矩陣，通過用戶信任關系矩陣和用戶-項目評分矩陣組合得到信任用戶-項目評分矩陣。以信任用戶-項目評分矩陣替代傳統算法中用戶-項目評分矩陣計算用戶之間的相似性，進而預測用戶項目評分，給出推薦列表。引入信任關系進行用戶模型的數據篩選，能夠有效地改善傳統算法中構造用戶模型存在的問題[18]。算法流程如圖3所示。

圖3 在用戶模型中的結合信任算法流程

Fig. Flow chart of the CF algorithms based on trust in user model

在建立用戶模型過程中集合信任機制，根據信任的特性也會有不同的解決方案。文獻[19]利用靜態信任值構建信任用戶-項目評分矩陣，只有被目標用戶所信任的用戶給出的項目評分會被納入推薦過程中，同時利用信任的動態性，動態地更新信任值。文獻[20]提出基于初始信任的協同過濾方法，綜合考慮了信任的動態性和可傳遞性因素構造出用戶信任評分矩陣。文獻[21]通過特征學習的方法確認相似用戶，綜合社會信任關系得到推薦模型。

2.2 用戶相似度計算和尋找最近鄰中的信任研究

隨著協同過濾算法的深入發展，用戶概貌注入攻擊給僅靠用戶-項目評分矩陣得到用戶相似性進而預測評分的傳統算法帶來了極大挑戰。將用戶相似度和用戶間信任度結合共同作為鄰居選取的雙重依據，有效地解決了推薦系統的安全問題，也提高了推薦質量[22-24]。算法流程圖如圖4所示。

圖4 用戶相似度結合信任值算法流程圖

Fig.4 Flow chart of the CF algorithms based on trust in computing user similarity

文獻[25]采用的融合用戶可疑度的多維信任模型，計算得到目標用戶對每個興趣相似用戶的信任度，并以此作為選取可信鄰居用戶集的依據。文獻[17]在基于信任的協同過濾算法中從全局信任、局部信任和直接信任、間接信任的角度計算信任值，將信任度和相似度結合，得到最近鄰。文獻[26]在從直接信任和間接信任的角度基礎上，考慮直接信任的時間衰減因素，更符合實際情況，并且提出動態確認相似鄰居閾值的方法，提升了推薦算法的準確性和魯棒性。

2.3 多維度的信任研究

上面兩節描述的都是只在構建用戶模型或者用戶相似度計算過程中使用用戶間的信任關系，還有一些研究者發現，根據推薦使用的情景，在不同步驟考慮信任的不同特性，既使用信任值來篩選用戶又用作計算評價時的合并權重，給協同過濾算法提出了新的解決思路。

文獻[27]中引入帕雷托最優理論，以信任度為基礎結合用戶相似矩陣降低稀疏性，并且根據用戶信任度、相似度和可行度多維重構信任網絡。以重構信任網絡信任度和用戶相似度計算項目預測評分。文獻[28]提出了結合信任和相似度的多視圖過濾方法，利用概率統計方法有效地解決了算法的冷啟動問題，同時提高了推薦的準確率和覆蓋率。文獻[25]提出的基于可靠用戶的top-N推薦方法，在使用用戶信任度篩選可靠用戶集，基于有效用戶的評分信息采用多維度項目選取方法選取項目，最后采用均值的方法得到項目的預測評分。文獻[29]通過重啟動隨機游走度量用戶間信任，將用戶間信任情況作為用戶間相似性計算的一部分；然后利用相關性作為項目評分的權重，預測目標用戶對位置項目的喜愛程度，進行推薦。

3未來研究方向

協同過濾算法的研究在學者的不斷努力下逐步走向成熟。結合社會信任的協同過濾算法在一定程度上緩解了算法的冷啟動、稀疏性等問題，但是社會信任關系紛繁復雜，影響因素較多，現有算法仍存在著安全性差、推薦效果不佳等問題。因此，大數據背景下，基于信任的協同過濾算法在某些方面仍有待完善，未來的研究方向如下。

3.1 算法安全性[30]

隨著互聯網應用日益廣泛，用戶的真實信息越來越多地暴露在網絡上，這些信息有利于系統給用戶提供個性化的服務和推薦，但是網上的信息越貼近用戶隱私遭受竊取的危險越大。在很多領域，推薦結果會引起不同的商業價值，這也使得一部分人深入研究推薦算法原理，通過惡意編造數據等方法力圖修改推薦結果，由此即違背了推薦系統設計的本意和推薦的公平性。社會網絡中的信任關系在一定程度上緩解了推薦的安全性問題，但是算法的安全性問題仍然需要給予更多的關注。

3.2 考慮現實社會關系[31-32]

社交網絡中用戶之間的信任關系通常以“好友”、“關注”等方式刻畫，人們通常認為信任度和興趣相似度具有正相關性。但是信任具有方向性，社會關系不同會對信任關系帶來影響。在微博中，商家用戶會關注普通用戶，這兩者之間構成了信任關系，但是普通用戶跟商家用戶的興趣相似度其實并不高。同時，社會關系紛繁復雜，在不同情境下，信任度和興趣相似度也不是時刻均為正相關。例如，同事之間的信任關系和家人之間的信任關系對用戶的興趣影響就各有不同[33]。社交網絡中的關鍵用戶的影響力對推薦也會起到至關重要的作用，如何區分用戶社會關系，合理確定不同信任影響的權重研究有待進一步深化。

3.3 算法時效性[11]

信任具有動態性，信任度和興趣相似度會隨著時間變化或者因為某一次推薦結果而變化[34]。而且用戶的偏好會隨著外部環境不同而發生變化，如何在不同情境下動態地計算得到信任值，進而得到信任變化對用戶興趣的影響，實時更新推薦結果也有待于研究者的深入探索與挖掘。

3.4 基于情感的推薦

基于情感的服務是下一代互聯網服務的發展方向之一，情感分析能夠分析用戶對事物的喜好、厭惡程度，從更深層次了解用戶，為用戶提供最優質的服務。目前，基于情感的推薦研究多集中在用戶標簽分析和基于內容的分析上，其中存在著計算數據量大，分析結果不準確等問題，社會信任關系和情感分析結合的研究方法至今仍處于萌芽階段。如何結合社會信任和情感分析技術，構建新型推薦框架將是推薦算法研究的一個重要領域。

4 結束語

本文總結了目前基于信任的協同過濾算法的研究現狀，通過描述信任的特性和傳統的協同過濾算法對課題的研究背景進行展現。同時，從結合信任關系的角度，重點介紹了基于信任的協同過濾算法發展方向，最后針對當前課題的發展過程中出現的不足和挑戰，提出了社會網絡中協同過濾推薦算法未來的研究方向，為協同過濾算法研究者工作方向提供指引作用。

參考文獻：

[1] YANG X， GUO Y， LIU Y， et al. A survey of collaborative filtering based social recommender systems[J]. Computer Communications， 2014， 41（5）：1–10.

[2] ADOMAVICIUS A， GEDIMINAS T. Toward the next generation of recommender systems： A survey of the state-of-the-art and possible extensions[J]. IEEE Transactions on Knowledge & Data Engineering， 2005， 17（6）：734-749.

[3] 黃仁， 孟婷婷. 個性化推薦算法綜述[J]. 中小企業管理與科技， 2015 （8）： 271-273.

[4] KONSTAS I， STATHOPOULOS V， JOSE J M. On social networks and collaborative recommendation[C]// Proceedings of the 32nd International ACM SIGIR Conference on Research and development in Information Retrieval， Boston， Massachusetts：ACM，2009：195-202.

[5] BOBADILLA J， ORTEGA F， HERNANDO A， et al. Recommender systems survey[J]. Knowledge-Based Systems， 2013， 46（1）：109–132.

[6] CHEN C， ZENG J， ZHENG X， et al. Recommender system based on social trust relationships[C]//e-Business Engineering （ICEBE）， 2013 IEEE 10th International Conference on ，Coventry： IEEE， 2013： 32-37.

[7] 李慧， 馬小平， 胡云，等. 融合社會網絡與信任度的個性化推薦方法研究[J]. 計算機應用研究， 2014， 31（3）： 808-810.

[8] KONSTAS I， STATHOPOULOS V， JOSE J M. On social networks and collaborative recommendation[C]//Proceedings of the 32nd international ACM SIGIR conference on Research and development in information retrieval，Boston， Massachusetts：ACM， 2009： 195-202.

[9] LIU F， LEE H J. Use of social network information to enhance collaborative filtering performance[J]. Expert Systems with Applications， 2010， 37（7）：4772–4778.

[10]PHAM M C， CAO Y， KLAMMA R， et al. A clustering approach for collaborative filtering recommendation using social network analysis[J]. Journal of Universal Computerence， 2011， 17（4）：583-604.

[11]LIU D， LAI C， CHIU H. Sequence-based trust in collaborative filtering for document recommendation.[J]. International Journal of Human-Computer Studies，2011， 69（9）：587–601.

[12] 馮萍萍. 融合雙重信任網絡的協同過濾推薦算法研究[D]. 秦皇島：燕山大學，2014.

[13] Agarwal V， Bharadwaj K K. Trust-enhanced recommendation of friends in web based social networks using genetic algorithms to learn user preferences[M]//Trends in Computer Science， Engineering and Information Technology. Berlin Heidelberg： Springer ， 2011： 476-485.

[14]XU X W， WANG F D .Trust -based collaborative filtering algorithm [C]//International Symposium on Computational Intelligence and Design 2012，Hangzhou：IEEE，2012：321-324

[15]CHENG J， ZHOU J， ZHANG Y. Preference-based top-K influential nodes mining in social networks[C]//Trust Security & Privacy in Computing & Communications IEEE International，Changsha： IEEE， 2011：1512-1518.

[16] 李湛. 基于社會信任網絡的協同過濾推薦方法研究[D]. 大連：大連理工大學， 2013.

[17]吳慧， 卞藝杰， 趙喆等. 基于信任的協同過濾算法[J]. 計算機系統應用， 2014， （7）：131-135.

[18]GHAZARIAN S， NEMATBAKHSH M. Enhancing memory-based collaborative filtering for group recommender systems[J]. Expert Systems with Applications， 2015，42（7）：3801-3812

[19]劉英南. 在線社會網絡中基于動態信任的推薦機制研究[D]. 上海：華東師范大學，2014.

[20]劉世光. 基于初始信任的協同過濾方法研究[D].秦皇島： 燕山大學，2014.

[21] MA H， KING I， LYU M R. Learning to recommend with social trust ensemble[C]// Proceedings of International Acm Sigir Conference on Research & Development in Information Retrieval， Boston， Massachusetts：ACM，2009：203-210.

[22]Cai X， Bain M， Krzywicki A， et al. Collaborative filtering for people to people recommendation in social networks[M]// Advances in Artificial Intelligence. Berlin Heidelberg：Springer， 2011： 476-485.

[23]BOBADILLA J， SERRADILLA F， HERNANDO A. Collaborative filtering adapted to recommender systems of e-learning[J]. Knowledge-Based Systems， 2009， 22（4）：261–265.

[24]Liu Q， Gao Y， Peng Z. Advances in Swarm Intelligence[M]. Germany： Springer Berlin Heidelberg， 2012：164-174.

[25]賈冬艷. 基于多維信任模型的可信推薦方法研究[D]. 秦皇島：燕山大學， 2013.

[26] XIE Shengjun. A collaborative filtering recommendation algorithm improved by trustworthiness[J]. International Journal of Future Generation Communication and Networking， 2014，7（2）：35-46.

[27] AZADJALAL M M， MORADI P， ABDOLLAHPOURI A. Application of game theory techniques for improving trust based recommender systems in social networks[C]//Computer and Knowledge Engineering （ICCKE）， 2014 4th International eConference on， Mashhad： IEEE， 2014： 261-266.

[28] GUO G， ZHANG J， YORKE-SMITH N. Leveraging multiviews of trust and similarity to enhance clustering-based recommender systems[J]. Knowledge Based Systems， 2015， （9）：14–27.

[29] 俞琰， 邱廣華. 融合社會網絡的協同過濾推薦算法研究[J]. 現代圖書情報技術， 2012， （6）：54-59

[30]DOKOOHAKI N， KALELI C， POLAT H， et al. Achieving optimal privacy in trust-aware social recommender systems[J]. Lecture Notes in Computer Science， 2010， 6430：62-79.

[31]WEI C， KHOURY R， FONG S. Web 2.0 Recommendation service by multi-collaborative filtering trust network algorithm[J]. Information Systems Frontiers， 2013， 15（4）：533-551.

[32]朱強，孫玉強. 一種基于信任度的協同過濾推薦方法[J]. 清華大學學報（自然科學版），2014，03：360-365.

[33]武春嶺， 胡云冰， 魯先志. 基于個人和社會隱含因子的社會化推薦[J]. 計算機應用與軟件， 2014， （9）：98-101. DOI：10.3969/j.issn.1000-386x.2014. 09.025.

[34]MOGHADDAM M G， MUSTAPHA N， MUSTAPHA A， et al. AgeTrust： A New Temporal Trust-Based Collaborative Filtering Approach[C]//International Conference on Information Science & Applications， Seoul， South Korea：IEEE， 2014：1 - 4.