基于弱關(guān)系的異質(zhì)社交網(wǎng)絡(luò)推薦

荀亞玲，畢慧敏，張繼福

(太原科技大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，山西 太原 030024)

0 引 言

推薦系統(tǒng)作為一種信息過濾手段，幫助用戶從大量信息中發(fā)現(xiàn)自己感興趣的內(nèi)容。傳統(tǒng)推薦算法大多以與目標(biāo)用戶關(guān)系密切的強(qiáng)關(guān)系對(duì)象或者以與目標(biāo)項(xiàng)目相似度高為標(biāo)準(zhǔn)進(jìn)行協(xié)同過濾推薦，具有很好的可解釋性[1-3]，但強(qiáng)關(guān)系推薦因其本身圈子小、產(chǎn)生的嘮叨型內(nèi)容較優(yōu)質(zhì)內(nèi)容多，往往會(huì)導(dǎo)致推薦的單一化[4-6]。與強(qiáng)關(guān)系相反，弱關(guān)系具有更為豐富的語(yǔ)義信息及強(qiáng)大的信息影響力[7,8]，因此，基于弱關(guān)系的推薦，能夠擺脫傳統(tǒng)的基于強(qiáng)關(guān)系推薦帶來的推薦類型單一、推薦項(xiàng)目重復(fù)性等問題。

豐富的社交網(wǎng)絡(luò)常被建模為同質(zhì)或異質(zhì)結(jié)構(gòu)網(wǎng)絡(luò)，同質(zhì)社交網(wǎng)絡(luò)中節(jié)點(diǎn)和關(guān)系類型單一，且具有很強(qiáng)的不對(duì)稱性和群體規(guī)模小等特征，不利于消除用戶的感知偏差。而異質(zhì)網(wǎng)絡(luò)融合了更多類型的對(duì)象以及對(duì)象間復(fù)雜的交互，也可以跨網(wǎng)絡(luò)平臺(tái)融合更多豐富的語(yǔ)義信息。考慮弱關(guān)系的社交網(wǎng)絡(luò)包含了很多不同類型的對(duì)象和對(duì)象之間復(fù)雜的交互。若將這些相互作用的對(duì)象建模為同質(zhì)網(wǎng)絡(luò)是很困難的，難以體現(xiàn)不同類型對(duì)象的特征信息差異[9]，往往只能抽取實(shí)際交互系統(tǒng)的部分信息，或是沒有區(qū)分交互系統(tǒng)中對(duì)象和關(guān)系的差異性，均會(huì)造成信息不完整或信息損失。因此，可以融合更多類型對(duì)象及其復(fù)雜交互關(guān)系的異質(zhì)信息網(wǎng)絡(luò)(heterogeneous information network)被引入推薦系統(tǒng)[10-14]。

為準(zhǔn)確地選擇推薦的主體范圍及有效地利用實(shí)體間的交互信息進(jìn)行有效推薦，提出一種結(jié)合弱關(guān)系的異質(zhì)社交網(wǎng)絡(luò)推薦算法，充分克服了推薦結(jié)果趨于同質(zhì)性與冗余共享信息的問題。主要貢獻(xiàn)包括：①利用用戶間信任值對(duì)引入弱關(guān)系產(chǎn)生的大量用戶節(jié)點(diǎn)進(jìn)行有效篩選；②結(jié)合弱關(guān)系構(gòu)建了一種全關(guān)系的異質(zhì)信息網(wǎng)絡(luò)模型(UI-HIN)；③提出了一種最佳信任路徑選擇算法(BTP)。

1 相關(guān)工作

根據(jù)推薦方式的不同，傳統(tǒng)的推薦算法主要分為3類：基于內(nèi)容的推薦、協(xié)同過濾推薦和混合推薦。這些大都是建立在“強(qiáng)關(guān)系”上的推薦，使用“相似度系數(shù)”來衡量?jī)蓚€(gè)用戶間的相似度，推薦具有較強(qiáng)的可解釋性但面臨著個(gè)性化缺失的問題。此外，個(gè)人隱私問題越來越受到互聯(lián)網(wǎng)用戶的關(guān)注，傳統(tǒng)推薦方法收集用戶數(shù)據(jù)越來越困難，造成“冷啟動(dòng)”制約推薦方法的性能，難以挖掘用戶潛在興趣。

