信任社交網(wǎng)絡(luò)中基于圖熵的個(gè)性化推薦算法

蔡永嘉 李冠宇 關(guān)皓元

摘 要：隨著社交網(wǎng)絡(luò)的飛速發(fā)展引起了人們對(duì)推薦系統(tǒng)（RS）的廣泛關(guān)注。針對(duì)社交網(wǎng)絡(luò)中現(xiàn)有推薦方法仍存在冷啟動(dòng)問題以及未考慮用戶所處的社交網(wǎng)絡(luò)信息的情況，提出了在信任社交網(wǎng)絡(luò)中基于圖熵的個(gè)性化推薦算法（PRAGE）。首先，根據(jù)用戶物品和它們之間的反饋信息建立用戶物品圖（UIG），同時(shí)引入信任機(jī)制建立用戶信任圖（UTG）;其次，通過對(duì)兩個(gè)圖使用隨機(jī)游走算法得到用戶與物品的初始相似度和基于信任機(jī)制的新的用戶物品相似度;重復(fù)隨機(jī)游走過程直至相似度穩(wěn)定到收斂值;然后，使用UIG和UTG的圖熵對(duì)兩組相似度進(jìn)行加權(quán)并最終相應(yīng)地得出目標(biāo)用戶的最終推薦列表。在真實(shí)的數(shù)據(jù)集Epinions和FilmTrust上的實(shí)驗(yàn)結(jié)果表明，相比經(jīng)典的基于隨機(jī)游走算法，PRAGE的精確率分別提高了34.7%和19.4%，召回率分別提高了28.9%和21.1%，能夠有效地緩解推薦的冷啟動(dòng)問題且在精確率和覆蓋率指標(biāo)上均優(yōu)于對(duì)比算法。

關(guān)鍵詞：社交網(wǎng)絡(luò);信任機(jī)制;隨機(jī)游走;圖熵;推薦算法

中圖分類號(hào)： TP301.6; TP18

文獻(xiàn)標(biāo)志碼：A

Abstract： Widespread attentions have been drawn to Recommendation Systems （RS） as rapid development of social networks. To solve the cold-start problem and neglect to users social network information in current recommendation algorithms， a novel Personalized Recommend Algorithm based on Graph Entropy （PRAGE） in trust social network was proposed. Firstly， a weighted User-Item Graph （UIG） was built based on feedback information， and a trust mechanism was introduced to establish a User Trust Graph （UTG）. Secondly， by using random walk algorithm on two graphs， the initial similarity of user and item and new user-item similarity based on trust mechanism were obtained; the above algorithm process was repeated until the similarity value reaches convergence value. Then， a method to weight two sets of similarity values with graph entropies of both UIG and UTG was proposed and final recommendation list was accordingly created. The experimental results on two real-world datasets named as Epinions and FilmTrust reveal that， compared with classical Random Walk algorithm， the accuracy of PRAGE is increased by about 34.7%and 19.4% respectively， and its recall is increased by 28.9% and 21.1% respectively， which can alleviate cold start problem effectively and has better performance in accuracy and coverage.

Key words： social network; trust mechanism; random walk; graph entropy; recommendation algorithm

0 引言

隨著電子商務(wù)的飛速發(fā)展，推薦系統(tǒng)（Recommendation System， RS）被廣泛用于這些網(wǎng)站為用戶提供相應(yīng)的產(chǎn)品，但是如何從海量的數(shù)據(jù)中提取有效的信息是目前RS亟待解決的問題[1]。個(gè)性化推薦旨在克服信息過載為用戶提供感興趣的物品而在RS上廣泛運(yùn)用。換言之，個(gè)性化的推薦系統(tǒng)挖掘用戶潛在興趣從大量可用選擇找到用戶感興趣的物品。為了提供高質(zhì)量的推薦，這些方法需要預(yù)測(cè)和比較物品的效用從而確定要推薦的物品。目前個(gè)性化推薦方法主要有基于用戶歷史數(shù)據(jù)進(jìn)行推薦[2]、基于關(guān)聯(lián)規(guī)則的推薦[3]、基于上下文信息的推薦[4]、基于社交網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行推薦[5]等。

