基于改進二部圖與專家信任的混合推薦算法

黃熠姿

摘要：針對傳統(tǒng)協(xié)同過濾算法出現(xiàn)的稀疏數(shù)據(jù)、用戶冷啟動等問題以及復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)的廣泛應(yīng)用，本文提出結(jié)合改進的二部圖與改進的專家信任算法來提高推薦準(zhǔn)確度。基于普通二部圖算法，將用戶對項目的評分作為節(jié)點之間的分配資源權(quán)重，不僅關(guān)注用戶與項目之間的聯(lián)系，同時體現(xiàn)用戶對項目的喜好程度；其次，本文根據(jù)用戶的評論數(shù)和與該用戶對項目評分相同的數(shù)目來判斷該用戶的專家信任度，改進傳統(tǒng)系統(tǒng)過濾算法。為了提高推薦準(zhǔn)確度，改進缺點，我們將兩者算法進行加權(quán)混合，加權(quán)因子根據(jù)實驗中最小MAE值對應(yīng)的權(quán)值來確定，形成混合推薦算法。最后針對基于用戶的協(xié)同過濾、傳統(tǒng)二部圖以及本文提出的混合算法計算MAE值和平均Hamming距離，對比分析本文算法的推薦準(zhǔn)確度與多樣性，實驗表明本文方法推薦效果較好，準(zhǔn)確率高，個性化強，有研究和應(yīng)用價值。

Abstract： In view of the limitations like data sparseness， new users with little record of traditional collaborative filtering recommendation algorithm and the wide application of complex network structure， this paper argues to coalesce the recommendation algorithm based on expert trust and the modified bipartite graph recommendation algorithm. First of all， we proposed an improved recommendation algorithm based on weighted networks， not only pay attention to the connection between users and projects， but also reflect the users' preferences in projects. Secondly， the degree of expert trust is determined by user comments and project reviews. And in order to improve the accuracy of recommendation， we coalesce this two kinds of algorithm and give them weight. Finally， we determine the weights and calculate MAE and the average Hamming distance of the traditional collaborative filtering， the traditional bipartite graph and the hybrid recommendation algorithm through experiments， which shows that the hybrid recommendation algorithm has higher accuracy， stronger individuation， and more research and application value.

關(guān)鍵詞：推薦算法；二部圖；專家信任；加權(quán)混合

Key words： recommendation algorithm；bipartite graph；expert trust；weighted mixture

中圖分類號：TP391.3 文獻標(biāo)識碼：A 文章編號：1006-4311（2017）19-0160-05

0 引言

信息時代的迅速發(fā)展使人們能夠方便快速地通過互聯(lián)網(wǎng)獲取各種電影資源，海量的電影資源及相應(yīng)的用戶評分信息很容易造成信息過載。已有很多研究證明電影的評分會對觀影者的觀影行為產(chǎn)生影響。以評分信息能夠影響用戶的觀影行為為邏輯基礎(chǔ)，研究者開始利用推薦技術(shù)對評分信息進行處理挖掘。既有的推薦算法包括：基于內(nèi)容的推薦[1]、基于相似用戶的協(xié)同過濾推薦[2]、基于知識的推薦[3]以及混合方法推薦[4]。

但是，傳統(tǒng)的推薦方法不能有效解決數(shù)據(jù)稀疏性問題與數(shù)據(jù)冷啟動問題，這會影響到數(shù)據(jù)的準(zhǔn)確性和可信度。數(shù)據(jù)稀疏性問題指的是可以利用的數(shù)據(jù)相對于整個用戶物品空間比較少。推薦系統(tǒng)冷啟動問題指的是用戶或項目沒有歷史行為信息或者只有少量的歷史行為信息，這時就無法對用戶或者項目精確地建模，進而造成推薦效果比較差。近幾年將復(fù)雜網(wǎng)絡(luò)應(yīng)用于推薦系統(tǒng)的研究日益增多，并能提供相對有效的解決數(shù)據(jù)稀疏、擴展性等問題，基于網(wǎng)絡(luò)結(jié)構(gòu)的算法是根據(jù)物質(zhì)的擴散、熱傳導(dǎo)[5-6]原理，將用戶與項目看成抽象的節(jié)點，發(fā)現(xiàn)他們之間潛在的聯(lián)系，Zhou等提出了NBI（Network-Based Inference）算法[7]，利用二部圖分配資源，從而預(yù)測用戶感興趣的項目，得到了更好的推薦效果。研究者們也在將信任引入推薦系統(tǒng)，緩解數(shù)據(jù)稀疏性和冷啟動問題來提高推薦準(zhǔn)確度，目前已取得不少進展。Papagelis[8]等人在協(xié)同過濾推薦系統(tǒng)中使用信任推薦，Ma King和Lyu[9]提出集成信任網(wǎng)絡(luò)的這些方法都為緩和數(shù)據(jù)稀疏問題提供了解決途徑。Jamali[10]等人介紹了一種在信任網(wǎng)絡(luò)隨機游走算法，根據(jù)隨機游走概率選擇項目，為冷啟動問題提供了解決辦法。