文獻(xiàn)[15]在用戶協(xié)同過濾的基礎(chǔ)上通過計(jì)算活動(dòng)用戶與少量專家用戶之間的相似度作為信任值解決用戶評(píng)分?jǐn)?shù)據(jù)稀疏造成的冷啟動(dòng)問題。文獻(xiàn)[16]提出一種融合項(xiàng)目特征和移動(dòng)用戶信任關(guān)系的協(xié)同過濾推薦算法緩解評(píng)分?jǐn)?shù)據(jù)稀疏對(duì)協(xié)同過濾算法的影響，提高了移動(dòng)推薦的準(zhǔn)確度。同傳統(tǒng)的推薦算法相比，增加的“信任”機(jī)制雖然有效地緩解了數(shù)據(jù)稀疏問題，但根本上還是以相似度作為標(biāo)準(zhǔn)來衡量信任值，并沒有改變推薦的主體，推薦重復(fù)問題沒有得到解決。同強(qiáng)關(guān)系相反，弱關(guān)系可以是雙向的也可以是單向的，因?yàn)椴恍枰^強(qiáng)的互動(dòng)，所以維系起來成本更低，依靠“弱關(guān)系”的力量可以擴(kuò)大推薦的選擇范圍增加推薦的新穎性，減少了嘮叨型內(nèi)容，使推薦更加明確。文獻(xiàn)[17]提出一種考慮子群貢獻(xiàn)和興趣活躍兩個(gè)因素的動(dòng)態(tài)群聚合方案集成所有子組的推薦列表，以生成該組的最終結(jié)果。文獻(xiàn)[18]提出了基于用戶評(píng)分和社會(huì)關(guān)系的隱含偏好社區(qū)的推薦模型。在基于社區(qū)推薦算法中將社交網(wǎng)絡(luò)中的用戶組織成社區(qū)的形式，社區(qū)的代表性特點(diǎn)就是興趣高度一致性，這種基于社區(qū)的推薦通常會(huì)使得推薦類型過于局限，不利于用戶產(chǎn)生對(duì)新類型項(xiàng)目的興趣。

為了融合更加豐富的異構(gòu)信息，基于異質(zhì)信息網(wǎng)絡(luò)的推薦算法得到了廣泛關(guān)注。有學(xué)者將元圖的概念引入異質(zhì)信息網(wǎng)絡(luò)推薦，采用矩陣分解和因子分解機(jī)的方法進(jìn)行信息融合，獲取相似元圖間的潛在特征，不同元圖間的有用特征生成用戶和項(xiàng)目關(guān)系進(jìn)行推薦[11]。也有一些研究人員提出將意向推薦中復(fù)雜的對(duì)象和豐富的交互建模為一個(gè)異構(gòu)信息網(wǎng)絡(luò)和元路徑引導(dǎo)的意圖推薦嵌入方法(MEIRec)學(xué)習(xí)意圖推薦中對(duì)象的嵌入[12]。已有的基于神經(jīng)網(wǎng)絡(luò)的協(xié)同過濾模型(NeuACF)提取不同的元路徑用戶和項(xiàng)目的不同方面級(jí)相似矩陣，通過深層神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)方面級(jí)潛在因素進(jìn)行推薦[13]。基于注意的HIN嵌入元路徑融合模型(AMPE)的提出，提取并學(xué)習(xí)了HIN中多個(gè)具有元路徑的同質(zhì)網(wǎng)絡(luò)與注意機(jī)制融合[14]。然而，現(xiàn)有算法的異質(zhì)網(wǎng)絡(luò)往往又只關(guān)注異質(zhì)信息，忽視了同質(zhì)信息，導(dǎo)致推薦信息的缺失。

綜上所述，弱關(guān)系可以使用戶的社交網(wǎng)絡(luò)范圍會(huì)更廣，接觸到的內(nèi)容也會(huì)更豐富，根據(jù)弱關(guān)系構(gòu)建的社交網(wǎng)絡(luò)內(nèi)容比強(qiáng)關(guān)系產(chǎn)生的內(nèi)容更加優(yōu)質(zhì)。將這種包含大量相互作用、不同類型實(shí)體的多類型網(wǎng)絡(luò)化數(shù)據(jù)建模成異質(zhì)信息網(wǎng)絡(luò)能夠充分利用網(wǎng)絡(luò)中豐富的對(duì)象和關(guān)系的信息，使得推薦更加真實(shí)、新穎。

