基于影響力控制的熱傳導(dǎo)算法

雷震，文益民,2，王志強(qiáng)，繆裕青,2

(1．桂林電子科技大學(xué) 計(jì)算機(jī)與信息安全學(xué)院,廣西 桂林 541004； 2. 桂林電子科技大學(xué) 廣西可信軟件重點(diǎn)實(shí)驗(yàn)室,廣西 桂林 541004)

?

基于影響力控制的熱傳導(dǎo)算法

雷震1，文益民1,2，王志強(qiáng)1，繆裕青1,2

(1．桂林電子科技大學(xué) 計(jì)算機(jī)與信息安全學(xué)院,廣西 桂林 541004； 2. 桂林電子科技大學(xué) 廣西可信軟件重點(diǎn)實(shí)驗(yàn)室,廣西 桂林 541004)

摘要：因特網(wǎng)上信息嚴(yán)重過(guò)載，使得用戶不容易從紛繁的信息中找到適合自己的內(nèi)容。如何準(zhǔn)確地向用戶推薦他們想要的信息成為急待解決的問(wèn)題。熱傳導(dǎo)算法(HC)被廣泛地應(yīng)用于個(gè)性化推薦領(lǐng)域，但是它的熱量傳播機(jī)制不利于經(jīng)歷豐富的用戶喜歡的流行物品得到更多的熱量。因此，本文提出了基于影響力控制的熱傳導(dǎo)算法(THC)。THC引入兩個(gè)參數(shù)控制度數(shù)大的用戶喜歡的度數(shù)大的物品對(duì)目標(biāo)用戶推薦的影響。另外，本文提出利用用戶對(duì)景點(diǎn)的各項(xiàng)評(píng)分及評(píng)論的情感極性來(lái)判斷用戶是否喜歡一個(gè)景點(diǎn)，還提出了一個(gè)新的指標(biāo)buir以度量度數(shù)大的用戶喜歡的度數(shù)大的物品出現(xiàn)在推薦列表中的比例。實(shí)驗(yàn)結(jié)果表明：適度增大的度數(shù)大的用戶喜歡的度數(shù)大的物品的影響，有助于推薦出目標(biāo)用戶喜歡的物品，從而有助于提升推薦效果。

關(guān)鍵詞：熱傳導(dǎo)；個(gè)性化推薦；用戶偏好；情感極性；二部網(wǎng)絡(luò)；信息過(guò)載；物品流行度；用戶影響力

隨著互聯(lián)網(wǎng)的迅速發(fā)展，用戶越來(lái)越喜歡到相關(guān)網(wǎng)站上尋找自己想要的信息。以旅游領(lǐng)域?yàn)槔?，有機(jī)構(gòu)預(yù)計(jì)2016年中國(guó)在線旅游市場(chǎng)規(guī)模將達(dá)到4 440億元。游客訪問(wèn)旅游網(wǎng)站，尋找他們感興趣的旅游信息，確定他們想去游玩的景點(diǎn)[1]。但是，旅游網(wǎng)站上信息過(guò)載嚴(yán)重，游客不容易從紛繁的旅游信息中選擇合適自己需求的信息。進(jìn)入Web 2.0時(shí)代，搜索和推薦為減輕用戶尋找符合自己需要信息的困難提供了可能，其中利用用戶的歷史信息來(lái)預(yù)測(cè)用戶選擇的個(gè)性化推薦系統(tǒng)成為一種解決信息過(guò)載問(wèn)題的有效工具[2-5]?，F(xiàn)今，商家廣泛使用個(gè)性化推薦系統(tǒng)來(lái)對(duì)潛在的消費(fèi)者進(jìn)行物品、服務(wù)或信息的推薦。例如，亞馬遜使用基于物品的協(xié)同過(guò)濾系統(tǒng)[6]進(jìn)行個(gè)性化書(shū)本推薦；Google利用用戶的點(diǎn)擊行為數(shù)據(jù)建立了新聞推薦系統(tǒng)[7]；百度開(kāi)發(fā)了Q&A社區(qū)的推薦系統(tǒng)[8]等。

近些年，根據(jù)物理動(dòng)力學(xué)原理設(shè)計(jì)的HC算法，已經(jīng)被成功地應(yīng)用到了推薦領(lǐng)域。HC算法將用戶與物品的關(guān)系用一個(gè)二部網(wǎng)絡(luò)來(lái)表示。但是，HC算法也存在一些不足。在HC算法中，目標(biāo)用戶喜歡的物品產(chǎn)生的熱量在兩步傳播過(guò)程中被分別除以了用戶的度和物品的度，所以它削弱了度數(shù)大的用戶喜歡的度數(shù)大的物品對(duì)目標(biāo)用戶選擇物品時(shí)的影響。事實(shí)上，目標(biāo)用戶對(duì)物品的選擇往往受到與他關(guān)聯(lián)的經(jīng)歷豐富的用戶(度數(shù)大的用戶)喜歡的流行物品(度數(shù)大的物品)較大的影響。以旅游推薦為例，如果某用戶不是很清楚什么樣的旅游產(chǎn)品適合自己，他會(huì)愿意聽(tīng)取旅游經(jīng)歷豐富的游客的意見(jiàn)，而旅游經(jīng)歷豐富的游客一般會(huì)推薦該用戶自己喜歡的而且比較流行的景點(diǎn)(度數(shù)大的景點(diǎn))。