目前基于用戶行為數(shù)據(jù)的推薦算法主要有基于內(nèi)容推薦算法[6]和協(xié)同過濾（Collaborative Filtering， CF）算法[7]。前者是通過分析用戶和物品的配置文件，根據(jù)用戶購買或?yàn)g覽的物品更新配置文件從而找出相似度高的物品推薦給用戶，推薦結(jié)果直觀但不能挖掘用戶潛在的興趣點(diǎn);后者為當(dāng)下應(yīng)用最廣泛的算法，CF基于用戶對(duì)物品的評(píng)分反饋信息計(jì)算用戶之間的相似度，通過鄰居用戶對(duì)物品的反饋來預(yù)測(cè)目標(biāo)用戶對(duì)物品的偏好程度[8]。目前CF算法主要分為基于存儲(chǔ)和基于模型的方法。基于存儲(chǔ)的方法使用相似性度量標(biāo)準(zhǔn)直接對(duì)包含所有評(píng)級(jí)的用戶項(xiàng)目評(píng)分矩陣進(jìn)行操作來表示用戶對(duì)物品的偏好[9]。相似性度量基于它們各自的評(píng)級(jí)來計(jì)算兩個(gè)用戶之間或兩個(gè)項(xiàng)目之間的相似性?；谀Ｐ偷姆椒ㄖ饕袌D模型、概率模型等，其中基于圖的推薦是一種更直觀、靈活的推薦算法[10]。它將用戶和物品之間的聯(lián)系用二分圖形式化表示，通過在二分圖上展開隨機(jī)游走（Random Walk）算法計(jì)算相似度從而得到與目標(biāo)用戶最為相似的物品。最早的圖推薦算法為Haveliwala等[11]提出的基于隨機(jī)游走的TSPR（Topic-Sensitive PageRank）算法，該算法采用一階馬爾可夫鏈在用戶物品二分圖上計(jì)算游走概率直至收斂到穩(wěn)定值再推薦。Park等[12]提出了在推薦系統(tǒng)中矩陣分解和Random Walk之間比較研究，其中Random Walk在隱式分解下表現(xiàn)更好?；谟脩舴答仈?shù)據(jù)的推薦能夠挖掘用戶的興趣點(diǎn)，但也存在數(shù)據(jù)稀疏和冷啟動(dòng)問題，導(dǎo)致推薦性能下降。

基于關(guān)聯(lián)規(guī)則的推薦旨在挖掘用戶和物品之間的關(guān)聯(lián)規(guī)則，通過這種規(guī)則向用戶推薦物品，但該方法的規(guī)則抽取難度較大且不易捕捉用戶的個(gè)性化信息。另一方面，為了能夠緩解RS中的冷啟動(dòng)和數(shù)據(jù)稀疏問題，許多文獻(xiàn)提出基于社交網(wǎng)絡(luò)結(jié)構(gòu)的推薦方法。Li等[13]考慮了社交推薦系統(tǒng)中用戶之間的直接聯(lián)系，提出了一種具有社交影響力的推薦方法，在社交網(wǎng)絡(luò)平臺(tái)上影響力越大其推薦的權(quán)重也越大。Liu等[14]提出了將用戶好友信息加入到協(xié)同推薦算法中，主要思想為通過計(jì)算用戶間相似度矩陣得出用戶鄰居集，若其中含有用戶好友則增加權(quán)重來預(yù)測(cè)物品進(jìn)行推薦。該方法引入好友信息雖能一定程度緩解冷啟動(dòng)問題，但算法性能依舊不好，仍存在數(shù)據(jù)稀疏問題。

Eirinaki等[15]提出了信任感知推薦系統(tǒng)，通過定義信任度來建立用戶間的信任傳播網(wǎng)絡(luò)，將信任度代替用戶間相似度從而計(jì)算用戶最信任的鄰居集來對(duì)目標(biāo)用戶進(jìn)行推薦。Moradi等[16]提出了一種基于信任的圖聚類推薦算法，該方法將用戶群基于皮爾森系數(shù)和信任值的加權(quán)構(gòu)建成一個(gè)無向圖，在其中尋找最稀疏子圖來聚類從而獲得目標(biāo)用戶的最相似鄰居集，進(jìn)而對(duì)其推薦?；谏缃痪W(wǎng)絡(luò)結(jié)構(gòu)的推薦算法考慮了用戶的好友信息和所處的社交網(wǎng)絡(luò)信息，在一定程度上改善了推薦算法的性能并緩解了RS的冷啟動(dòng)問題。