2 基于弱關(guān)系的異質(zhì)網(wǎng)絡(luò)推薦算法

弱關(guān)系本質(zhì)上并不是強(qiáng)調(diào)關(guān)系的密切程度，而是信息的傳遞，其融合了網(wǎng)絡(luò)中豐富的語(yǔ)義和交互信息，推薦的項(xiàng)目類型跨度較大，可以實(shí)現(xiàn)改善了推薦新穎性。弱關(guān)系包含用戶弱關(guān)系和項(xiàng)目弱關(guān)系。用戶弱關(guān)系是指用戶之間關(guān)系并不緊密，即我們所謂的泛泛之交。項(xiàng)目弱關(guān)系指交互項(xiàng)目可能涉及不同領(lǐng)域，項(xiàng)目與項(xiàng)目可能沒有屬性上的相似性，但卻同時(shí)出現(xiàn)在用戶的歷史記錄里。該推薦算法首先建立基于用戶弱關(guān)系的社交網(wǎng)絡(luò)模型，借助用戶間信任值篩選節(jié)點(diǎn)后，再引入項(xiàng)目節(jié)點(diǎn)建立異質(zhì)網(wǎng)絡(luò)模型，最后通過優(yōu)化的路徑優(yōu)化算法選擇一組最佳推薦路徑。

2.1 基于弱關(guān)系的用戶社交網(wǎng)絡(luò)

社交網(wǎng)絡(luò)被建為有向圖G，G中節(jié)點(diǎn)代表用戶，包含弱關(guān)系用戶；節(jié)點(diǎn)Un，U′n之間的邊表示關(guān)系；邊上的標(biāo)簽代表節(jié)點(diǎn)間信任值V(Un,U′n)，信任是不對(duì)稱的(從Un到U′n的信任值不等于從Un到U′n的)。另外，沒有直接信任關(guān)系的節(jié)點(diǎn)之間沒有連接。設(shè)置最小信任閾值和最大請(qǐng)求長(zhǎng)度篩選去除不符合條件的節(jié)點(diǎn)，建立的用戶社交網(wǎng)絡(luò)模型如圖1所示。

圖1 用戶社交網(wǎng)絡(luò)

其中，V(Un,U′n)的獲取主要來自以下信任值的結(jié)合：

(1)用戶本身自帶的信任值V(Un)

用戶本身自帶的信任值是指用戶的地位、職業(yè)、資歷而產(chǎn)生的影響力，以“法定”為支柱，可以說是一種強(qiáng)制性影響，我們可以分別從這3個(gè)因素考慮：

1)地位因素：根據(jù)人類傳統(tǒng)觀念，米爾拉格姆實(shí)驗(yàn)表明正常的普通人在權(quán)威的壓力下都可以成為施虐者。大腦惰性讓我們認(rèn)為權(quán)威人士不同于普通人，由經(jīng)驗(yàn)產(chǎn)生了對(duì)權(quán)威的服從感(比如同樣是推薦一部電影，一位專業(yè)影評(píng)人的推薦比普通人更令人信服);

2)職業(yè)因素：在社會(huì)中扮演同樣角色的人會(huì)產(chǎn)生很多必要性的推薦，不一定是用戶感興趣的，卻是用戶不得不用的(比如辦公APP，很少人會(huì)喜歡，但又不得不用);

3)資歷因素：現(xiàn)實(shí)生活中，人們對(duì)某領(lǐng)域資歷較深的人更具信任感。

(2)相鄰用戶之間因?yàn)樾畔⒔换ザa(chǎn)生的信任值

這種信任是指直接用戶節(jié)點(diǎn)間的關(guān)注熱度(比如微博的轉(zhuǎn)發(fā)、點(diǎn)贊、評(píng)論、瀏覽)，由用戶行為決定。

2.2 全關(guān)系用戶-項(xiàng)目異質(zhì)網(wǎng)絡(luò)模型

傳統(tǒng)異質(zhì)網(wǎng)絡(luò)又只關(guān)心異質(zhì)關(guān)系而忽視了同質(zhì)信息，因此，通過對(duì)傳統(tǒng)異質(zhì)網(wǎng)絡(luò)進(jìn)行了拓展，引入項(xiàng)目節(jié)點(diǎn)，構(gòu)建了全關(guān)系的用戶-項(xiàng)目異質(zhì)網(wǎng)絡(luò)模型。