基于此，本文以圖論和基于信任的協(xié)同過濾的建模思想為基礎(chǔ)，試將二部圖和專家推薦相結(jié)合的混合推薦算法對傳統(tǒng)推薦算法進行改進，以有效地解決數(shù)據(jù)稀疏性和冷啟動問題。

1 既有方法回顧

1.1 傳統(tǒng)二部圖結(jié)構(gòu)的推薦算法

二部圖是圖論中一種特殊的網(wǎng)絡(luò)，它包含兩類節(jié)點，在推薦系統(tǒng)中，一類是用戶集合U={u1，u2，…，un}，一類是項目集合Y={y1，y2，…，yn}，用戶與項目之間的關(guān)系組成連邊e（ui，yj），這樣，節(jié)點集合U，Y與邊的集合E構(gòu)成了一個二部圖網(wǎng)絡(luò)G=（U，Y，E）。

1.3 既有方法綜述

從上述的描述中發(fā)現(xiàn)，基于二部圖的推薦算法則可以在一定程度上解決常見的數(shù)據(jù)稀疏、擴展性等問題[12]，同時可以增大冷門商品的推薦比例，增加了推薦的多樣性。但該算法仍存在缺陷，只考慮了用戶選擇或者沒有選擇商品，沒有考慮用戶對不同商品的喜好情況不同。傳統(tǒng)的協(xié)同過濾算法，在確定最近鄰時，通常只考慮用戶的評分相似性，沒有考慮近鄰近用戶的身份屬性，研究學(xué)者在此基礎(chǔ)上引入了近鄰用戶的信任值作為相似度，但也沒有有效地解決問題。所以基于以上不足，本文能夠?qū)⒁陨蟽煞N算法進行改進以解決上述問題，同時將兩種算法混合推薦給用戶，使推薦的準(zhǔn)確性增加。

2 改進二部圖與專家信任的混合算法

2.1 基于二部圖的改進推薦算法

2.1.1 用戶評分標(biāo)準(zhǔn)化

在現(xiàn)實生活中，每個人的評分標(biāo)準(zhǔn)和分?jǐn)?shù)高低偏好會有差異，例如對于評分范圍為1-5分的商品來說，有的用戶可能習(xí)慣性評分偏高，將認(rèn)為一般的商品評4分，認(rèn)為滿意的商品評5分，而有的用戶則打分較苛刻，將認(rèn)為一般的商品普遍評3分，認(rèn)為滿意的評4分，只有極其滿意的少數(shù)商品才評5分，這樣可能會因為兩個用戶對某件商品滿意度相似而評分不同導(dǎo)致相似度降低，推薦不準(zhǔn)確，為了盡量消除用戶之間這種評分標(biāo)準(zhǔn)的誤差，本文將用戶評分比上該用戶所有評分的平均值作為新的標(biāo)準(zhǔn)化評分矩陣，即：

2.1.2 加權(quán)的二部圖算法

普通二部圖節(jié)點之間的邊值只有0和1，即選擇與不選擇，這只考慮了用戶與項目之間是否有聯(lián)系[14]，而未考慮用戶對項目的喜愛程度，而實際中，如用戶看過某部電影并不代表他喜歡該部電影，可能對電影評分很低，但二部圖中無法體現(xiàn)，所有用戶看過的電影在圖中所占權(quán)重一樣（都為1），這并不符合用戶的真實評價與推薦力度，所以本文將用戶對某個項目的評分（標(biāo)準(zhǔn)化轉(zhuǎn)換之后的）作為“用戶”—“項目”的權(quán)重，評分高的項目自然在推薦算法中占得更大權(quán)重，也更傾向于推薦給相似用戶，符合用戶期望。假設(shè)三個用戶對四部電影的評分標(biāo)準(zhǔn)化之后的評分矩陣為：