針對(duì)目前基于社交網(wǎng)絡(luò)的推薦算法僅考慮用戶相似鄰居集來推薦而忽略了用戶對(duì)物品的多反饋信息的問題，且考慮如何權(quán)衡兩者的權(quán)重，本文提出了一種在信任社交網(wǎng)絡(luò)中基于圖熵的個(gè)性化推薦算法（Personalized Recommend Algorithm based on Graph Entropy， PRAGE）。首先，根據(jù)用戶物品及反饋信息構(gòu)建用戶物品二分圖（User-Item Graph， UIG）;其次，根據(jù)信任機(jī)制構(gòu)建用戶間信任圖（User Trust Graph， UTG）;然后，根據(jù)Random Walk算法的思想在兩圖上游走并重復(fù)直至得到反饋圖中用戶物品相似度和信任圖中相似度的收斂值;最后，為了獲取推薦相似度的平衡，采用圖熵的方法對(duì)兩組相似度進(jìn)行加權(quán)來獲得最終的用戶物品相似度用以推薦。在真實(shí)的數(shù)據(jù)集上實(shí)驗(yàn)結(jié)果表明，該算法能夠很好地緩解冷啟動(dòng)問題，并在用戶反饋數(shù)據(jù)稀疏的情況下，在推薦的精確率、召回率、覆蓋率等度量指標(biāo)上仍取得很好的性能。

1 算法設(shè)計(jì)

本文提出的PRAGE將隨機(jī)游走的思想應(yīng)用于所提出的用戶物品二分圖和用戶間信任圖上：前者生成基于用戶對(duì)物品反饋信息的用戶物品相似度;后者生成基于信任用戶的相似度。重復(fù)迭代算法在相似度穩(wěn)定到收斂值后，基于圖熵來分配兩個(gè)相似度值的權(quán)重得到最終的相似度。最后，根據(jù)最終的用戶物品相似度計(jì)算每個(gè)用戶的推薦列表。算法流程如圖1所示。

1.1 構(gòu)建用戶物品圖

首先，PRAGE需要根據(jù)用戶和相關(guān)的物品構(gòu)建UIG。由G（V，E）表示，V表示包括用戶節(jié)點(diǎn)和物品節(jié)點(diǎn)的集合，E為用戶和物品邊的集合，且邊上的權(quán)重表示用戶對(duì)該物品的感興趣程度。如何確定用戶與物品邊上的權(quán)重是確定用戶物品相似度的關(guān)鍵。譬如目前的圖推薦算法利用用戶對(duì)物品的評(píng)分信息來度量相似度，但卻忽略了多反饋對(duì)相似度的影響，譬如用戶對(duì)物品的收藏、評(píng)論、分享、屏蔽等都將影響用戶對(duì)該物品的相似度權(quán)重。

對(duì)此將考慮用戶多種反饋行為對(duì)其造成的影響，不同的用戶反饋對(duì)用戶物品相似度權(quán)重的影響是不同的。譬如用戶對(duì)一部電影的收看和收藏所體現(xiàn)出來用戶的興趣程度明顯后者更高。根據(jù)這個(gè)考慮，用戶物品邊的權(quán)重設(shè)計(jì)如下：假如用戶對(duì)物品產(chǎn)生了N種反饋，為每種反饋的權(quán)重具體情況進(jìn)行分析設(shè)計(jì)權(quán)重。譬如用戶對(duì)物品的評(píng)分為3（總分為5），那么就評(píng)分而言其所占權(quán)重為0.6。假如用戶收藏了該物品，那么基于該反饋權(quán)重設(shè)置為1。綜上某用戶對(duì)物品的反饋融合成的權(quán)重計(jì)算公式如下所示：

其中：N表示用戶對(duì)物品產(chǎn)生了反饋類型數(shù); frep表示用戶對(duì)物品的屏蔽或舉報(bào)反饋信息，如有設(shè)置為0，無該信息則設(shè)置為1; fj（u，i）分別表示用戶對(duì)物品各種反饋信息的值。圖2為用戶物品圖的一個(gè)例子。假如用戶A觀看了a、b、c三部電影，收藏了b、c，并分別對(duì)其評(píng)分2、3、4分;則w（A，a）、w（A，b）、w（A，c）分別為0.4、0.8、0.9。

1.2 構(gòu)建用戶信任圖