定義1 異質(zhì)信息網(wǎng)絡(luò)：包含多種類型的節(jié)點(diǎn)和邊，并且具有豐富語(yǔ)義的信息網(wǎng)絡(luò)。信息網(wǎng)絡(luò)被定義為一個(gè)有向網(wǎng)絡(luò)圖G=(V,E)，其中，V是所有實(shí)體結(jié)點(diǎn)的集合，E是所有關(guān)系邊的集合。并且存在著一個(gè)結(jié)點(diǎn)類型的映射函數(shù)φ:V→A和一個(gè)邊類型的映射函數(shù)Ψ:E→R，對(duì)于每個(gè)對(duì)象v∈V屬于一種特殊的對(duì)象類型φ(v)∈A，每個(gè)鏈接e∈E屬于一種特殊的關(guān)系類型Ψ(e)∈R，那么這種網(wǎng)絡(luò)類型就是信息網(wǎng)絡(luò)。當(dāng)對(duì)象類型的種類|A|>1或者關(guān)系類型的種類|R|>1時(shí)，這種信息網(wǎng)絡(luò)是異質(zhì)信息網(wǎng)絡(luò)。

定義2 關(guān)系用戶-項(xiàng)目異質(zhì)網(wǎng)絡(luò)：一個(gè)包含(用戶,用戶)、(用戶,項(xiàng)目)、(項(xiàng)目,項(xiàng)目)節(jié)點(diǎn)對(duì)以及節(jié)點(diǎn)對(duì)間不同類型關(guān)系的帶權(quán)有向圖G=(U,I,E(Un,U′n),E(Un,Im),E(Im,I′m),V(Un,U′n),V(Un,Im),S(Im,I′m)),其中U代表用戶的集合，I代表U使用的項(xiàng)目集合，E(Un,U′n)代表用戶與用戶信任關(guān)系的有向邊，E(Un,Im)代表用戶與項(xiàng)目的使用被使用關(guān)系的有向邊，E(Im,I′m)代表項(xiàng)目與項(xiàng)目關(guān)系的有向邊，V(Un,U′n)代表用戶之間的信任值，V(Un,Im)代表用戶對(duì)項(xiàng)目的信任值，S(Im,I′m)代表項(xiàng)目間信任值。

圖2為一個(gè)典型的全關(guān)系異質(zhì)信息網(wǎng)絡(luò)模型，其中，S(Im,I′m)的大小和方向由關(guān)聯(lián)規(guī)則的知識(shí)確定，首先依靠關(guān)聯(lián)規(guī)則挖掘頻繁項(xiàng)集，然后根據(jù)支持度確定關(guān)聯(lián)的大小和方向，具體的求解過程如下：

圖2 用戶-項(xiàng)目異質(zhì)信息網(wǎng)絡(luò)模型

(1)根據(jù)項(xiàng)目-項(xiàng)目的歷史數(shù)據(jù)挖掘潛在的頻繁項(xiàng)集，如頻繁N項(xiàng)集{Ip,…,Ip+n,…,Ip+N}；

(2)計(jì)算頻繁N項(xiàng)集中每個(gè)項(xiàng)目存在條件下存在其余項(xiàng)目的概率S(Ip,Ip+n)，S(Ip+n,Ip)

(1)

(2)

(3)特別地，針對(duì)在用戶的評(píng)價(jià)矩陣中得分較高但沒有出現(xiàn)在由(1)獲得的頻繁N項(xiàng)集中的項(xiàng)目，通過該項(xiàng)目出現(xiàn)在用戶記錄中的屬性信息，挖掘具有相同屬性信息的項(xiàng)目與其的關(guān)聯(lián)，構(gòu)造相應(yīng)的項(xiàng)目-項(xiàng)目關(guān)聯(lián)邊(方向指向該項(xiàng)目，大小為用戶評(píng)價(jià)矩陣中對(duì)該項(xiàng)目的平均評(píng)價(jià)值)，得到相應(yīng)的頻繁N項(xiàng)集。

2.3 BTP算法思想與相關(guān)定義

