一種基于用戶信任網(wǎng)絡(luò)的物質(zhì)擴(kuò)散推薦算法

梁 藝，韓立新

(河海大學(xué)計(jì)算機(jī)與信息學(xué)院,江蘇 南京 211100)

0 引 言

基于集體智慧及合作共享的Web2.0的出現(xiàn)及迅速發(fā)展，極大豐富了社交網(wǎng)絡(luò)，基于標(biāo)簽的社會(huì)化標(biāo)注系統(tǒng)為越來越多社區(qū)網(wǎng)站所采用,例如圖片標(biāo)注網(wǎng)站Filckr、代碼標(biāo)注網(wǎng)站SourceForge、網(wǎng)站連接標(biāo)注網(wǎng)站Delicious等。在其上，用戶可以用簡(jiǎn)短的標(biāo)簽對(duì)目標(biāo)資源進(jìn)行主觀評(píng)價(jià)。標(biāo)簽由用戶主動(dòng)標(biāo)注，反映了用戶的偏好，非常適合對(duì)用戶的興趣進(jìn)行建模。同時(shí)標(biāo)簽本身的語義信息也很好地反映了資源本身的屬性與內(nèi)容。因此如何充分利用標(biāo)簽標(biāo)注信息，成為推薦系統(tǒng)的研究熱點(diǎn)之一。

傳統(tǒng)推薦系統(tǒng)構(gòu)建資源模型時(shí)，往往僅僅基于所有用戶的選擇歷史，假定各個(gè)用戶都是獨(dú)立且沒有聯(lián)系，未能充分考慮用戶之間的信任關(guān)系，并且由于新資源沒有充分地被選擇歷史，存在冷啟動(dòng)及稀疏性問題。因此基于社會(huì)化標(biāo)注網(wǎng)站中標(biāo)簽在用戶之間的共現(xiàn)現(xiàn)象，本文設(shè)計(jì)一種信任網(wǎng)絡(luò)，以期利用標(biāo)簽信息充分挖掘用戶之間的信任關(guān)系，優(yōu)化基于用戶的資源模型。在此基礎(chǔ)上，設(shè)計(jì)基于資源相似性及用戶標(biāo)注記錄的資源-資源-標(biāo)簽三部圖，在其上執(zhí)行物質(zhì)擴(kuò)散算法，得出推薦結(jié)果。

1 相關(guān)工作

1.1 信任網(wǎng)絡(luò)

Golbeck[1]對(duì)信任給出了如下定義：如果用戶A認(rèn)為根據(jù)用戶B的行為進(jìn)行決策將會(huì)產(chǎn)生積極意義，則A信任B。而信任網(wǎng)絡(luò)則由各個(gè)用戶之間的信任關(guān)系構(gòu)建而成，刻畫用戶之間的信任程度。使用信任信息可以緩解傳統(tǒng)CF推薦算法中的數(shù)據(jù)稀疏性問題[2]。自FaceBook為代表的社交網(wǎng)絡(luò)興起以來，用戶在網(wǎng)上諸如關(guān)注、評(píng)論、注釋這樣的行為與表現(xiàn)日益豐富，眾多研究者均開始借助用戶的主動(dòng)標(biāo)注信息提取用戶之間的信任關(guān)系，進(jìn)而優(yōu)化原算法。Kim等人[3]基于標(biāo)簽共現(xiàn)，利用KL散度來衡量用戶信任關(guān)系，改進(jìn)了傳統(tǒng)直接利用標(biāo)簽共現(xiàn)衡量用戶信任度的方法。Bhuiyan等人[4]將用戶標(biāo)簽信息與資源文本描述信息結(jié)合起來以提取用戶信任關(guān)系。Norwati等人[5]在文獻(xiàn)[4]的基礎(chǔ)上混合了Golbeck[6]提出的Tidal Trust方法，更準(zhǔn)確地衡量了用戶信任度。

以往基于標(biāo)簽衡量用戶信任的推薦方法一般直接用于優(yōu)化或替代CF中的第一步，即尋找相似用戶。本文則將用戶信任信息用于對(duì)基于用戶的資源模型進(jìn)行更新優(yōu)化。

1.2 物質(zhì)擴(kuò)散推薦算法