本文所提出的PRAGE中不僅僅只考慮了用戶對(duì)物品的相關(guān)反饋信息來計(jì)算用戶和物品的相似度，同樣的，也考慮了用戶之間的信任關(guān)系。首先構(gòu)建UTG，目的是在信任社交網(wǎng)絡(luò)上找尋與目標(biāo)用戶相似度高的用戶，使得目標(biāo)用戶對(duì)沒有選擇的物品分配相應(yīng)的權(quán)重，這樣有利于推薦的多樣性。首先用戶間的信任度[17]公式計(jì)算如下：

其中：dA，B表示用戶A、B在信任社交網(wǎng)絡(luò)上的信任傳播距離;dmax表示在信任社交網(wǎng)絡(luò)上允許用戶間傳播的最大距離，計(jì)算公式如式（3）所示：

其中n和k分別表示系統(tǒng)中信任網(wǎng)絡(luò)范圍大小和平均度[18]。

構(gòu)建用戶間信任圖之后，基于信任的用戶物品相似度計(jì)算方法如下：

其中：NT為與目標(biāo)用戶有信任度的用戶集合;NT表示其用戶節(jié)點(diǎn)個(gè)數(shù);simF（u′，i）表示基于用戶反饋信息的用戶物品相似度;Tu′，u表示由式（2）計(jì)算得出的用戶信任度。圖3為UTG的一個(gè)例子，本文認(rèn)為計(jì)算用戶間信任度是相互的，故用無向圖表示，那么對(duì)用戶A基于信任用戶的相似度信息可以計(jì)算為如下：

1.3 Random Walk和基于圖熵推薦

1.3.1 基于圖模型進(jìn)行Random Walk

如圖1所示本文提出的PRAGE的步驟，在構(gòu)建完UIG和UTG之后，需要基于這兩個(gè)圖進(jìn)行Random Walk，該過程的主要思想為以每個(gè)用戶自身為出發(fā)點(diǎn)，每到達(dá)下一個(gè)節(jié)點(diǎn)時(shí)，需要判斷是以概率β繼續(xù)向下個(gè)節(jié)點(diǎn)游走還是以1-β的概率返回出發(fā)節(jié)點(diǎn)重新游走;如果往下個(gè)節(jié)點(diǎn)游走，則按權(quán)重比例隨機(jī)選擇下個(gè)節(jié)點(diǎn)作為游走節(jié)點(diǎn);一輪Random Walk之后，各節(jié)點(diǎn)被訪問到的概率即為用戶和該節(jié)點(diǎn)的相似度;重復(fù)迭代游走過程直至用戶和各節(jié)點(diǎn)的游走概率收斂到穩(wěn)定值。假設(shè)simn（u，i）表示完成第n輪Random Walk之后用戶u和各節(jié)點(diǎn)的相似度收斂值，i∈V，則simn（u，i）計(jì)算公式如下：

其中：Vi、Vj分別表示在圖中與節(jié)點(diǎn)i、 j直接相連的節(jié)點(diǎn)集合。在UIG上根據(jù)式（1）和Random Walk游走公式可以算出基于用戶對(duì)物品反饋的收斂相似度simnF（u，i），同時(shí)根據(jù)式（4）和Random Walk游走公式可以得出基于信任用戶的各節(jié)點(diǎn)相似度的收斂值simnT（u，i）。

1.3.2 基于圖熵的推薦

在對(duì)圖進(jìn)行Random Walk之后，最終用戶與各節(jié)點(diǎn)的相似度如式（6）所示，其中λ∈[0，1]為調(diào)節(jié)參數(shù)，它綜合考慮了用戶對(duì)物品的反饋信息和信任用戶的信息。

由于UIG和UTG包含不同的信息量和不同的結(jié)構(gòu)，因此本文提出基于圖熵來計(jì)算λ，圖熵在復(fù)雜網(wǎng)絡(luò)中被廣泛應(yīng)用以捕獲圖的結(jié)構(gòu)信息量[19]。加權(quán)系數(shù)λ計(jì)算公式如下：

其中：HF、HT分別表示用戶物品圖和用戶信任圖的熵，我們認(rèn)為圖的信息量越豐富，它所占的權(quán)重就越多。本文采用文獻(xiàn)[20]中的圖熵計(jì)算方法，圖熵計(jì)算方法公式如下：