2.1.3 加權(quán)的二部圖算法特點分析

加權(quán)后的二部圖算法能夠更好地體現(xiàn)用戶對項目的喜好程度，對于用戶評分高的項目會加大被推薦的機會，對于用戶不喜歡的項目將降低其推薦權(quán)重，使得所推薦的項目更加符合用戶偏好，提高推薦準(zhǔn)確率。但是加了權(quán)重之后可能會降低冷門項目的推薦度，如某冷門項目被選擇的次數(shù)很少但評分都很高，則其權(quán)值之和仍會偏高，只要該項目的連邊比其他熱門項目少很多，高評分并不會有太大影響。

2.2 基于改進協(xié)同過濾的專家信任算法

Goldbaum.D[15]提出Follow the Leader模型，認(rèn)為用戶都傾向于接受專家的觀點。Reichiling等[16]將專家推薦系統(tǒng)定義如下：專家推薦系統(tǒng)是為了滿足用戶在特定場景下對專家的需要，幫助他們及時準(zhǔn)確找到相關(guān)的專家來解決問題的推薦系統(tǒng)。本文認(rèn)為，專家信任度表示的是用戶在網(wǎng)絡(luò)中向其他用戶提供可靠信息的可信度。利用專家信任可以有效改善新用戶的冷啟動問題。

2.2.1 專家信任

3 實驗結(jié)果及分析

本文采用的實驗數(shù)據(jù)是由美國明尼蘇達大學(xué)的GroupLens研究小組建立的電影數(shù)據(jù)集MovieLens，來源網(wǎng)站http：//www.grouplens.org。該數(shù)據(jù)集包含900個用戶（每個用戶評論電影數(shù)量大于20）對1526部電影的52萬條評分?jǐn)?shù)據(jù)，評分范圍1-5，1為不喜歡，5為很喜歡。本算法將選取的數(shù)據(jù)劃分為訓(xùn)練集（90%）和測試集（10%），首先根據(jù)本文算法中不同權(quán)值下的最小MAE確定權(quán)重因子γ，接著將基于用戶相似度的協(xié)同過濾（CF）、傳統(tǒng)二部圖算法（NBI）及本文推薦算法在不同推薦長度下的平均絕對誤差值和平均Hamming距離進行對比分析，總結(jié)本文算法的推薦準(zhǔn)確度和個性化程度。

3.1 混合權(quán)重因子γ的確定

由圖4可以看到，隨著權(quán)重因子的增加MAE逐漸降低，當(dāng)γ為0.9時MAE到達最低值0.845，之后當(dāng)γ=1時，即完全由改進二部圖算法得出的MAE增大，從該趨勢可以看出，權(quán)重因子的取值變化對推薦準(zhǔn)確率影響較大，γ為0.9左右時準(zhǔn)確率最高，所以在接下來的實驗中我們以γ=0.9作為最終的權(quán)重。

3.2 推薦準(zhǔn)確度對比實驗分析

本實驗基于權(quán)重因子γ=0.9的條件下，分別對比各個算法在不同推薦用戶長度下的MAE值，比較用戶相似度的協(xié)同過濾、傳統(tǒng)二部圖算法及本文推薦算法的推薦準(zhǔn)確度，實驗結(jié)果如圖5。

根據(jù)對比圖表可以看出，在推薦用戶長度小于60之前，文本算法都優(yōu)于其他算法，推薦準(zhǔn)確率有較大提高，因為本算法引入信任度，對鄰居用戶的選取有雙重標(biāo)準(zhǔn)，專家可以提高推薦的可信度，縮小預(yù)測評分和實際評分之間的差距。但當(dāng)推薦用戶大于30之后混合算法的MAE值增大，并在之后精確度要低于NBI算法，可能加入專家信任度較低的用戶無法進行精準(zhǔn)推薦，以及排名靠后的用戶對目標(biāo)用戶的貢獻度下降，從而影響了推薦的準(zhǔn)確度。

3.3 推薦多樣性對比實驗分析

由圖可以明顯看出本文算法又大幅度提高了推薦的多樣性，因為考慮了用戶與項目的度的影響，有效抑制了大眾流行電影的推薦程度，使對目標(biāo)用戶有貢獻的用戶更加精準(zhǔn)，提高了推薦的個性化，滿足了不同用戶的多興趣需求。