基于物質(zhì)擴(kuò)散的推薦算法最早由Zhou等人[7]提出，將用戶與項(xiàng)目都抽象成一個(gè)節(jié)點(diǎn)，根據(jù)歷史選擇記錄組成用戶-資源二部圖，并認(rèn)為用戶已選擇的資源擁有可以稱之為能量的推薦能力。當(dāng)需要向一位用戶生成推薦時(shí)，即從用戶已選擇的資源開始經(jīng)過資源到用戶及用戶到資源2次擴(kuò)散，將能量擴(kuò)散至其他資源，對(duì)最終用戶尚未選擇的資源能量進(jìn)行排序，即可得出最終推薦結(jié)果。賈春曉[8]證明了在不同的推薦列表長(zhǎng)度時(shí)，基于物質(zhì)擴(kuò)散的二分網(wǎng)絡(luò)推薦算法的命中率和排序分均優(yōu)于協(xié)同推薦算法。

近年來，學(xué)者們紛紛對(duì)物質(zhì)擴(kuò)散推薦算法進(jìn)行了改進(jìn)。Zhang等人[9]建立了用戶-資源-標(biāo)簽三部圖，以用戶已選擇資源作為能量源，通過將經(jīng)標(biāo)簽與用戶擴(kuò)散返回的能量進(jìn)行加權(quán)融合，得出最后推薦結(jié)果。張新猛等人[10]認(rèn)為資源本身的文本內(nèi)容反映用戶的偏好，將其融合到物質(zhì)擴(kuò)散推薦算法中，提高了結(jié)果。文獻(xiàn)[11-12]同時(shí)將未選擇資源向已選擇資源的擴(kuò)散考慮進(jìn)來，并對(duì)熱門商品進(jìn)行了懲罰，優(yōu)化了原算法。通過對(duì)比以往基于二部圖的優(yōu)化方法發(fā)現(xiàn)，其僅僅從優(yōu)化初始能量分配[13]、能量擴(kuò)散分配比例[14]等方面入手,而沒有更深入地試圖優(yōu)化二部圖的結(jié)構(gòu)。在本文中，區(qū)別于以往稀疏的二部圖，根據(jù)資源之間的相似性建立了資源-資源完全二部圖，并與資源-標(biāo)簽二部圖合并，組成資源-資源-標(biāo)簽三部圖作為執(zhí)行物質(zhì)擴(kuò)散算法的基礎(chǔ)。

2 基于用戶信任網(wǎng)絡(luò)的物質(zhì)擴(kuò)散推薦算法(UTNDR)

傳統(tǒng)基于用戶的資源模型通常沒有考慮用戶之間的信任關(guān)系，因此本算法要解決的問題有2個(gè)：1)如何構(gòu)建基于用戶信任網(wǎng)絡(luò)的資源模型；2)如何將資源模型與物質(zhì)擴(kuò)散推薦算法結(jié)合起來進(jìn)行推薦。

本文算法的具體流程概括如下:

步驟1構(gòu)建用戶信任網(wǎng)絡(luò)。

步驟2基于用戶信任網(wǎng)絡(luò)，構(gòu)建基于用戶的資源模型。

步驟3計(jì)算資源相似度，組成資源-資源完全二部圖。

步驟4將資源-資源二部圖與資源-標(biāo)簽二部圖合并，組成資源-資源-標(biāo)簽三部圖。

步驟5針對(duì)每一名用戶，在資源-資源-標(biāo)簽三部圖上執(zhí)行物質(zhì)擴(kuò)散算法，得到推薦結(jié)果。

2.1 符號(hào)定義

符號(hào)定義見表1。

表1 符號(hào)定義

符號(hào)說明U用戶集R資源集T標(biāo)簽集p用戶數(shù)量q資源數(shù)量o標(biāo)簽數(shù)量

2.2 具體算法流程

2.2.1 構(gòu)建用戶信任網(wǎng)絡(luò)