它首先基于圖的拓?fù)浣Y(jié)構(gòu)多樣性信息來計(jì)算圖中的節(jié)點(diǎn)熵：其中rij是圖中節(jié)點(diǎn)ni到節(jié)點(diǎn)nj的轉(zhuǎn)移概率。在計(jì)算節(jié)點(diǎn)熵時(shí)只考慮整個(gè)圖的拓?fù)浣Y(jié)構(gòu)而不區(qū)分節(jié)點(diǎn)類型，因此，與使用多個(gè)相鄰矩陣來描述不同節(jié)點(diǎn)類型之間的連接不同，本文使用單個(gè)相鄰矩陣來描述整個(gè)主圖的拓?fù)浣Y(jié)構(gòu)，然后圖的熵是圖中所有節(jié)點(diǎn)熵的總和。

1.4 算法描述分析

PRAGE描述偽代碼如下。

有序號(hào)的程序——————————Shift+Alt+Y

程序前

輸入：構(gòu)建用戶物品圖和用戶信任圖，分別用G1、G2表示; β為Random Walk轉(zhuǎn)移概率。

輸出：對(duì)目標(biāo)用戶按照相似度降序的Top-N推薦列表。

程序后

從算法描述可以看出假如算法輸入圖為m個(gè)用戶對(duì)n個(gè)物品的反饋信息及m個(gè)信任用戶的信任圖，第3）～6）行表示計(jì)算得到基于UIG的相似度;第7）～10）行表示計(jì)算基于UTG得到的相似度;然后根據(jù)Random Walk迭代得到相似度收斂值;第12）～14）行表示基于圖熵得到最終相似度并對(duì)目標(biāo)用戶進(jìn)行Top-N推薦，并且假設(shè)t輪概率收斂從PRAGE可以看出其時(shí)間復(fù)雜度為：

2 實(shí)驗(yàn)結(jié)果和分析

本章主要介紹實(shí)驗(yàn)平臺(tái)和實(shí)驗(yàn)所需要的數(shù)據(jù)集以及在幾個(gè)度量指標(biāo)上對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析，并且將所提出的PARGE算法與現(xiàn)有相關(guān)算法作對(duì)比分析。

2.1 實(shí)驗(yàn)平臺(tái)和數(shù)據(jù)集

實(shí)驗(yàn)平臺(tái)運(yùn)行在Windows 10系統(tǒng)上，處理器為Core i5-6500U，內(nèi)存為8GB，實(shí)驗(yàn)工具為Visual Studio 2015。為評(píng)估PRAGE的推薦效果和性能，將采用拓展的數(shù)據(jù)集Epinions和FilmTrust來檢測(cè)該算法的有效性，前者來自網(wǎng)站http：//www.trustlet.org/wiki/Downloaded_Epinions_dataset，后者來自網(wǎng)站http：//trust.mindswap.org/FilmTrust;同時(shí)為了更好地推薦和捕獲用戶的偏好，將獲取數(shù)據(jù)集中在評(píng)分3以上（總分5）的數(shù)據(jù)。表1為處理之后的數(shù)據(jù)。此外數(shù)據(jù)集被隨機(jī)地分為9∶1，其中90%作為訓(xùn)練集，10%為測(cè)試集。實(shí)驗(yàn)每次隨機(jī)劃分?jǐn)?shù)據(jù)后將進(jìn)行10次取平均值比較推薦結(jié)果。

2.2.1 準(zhǔn)確率

推薦的準(zhǔn)確率（ P）描述的是在推薦列表中有多少是符合目標(biāo)用戶偏好的，也就是對(duì)用戶生成的最終推薦列表中推薦測(cè)試數(shù)據(jù)集數(shù)目Ti（L）所占的比例，公式如下：

2.2.2 召回率

推薦召回率（R）是指推薦列表中正確命中數(shù)和測(cè)試數(shù)據(jù)集中用戶實(shí)際選擇的物品數(shù)的比值[22]。同樣反映了用戶推薦命中的比例，R數(shù)值越大，表示推薦的效果越好。R計(jì)算公式如下：

2.2.3 F1指標(biāo)

F1是用來衡量推薦算法準(zhǔn)確度的一種度量指標(biāo)，它同時(shí)兼顧考慮了算法的P和R，是兩種度量指標(biāo)的加權(quán)平均。計(jì)算公式如下所示：

2.2.4 覆蓋率