本文主要做了如下研究：一是增大與目標(biāo)用戶關(guān)聯(lián)的經(jīng)歷豐富的用戶以及這些用戶喜歡的流行物品對(duì)目標(biāo)用戶選擇物品的影響，從而提出了HC的改進(jìn)算法THC；二是在旅游領(lǐng)域?yàn)榱烁鼫?zhǔn)確地判斷用戶是否喜歡一個(gè)景點(diǎn)，采用了綜合評(píng)價(jià)的方法。本文根據(jù)用戶對(duì)景點(diǎn)的整體評(píng)分、風(fēng)景評(píng)分、趣味評(píng)分、性價(jià)比評(píng)分以及用戶對(duì)景點(diǎn)評(píng)論的情感極性來(lái)判斷用戶是否真的喜歡該景點(diǎn)，從而提出了旅游推薦領(lǐng)域的用戶態(tài)度判斷算法。

1相關(guān)工作

迄今為止,眾多的推薦系統(tǒng)研究者已經(jīng)提出很多算法，如基于協(xié)同過(guò)濾的方法[6-9]、基于內(nèi)容分析的方法[10]、鏈接預(yù)測(cè)方法[11-12]及混合方法[13]。文獻(xiàn)[14]發(fā)現(xiàn)協(xié)同過(guò)濾算法(CF)推薦的TOP-n個(gè)物品更傾向于流行的物品，但是較少關(guān)注用戶可能潛在感興趣的物品[15]。為了克服CF的弱點(diǎn)，文獻(xiàn)[13]提出了熱傳導(dǎo)(HC)算法來(lái)解決推薦系統(tǒng)中的準(zhǔn)確性-多樣性兩難問(wèn)題。文獻(xiàn)[16]提出的物質(zhì)擴(kuò)散(MD)算法，是一種類似于HC的推薦算法，它能帶來(lái)較高的準(zhǔn)確率。文獻(xiàn)[17]認(rèn)為MD算法與HC算法分別在準(zhǔn)確率和多樣性上有優(yōu)勢(shì)，他們分析了不同度的物品在傳播過(guò)程中的影響并引入一個(gè)參數(shù)控制影響程度，提出了一種混合算法。文獻(xiàn)[18]認(rèn)為用戶從不同流行度的物品上獲得的熱量應(yīng)該不同，它們利用一個(gè)參數(shù)來(lái)調(diào)控物品流行度對(duì)用戶獲得熱量的影響并提出了非平衡熱傳導(dǎo)推薦算法。文獻(xiàn)[19]發(fā)現(xiàn)，HC算法中所有不同度的物品和用戶都被同等看待。因此，他們利用邊連接的用戶與物品的度來(lái)衡量邊的權(quán)重，并提出了基于權(quán)重的HC算法(WHC)；但是該算法將用戶和物品的度對(duì)權(quán)重的影響程度視為相同。文獻(xiàn)[5]認(rèn)為HC算法的準(zhǔn)確率較低是由于它傾向于推薦度數(shù)小的物品。為降低度數(shù)小的物品對(duì)目標(biāo)用戶推薦的影響，他們提出了基于偏向的熱傳導(dǎo)算法(BHC)。BHC算法通過(guò)降低度數(shù)小的物品的影響，來(lái)優(yōu)先推薦度數(shù)大的物品，但是削弱了度數(shù)大的用戶對(duì)目標(biāo)用戶的影響。相對(duì)于WHC算法而言，THC算法將用戶與物品的度對(duì)目標(biāo)用戶選擇物品的影響區(qū)別對(duì)待；相對(duì)于BHC算法而言，THC算法不僅考慮到了物品的度對(duì)目標(biāo)用戶選擇物品的影響，還考慮到了用戶的度對(duì)目標(biāo)用戶的影響。

2熱傳導(dǎo)算法

(1)

圖1中給出了HC算法的示例。圖1(a)目標(biāo)用戶喜歡的物品被激活，被賦值熱量1，其余的物品被賦值熱量0；圖1(b)每個(gè)用戶得到的熱量是他喜歡的所有物品的熱量均值；圖1(c)每個(gè)物品得到的熱量是所有喜歡該物品的用戶的熱量均值。

圖1　用戶-物品二部網(wǎng)絡(luò)中的熱傳導(dǎo)Fig.1　Heat conduction in user-item bipartite network

3基于影響力控制的熱傳導(dǎo)算法