如圖1所示，社會(huì)化標(biāo)注系統(tǒng)中的標(biāo)注信息可以由用戶-標(biāo)簽-資源三部圖展現(xiàn)。標(biāo)簽反映用戶的偏好與興趣，如果2名用戶曾使用了同一個(gè)標(biāo)簽，則認(rèn)為他們有一定聯(lián)系且有一定互信任度。如此，將這種基于標(biāo)簽共現(xiàn)的聯(lián)系表示為信任網(wǎng)絡(luò)中連接這2名用戶的一條邊，考慮到所有的標(biāo)簽共現(xiàn)，就組成了信任網(wǎng)絡(luò)。據(jù)此，圖1中所有用戶的信任網(wǎng)絡(luò)如圖2所示。

圖1 用戶-標(biāo)簽-資源三部圖

圖2 用戶信任網(wǎng)絡(luò)

因此，信任網(wǎng)絡(luò)可以定義為：

G={U，E}

(1)

其中U表示所有用戶節(jié)點(diǎn)，E為G中邊集，記錄用戶之間的所有信任聯(lián)系。

E中任意一條邊eij定義為：

eij={Ui,Uj,trij}

其中trij為Ui與Uj之間的信任度值，即Ui與Uj共同使用過的標(biāo)簽數(shù)量。例如圖1中U3與U5都曾使用過標(biāo)簽t2,t3,則其信任度為2。

2.2.2 構(gòu)建基于用戶的資源模型

2.2.2.1 基于TF-IDF的初始資源模型

將不同用戶的活躍度差異考慮進(jìn)來，基于搜索引擎中經(jīng)典的TF-IDF來建立初始資源模型，以減少過于活躍的用戶對(duì)模型的影響。

Profile(rj)={w1j,w2j,w3j,…,wpj}

(2)

其中，wij=tfij×idfij，tfij定義為ui對(duì)rj的標(biāo)記次數(shù)與ui對(duì)所有資源的最高標(biāo)注次數(shù)之比：

(3)

idfij定義為ui對(duì)所有資源的標(biāo)注次數(shù)之和與對(duì)rj的標(biāo)注次數(shù)之比的對(duì)數(shù)：

(4)

2.2.2.2 利用用戶信任網(wǎng)絡(luò)優(yōu)化資源模型

初始資源模型沒有考慮用戶之間的信任關(guān)系。這里在用戶信任網(wǎng)絡(luò)中使用基于隨機(jī)游走的PageRank算法對(duì)資源模型進(jìn)行更新優(yōu)化。

基于PageRank模型，漫步者以初始資源模型中非零用戶節(jié)點(diǎn)為起點(diǎn)根據(jù)與相鄰節(jié)點(diǎn)間邊的權(quán)重隨機(jī)地漫步至相鄰節(jié)點(diǎn)，并將自身權(quán)重傳播至相鄰節(jié)點(diǎn)，則由當(dāng)前用戶節(jié)點(diǎn)Ui游走至其一個(gè)相鄰用戶節(jié)點(diǎn)Uj的概率為：

(5)

其中，n(i)表示Ui的相鄰節(jié)點(diǎn)，trij表示用戶Ui與Uj之間的信任度。

使用PRi(k)來表示第k次迭代后用戶Ui節(jié)點(diǎn)的權(quán)重，由式(5)則有下式：

PRi(k)=d∑j∈n(i)ajiPRj(k-1)+(1-d)PRi(0)

(6)

其中，PRi(0)表示用戶Ui節(jié)點(diǎn)的初始權(quán)重，d為阻尼參數(shù)，控制節(jié)點(diǎn)從相鄰節(jié)點(diǎn)接收權(quán)重的比例。

最終，PageRank算法迭代一定次數(shù)后，所有用戶節(jié)點(diǎn)的權(quán)值會(huì)收斂至一定值，即為其最終權(quán)重。

2.2.3 計(jì)算資源相似度，組成資源-資源完全二部圖

采用經(jīng)典的余弦相似性分別兩兩計(jì)算資源間的相似性：

(7)

基于式(7)計(jì)算的相似性值，生成資源-資源二部圖。這里的二部圖為一完全二部圖，即左邊集合的任一頂點(diǎn)與右邊集合的任意頂點(diǎn)間均有連接，其權(quán)值為相似性值。

2.2.4 將資源-資源二部圖與資源-標(biāo)簽二部圖合并，組成資源-資源-標(biāo)簽三部圖