推薦覆蓋率（請(qǐng)補(bǔ)充CVR的英文全稱CVR）表示在全部物品中推薦列表Top-N所占的比例，該指標(biāo)用于反映推薦的多樣性性能。CVR越高表示推薦給用戶的物品多樣性越大，越有新穎性。計(jì)算公式如下：

其中：VI為物品集合，R（u）表示給用戶推薦物品集合。

2.3 實(shí)驗(yàn)結(jié)果分析

首先本文所提出的PRAGE總結(jié)了在兩個(gè)數(shù)據(jù)集Epinions和FilmTrust上對(duì)于不同劃分的數(shù)據(jù)集后圖的熵和加權(quán)系數(shù)λ的結(jié)果，多次實(shí)驗(yàn)得到權(quán)值都是相似的結(jié)果，將取均值來獲得最好的推薦。觀察到UIG熵由于其較為復(fù)雜的拓?fù)浣Y(jié)構(gòu)而大于用戶信任圖熵。隨著信任用戶群增加，圖熵也相應(yīng)地增加，加權(quán)系數(shù)λ的值則減小，這很好地反映了PRAGE的設(shè)計(jì)目標(biāo)，即很好地利用用戶所處的社交網(wǎng)絡(luò)信息來對(duì)用戶作出合理的推薦。

表2表示在Epinions和FilmTrust數(shù)據(jù)集上各算法在P、R、F1和CVR這幾個(gè)度量指標(biāo)上的比較結(jié)果，且實(shí)驗(yàn)最終相似度加權(quán)系數(shù)λ基于圖熵所計(jì)算得到的權(quán)重分別為0.79和0.55。其中參與和本文提出的PRAGE比較的算法有：基于Random Walk的上下文敏感排名（Topic-Sensitive PageRank， TSPR）算法[11]、融入社交關(guān)系的協(xié)同過濾（Social network Collaborative Filtering， SCF）算法[14]、基于用戶信任的圖聚類（Dense Graph Clustering Collaborative Filtering， DGCCF）算法[16]。其中為了驗(yàn)證在用戶反饋圖上進(jìn)行Random Walk算法具有更好的推薦效果，以及目前只考慮用戶好友信息或信任值，忽略了用戶對(duì)物品多反饋信息的影響，于是選擇了上述對(duì)比算法來驗(yàn)證PRAGE的有效性。

從表2可以看出在Epinions數(shù)據(jù)集上與目前現(xiàn)有的推薦方法相比，所提出的方法獲得較好的P和CVR。其中：與TSPR算法相比P提高了34.7%，R提高了28.9%;與TSPR和SCF算法相比，CVR分別提高了30.6%和8.1%。此外，所提出的方法在推薦的召回率上也獲得很好的性能，在R度量指標(biāo)上略微小于DGCCF算法，但就F1衡量指標(biāo)上仍獲得較好的性能。另外，基于這些評(píng)估度量的實(shí)驗(yàn)在FilmTrust數(shù)據(jù)集上重復(fù)進(jìn)行，相應(yīng)的結(jié)果如表2所示。所提出的方法比TSPR在P和R上分別提高了19.4%和21.1%，同時(shí)在其他評(píng)估指標(biāo)下均獲得不錯(cuò)的性能。在兩個(gè)數(shù)據(jù)集下的實(shí)驗(yàn)結(jié)果可以看出，推薦的CVR比對(duì)比算法均有提升，由于TSPR存在因數(shù)據(jù)稀疏造成的冷啟動(dòng)問題且本文提出的PARGE綜合考慮了用戶對(duì)物品的多反饋和信任用戶信息很大程度地提升了推薦的多樣性和新穎性

由于TSPR存在數(shù)據(jù)稀疏引起的冷啟動(dòng)問題，而本文提出的PARGE綜合考慮了用戶對(duì)物品的多反饋和信任信息從而很大程度上提升了推薦的多樣性和新穎性

此句不通順，請(qǐng)作相應(yīng)調(diào)整，故可以將新物品推薦給感興趣的用戶或?qū)π掠脩敉扑]感興趣的物品，比對(duì)比算法PARGE可以進(jìn)一步緩解推薦冷啟動(dòng)問題。

另外，在Epinions數(shù)據(jù)集上對(duì)于所有用戶基于對(duì)目標(biāo)用戶推薦不同的列表長(zhǎng)度Top-N其度量指標(biāo)P和R的實(shí)驗(yàn)結(jié)果如表3和表4所示。