在推薦領(lǐng)域，目標(biāo)用戶對(duì)物品的選擇與其相關(guān)聯(lián)的經(jīng)歷豐富的用戶有關(guān)。以旅游領(lǐng)域?yàn)槔?，比如：一個(gè)游客近期想準(zhǔn)備一次旅游，由于他掌握的旅游信息有限，所以他很可能不太清楚去哪里游玩比較合適。他一般會(huì)咨詢旅游經(jīng)歷豐富的朋友，了解他們?cè)?jīng)玩過(guò)的哪些景點(diǎn)比較好。這些旅游經(jīng)歷豐富的用戶一般會(huì)建議他去游玩自己去過(guò)并且喜歡的一些流行的景點(diǎn)，該游客然后會(huì)綜合他們的意見(jiàn)，從中選擇自己想要去的景點(diǎn)。受到以上的啟發(fā)，本文試圖優(yōu)先推薦與目標(biāo)用戶有關(guān)聯(lián)的經(jīng)歷豐富的用戶喜歡的度數(shù)大的物品。

(2)

式中λ和β分別用來(lái)控制度數(shù)大的用戶喜歡的度數(shù)大的物品對(duì)目標(biāo)用戶影響的程度，它們的取值范圍都是0～1。當(dāng)λ=β=1時(shí)，wγθ就變成了基本熱傳導(dǎo)算法中的傳導(dǎo)率。當(dāng)λ和β從1到0變化時(shí)，度數(shù)大的用戶喜歡的度數(shù)大的物品對(duì)目標(biāo)用戶的推薦的影響程度會(huì)越來(lái)越大。

輸入用戶-物品對(duì)數(shù)據(jù)集T，推薦物品個(gè)數(shù)L，目標(biāo)用戶u；

輸出top-L個(gè)物品。

1)目標(biāo)用戶u喜歡的物品被激活，被賦值熱量1；

2)熱量按式(2)的傳播方式從物品傳到用戶；

3)熱量按式(2)的傳播方式從用戶傳到物品；

4)物品按照其上面的熱量按降序排序后，推薦給目標(biāo)用戶u top-L個(gè)物品。

4旅游評(píng)價(jià)中的用戶態(tài)度判斷算法

在推薦領(lǐng)域，有時(shí)僅憑一個(gè)單獨(dú)的評(píng)分并不足以確定用戶是否真的喜歡當(dāng)前物品。以旅游領(lǐng)域?yàn)槔?，如圖2所示，某用戶對(duì)某景點(diǎn)的整體評(píng)分為3，可以認(rèn)為該用戶喜歡該景點(diǎn)。但是，進(jìn)一步觀察發(fā)現(xiàn)：用戶對(duì)當(dāng)前景點(diǎn)的景色評(píng)分為4，對(duì)景點(diǎn)的趣味性、性價(jià)比的評(píng)分均為1。這說(shuō)明用戶對(duì)這個(gè)景點(diǎn)也有不滿意的地方。用戶對(duì)景點(diǎn)的態(tài)度也會(huì)體現(xiàn)在其對(duì)該景點(diǎn)的評(píng)論中。圖2給出的評(píng)論中出現(xiàn)了‘馬達(dá)聲吵死了’，‘大殺(煞)風(fēng)景’及‘沒(méi)有想象中的輕舟已過(guò)萬(wàn)重山的感覺(jué)’等文字。從評(píng)論中可以看出用戶對(duì)這次旅游的體驗(yàn)并不滿意。

圖2　用戶對(duì)景點(diǎn)評(píng)價(jià)和評(píng)論實(shí)例Fig.2　An example of a user’s evaluation and comment on a scenery spot

因此本文設(shè)計(jì)了確定用戶是否喜歡某景點(diǎn)的算法，即旅游評(píng)價(jià)中的用戶態(tài)度判斷算法。設(shè)計(jì)理由如下：如果用戶真的喜歡當(dāng)前景點(diǎn)，那么該用戶對(duì)當(dāng)前景點(diǎn)的各項(xiàng)評(píng)分應(yīng)該都比較高，則所有評(píng)分的均值也應(yīng)該比較大。因此，計(jì)算各項(xiàng)評(píng)分的均值sa，讓均值大小作為判斷用戶是否喜歡該景點(diǎn)的依據(jù)之一。另外，如果用戶真的喜歡當(dāng)前景點(diǎn)，該用戶對(duì)當(dāng)前景點(diǎn)評(píng)論的情感一定會(huì)是非負(fù)向的。算法中，評(píng)論的情感極性計(jì)算方法采用文獻(xiàn)[20]中的情感提取算法。以圖2為例，通過(guò)分析可知，根據(jù)整體評(píng)分會(huì)認(rèn)為用戶喜歡該景點(diǎn)，但用態(tài)度判斷算法可以確定該用戶對(duì)該景點(diǎn)并不是很滿意，因?yàn)閟a<3且評(píng)論的情感極性為負(fù)。使用旅游評(píng)價(jià)中的用戶態(tài)度判斷算法能較為準(zhǔn)確地判斷用戶是否喜歡某景點(diǎn)。用戶態(tài)度判斷算法如下。