從圖1所示的用戶-標(biāo)簽-資源三部圖提取出資源-標(biāo)簽二部子圖。并與2.2.3節(jié)中所得的資源-資源完全二部圖合并，可得資源-資源-標(biāo)簽三部圖。將初始的無向邊替換為有向邊，以表示物質(zhì)擴(kuò)散算法中能量的傳輸方向。如圖3所示。

圖3 資源-資源-標(biāo)簽三部圖

2.2.5 在資源-資源-標(biāo)簽三部圖上執(zhí)行物質(zhì)擴(kuò)散算法，得到推薦結(jié)果

現(xiàn)為一用戶ui推薦資源，根據(jù)ui以往的標(biāo)注歷史可以得到初始能量分布為：

v(ui)=(uri1,uri2,…,uriq,uti1,uti2,…,utio)

(8)

其中元素值為ui對(duì)各個(gè)資源的標(biāo)注次數(shù)或標(biāo)簽的使用次數(shù)。

與傳統(tǒng)物質(zhì)擴(kuò)散推薦算法需要進(jìn)行2次往返擴(kuò)散過程不同，本文提出的算法這一部分只需進(jìn)行一次擴(kuò)散，即同時(shí)進(jìn)行資源->資源，標(biāo)簽->資源的一次性擴(kuò)散。

其中資源rj到ri的擴(kuò)散效率RSij為：

(9)

標(biāo)簽tj到ri的擴(kuò)散效率TSij為：

(10)

通過對(duì)最終資源的能量值排序，就可得到最終的推薦結(jié)果。這一過程可以向量化表示為：

e(ui)=Mv(ui)

(11)

其中：

(12)

e(ui)=(eri1,eri2,…,eriq)表示一次模擬擴(kuò)散后各個(gè)資源的能量值。對(duì)最終各個(gè)資源的能量值進(jìn)行排序后，即可得到針對(duì)用戶ui的最終推薦結(jié)果。

2.3 相關(guān)工作比較

在眾多推薦算法中，構(gòu)建資源模型是一重要的步驟。以往推薦系統(tǒng)構(gòu)建資源模型時(shí)，往往僅僅基于評(píng)分矩陣[15]或其為所有用戶的01選擇歷史[7]，假定各個(gè)用戶都是獨(dú)立而沒有聯(lián)系，未能充分考慮用戶之間的信任關(guān)系。標(biāo)簽反映用戶的偏好與興趣，眾多算法都將標(biāo)簽信息融入到原有算法中，提高了推薦結(jié)果[9,15]，但其一般僅將由資源-標(biāo)簽關(guān)系獲得的推薦結(jié)果與原來由資源-用戶關(guān)系獲得的推薦結(jié)果進(jìn)行一定的加權(quán)融合，未能從用戶信任關(guān)系角度出發(fā)，更深地挖掘用戶興趣關(guān)聯(lián)。因此本文從優(yōu)化資源模型角度出發(fā)，基于標(biāo)簽共現(xiàn)現(xiàn)象建立了用戶信任網(wǎng)絡(luò)，將標(biāo)注信息轉(zhuǎn)化為用戶互信任信息，對(duì)資源模型進(jìn)行了更新優(yōu)化，并配合改進(jìn)的物質(zhì)擴(kuò)散算法以提升推薦結(jié)果。

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

3.1 實(shí)驗(yàn)數(shù)據(jù)

提供標(biāo)注服務(wù)的社區(qū)網(wǎng)站有很多，本文采用MovieLens和Delicious的數(shù)據(jù)，以及采用文獻(xiàn)[15]中的p-core方法使實(shí)驗(yàn)數(shù)據(jù)較為稠密，以更好地驗(yàn)證所提模型的有效性。具體操作為，過濾掉MovieLens數(shù)據(jù)集中出現(xiàn)次數(shù)少于5次及Delicious數(shù)據(jù)集中出現(xiàn)次數(shù)少于20次的所有標(biāo)簽、用戶及資源種類。過濾數(shù)據(jù)后2數(shù)據(jù)集的詳細(xì)分布信息如表2所示。

表2 數(shù)據(jù)詳細(xì)信息

數(shù)據(jù)集標(biāo)注數(shù)目用戶數(shù)目資源數(shù)目標(biāo)簽數(shù)目MovieLens3533681924452309Delicious7207887665156125746

