基于用戶興趣和社交信任的聚類推薦算法

肖曉麗 錢婭麗 李旦江 譚柳斌

摘要：個性化推薦系統中使用最廣泛的算法是協同過濾算法，針對該算法存在的數據稀疏和擴展性差問題，提出了一種基于用戶興趣和社交信任的聚類推薦算法。該算法首先基于聚類技術根據用戶評分信息將具有相同興趣的用戶聚為一類，并建立基于用戶興趣相近的鄰居集合。為了提高興趣相似度計算的準確性，采用了修正余弦計算公式來消除評分標準的差異問題。然后，引入信任機制，通過定義直接信任、間接信任、傳遞路徑和計算方法來度量社交網絡用戶之間隱含的信任值，將社交網絡轉換為信任網絡，依據信任程度來創建基于社交信任的鄰居集合。通過加權的方式將基于兩種鄰居集合的預測值融合起來為用戶產生項目的推薦。在Douban數據集上進行仿真實驗，確定了最優的協調因子值和分類數值，并與基于用戶的協同過濾算法和基于信任的推薦算法進行對比，實驗結果表明，所提算法的平均絕對誤差（MAE）減少了6.7%，準確率（precision）、覆蓋（recall）和F1值分別增加了25%、40%和37%，有效提高了推薦系統的推薦質量。

關鍵詞：協同過濾；數據稀疏；社交信任；聚類技術；信任網絡

中圖分類號：TP391.1 文獻標志碼：A

Abstract：Collaborative filtering algorithm is the most widely used algorithm in personalized recommendation system. Focusing on the problem of date sparseness and poor scalability， a new clustering recommendation algorithm based on user interest and social trust was proposed. Firstly， according to user rating information， the algorithm divided users into different categories by clustering technology， and set up a user neighbor set based on interest. In order to improve the accuracy of the calculation of interest similarity， the modified cosine formula was used to eliminate the difference of user scoring criteria. Then， the trust mechanism is introduced to measure implicit trust value among users by defining the direct trust calculation method and indirect trust calculation method， converted a social network to a trust network， and set up a user neighbor set based on trust. Finally， this algorithm combined the predictive value of two neighbor sets to generate recommendations for users by weighting method. The simulation experiment was carried out to test the performance on Douban dataset， found suitable value of α and k. Compared with collaborative filtering algorithm based on users and recommendation algorithm based on trust， the Mean Absolute Error （MAE） decreased by 6.7%， precision， recall and F1 increased by 25%，40% and 37%. The proposed algorithm can effectively improve the quality of recommendation system.

Key words：collaborative filtering； date sparseness； social trust； clustering technique； trust network

0 引言

隨著Web 2.0時代的到來，互聯網上的資源與信息迅速膨脹，用戶很難在海量信息中獲得對自己有用的信息[1]。解決這類問題最有效的工具就是個性化推薦系統，它通過分析用戶的喜好，為用戶推薦其感興趣的信息，從而節省篩選信息的時間[2]。

個性化推薦系統中使用最廣泛的算法是協同過濾算法，該算法需計算目標用戶（或項目）與全體用戶（或項目）之間的相似度，隨著用戶和項目的增加，數據稀疏和擴展性差問題成為影響推薦系統推薦質量的關鍵因素[3-4]。為了解決此問題，許多學者引入聚類技術對協同過濾算法進行優化，如尹航等[5]提出的采用聚類算法優化的k近鄰協同過濾算法，王明佳等[6]提出的基于模糊聚類的協同過濾算法，孫輝等[7]提出的一種相似度改進的用戶聚類協同過濾推薦算法，吳湖等[8]提出的兩階段聯合聚類協同過濾算法，王雪蓉等[9]提出的用戶行為關聯聚類的協同過濾推薦算法。上述方法在一定程度上改善了數據稀疏問題對推薦精度的影響；然而傳統的協同過濾算法及其改進算法都是利用用戶評分信息計算用戶之間的相似度[10]，在用戶評分信息不足的情況下不能夠得到準確的推薦結果。