輸入 用戶對(duì)該景點(diǎn)的整體評(píng)分st； 用戶對(duì)該景點(diǎn)的風(fēng)景評(píng)分sg；用戶對(duì)該景點(diǎn)的趣味評(píng)分si；用戶對(duì)該景點(diǎn)的性價(jià)比評(píng)分sp；用戶對(duì)該景點(diǎn)的評(píng)論信息C；

輸出true，用戶喜愛(ài)該景點(diǎn)；false，用戶不喜歡該景點(diǎn)。

1)利用ICTCLAS對(duì)C進(jìn)行分詞，去掉停用詞，利用詞性標(biāo)注來(lái)去掉中性詞；

2)對(duì)C中的其余詞，判斷其是否是情感詞；

3)對(duì)每一個(gè)否定詞wi，找出與其最近的情感詞并且將其情感值從swi+1變成-swi+1；

4)對(duì)每一個(gè)程度副詞，找出與其最近的情感詞并且用程度副詞對(duì)應(yīng)的系數(shù)α乘以情感詞的情感值；

5)利用如下公式計(jì)算評(píng)論C的情感極性值；

式中，Sc與Swi分別代表評(píng)論C與情感詞wi的情感值；m是評(píng)論中的詞語(yǔ)個(gè)數(shù)；

6)計(jì)算所有評(píng)分的均值Sa：

7)如果Sa≥3且Sc≥0，返回true；否則返回false。

5實(shí)驗(yàn)與結(jié)果

5.1數(shù)據(jù)集

桂林是全國(guó)乃至世界知名的旅游目的地。本文從http://www.ctrip.com上抓取了關(guān)于桂林市旅游的數(shù)據(jù)來(lái)驗(yàn)證提出的算法。數(shù)據(jù)包含了用戶對(duì)景點(diǎn)的評(píng)分和評(píng)論，評(píng)分包含了4個(gè)方面：用戶對(duì)景點(diǎn)的整體評(píng)分、用戶對(duì)景點(diǎn)的景色評(píng)分、用戶對(duì)景點(diǎn)的趣味性評(píng)分以及用戶對(duì)景點(diǎn)的性價(jià)比評(píng)分(如圖2)。本文采集了包含18 151個(gè)用戶對(duì)143個(gè)景點(diǎn)的18 304條評(píng)分及評(píng)論記錄。為了有效驗(yàn)證算法，對(duì)數(shù)據(jù)集進(jìn)行了預(yù)處理。刪除評(píng)價(jià)景點(diǎn)數(shù)量少于2條的用戶，刪除沒(méi)有用戶評(píng)分的景點(diǎn)，再利用旅游評(píng)價(jià)中的用戶態(tài)度判斷算法計(jì)算用戶是否喜歡某景點(diǎn)。數(shù)據(jù)集包含1 164個(gè)用戶對(duì)143個(gè)景點(diǎn)的5 672條評(píng)分及評(píng)論信息。

為了對(duì)提出算法的有效性進(jìn)行更可靠的驗(yàn)證，本文還使用了電影評(píng)分的數(shù)據(jù)集[21]進(jìn)行對(duì)比實(shí)驗(yàn)。刪除對(duì)電影評(píng)分?jǐn)?shù)目少于2條的用戶，刪除沒(méi)有用戶評(píng)分的電影，最終得到370個(gè)用戶對(duì)578部電影的9 331條評(píng)分記錄。

每組實(shí)驗(yàn)中，數(shù)據(jù)集被分為2部分，其中隨機(jī)挑選出用戶-物品二部網(wǎng)絡(luò)中20%的邊作為測(cè)試集，其余80%的邊為訓(xùn)練集[5]。每組實(shí)驗(yàn)都重復(fù)50次，最終的實(shí)驗(yàn)結(jié)果是這50次實(shí)驗(yàn)結(jié)果的平均值。

5.2評(píng)價(jià)指標(biāo)

為了評(píng)判提出的想法是否達(dá)到了預(yù)期效果，即度數(shù)大的用戶喜歡的度數(shù)大的物品是否被推薦出來(lái)。本文提出了一個(gè)大度用戶大度物品率指標(biāo)(buir)，用來(lái)衡量推薦出的度數(shù)大的用戶喜歡的度數(shù)大的物品出現(xiàn)在推薦列表中的比例。式(3)給出了目標(biāo)用戶i的該指標(biāo)計(jì)算方法。

(3)