5 總結(jié)與展望

針對基于用戶的協(xié)同過濾和傳統(tǒng)二部圖推薦算法的優(yōu)缺點，本文將基于用戶的協(xié)同過濾改進為基于專家信任的推薦算法，將傳統(tǒng)二部圖的資源分配規(guī)則改進為以評分為權(quán)重的帶權(quán)二部圖，提出將二部圖與專家信任度調(diào)和權(quán)重，形成綜合推薦方法。實驗結(jié)果表明，將評分引入二部圖并將二部圖與專家算法結(jié)合是可行的，推薦結(jié)果精度得到了較大程度的改善，冷門電影的推薦使多樣性增加，且該方法在新用戶冷啟動和數(shù)據(jù)稀疏條件下也能比較靈活地實施推薦策略。但是，該算法在推薦用戶數(shù)量增加到一定程度時準(zhǔn)確度降低，且算法的時間和空間復(fù)雜程度還需要考慮，筆者將在今后的工作中對這些內(nèi)容作進一步研究和探討，不斷優(yōu)化推薦算法，改善算法執(zhí)行性能。

參考文獻：

[1]Lop sP， de Gemmis M， Semeraro G. Content-based recommender systems： State of the art and trends[M]//Recommender Systems Handbook. Springer US， 2011： 73-105.

[2]Schafer J B， Frankowski D， Herlocker J ， et al. Collaborative filtering recommender system [M]// The adaptive web. Springer Berlin Heidelberg.2007：291-324.

[3]Burke， Robin. Knowledge based recommender systems.[J] Encyclopedia of library and information systems 69，no.supplement 32 （2000）：175-186.

[4]Burke， R. Hybrid recommender systems： Survey and experiments. User Modeling and User-Adapted Interaction 12（4）， 331-370 （2002）.

[5]Liu Jianguo， Wang Binghong， Guo Qiang. Improved collaborative filtering algorithm via information transformation [J]. International Journal of Physics C， 2009，20（2）：285-293.

[6]Zhang Yicheng， Blattner M. Heat conduction process on community networks as a recommendation model [J]. Physical Review Letters， 2007，99（15）：154301.

[7]Zhou Tao， Ren Jie， MedoM， et al. Bipartite network projection and personal recommendation[J]. Physical Review E， 2007， 76（4）： 046115.

[8]Papagelis M， Plexousakis D， Kutsuras T. Alleviating the sparsity problem of collaborative filtering using trust inferences[M]//Trust management. Springer Berlin Heidelberg， 2005： 224-239.

[9]Ma Hao， King I， Lyu MR. Learning to recommend with social trust ensemble[C]//Proceedings of the 32nd international ACM SIGIR conference on Research and development in information retrieval. ACM， 2009： 203-210.

[10]Jamali M， Ester M. Trustwalker： a random walk model for combining trust-based and item-based recommendation[C]//Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM， 2009： 397-406.

[11]王茜，段雙艷.一種改進的基于二部圖網(wǎng)絡(luò)結(jié)構(gòu)的推薦算法[J].計算機應(yīng)用研究，2016，30（3）：771-774.

[12]Adomavicius G， Tuzhilin A. Toward the Next Generation of Recommender Systems： ASurvey of the State-of-the-art and Possible Extensions[J]. IEEE Transactions on Knowledge and Data Engineering， 2005，17（6）： 734-749.

[13]馬駿康.基于改進協(xié)同過濾與二部圖網(wǎng)絡(luò)的加權(quán)混合推薦技術(shù)研究[D].華東師范大學(xué)，2013.

[14]張新猛，蔣盛益.基于加權(quán)二部圖的個性化推薦算法[J]. 計算機應(yīng)用，2012，32（03）：654-657.

[15]REICHLING T， SCHUBERT K， WULF V. Matching Human Actors Based on Their Texts： Design and Evaluation of an Instance of the Expert Finding Framework[C]// Proceedings of GROUP， New York， 2005.

[16]Goldbaum D.Follow the leader： Simulations on a dynamic social network[EB/OL].[2011926].http：//www.business.uts.edu.au/finance/research/wpapers/wp155.pdf.

[17]Donovan J O，Smyth B. Eliciting trust values from recommendation errors[C] //Proceedings of the 18th International Florid Artificial Intelligence Research Society Conference，Clearwater Beach： AAAI Press，2005： 289-294.