用戶之間的信任關系作為社交網絡中一個重要信息，為系統推薦提供了依據[11]，許多學者在這個方面進行了研究，如鄒本友等[12]提出的基于用戶信任和張量分解的社會網絡推薦，張富國[13]提出的用戶多興趣下基于信任的協同過濾算法，王興茂等[14]提出的基于一跳信任模型的協同過濾推薦算法，楊興耀等[15]提出的基于信任模型填充的協同過濾推薦模型。目前大多數基于信任的個性推薦算法中信任關系值是事前給定的，如馮勇等[16]提出的基于社會網絡分析的協同推薦方法改進，將用戶預填的家人朋友同事關系直接轉換成信任度值，融入到用戶相似度計算中；夏小伍等[17]提出的基于信任模型的協同過濾推薦算法，是根據共同評分過的項目得出信任值；周璐璐[18]提出的融合社會信任關系的改進推薦系統，信任值來自事先給定的社會信任圖。然而大多數社交網絡并沒有提供用戶之間的顯式的信任關系值，如何挖掘用戶之間的隱式信任關系，度量用戶信任值是目前待解決的問題。

針對這些問題，本文提出一種基于用戶興趣和社交信任的協同過濾算法。該算法首先引入聚類技術根據用戶評分信息將用戶分為不同類別，在聚類的基礎上建立基于用戶興趣的鄰居集合。在用戶興趣相似度計算時，為了避免不同用戶的評分標準不一樣，本文采用了修正的余弦計算公式來消除評分標準的差異。同時，引入信任機制，度量社交網絡中用戶之間信任關系的強弱，通過定義直接信任、間接信任、傳遞路徑將社交網絡轉換為信任網絡，依據信任程度來創建基于社交信任的鄰居集合。最后，通過加權的方式將基于兩種鄰居集合的預測值融合起來為用戶產生推薦。在Douban數據集上進行實驗，與基于用戶的協同過濾算法和基于信任的推薦算法相比，本文不僅在平均絕對誤差方面擁有優秀的表現，而且在查準率和查全率方面同樣表現出色。

1 基于用戶興趣和社交信任的推薦算法

1.1 問題描述

本文主要利用用戶歷史評分信息和用戶社會關系來對用戶進行項目推薦，首先對這兩大數據進行描述。定義m個用戶的集合為U={u1，u2，…，um}，n個項目的集合為V={v1，v2，…，vn}。建立用戶及項目之間關系的模型，如圖1所示。其中，圓形代表用戶，三角形代表項目，實線箭頭連接著兩個用戶，代表兩個用戶之間的關注關系，虛線箭頭連接著用戶和項目，代表用戶的興趣。

2 本文算法步驟及時間復雜度分析

2.1 算法步驟

輸入 目標用戶u0，用戶評分信息，用戶關注關系信息；

輸出 評分最高的N個推薦項目。

步驟1 根據用戶評分信息建立用戶項目矩陣，根據用戶關注關系信息建立用戶關注關系矩陣。

步驟2 根據用戶項目評分矩陣，使用k均值聚類方法將用戶分類，得到k個類別的聚類中心。

步驟3 通過式（2）計算用戶u0和每個聚類中心的相似度，并將用戶u0加入到相似度最高的類。

步驟4 利用式（2）計算用戶u0與簇內所有用戶的相似度，得到基于用戶興趣的相似度sim_c（u0，u）值。

步驟5 根據用戶關注關系矩陣，利用式（3）、（5）、（6）計算用戶u0與集合U中用戶基于信任的相似度sim_t（u0，u）的值。

步驟6 根據基于用戶u0興趣的相似度和基于用戶信任的相似度，為用戶u0選擇基于用戶興趣的鄰居集合TU和基于用戶信任的鄰居集合FU。

步驟7 提取出集合TU和FU中所有用戶的評分項目，并去剔除用戶u0已經評分過的項目，構成候選集P。

步驟8 對于集合P中每個候選項目v，通過式（7）計算預測評分值，根據預測的評分降序排序并向用戶u0提供N個推薦項目。

2.2 時間復雜度分析