式中：Ti是用戶i的推薦列表中物品構(gòu)成的集合，L是推薦列表長(zhǎng)度。Ri是與目標(biāo)用戶i關(guān)聯(lián)的度數(shù)大的用戶喜歡的度數(shù)大的物品集合。任意一個(gè)用戶，如果他與用戶i有共同喜歡的物品，則將該用戶稱為與用戶i有關(guān)聯(lián)的用戶，所有這樣的用戶構(gòu)成的集合稱為與用戶i關(guān)聯(lián)的用戶集合AU。將AU中的所有用戶按照其度進(jìn)行降序排序，并取排在前1/3的用戶，將這些用戶構(gòu)成的集合稱為與用戶i關(guān)聯(lián)的度數(shù)大的用戶集合BU。對(duì)BU中的每一個(gè)用戶j，將用戶j喜歡的物品按其度進(jìn)行降序排序，并取排在前1/3的物品，將這些物品稱為用戶j喜歡的度數(shù)大的物品。將與用戶i關(guān)聯(lián)的度數(shù)大的用戶集合BU中的所有用戶喜歡的度數(shù)大的物品構(gòu)成集合，稱之為與用戶i關(guān)聯(lián)的大度用戶喜歡的大度物品集合，即Ri。對(duì)測(cè)試集中的所有用戶的大度用戶大度物品率取平均就可以得到該算法的大度用戶大度物品率。

為了分析提出算法的效果，本文采用了以下4個(gè)指標(biāo)[5]：排序得分(ranking score)、新穎性(novelty)、多樣性(diversity)及覆蓋率(coverage)。

ranking score(RS)：一個(gè)好的推薦算法應(yīng)該將用戶喜歡的物品排在前面。測(cè)試集中，如果物品α被目標(biāo)用戶i喜歡，物品α位于用戶i的推薦列表中排序?yàn)閞的位置，那么物品α的排序得分為

(4)

式中：m是訓(xùn)練集中物品總數(shù)，ki是訓(xùn)練集中用戶i喜歡的物品總數(shù)。每個(gè)用戶的排序得分，是所有推薦給他并且他的確喜歡的物品的排序得分均值。對(duì)測(cè)試集中所有用戶的排序得分求平均值，就可以得到算法的排序得分。

novelty：新穎性被定義為所有被推薦物品度的平均值。一個(gè)推薦算法的新穎性計(jì)算如式(5)：

(5)

式中：ki是物品i的度，n是算法給所有用戶推薦的物品總數(shù)。推薦算法的新穎性值越小，推薦出來(lái)的物品越新穎。

diversity：一個(gè)推薦算法應(yīng)該給不同的用戶推薦不同的物品。式(6)給出了多樣性的計(jì)算方法：

(6)

式中：L是推薦列表長(zhǎng)度，Qij(L)是用戶ui、uj推薦列表中相同物品的個(gè)數(shù)，Hij表示推薦算法給用戶ui、uj兩者推薦結(jié)果間的多樣性。求出測(cè)試集中任意兩個(gè)用戶的推薦結(jié)果間的多樣性值的平均值，就可以得到一個(gè)推薦算法的多樣性值。多樣性值越大意味著一個(gè)推薦算法給不同的人推薦結(jié)果越不一樣。

coverage：推薦算法的覆蓋率是指算法能推薦的物品種類占所有物品種類的比例。式(7)給出了覆蓋率的計(jì)算方法：

(7)

式中：n是算法給全體用戶推薦的不同物品的數(shù)量，N是物品總數(shù)。覆蓋率越大意味著算法能推薦出的不同物品的數(shù)量越多。

5.3實(shí)驗(yàn)方案

為了觀察buir指標(biāo)隨參數(shù)λ和β的變化情況以及它對(duì)其他指標(biāo)的影響，實(shí)驗(yàn)提供了THC算法分別在旅游數(shù)據(jù)集和電影數(shù)據(jù)集上推薦列表長(zhǎng)度分別為5、8、10、12時(shí)，各指標(biāo)隨參數(shù)變化的情況圖。圖分為8組，每組5張，共計(jì)40張。由于每組圖的變化情況類似，本文只提供了推薦列表L=10時(shí)THC算法在旅游數(shù)據(jù)集上的結(jié)果，以分析buir與其他指標(biāo)的關(guān)系。各指標(biāo)的變化分別如圖3～7所示。為了進(jìn)一步分析THC方法的有效性，分別使用旅游數(shù)據(jù)集和電影評(píng)分?jǐn)?shù)據(jù)集對(duì)BHC[5]、WHC[18]、MD[16]、HC[5]及THC在推薦列表的長(zhǎng)度分別為5、8、10、12時(shí)的排序得分進(jìn)行比較。實(shí)驗(yàn)結(jié)果如圖8、9所示。需要說(shuō)明的是：某用戶對(duì)某電影喜愛(ài)的條件是該用戶對(duì)該電影的評(píng)分大于或等于3。某用戶對(duì)某景點(diǎn)是否喜愛(ài)的判斷是利用旅游評(píng)價(jià)中的用戶態(tài)度判斷算法計(jì)算得出。BHC和WHC中的參數(shù)變化范圍為0～1。

圖3　L=10時(shí)，THC算法在旅游評(píng)價(jià)數(shù)據(jù)集上buir指標(biāo)隨參數(shù)變化圖Fig.3　The variation of THC’s buir index on the travel data set when L=10

圖4　L=10時(shí)，THC算法在旅游評(píng)價(jià)數(shù)據(jù)集上排序得分指標(biāo)隨參數(shù)變化Fig.4　The variation of THC’s rank score index on the travel data set when L=10