從表3～4中結(jié)果清楚地可以看出，在大多數(shù)情況下，隨著推薦列表長(zhǎng)度Top-N參數(shù)的值增加P度量指標(biāo)降低，而R度量指標(biāo)反而增加。這是由于P和R指標(biāo)在本質(zhì)上顯然是相互沖突的[21]。此外，實(shí)驗(yàn)結(jié)果還表明，所提出的方法在P度量指標(biāo)上均優(yōu)于所對(duì)比的算法，而在推薦列表為50時(shí)推薦的R度量上劣于DGCCF算法，但是在推薦列表10和20時(shí)召回率要好于DGCCF算法，這說明在推薦列表相對(duì)較短時(shí)，所提出的算法推薦效果要好于DGCCF算法。

同時(shí)，在FilmTrust數(shù)據(jù)集上基于不同的推薦列表Top-N推薦的P和R的實(shí)驗(yàn)結(jié)果亦如表3～4所示。從表中同樣可以看出隨著推薦列表增加，P減小R增加的趨勢(shì)，且在該數(shù)據(jù)集上本文提出的算法的P和R均優(yōu)于對(duì)比算法。該實(shí)驗(yàn)結(jié)果表明在數(shù)據(jù)集較小的推薦系統(tǒng)中，所提算法也很高效。

為了進(jìn)一步闡述算法PRAGE的優(yōu)越性能，給出了在兩個(gè)數(shù)據(jù)集上通過圖熵確認(rèn)在最終用戶物品相似度的最優(yōu)加權(quán)系數(shù)和推薦列表長(zhǎng)度從1到測(cè)試集長(zhǎng)度下的相應(yīng)的P-R曲線。如圖4所示，所提出的方法在不同推薦列表長(zhǎng)度下的準(zhǔn)確率和召回率曲線最佳。對(duì)于兩個(gè)數(shù)據(jù)集從左下到右上的各曲線的順序表示相應(yīng)的算法，在P-R曲線上將越接近（1，1）點(diǎn)作為衡量性能的標(biāo)準(zhǔn)，可以看出PRAGE曲線明顯優(yōu)于其他算法曲線，表示在不同的測(cè)試集下本文算法準(zhǔn)確率和召回率綜合優(yōu)于對(duì)比算法，這進(jìn)一步支持了表3～4的實(shí)驗(yàn)結(jié)果。

3 結(jié)語

本文針對(duì)目前推薦系統(tǒng)中仍存在冷啟動(dòng)問題以及未考慮用戶所處的社交網(wǎng)絡(luò)信息的情況，提出了社交網(wǎng)絡(luò)上基于圖熵的個(gè)性化推薦算法（PRAGE）。首先根據(jù)用戶物品及反饋信息構(gòu)建用戶物品二分圖;其次根據(jù)信任機(jī)制構(gòu)建用戶間信任圖;然后根據(jù)Random Walk在兩圖上游走并重復(fù)直至得到各相似度的收斂值;最后為了獲取推薦相似度的平衡，采用圖熵的方法來對(duì)兩組相似度進(jìn)行加權(quán)來獲得最終的用戶物品相似度用以推薦。在真實(shí)的數(shù)據(jù)集上實(shí)驗(yàn)結(jié)果表明，該算法能夠很好地緩解冷啟動(dòng)問題，并在用戶數(shù)據(jù)稀疏的情況下仍取得很好的性能。當(dāng)然除了本文考慮到的因素之外，是否還有其他重要因素能對(duì)用戶推薦產(chǎn)生影響是下一步的研究方向;同時(shí)在龐大的用戶社交網(wǎng)絡(luò)上除了信任度，如何更有效地挖掘出用戶的隱性個(gè)性化信息也是接下來研究的重要方向。

參考文獻(xiàn) （References）

[1] L L， MEDO M， YEUNG C H， et al. Recommender systems [J]. Physics Reports， 2012， 519（1）： 1-49.

[2] JAIN A， LIU X， YU Q. Aggregating functionality， use history， and popularity of APIs to recommend mashup creation [C]// Proceedings of the 2015 International Conference on Service-Oriented Computing. Berlin：Springer， 2015： 188-202.

[3] PERWEZ S K， ZUBAIR H M， GHALIB M R， et al. Association rule mining technique for psychometric personality testing and behaviour prediction [J]. International Journal of Engineering & Technology， 2013， 5（5）： 4349-4361.