時間復雜度分析：在計算基于用戶興趣的相似度時，傳統的協同過濾算法是直接計算目標用戶u0與全體m個用戶之間的相似度，同時需要對比n個項目以確定共同評分過的項目，因此，目標用戶u0與所有用戶相似性的時間復雜度為O（m×n）。本文的算法在計算用戶興趣的相似度時引入了聚類的方法，離線產生聚類中心，在線僅需計算目標用戶與聚類中心之間的相似度，然后計算目標用戶與類別內的p個用戶的相似度， p是聚類后同類別中用戶的個數，是一個遠遠小于m的常數。計算目標用戶u0與聚類中心相似性的時間復雜度為O（k×n），計算目標用戶u0與類別內用戶相似性的時間復雜度為O（p×n），總的時間復雜度為O（k×n）+O（p×n）。因為k， p是遠遠小于m的數，所以新算法降低了時間復雜度。

3 實驗和分析

3.1 數據集及預處理

本實驗選用來源于豆瓣網的Douban數據集（http：//www.datatang.com/data/13784）。該數據集是對電影部分評分的數據，評分的范圍是1～5分。同時，用戶還通過關注其他用戶建立社交關系，從對方的動態和發布的內容中獲取自己感興趣的部分。該部分數據包含129490個用戶對58541部電影的評分，并有1692952條關注關系信息。實驗采用五折交叉驗證的方法，按照4∶1的比例把數據集分成訓練集和測試集，將5次實驗結果的平均值作為對算法精度的估計。

3.2 實驗評價標準

本文采用平均絕對誤差（Mean Absolute Error， MAE）、 precision、recall和F1值四種常見的評價指標。MAE用來衡量預測評分與真實值之間的差異，MAE值越小，表示偏差越小，推薦效果越好，計算如式（8）所示； precision是查準率，用于衡量最后的推薦結果列表中有多少是用戶真正喜歡的項； recall是查全率，用于衡量最后的推薦列表中包含了多少用戶真正喜歡的東西； F1值是考察查全率與查準率的綜合評價指數，計算公式如（9）～（11）所示。

3.3 α的選擇

本文相似度計算由用戶興趣相似度和用戶社交信任相似度兩部分構成，α作為平衡因子調節這兩部分權重。α的取值范圍為[0，1]，每次增加0.1。當α取0時，算法只根據基于用戶興趣的鄰居預測值產生推薦；當α取1時，根據基于用戶信任的鄰居預測值產生推薦；當0<α<1時，算法綜合考慮了基于用戶信任的鄰居和基于用戶信任的鄰居預測值產生推薦，且α越大基于用戶信任預測值所占的比重越大。

從圖3看出，通過實驗得到，隨著α的增大，MAE值先減小后增大，α在區間[0.5，0.7]有最小的平均絕對值誤差；α在區間[0.6，0.7]有最好的查準率；α在區間[0.55，0.65]有最優的查全率。綜上，α取0.6時，有最佳推薦效果。此外，實驗結果表明，綜合基于用戶興趣和基于信任兩方面信息比只考慮其中一方面的信息有更好的推薦效果，同時也說明在此數據集上選擇鄰居用戶時基于用戶信任的相似度比基于用戶興趣的相似度貢獻大，所以在預測評分時給基于用戶信任相似度所選擇的鄰居用戶賦予了更高的權重，也說明人們更愿意相信與自己有信任關系的朋友的推薦。

3.4 k均值聚類算法中分類數k的選擇

k均值聚類方法受分類數k的影響，在不同問題下最佳分類數k的取值不同，需要確定最適合本文算法的分類數。本實驗以聚類數k為變量，k的取值范圍為[30，75]，每次增加5。實驗結果如圖4所示，從圖中可以看出并不是k越大效果就越好，隨著k值增加，MAE值先減小再增加。在[30，45]區間內，MAE值逐漸減小，說明隨著k的增加，分類更為準確，同類別的用戶的相似度更大；在[45，75]的區間內，MAE值逐漸增大，此時隨著聚類k的增大，某些類別內只存在很少的用戶，分類數的增加并不能夠很好地劃分類別。分類數k=45時，MAE最小，表明推薦效果最佳。

3.5 幾種算法的推薦效果比較

為了更好地評價算法的推薦質量，用本文提出的算法與傳統的基于用戶的協同過濾（userbased CF）算法、基于信任的推薦（trustbased）算法和本文算法（不含間接信任）4種算法進行比較分析。