圖5　L=10時(shí)，THC算法在旅游評(píng)價(jià)數(shù)據(jù)集上新穎性指標(biāo)隨參數(shù)變化Fig.5　The variation of THC’s novelty index on the travel data set when L=10

圖6　L=10時(shí)，THC算法在旅游評(píng)價(jià)數(shù)據(jù)集上多樣性指標(biāo)隨參數(shù)變化Fig.6　The variation of THC’s diversity index on the travel data set when L=10

圖7　L=10時(shí)，THC算法在旅游評(píng)價(jià)數(shù)據(jù)集上覆蓋率指標(biāo)隨參數(shù)變化Fig.7　The variation of THC’s coverage index on the travel data set when L=10

圖8　電影評(píng)分?jǐn)?shù)據(jù)集上各算法的排序得分對(duì)比結(jié)果Fig.8　The comparison of rank score index on the movie data set

圖9　旅游評(píng)價(jià)數(shù)據(jù)集上各算法的排序得分對(duì)比結(jié)果Fig.9　The comparison of rank score index on the travel data set

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

圖3～7中的黑色代表各圖中相應(yīng)指標(biāo)值較大的區(qū)域，白色代表各圖中相應(yīng)指標(biāo)值較小的區(qū)域，圖中顏色越黑表示相應(yīng)指標(biāo)值越大。由圖3可以看出，當(dāng)λ取值小于0.5，β取值也小于0.5時(shí)，此時(shí)推薦出來(lái)的度數(shù)大的用戶喜歡的度數(shù)大的物品較多。圖4中相應(yīng)區(qū)域的排序得分較低，這說(shuō)明度數(shù)大的用戶喜歡的度數(shù)大的物品一般是大家所喜歡的物品，與文中開(kāi)始提出的假設(shè)一致；由于此時(shí)推薦出來(lái)的度數(shù)大的物品較多，所以推薦的物品的新穎性較低即新穎性值較大，這與圖5中相應(yīng)區(qū)域的指標(biāo)數(shù)據(jù)是一致的；另外，度數(shù)大的用戶喜歡的度數(shù)大的物品在整個(gè)系統(tǒng)的所有物品中占的比例是比較小的，因?yàn)榇蠖鄶?shù)物品都不是流行物品，所以此時(shí)多樣性和覆蓋率都較低，這與圖6和圖7中相應(yīng)區(qū)域的指標(biāo)數(shù)據(jù)一致。對(duì)于圖4，數(shù)據(jù)表明：當(dāng)λ與β分別取0.05、0.55時(shí)，排序得分取得最優(yōu)值0.029 8，但此時(shí)buir并不是最大。可以得出這樣的結(jié)論：雖然目標(biāo)用戶會(huì)喜歡度數(shù)大的用戶喜歡的度數(shù)大的物品，但是推薦的量要適度。還可以發(fā)現(xiàn)：此時(shí)的排序得分要比當(dāng)λ=β=1.0時(shí)的HC算法的排序得分要好，而此時(shí)的buir指標(biāo)也比HC的要高。

通過(guò)分析各個(gè)評(píng)價(jià)指標(biāo)變化圖，可以得出如下結(jié)論：1)如果要向用戶推薦較多度數(shù)大的用戶喜歡的度數(shù)大的物品，則應(yīng)該將λ與β的取值范圍都限制在0～0.5，因?yàn)樵诖朔秶衎uir的值均較大。2)如果要使算法的排序得分取得最大值，2個(gè)參數(shù)λ與β的最優(yōu)值應(yīng)該從0～1之間尋找。雖然λ與β在0～0.5取值時(shí)，度數(shù)大的用戶喜歡的度數(shù)大的物品更可能被推薦，但是并不一定是推薦得越多，排序得分越好。3)如果要向用戶推薦較多的新穎物品，則不該將λ與β的取值范圍都限制在0～0.5，因?yàn)楫?dāng)buir較大時(shí)，推薦出來(lái)的度數(shù)大的用戶喜歡的度數(shù)大的物品較多，此時(shí)推薦出來(lái)的物品必然不新穎。

圖8和圖9是BHC、MD、WHC、HC及THC在兩個(gè)數(shù)據(jù)集上推薦列表的長(zhǎng)度分別為5、8、10、12時(shí)排序得分的對(duì)比結(jié)果。其中BHC、WHC及THC是取所有不同參數(shù)結(jié)果中的最優(yōu)值。通過(guò)觀察可以發(fā)現(xiàn)，本文提出的THC算法，與基本的HC算法相比，在所有的情況下排序得分都要好；與MD、WHC、BHC算法相比，排序得分也都要好，雖然提升程度較小。

通過(guò)上面的分析可以知道：通過(guò)適度的優(yōu)先推薦度數(shù)大的用戶喜歡的度數(shù)大的物品，有助于向用戶推薦其喜歡的物品，從而有助于提升算法的效果。另外，還可以發(fā)現(xiàn)MD和BHC算法的排序得分在所有情形下都比HC算法要好，這與文獻(xiàn)[5]中的結(jié)論一致；WHC算法在所有條件下都比HC算法的排序得分好，這與文獻(xiàn)[19]中的結(jié)論一致。