異質(zhì)信息網(wǎng)絡(luò)中邊的權(quán)值描述了具有直接關(guān)系的節(jié)點(diǎn)間不同類型的信任關(guān)系，為了挖掘具有間接關(guān)系的節(jié)點(diǎn)之間的推薦影響力，應(yīng)用節(jié)點(diǎn)間的信任傳遞特性發(fā)現(xiàn)，具有間接關(guān)系的兩個(gè)節(jié)點(diǎn)之間可能會(huì)存在一條或多條連接路徑。由圖1可知節(jié)點(diǎn)U1到U10有6條路徑：U1→U2→U5→U10，U1→U2→U5→U8→U10，U1→U2→U6→U8→U10，U1→U3→U6→U8→U10，U1→U3→U7→U9→U10，U1→U4→U7→U9→U10，如果考慮所有從U1到U10的路徑，雖然使用了網(wǎng)絡(luò)中的所有可能信息，但由于節(jié)點(diǎn)數(shù)量的龐大，不同節(jié)點(diǎn)之間的信任值不同，對(duì)每一組節(jié)點(diǎn)對(duì)分別設(shè)置最大請(qǐng)求長(zhǎng)度(MTL)和最小信任閾值(MTT)，無疑增加了工作量，如果使用固定長(zhǎng)度的路徑會(huì)損失有價(jià)值信息。

定義3 最佳信任路徑L：對(duì)于每條L滿足RL<>TVT。其中，RL和RVT分別表示路徑L的長(zhǎng)度和信任總值；TTL和TVT分別為設(shè)置的最大請(qǐng)求長(zhǎng)度和最小信任閾值。

BTP算法流程可分為3部分：①根據(jù)重啟隨機(jī)游走算法(ppr)的思想得到目標(biāo)節(jié)點(diǎn)與其余節(jié)點(diǎn)的相關(guān)度矩陣，去除相關(guān)度低的節(jié)點(diǎn)；②對(duì)于具有相同終止節(jié)點(diǎn)的可能信任路徑，求取它們的平均請(qǐng)求長(zhǎng)度(ARL)和平均信任總值(AVT)作為最佳信任路徑的篩選依據(jù)

(3)

式中：RL代表路徑的請(qǐng)求長(zhǎng)度，β≥0表示當(dāng)路徑的請(qǐng)求長(zhǎng)度大于以相同節(jié)點(diǎn)為終止節(jié)點(diǎn)的路徑集合的ARL時(shí)，所能接受的最大請(qǐng)求長(zhǎng)度差值；RVT代表路徑的信任總值，γ≥0表示在路徑請(qǐng)求長(zhǎng)度小于以相同節(jié)點(diǎn)為終止節(jié)點(diǎn)的路徑集合的ARL時(shí)，允許路徑的信任總值小于AVT的最大值；③對(duì)于從源節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)只有一條路徑的情況，因?yàn)樵冖俸Y選終止節(jié)點(diǎn)用戶時(shí)就避免了請(qǐng)求長(zhǎng)度過長(zhǎng)、信任值過小的情況，所以直接將這種類型路徑作為最佳信任路徑。

2.4 BTP算法描述

輸入：由重啟隨機(jī)游走算法(ppr)得到的高相關(guān)度節(jié)點(diǎn)集合Tn；Tn的個(gè)數(shù)N；源或目標(biāo)節(jié)點(diǎn)Sn

基于穩(wěn)定農(nóng)戶的宅基地占有使用權(quán)、充分保障其在農(nóng)村的基本居住權(quán)，筆者認(rèn)為未來應(yīng)探索建立農(nóng)村宅基地差別化有償使用制度。具體而言，一方面針對(duì)農(nóng)村集體經(jīng)濟(jì)組織成員，要堅(jiān)持首次申請(qǐng)無償取得、福利分配制度，即延續(xù)當(dāng)前以“一戶一宅”“面積控制”為特征的初次無償分配、永久使用宅基地制度，繼續(xù)發(fā)揮宅基地使用權(quán)的保障功能，但若其宅基地使用面積超過地方規(guī)定標(biāo)準(zhǔn)，則需要繳納超額使用費(fèi)。另一方面，城鎮(zhèn)居民或非本集體經(jīng)濟(jì)組織成員因買賣農(nóng)村房屋而使用農(nóng)村宅基地的，可以認(rèn)為買方與房屋所在的集體之間建立了土地租賃關(guān)系，也應(yīng)向集體經(jīng)濟(jì)組織繳納宅基地有償使用費(fèi)。

輸出：最佳信任路徑集合PATH

算法過程：