圖5顯示了4種算法在平均絕對誤差上的比較，從實驗結果中可以看出，當本文算法不考慮間接信任時，平均絕對值誤差會比考慮間接信任時大，說明結合間接信任的算法有效的減少了誤差。在推薦個數較少時，基于用戶的協同過濾算法比基于信任的推薦算法預測平均誤差要小，隨著推薦個數的增大，基于信任的推薦算法要優于基于用戶的協同過濾算法，然而本文算法在平均絕對誤差上明顯優于對比算法。

圖6顯示了4種算法在查準率上的比較，從實驗結果中可以看出，本文算法查準率高于其他算法且處于相對穩定的狀態，4種算法在推薦數為20時準確率最高，之后隨著推薦數增加，引入了更多不準確的推薦，導致各個算法的準確率整體呈下降趨勢，同時，結合間接信任關系的算法提升了查準率。

圖7顯示了4種算法在查全率上的比較，從實驗結果中可以看出，開始時3種算法的查全率相差不大，當推薦數達到20時，本文算法和基于信任的推薦算法比基于用戶的協同過濾算法的查全率要高。四種算法的查全率都是隨著推薦個數增加而增加，然而本文算法在結合間接信任時始終處于最優狀態。

圖8顯示了4種算法在F1值上的比較，F1是根據查準率和查全率得到的一項綜合性評價指標。由于本文算法在查準率和查全率上都優于基于用戶的協同過濾算法和基于信任的推薦算法，因此本文算法的F1值也優于對比算法。另外，本文算法和基于信任的推薦算法的F1值明顯優于基于用戶的協同過濾算法，本文算法綜合用戶興趣、直接信任和間接信任有效提升了推薦系統的性能。

4 結語

傳統的協同過濾推薦算法是在整個用戶空間上根據用戶項目評分來計算用戶間的相似性，不僅計算量大，而且忽略了其他用戶對目標用戶興趣的影響，這無疑會降低推薦的質量。本文利用聚類算法將用戶分類，然后將信任機制引入到個性化推薦方法中，通過定義直接信任和間接信任來度量社交網絡用戶之間的隱含信任關系，將社交網絡轉換為信任網絡。在基于用戶評分矩陣和用戶信任關系上分別選擇鄰居用戶，加權為用戶產生推薦。另外，在計算用戶興趣相似度時，本文采用了修正的余弦計算公式來消除評分標準的差異問題，提高了興趣相似度計算的準確性。為了對本文算法進行評價，本文引進了兩個實驗，確定了合適的協調因子α值和分類數k值，然后再與基于用戶的協同過濾算法和基于信任的推薦算法進行對比實驗，實驗結果表明本文算法在MAE、 precision、recall、F1值上優于傳統的基于用戶的協同過濾算法、基于信任的推薦算法和不含間接信任的本文算法，有效提高了推薦系統的推薦質量。

參考文獻：

[1]CHOI K， SUH Y. A new similarity function for selecting neighbors for each target item in collaborative filtering [J]. KnowledgeBased Systems， 2013， 37： 146-153.

[2]KRZYWICKI A， WOBCKE W， KIM Y S， et al. Collaborative filtering for peopletopeople recommendation in online dating： data analysis and user trial [J]. International Journal of Human Computer Studies， 2015， 76： 50-66.

[3]施鳳仙， 陳恩紅.結合項目區分用戶興趣度的協同過濾算法[J].小型微型計算機系統， 2012， 33（7）：1533-1536.（SHI F X， CHEN E H.Combining the items discriminabilities on user interests for collaborative filtering[J]. Journal of Chinese Computer Systems， 2012， 33（7）： 1533-1536.）

[4]吳泓辰， 王新軍， 成勇， 等.基于協同過濾與劃分聚類的改進推薦算法[J].計算機研究與發展， 2011， 48（S3）：205-212.（WU H C， WANG X J， CHENG Y， et al. Advanced recommendation based on collaborative filtering and partition clustering[J]. Journal of Computer Research and Development， 2011， 48（S3）： 205-212.）

[5]尹航， 常桂然， 王興偉.采用聚類算法優化的K近鄰協同過濾算法[J].小型微型計算機系統， 2013， 34（4）：806-809.（YIN H， CHANG G R， WANG X W. Effect of clustering algorithm in Knearestneighborhood based collaborative filtering[J]. Journal of Chinese Computer Systems， 2013， 34（4）： 806-809.）