表2中標(biāo)注數(shù)目是標(biāo)注行為的總發(fā)生數(shù)目。

3.2 評(píng)估標(biāo)準(zhǔn)

采用最經(jīng)典的精確率、召回率以及F值來評(píng)估算法。對(duì)于每一個(gè)用戶，從其歷史標(biāo)注信息中提取其所有標(biāo)注過的資源，記為Rh，然后根據(jù)算法得出規(guī)模為k的推薦結(jié)果集Ru。

精確率用于衡量推薦結(jié)果集中有多少為用戶真實(shí)選擇，計(jì)算公式為：

(13)

召回率表示用戶真實(shí)選擇的資源有多少為推薦算法所命中，計(jì)算公式為：

(14)

精確率和召回率指標(biāo)有時(shí)候會(huì)出現(xiàn)矛盾的情況，F(xiàn)值可以綜合考慮他們，其計(jì)算公式為：

這里取α為1，即F1值。

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

本文選擇Gemmell等人[15]提出的一種基于標(biāo)注數(shù)據(jù)的線性加權(quán)混合方法(LHCF)及Zhang等人[9]提出的基于三部圖的物質(zhì)擴(kuò)散推薦算法(IDTG)與本文提出的基于用戶信任網(wǎng)絡(luò)的物質(zhì)擴(kuò)散推薦算法(UTNDR)進(jìn)行比較。Gemmell等人創(chuàng)造性地將用戶-資源-標(biāo)簽三維信息降維提取出用戶-資源、用戶-標(biāo)簽、資源-標(biāo)簽信息，并在其上分別應(yīng)用經(jīng)過改進(jìn)適應(yīng)的CF算法，得出各自的推薦結(jié)果，最后利用梯度下降法在訓(xùn)練集上訓(xùn)練出各自最好的權(quán)重系數(shù)，進(jìn)而得出最終的推薦結(jié)果。Zhang等人建立了用戶-資源-標(biāo)簽三部圖，將經(jīng)標(biāo)簽與用戶擴(kuò)散返回的能量進(jìn)行線性加權(quán)融合，得出最后推薦結(jié)果。

在具體試驗(yàn)中，采用交叉驗(yàn)證法，取10次平均結(jié)果作為最終結(jié)果。每一次隨機(jī)選取70%的數(shù)據(jù)作為訓(xùn)練集，剩余30%作為測(cè)試集，訓(xùn)練完模型后，選取測(cè)試集中的50%用來生成推薦，剩余50%用來與推薦結(jié)果作比較，計(jì)算得出精確率及召回率。

在資源推薦目標(biāo)數(shù)量k取不同值時(shí)，在2數(shù)據(jù)集上的精確率比較結(jié)果如圖4及圖5所示。

圖4 Delicious精確率比較結(jié)果

圖5 MovieLens精確率比較結(jié)果

2數(shù)據(jù)集上召回率比較結(jié)果如圖6及圖7所示。

圖6 Delicious召回率比較結(jié)果

圖7 MovieLens召回率比較結(jié)果

2個(gè)數(shù)據(jù)集上F1值比較結(jié)果如表3及表4所示。

表3 Delicious F1值比較結(jié)果/%

151015202530UTNDR3．076．157．377．737．737．587．37LHCF2．794．945．305．625．645．655．56IDTG3．135．546．546．836．987．016．90

表4 MovieLens F1值比較結(jié)果/%

151015202530UTNDR8．3912．9413．2512．2311．1110．049．07LHCF6．2110．8110．589．689．048．217．50IDTG7．0311．7511．8610．959．939．278．29

以上最佳結(jié)果Delicious數(shù)據(jù)集于阻尼參數(shù)d為0.45時(shí)取得，MovieLens則在d取0.2時(shí)取得。對(duì)比結(jié)果，可以發(fā)現(xiàn)，本文提出的算法無論是在Delicious數(shù)據(jù)集上，還是Movielens數(shù)據(jù)集上，精確率、召回率及F1值均整體優(yōu)于對(duì)比算法，證明了本文算法的優(yōu)越性。

4 結(jié)束語