[4] HAO F， LI S， MIN G， et al. An efficient approach to generating location-sensitive recommendations in Ad-Hoc social network environments [J]. IEEE Transactions on Services Computing， 2015， 8（3）： 520-533.

[5] AHMADIAN S， MEGHDADI M， AFSHARCHI M. A social recommendation method based on an adaptive neighbor selection mechanism [J]. Information Processing & Management， 2018， 54（4）： 707-725.

[6] 曾春，邢春曉，周立柱.基于內(nèi)容過濾的個(gè)性化搜索算法[J].軟件學(xué)報(bào)，2003，14（5）：999-1004.（ZENG C， XING C X， ZHOU L Z. A personalized search algorithm by using content-based filtering [J]. Journal of Software， 2003， 14（5）： 999-1004.）

[7] PESSEMIER T D. Collaborative recommendations with content-based filters for cultural activities via a scalable event distribution platform [J]. Multimedia Tools & Applications， 2012， 58（1）： 167-213.

[8] 黃創(chuàng)光，印鑒，汪靜，等.不確定近鄰的協(xié)同過濾推薦算法[J].計(jì)算機(jī)學(xué)報(bào)，2010，33（8）：1369-1377.（HUANG C G， YING J， WANG J， et al. Uncertain neighbors collaborative filtering recommendation algorithm [J]. Chinese Journal of Computers， 2010， 33（8）： 1369-1377.）

[9] BOJNORDI E， MORADI P. A novel collaborative filtering model based on combination of correlation method with matrix completion technique [C]// Proceedings of the 2012 CSI International Symposium on Artificial Intelligence and Signal Processing. Piscataway， NJ： IEEE， 2012： 191-194.

[10] GORI M， PUCCI A. ItemRank： a random-walk based scoring algorithm for recommender engines [C]// Proceedings of the 2007 International Joint Conference on Artificial Intelligence. San Francisco： Morgan Kaufmann， 2007： 2766-2771.

[11] HAVELIWALA T H. Topic-sensitive PageRank： a context-sensitive ranking algorithm for Web search [J]. IEEE Transactions on Knowledge & Data Engineering， 2003， 15（4）： 784-796.

[12] PARK H， JUNG J， KANG U. A comparative study of matrix factorization and random walk with restart in recommender systems [J]. ArXiv Preprint， 2017， 2017： 1708.09088.

[13] LI C， XIONG F. Social recommendation with multiple influence from direct user interactions [J]. IEEE Access， 2017， 5： 16288-16296.

[14] LIU F， HONG J L. Use of social network information to enhance collaborative filtering performance [J]. Expert Systems with Applications， 2010， 37（7）： 4772-4778.

[15] EIRINAKI M， LOUTA M D， VARLAMIS I. A trust-aware system for personalized user recommendations in social networks [J]. IEEE Transactions on Systems， Man & Cybernetics Systems， 2014， 44（4）： 409-421.

[16] MORADI P， AHMADIAN S， AKHLAGHIAN F. An effective trust-based recommendation method using a novel graph clustering algorithm [J]. Physica A： Statistical Mechanics & Its Applications， 2015， 436： 462-481.

[17] MASSA P， AVESANI P. Trust-aware recommender systems [C]// Proceedings of the 2007 ACM Conference on Recommender Systems. New York： ACM， 2007： 17-24.

[18] YUAN W， GUAN D， LEE Y K， et al. Improved trust-aware recommender system using small-worldness of trust networks [J]. Knowledge-Based Systems， 2010， 23（3）： 232-238.

[19] DEHMER M. Information processing in complex networks： graph entropy and information functionals [J]. Applied Mathematics & Computation， 2008， 201（1/2）： 82-94.

[20] EAGLE N， MACY M， CLAXTON R. Network diversity and economic development [J]. Science， 2010， 328（5981）： 1029-1031.

[21] HERLOCKER J L， KONSTAN J A， TERVEEN L G， et al. Evaluating collaborative filtering recommender systems [J]. ACM Transactions on Information Systems， 2004， 22（1）： 5-53.

[22] DAVIS J， GOADRICH M. The relationship between precision-recall and ROC curves [C]// ICML 06 ： Proceedings of the 2006 International Conference on Machine Learning. New York： ACM， 2006： 233-240.