(1) EnQueue(Q,Tn); (2) For i in range(N): (3)If Q.front==Q.rear (4) return error; (5)DeQueue(Q,e); (6) ptp(Sn,e) /*ptp()用來查找得到節(jié)點(diǎn)e和Sn間的所有路徑*/ (7) path←e; /*path存放已構(gòu)路徑,e為路徑的起點(diǎn)*/ (8) R←[path, Sn]; /*R存放節(jié)點(diǎn)e和Sn之間的所有路徑*/ (9) P=0; /*算法開始定義節(jié)點(diǎn)間路徑數(shù)量為0*/ (10) ADJ←getadj(adj,getLast(path)); /*將已構(gòu)建路徑最后節(jié)點(diǎn)的鄰居adj放入ADJ中*/ (11) For each adj in ADJ (12) if adj∈getadj(Sn) then /*若adj不屬于終止節(jié)點(diǎn)的鄰居節(jié)點(diǎn)則將adj加入當(dāng)前路徑*/ (13) add(adj,path); (14) ptp(Sn,adj); (15) else /*否則當(dāng)前路徑將作為節(jié)點(diǎn)間的路徑*/ (16) add(adj,path); (17) P++; (18) R←[Sn,path]; (19) End For (20) While P /*篩選R中路徑得到最佳信任路徑*/ (21) if (RL>ARL&&RL-ARL≤ (22) β &&RVT≥AVT) (23) PATH←[Sn,R[p]]; (24) else if (RVT

通過動(dòng)態(tài)規(guī)劃求最短路徑的思想確定BTP算法中的β、γ值，動(dòng)態(tài)規(guī)劃的思想解決的最基本的一個(gè)問題就是：尋找有向無環(huán)圖(籬笆網(wǎng)絡(luò))當(dāng)中兩個(gè)點(diǎn)之間的最短路徑，也就是各邊上權(quán)值之和最小的路徑。所以，先將有著相同終止節(jié)點(diǎn)的路徑上的信任值取倒數(shù)，這樣得到的“最短路徑(SP)”其實(shí)就是信任值最高的路徑。β,γ的值定義為

β=|getLength(SP)-ARL|

(4)

γ=|getValue(SP)-AVT|

(5)

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

在5個(gè)真實(shí)數(shù)據(jù)集上實(shí)驗(yàn)驗(yàn)證BTP算法的有效性。

3.1 評(píng)估數(shù)據(jù)集

實(shí)驗(yàn)數(shù)據(jù)集包括：DVD類別數(shù)據(jù)集CiaoDVD、電影推薦網(wǎng)站FilmTrust、豆瓣電影數(shù)據(jù)集Douban Movie、Yelp商業(yè)數(shù)據(jù)集以及社會(huì)化電子商務(wù)網(wǎng)站Epinions。數(shù)據(jù)集均包含了用戶對(duì)項(xiàng)目的評(píng)分信息和用戶之間的信任信息。數(shù)據(jù)集的基本特征信息見表1，其中Dataset(Density)字段記錄了數(shù)據(jù)集名稱及其稀疏度，Relations表明了該數(shù)據(jù)集中的對(duì)象類型以及其交互類型，Number of A和Number of B分別對(duì)應(yīng)于Relations字段的前后交互對(duì)象的數(shù)目，而Number of (A-B)表示該交互關(guān)系的交互歷史記錄數(shù)。

表1 數(shù)據(jù)集的統(tǒng)計(jì)特征

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

盡管用戶訪問推薦的某一刻，其興趣是單一的，但用戶往往具有廣泛的興趣，推薦列表的多樣性將會(huì)增加用戶找到更多興趣項(xiàng)目的概率。而給用戶推薦其以前未聽說的物品，即新穎的推薦，有助于發(fā)掘長(zhǎng)尾商品和商家的項(xiàng)目推廣。預(yù)測(cè)準(zhǔn)確率和召回率是度量一個(gè)推薦系統(tǒng)或者推薦算法預(yù)測(cè)用戶行為的能力，是最重要的推薦系統(tǒng)離線評(píng)測(cè)指標(biāo)。因此，實(shí)驗(yàn)從多樣性、新穎性和準(zhǔn)確率召回率3個(gè)方面進(jìn)行了算法性能評(píng)價(jià)。對(duì)比算法如下：

Shikhar Sharma等提出的廣義復(fù)用網(wǎng)絡(luò)的鏈路預(yù)測(cè)算法[19]：封裝了各種異構(gòu)關(guān)系，通過層與層之間的似然度量給出鏈路預(yù)測(cè)結(jié)果。

UniWalk：XiongCai Luo等提出基于monte carlo的方法UniWalk[20]，以實(shí)現(xiàn)對(duì)大型圖的快速top-kSimRank計(jì)算。

由于每個(gè)數(shù)據(jù)集的稀疏差異，分別設(shè)置不同的實(shí)驗(yàn)比率并根據(jù)數(shù)據(jù)量隨機(jī)生成N個(gè)評(píng)估集，把結(jié)果取平均值作為最后的表現(xiàn)，其中test項(xiàng)為目標(biāo)用戶的歷史行為數(shù)據(jù)。數(shù)據(jù)集CiaoDVD、Yelp和DoubanMovie包含了項(xiàng)目的類型信息，因此對(duì)這3個(gè)數(shù)據(jù)集實(shí)驗(yàn)進(jìn)行推薦的多樣性和新穎性評(píng)估。將Ciao DVD數(shù)據(jù)集隨機(jī)分成10個(gè)評(píng)估集，分別隨機(jī)抽取20%的DoubanMovie和Yelp數(shù)據(jù)隨機(jī)生成10個(gè)評(píng)估集。實(shí)驗(yàn)結(jié)果如下。

3.2.1 推薦的多樣性評(píng)估

推薦多樣性要求推薦列表覆蓋用戶不同的興趣領(lǐng)域的同時(shí)能夠滿足用戶的主要興趣。為了對(duì)算法推薦的多樣性進(jìn)行評(píng)估，我們記錄實(shí)驗(yàn)推薦的項(xiàng)目類型以及每種類型的數(shù)量，并與目標(biāo)用戶的歷史項(xiàng)目類型、數(shù)量進(jìn)行比較。實(shí)驗(yàn)結(jié)果如圖3～圖5所示。

圖3 CiaoDVD數(shù)據(jù)集的推薦多樣性評(píng)估

圖4 Douban Movie 數(shù)據(jù)集的推薦多樣性評(píng)估

圖5 Yelp數(shù)據(jù)集的推薦多樣性評(píng)估

實(shí)驗(yàn)結(jié)果發(fā)現(xiàn)，3種算法的推薦列表中既包含與目標(biāo)用戶歷史興趣相似的項(xiàng)目又含有目標(biāo)用戶未涉及的項(xiàng)目。Link-Pre算法和UniWalk算法僅依據(jù)用戶社交網(wǎng)絡(luò)的歷史交互記錄，沒有考慮用戶以及項(xiàng)目節(jié)點(diǎn)之間的權(quán)值信息，使得推薦結(jié)果更加趨近于目標(biāo)用戶的歷史興趣。但BTP算法較其它兩種算法推薦涉及的項(xiàng)目類型更豐富，而且考慮到了用戶的主要興趣。

實(shí)驗(yàn)結(jié)果表明，Link-Pre算法因?yàn)檫^于依賴用戶歷史記錄導(dǎo)致去除與目標(biāo)用戶相同或相似歷史項(xiàng)目后出現(xiàn)無推薦項(xiàng)目的情況，與BTP算法相比，雖然會(huì)出現(xiàn)UniWalk和Link-Pre的推薦新穎性優(yōu)于BTP算法的情況，但推薦的多樣性較差。