6結(jié)束語(yǔ)

由于HC算法減弱了度數(shù)大的用戶喜歡的度數(shù)大的物品對(duì)目標(biāo)用戶的影響，本文提出了基于影響力控制的熱傳導(dǎo)算法THC。THC引入2個(gè)參數(shù)來(lái)控制度數(shù)大的用戶喜歡的度數(shù)大的物品被優(yōu)先推薦的程度。為了檢驗(yàn)提出的想法是否達(dá)到預(yù)期效果，在電影評(píng)分?jǐn)?shù)據(jù)集和旅游評(píng)價(jià)數(shù)據(jù)集上進(jìn)行了多項(xiàng)對(duì)比實(shí)驗(yàn)。本文還提出了旅游評(píng)價(jià)中的用戶態(tài)度判斷算法及一個(gè)新指標(biāo)buir。實(shí)驗(yàn)結(jié)果表明，當(dāng)THC中的2個(gè)參數(shù)λ和β較小時(shí)，度數(shù)大的用戶喜歡的度數(shù)大的物品能被更多的推薦，但這種推薦要有控制，否則會(huì)降低排序得分。實(shí)驗(yàn)結(jié)果還表明THC算法在排序得分指標(biāo)上比BHC、MD、WHC及HC算法表現(xiàn)更好。未來(lái)可考慮結(jié)合用戶間的朋友關(guān)系與信任關(guān)系進(jìn)一步調(diào)控度數(shù)大的用戶喜歡的度數(shù)大的物品對(duì)目標(biāo)用戶推薦的影響。

參考文獻(xiàn):

[1]文益民, 史一帆, 蔡國(guó)永, 等. 個(gè)性化旅游推薦研究綜述[EB/OL]. 北京: 中國(guó)科技論文在線, 2014. [2014-07-03]. http://www.paper.edu.cn/releasepaper/content/201407-56.

[2]RESNICK P, VARIAN H R. Recommender systems[J]. Communications of the ACM, 1997, 40(3): 56-58.

[3]ADOMAVICIUS G, TUZHILIN A. Toward the next generation of recommender systems: a survey of the state-of-the-art and possible extensions[J]. IEEE transactions on knowledge and data engineering, 2005, 17(6): 734-749.

[4]FELFERNIG A, GORDEA S, JANNACH D, et al. A short survey of recommendation technologies in travel and tourism[J]. OEGAI journal, 2007, 25(7): 17-22.

[5]LIU Jianguo, ZHOU Tao, GUO Qiang. Information filtering via biased heat conduction[J]. Physical review E, 2011, 84(3): 037101.

[6]LINDEN G, SMITH B, YORK J. Amazon. com recommendations: item-to-item collaborative filtering[J]. IEEE internet computing, 2003, 7(1): 76-80.

[7]DAS A S, DATAR M, GARG A, et al. Google news personalization: scalable online collaborative filtering[C]//Proceedings of the 16th International Conference on World wide Web. New York, USA, 2007: 271-280.

[8]LIU Qiwen, CHEN Tianjian, CAI Jing, et al. Enlister: baidu's recommender system for the biggest chinese Q & A website[C]//Proceedings of the Sixth ACM Conference on Recommender Systems. New York, USA, 2012: 285-288.

[9]HERLOCKER J L, KONSTAN J A, RIEDL J. Explaining collaborative filtering recommendations[C]//Proceedings of the 2000 ACM Conference on Computer Supported Cooperative Work. New York, USA, 2000: 241-250.

[10]PAZZANI M J. A framework for collaborative, content-based and demographic filtering[J]. Artificial intelligence review, 1999, 13(5-6): 393-408.

[11]ZHOU Tao, Lü Linyuan, ZHANG Yicheng. Predicting missing links via local information[J]. The european physical journal B, 2009, 71(4): 623-630.

[12]Lü Linyuan, ZHOU Tao. Link prediction in weighted networks: the role of weak ties[J]. EOL (europhysics letters), 2010, 89(1): 18001.

[13]ZHOU Tao, KUSCSIK Z, LIU Jianguo, et al. Solving the apparent diversity-accuracy dilemma of recommender systems[J]. Proceedings of the national academy of sciences of the United States of America, 2010, 107(10): 4511-4515.

[14]ZENG Wei, SHANG Mingsheng, ZHANG Qianming, et al. Can dissimilar users contribute to accuracy and diversity of personalized recommendation[J]. International journal of modern physics C, 2010, 21(10): 1217-1227.

[15]ZHANG Zike, YU Lu, FANG Kuan, et al. Website-oriented recommendation based on heat spreading and tag-aware collaborative filtering[J]. Physica A: statistical mechanics and its applications, 2014, 399: 82-88.

[16]ZHOU Tao, REN Jie, MEDO M, et al. Bipartite network projection and personal recommendation[J]. Physical review E, 2007, 76(4): 046115.