本文針對(duì)傳統(tǒng)基于用戶的資源模型沒有考慮用戶信任的不足，提出基于標(biāo)簽共現(xiàn)構(gòu)建的用戶信任網(wǎng)絡(luò)模型，通過PageRank算法對(duì)資源模型進(jìn)行了修正優(yōu)化，充分將用戶對(duì)資源的直接標(biāo)注頻率以及用戶互信任信息相結(jié)合。進(jìn)而基于修正優(yōu)化后的資源模型，計(jì)算資源彼此的相似度，生成資源-資源完全二部圖，并與資源-標(biāo)簽二部圖合并，組成資源-資源-標(biāo)簽三部圖。最終通過在三部圖上執(zhí)行物質(zhì)擴(kuò)散算法，得出最終結(jié)果。通過對(duì)比分析本文算法與對(duì)比算法在2大數(shù)據(jù)集上的基于精確率、召回率及F1值的表現(xiàn)，本文的算法較好地提升了推薦效果。下一步，將嘗試基于用戶信任網(wǎng)絡(luò)，從用戶社團(tuán)劃分及興趣遷移等方面入手，更好地建立用戶及資源模型，進(jìn)一步提升推薦結(jié)果。

[1] Golbeck J. Computing and Applying Trust in Web-based Social Networks[D]. Park:University of Maryland, 2005.

[2] Massa P, Bhattacharjee B. Using trust in recommender systems: An experimental analysis[C]// International Conference on Trust Management. 2004:221-235.

[3] Kim H, Kim H J. Improving recommendation based on implicit trust relationships from tags[C]// Proceedings of the 2nd International Conference on Computers, Networks, Systems, and Industrial Applications. 2012:25-30.

[4] Bhuiyan T, Xu Yue, Josang A, et al. Developing trust networks based on user tagging information for recommendation making[C]// International Conference on Web Information Systems Engineering. 2010:357-364.

[5] Mustapha N, Voon W P, Sulaiman N.User recommendation algorithm in social tagging system based on hybrid user trust[J]. Journal of Computer Science, 2013,9(8):1008-1018.

[6] Golbeck J. Generating predictive movie recommendations from trust in social networks[C]// International Conference on Trust Management. 2006:93-104.

[7] Zhou Tao, Ren Jie, Medo M, et al. Bipartite network projection and personal recommendation[J]. Physical Review E: Statistical, Nonlinear, and Soft Matter Physics, 2007,76(4):70-80.

[8] 賈春曉. 基于復(fù)雜網(wǎng)絡(luò)的推薦算法和合作行為研究[D]. 合肥:中國(guó)科學(xué)技術(shù)大學(xué), 2011.

[9] Zhang Zike, Zhou Tao, Zhang Yicheng. Personalized recommendation via integrated diffusion on user-item-tag tripartite graphs[J]. Physica A: Statistical Mechanics and Its Applications, 2010,389(1):179-186.

[10] 張新猛,蔣盛益,張倩生,等. 基于用戶偏好加權(quán)的混合網(wǎng)絡(luò)推薦算法[J]. 山東大學(xué)學(xué)報(bào)(理學(xué)版), 2015,50(9):29-35

[11] Chen Guilin, Gao Tianruan, Zhu Xuzhen, et al. Personalized recommendation based on preferential bidirectional mass diffusion[J]. Physica A: Statistical Mechanics and Its Applications, 2017,469:397-404.

[12] Zhu Xuezhen, Tian Hui, Zhang Ping, et al. Personalized recommendation based on unbiased consistence[J]. EPL (Europhysics Letters), 2015,111(4):48007-1-48007-6.

[13] Zhou Tao, Jiang Luoluo, Su Riqi, et al. Effect of initial configuration on network-based recommendation[J]. EPL (Europhysics Letters), 2008,81(5):58004-1-58004-5.

[14] Sarwar B, Karypis G, Konstan J, et al. Item-based collaborative filtering recommendation algorithms[C]// Proceedings of the 10th International Conference on World Wide Web. 2001:285-295.

[15] Gemmell J, Schimoler T, Mobasher B, et al. Resource recommendation in social annotation systems: A linear-weighted hybrid approach[J]. Journal of Computer and System Sciences, 2012,78(4):1160-1174.