3.2.2 推薦的新穎性評(píng)估

新穎的推薦是指給用戶推薦那些他們以前沒有聽說過的物品，而且越不熱門的物品越可能讓用戶覺得新穎。因此，如果推薦結(jié)果中物品的平均熱門程度較低，那么推薦結(jié)果就可能有比較高的新穎性。在將目標(biāo)用戶之前在網(wǎng)站中對(duì)其有過行為的物品從推薦列表中過濾掉的基礎(chǔ)上，利用推薦結(jié)果的平均流行度進(jìn)行推薦新穎性評(píng)估。實(shí)驗(yàn)結(jié)果如表2所示為Douban Movie數(shù)據(jù)集中編號(hào)為“288”的用戶的推薦新穎性評(píng)估結(jié)果。其中，新穎性評(píng)估公式為

表2 推薦的新穎性評(píng)估數(shù)據(jù)

(6)

式中：Pop代表項(xiàng)目在當(dāng)前數(shù)據(jù)中的用戶熱度(即被使用過的記錄條數(shù))，Rec(U)表示推薦列表，Test(U)表示目標(biāo)用戶的歷史項(xiàng)目集合，SimTest(U)表示與目標(biāo)用戶歷史項(xiàng)目相似的項(xiàng)目集合，N表示去掉Test(U)和SimTest(U)的項(xiàng)目個(gè)數(shù)。