[17]NIE Dacheng, AN Yahui, DONG Qiang, et al. Information filtering via balanced diffusion on bipartite networks[J]. Physica A: statistical mechanics and its applications, 2015, 421: 44-53.

[18]侯磊, 胡兆龍, 張博, 等. 基于流行度的非平衡熱傳導(dǎo)推薦算法研究[J]. 計(jì)算機(jī)應(yīng)用研究, 2015, 32(11): 3235-3237.

HOU Lei, HU Zhaolong, ZHANG Bo, et al. Information filtering via non-equilibrium heat conduction with consideration of popularity[J]. Application research of computers, 2015, 32(11): 3235-3237.

[19]LIU Jianguo, GUO Qiang, ZHANG Yicheng. Information filtering via weighted heat conduction algorithm[J]. Physica A: statistical mechanics and its applications, 2011, 390(12): 2414-2420.

[20]SHI Shaoliang, LI Yunpeng, WEN Yimin, et al. Adding the sentiment attribute of nodes to improve link prediction in social network[C]//Proceedings of the 12th International Conference on Fuzzy Systems and Knowledge Discovery. Zhangjiajie, China, 2015: 1263-1269.

[20]LIU Jinhu, ZHANG Zike, CHEN Lingjiao, et al. Gravity effects on information filtering and network evolving[J]. PLoS one, 2014, 9(3): e91070.

雷震，男，1991年生，碩士研究生，主要研究方向?yàn)橥扑]系統(tǒng)與數(shù)據(jù)挖掘。

文益民，男，1969年生，博士，教授，中國(guó)計(jì)算機(jī)學(xué)會(huì)高級(jí)會(huì)員。主要研究方向?yàn)闄C(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘、極化SAR圖像處理、社會(huì)計(jì)算。主持省部級(jí)科研項(xiàng)目8項(xiàng)，獲得省部級(jí)教學(xué)、科研獎(jiǎng)勵(lì)5項(xiàng)，發(fā)表學(xué)術(shù)論文30余篇，其中被SCI、EI收錄18篇，翻譯譯著1部。

王志強(qiáng)，男，1991年生，碩士研究生，主要研究方向?yàn)閿?shù)據(jù)挖掘、旅游推薦。

中文引用格式：雷震，文益民，王志強(qiáng)，等.基于影響力控制的熱傳導(dǎo)算法[J]. 智能系統(tǒng)學(xué)報(bào)， 2016, 11(3): 328-335.

英文引用格式：LEI Zhen， WEN Yimin， WANG Zhiqiang， et al. Heat conduction controlled by the influence of users and items[J]. CAAI transactions on intelligent systems, 2016,11(3): 328-335.

Heat conduction controlled by the influence of users and items

LEI Zhen1， WEN Yimin1,2， WANG Zhiqiang1， MIAO Yuqing1,2

(1.School of Computer Science and Information Security, Guilin 541004, China; 2. Guangxi Key Laboratory of Trusted Software, Guilin University of Electronic Technology, Guilin 541004, China)

Abstract：The overload of information on the Internet can lead to users feeling hopeless about finding the information they are seeking. Making accurate recommendations to users about the information they truly need is an urgent problem that must be addressed. The heat conduction (HC) algorithm has recently been applied in personalized recommendation technology, but its mechanism weakens the heat generated from the larger-degree itemsliked by the larger-degree users. To solve this problem, we propose an improved HC algorithm that is based on user influence control (THC). THC introduces two tunable parameters to better control the influence of larger-degree users′ preferences for larger-degree items on target users. We also consider a user′s comment scores and the sentiment polarity of a comment in a given scenario to accurately judge whether the user truly likes the given scenario. We also propose a new index, called a buir, which measures the ratio of the larger-degree items that are liked by larger-degree users on the recommendation list. Experimental results show that appropriately promoting the influence of larger-degree items that are liked by larger-degree users helps in making recommendations to target users regarding items in which they are truly interested, thereby improving the performance of the recommendation.

Keywords：heat conduction; personalized recommendation; user′s preference; sentiment polarity; bipartite network; information overload; item popularity; user's influence

作者簡(jiǎn)介：

中圖分類號(hào)：TP391

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

文章編號(hào)：1673-4785(2016)03-0328-08

通信作者：文益民.E-mail: ymwen2004@aliyun.com.

基金項(xiàng)目：國(guó)家自然科學(xué)基金項(xiàng)目(61363029)；廣西省科學(xué)研究與技術(shù)開(kāi)發(fā)項(xiàng)目(桂科攻14124005-2-1)；湖南省博士后科研專項(xiàng)計(jì)劃項(xiàng)目(2011RS4073)；廣西信息科學(xué)中心項(xiàng)目(YB408).

收稿日期：2016-03-19.網(wǎng)絡(luò)出版日期：2016-05-13.

DOI:10.11992/tis.201603042

網(wǎng)絡(luò)出版地址：http://www.cnki.net/kcms/detail/23.1538.TP.20160513.0920.016.html