[6]王明佳， 韓景倜， 韓松喬.基于模糊聚類的協同過濾算法[J].計算機工程， 2012， 38（24）：50-52.（WANG M J， HAN J T， HAN S Q. Collaborative filtering algorithm based on fuzzy clustering[J]. Computer Engineering， 2012， 38（24）： 50-52.）

[7]孫輝， 馬躍， 楊海波， 等.一種相似度改進的用戶聚類協同過濾推薦算法[J].小型微型計算機系統， 2014， 35（9）：1967-1970.（SUN H， MA Y， YANG H B， et al. Collaborative filtering recommendation algorithm by optimizing similarity and clustering user[J]. Journal of Chinese Computer Systems， 2014， 35（9）： 1967-1970.）

[8]吳湖， 王永吉， 王哲， 等.兩階段聯合聚類協同過濾算法[J].軟件學報， 2010， 21（5）：1042-1054.（WU H， WANG Y J， WANG Z， et al. Twophase collaborative filtering algorithm based on coclustering[J]. Journal of Software， 2010， 21（5）： 1042-1054.）

[9]王雪蓉， 萬年紅.云模式用戶行為關聯聚類的協同過濾推薦算法[J].計算機應用， 2011， 31（9）：2421-2425.（WANG X R， WANG N H. Cloud pattern collaborative filtering recommender algorithm using user behavior correlation clustering[J]. Journal of Computer Applications， 2011， 31（9）： 2421-2425.）

[10]榮輝桂， 火生旭， 胡春華， 等.基于用戶相似度的協同過濾推薦算法[J].通信學報， 2014， 35（2）：16-24.（RONG H G， HONG S X， HU C H， et al. User similaritybased collaborative filtering recommendation algorithm[J]. Journal on Communications， 2014， 35（2）： 16-24.）

[11]REAFEE W， SALIM N. the social network role in improving recommendation performance of collaborative filtering[C]// Proceedings of the 1st International Conference on Advanced Data and Information Engineering. Berlin： Springer， 2014： 231-240.

[12]鄒本友， 李翠平， 譚力文， 等.基于用戶信任和張量分解的社會網絡推薦[J].軟件學報， 2014， 25（12）： 2852-2864.（ZOU B Y， LI C P， TAN L W， et al. Social recommendations based on user trust and tensor factorization[J]. Journal of Software， 2014， 25（12）： 2852-2864.）

[13]張富國.用戶多興趣下基于信任的協同過濾算法研究[J].小型微型計算機系統， 2008， 29（8）：1415-1419.（ZHANG F G. Research on trust based collaborative filtering algorithm for users multiple interests[J]. Journal of Chinese Computer Systems， 2008， 29（8）： 1415-1419.）

[14]王興茂， 張興明， 鄔江興.基于一跳信任模型的協同過濾推薦算法[J].通信學報， 2015， 36（6）：193-200.（WANG X M， ZHANG X M， WU J X. Collaborative filtering recommendation algorithm based on onejump trust model[J]. Journal on Communications， 2015， 36（6）：193-200.）

[15]楊興耀， 于炯， 吐爾根·依布拉音， 等.基于信任模型填充的協同過濾推薦模型[J].計算機工程， 2015， 41（5）：6-13.（YANG X Y， YU J， IBRAHIM T， et al. Collaborative filtering recommendation model based on trust model filling[J]. Computer Engineering， 2015， 41（5）：6-13.）

[16]馮勇， 李軍平， 徐紅艷， 等.基于社會網絡分析的協同推薦方法改進[J].計算機應用， 2013， 33（3）：841-844.（FENG Y， LI J P， XU H Y， et al. Collaborative recommendation method improvement based on social network analysis[J]. Journal of Computer Applications， 2013， 33（3）： 841-844.）

[17]夏小伍， 王衛平.基于信任模型的協同過濾推薦算法[J]. 計算機工程， 2011， 37（21）：26-28.（XIA X W， WANG W P. Collaborative filtering recommendation algorithm based on trust model [J]. Computer Engineering， 2011， 37（21）：26-28.）

[18]周璐璐.融合社會信任關系的改進推薦系統[J].計算機應用與軟件， 2014， 31（7）： 31-35.（ZHOU L L. Improved recommendation system based on social trust relation[J]. Computer Applications and Software， 2014， 31（7）： 31-35.）