3.2.3 推薦的準(zhǔn)確率召回率

準(zhǔn)確率和召回率是度量一個(gè)推薦系統(tǒng)或者推薦算法預(yù)測(cè)用戶行為的能力的重要指標(biāo)，圖6～圖10展示了在5個(gè)不同數(shù)據(jù)集上各個(gè)算法的召回率和準(zhǔn)確率分布。

圖6 Douban Movie數(shù)據(jù)集的召回率和準(zhǔn)確率分布

由實(shí)驗(yàn)結(jié)果可以觀察到，進(jìn)行對(duì)比的3種算法的準(zhǔn)確率和召回率是交織在一起的，并且同數(shù)據(jù)的稀疏程度有關(guān)。Link-Pre算法的準(zhǔn)確率和召回率在Yelp、CiaoDVD和Epinion數(shù)據(jù)集中表現(xiàn)較好，因其僅依賴于用戶與項(xiàng)目的歷史記錄將數(shù)據(jù)分層進(jìn)行鏈路預(yù)測(cè)生成推薦，數(shù)據(jù)稀疏時(shí)，層與層之間會(huì)出現(xiàn)較多的缺失鏈路使推薦準(zhǔn)確率和召回率較高。反之，數(shù)據(jù)層之間缺失信息較少導(dǎo)致無鏈接預(yù)測(cè)，就會(huì)造成準(zhǔn)確率和召回率為0。UniWalk算法在FilmTrust和Douban Movie數(shù)據(jù)集中的準(zhǔn)確率和召回率較好是因?yàn)樵摓榕c歷史記錄相似的項(xiàng)目，準(zhǔn)確和召回率較高，反之，準(zhǔn)確率和召回率較低。BTP算法的準(zhǔn)確率和召回率在5個(gè)數(shù)據(jù)集中分布較居中，這主要是因?yàn)锽TP算法利用節(jié)點(diǎn)間的異質(zhì)信息進(jìn)行推薦，不同于以上兩種算法，BTP算法考慮了用戶對(duì)項(xiàng)目的評(píng)分信息和用戶間的信任信息改善了數(shù)據(jù)稀疏情況下的冷啟動(dòng)問題，使得算法推薦既注重用戶歷史興趣，又能幫助用戶挖掘潛在興趣，因此不論數(shù)據(jù)是否稀疏，推薦的準(zhǔn)確率和召回率都亞于其它算法。

圖7 Yelp數(shù)據(jù)集的召回率和準(zhǔn)確率分布

圖8 FilmTrust數(shù)據(jù)集的召回率和準(zhǔn)確率分布

圖9 CiaoDVD數(shù)據(jù)集的召回率和準(zhǔn)確率分布

圖10 Epinions數(shù)據(jù)集的召回率和準(zhǔn)確率分布

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

在線社交網(wǎng)絡(luò)日益龐大而復(fù)雜，傳統(tǒng)基于強(qiáng)關(guān)系的信息過濾方式，往往注重“人脈”，導(dǎo)致推薦結(jié)果單一且毫無新意。融合由信任關(guān)系信息產(chǎn)生的用戶間的信任度構(gòu)建目標(biāo)用戶所處的異質(zhì)社交網(wǎng)絡(luò)，再綜合目標(biāo)用戶自身的偏好和異質(zhì)網(wǎng)絡(luò)中其余節(jié)點(diǎn)的影響力生成推薦，為推薦研究提供了新思路。當(dāng)然，異質(zhì)信息推薦算法仍有繼續(xù)研究和探索的空間，如考慮異質(zhì)網(wǎng)絡(luò)中相同以及不同請(qǐng)求長(zhǎng)度下節(jié)點(diǎn)間的推薦影響，時(shí)間因素下節(jié)點(diǎn)間關(guān)系動(dòng)態(tài)更新模型、融入社會(huì)網(wǎng)絡(luò)中的上下文信息、探索用戶間不信任關(guān)系對(duì)推薦產(chǎn)生的作用等。