基于聯(lián)合復(fù)雜網(wǎng)絡(luò)Cn-RippleNet模型的推薦方法

羅宇泰, 徐濤, 徐章博

(西北民族大學(xué) 中國民族語言文字信息技術(shù)教育部重點實驗室, 甘肅 蘭州 730030)

傳統(tǒng)的推薦系統(tǒng)方法有基于協(xié)同過濾,通過分析用戶的歷史交互數(shù)據(jù),猜測他們可能的共同愛好[1]。但是該方法有著冷啟動和稀疏矩陣的問題。研究人員提出了許多解決方法,譬如結(jié)合知識圖譜、社會網(wǎng)絡(luò)[2],通過融合側(cè)面信息到矩陣中填補一定的數(shù)據(jù)空缺,但還是有較大的局限性。

在推薦系統(tǒng)中,基于知識圖譜的推薦方法有基于嵌入的方法和基于路徑的方法。2016年Zhang等人提出了協(xié)同知識庫嵌入(CKE)方法,他將協(xié)同過濾模型與嵌入結(jié)合[3]。2018年Wang等人提出的深度知識感知網(wǎng)絡(luò)(DKN),他將實體嵌入和詞嵌入分為2個不同的頻道,設(shè)計1個CNN模型將其結(jié)合[4]。2014年Yu等人提出了異構(gòu)信息網(wǎng)絡(luò)方法[5],2017年Zhao等人提出了基于元圖的推薦方法[6]。兩者都是通過創(chuàng)建異構(gòu)信息網(wǎng)絡(luò),基于網(wǎng)絡(luò)的潛在特征,從中抽取元路徑或者元圖,來代表用戶和項目之間的關(guān)系。Wang等人同時結(jié)合基于嵌入和路徑的方法提出了RippleNet[7]。Wang模擬水波紋傳播方式,對用戶偏好進行模擬,得到了非常好的效果。但RippleNet沒有考慮到限定域知識圖譜中的實體權(quán)重,導(dǎo)致該模型無法得到不同權(quán)重實體的推薦結(jié)果,沒有將推薦重點放在重要程度較高的實體上,從而降低了推薦準確度。

在復(fù)雜網(wǎng)絡(luò)科學(xué)中,國內(nèi)外學(xué)者對節(jié)點傳播能力的評估進行了大量研究,目前常用的方法有度中心性[8]、介數(shù)中心性[9]、緊密度中心性[10]等。為了解決這個問題,本文將運用復(fù)雜網(wǎng)絡(luò)科學(xué)的方法,把知識圖譜中三元組的實體抽象為節(jié)點,關(guān)系抽象為連邊,計算出復(fù)雜網(wǎng)絡(luò)中實體的節(jié)點影響力,并將其作為實體權(quán)重再放入RippleNet網(wǎng)絡(luò)中進行計算。

1 聯(lián)合復(fù)雜網(wǎng)絡(luò)的Cn-RippleNet算法

1.1 構(gòu)建基于知識圖譜的復(fù)雜網(wǎng)絡(luò)

本文使用RippleNet中的電影和書籍知識圖譜[7],這個圖譜數(shù)據(jù)文件是一個純文本文件,構(gòu)成該文件的數(shù)據(jù)是實體——關(guān)系——實體的三元組。以電影知識圖譜為例,構(gòu)建電影圖譜復(fù)雜網(wǎng)絡(luò)時,將所有實體抽象為為網(wǎng)絡(luò)的節(jié)點,實體之間的關(guān)系作為連邊,表示節(jié)點之間的關(guān)聯(lián)。建立的電影圖譜復(fù)雜網(wǎng)絡(luò)是一種無向非加權(quán)網(wǎng)絡(luò),具有如下特征:

1) 網(wǎng)絡(luò)規(guī)模巨大,包含169 366個節(jié)點和333 543條邊,因此建立非加權(quán)網(wǎng)絡(luò)以減少計算復(fù)雜度,便于特征分析。

2) 只描述實體與實體之間的關(guān)聯(lián)及關(guān)聯(lián)間的距離,忽略關(guān)系的方向。

因為以知識圖譜構(gòu)建的網(wǎng)絡(luò)不一定是全連通網(wǎng)絡(luò),導(dǎo)致某些節(jié)點無法參與計算其節(jié)點影響力,所以需要消除冗余,計算出電影知識圖譜的最大連通子網(wǎng)。這里本文使用丁連紅老師的基于集合運算的子網(wǎng)抽取算法(SNESO)[11]。該方法將電影知識圖譜文件Graph作為輸入,經(jīng)過子網(wǎng)抽取算法得到其輸出最大連通子網(wǎng)的節(jié)點集合MaxSubNet。

算法過程如下:

1) 從電影知識圖譜Graph中抽取1條擁有最大度值節(jié)點的三元組信息,將三元組中的2個實體作為中心節(jié)點,也就是作為最大連通子網(wǎng)的中心層SubNeti(這時i=1),將此中心層加入MaxSubNet。

2) 尋找SubNeti集合的相鄰節(jié)點,即遍歷Graph中的三元組(head,relation,tail),判斷其中的head,tail是否存在于SubNeti集合中。如果存在,則表示對應(yīng)head或者tail是集合SubNeti的相鄰節(jié)點,將這些相鄰節(jié)點加進相鄰節(jié)點集NeighborsSeti中。

3) 對比NeighborsSeti集和MaxSubNet集,查看NeighborsSeti中是否有新的節(jié)點并不存在于MaxSubNet集中,如果存在這樣的節(jié)點,則將NeighborsSeti并入MaxSubNet。并將SubNeti用NeighborsSeti與MaxSubNet的差集替換掉,作為新的SubNeti,i=i+1。跳轉(zhuǎn)到步驟2)。如果不存在新的節(jié)點,則進行步驟4)。

4) 返回MaxSubNet。

此算法的關(guān)鍵步驟是對Graph三元組的遍歷。從中心層出發(fā),每一次的遍歷Graph,都會得到當前層節(jié)點的所有相鄰節(jié)點。由于度值較大的節(jié)點存在于最大連通子網(wǎng)的概率更高,因此從度值最大的節(jié)點入手,找到最大連通子網(wǎng)的概率更高。

找到最大連通子網(wǎng)的所有實體,即MaxSubNet之后,再根據(jù)MaxSubNet從電影知識圖譜文件Graph中提取出最大子網(wǎng)的邊的集合,并且存儲在GraphLink中,最后由MaxSubNet和GraphLink生成如圖1所示結(jié)構(gòu)的最大連通子網(wǎng),存儲格式依然是三元組形式?？梢钥匆?中心層是由2個點構(gòu)成,層層擴散,2個點的相鄰實體作為第二層,第二層的相鄰實體作為第三層,層層遞歸得到整個子網(wǎng),直到?jīng)]有新的相鄰實體為止。

圖1 最大連通子網(wǎng)的模型結(jié)構(gòu)

1.2 節(jié)點影響力計算

節(jié)點影響力是指在復(fù)雜網(wǎng)絡(luò)中對所有節(jié)點進行建模分析,對網(wǎng)絡(luò)中具有影響力或重要的節(jié)點進行排序。一個復(fù)雜網(wǎng)絡(luò)通常包含有重要節(jié)點,并且少部分重要節(jié)點一般都能影響網(wǎng)絡(luò)中的大部分節(jié)點。在不同網(wǎng)絡(luò)中,研究人員都會從不同尺度、方向和實驗條件下建立節(jié)點影響力的測量指標,并盡量用最精確和快速的方式找到最有影響力的節(jié)點,并對其進行排序[12]。

本文用已構(gòu)建的最大連通子網(wǎng)作為一個復(fù)雜網(wǎng)絡(luò),對所有三元組的節(jié)點進行影響力計算。本文分別使用使用度中心性方法[8]介數(shù)中心性[9]、緊密度中心性[10]對電影知識圖譜網(wǎng)絡(luò)的節(jié)點影響力進行計算,尋找電影知識圖譜中相對影響力較大的節(jié)點,并從實驗結(jié)果中分析哪種方法更加有效。

在度中心性中,節(jié)點的度值是指連接某節(jié)點的其他節(jié)點的數(shù)量。度中心性則是根據(jù)單個節(jié)點度值大小和節(jié)點的總數(shù)來計算,節(jié)點度值越大,則度中心性也越大。在限定域知識圖譜中,大多數(shù)網(wǎng)絡(luò)的度分布為冪律分布,所以少數(shù)節(jié)點的度值較大,而大量的節(jié)點度值較小。因此,使用度中心性進行節(jié)點影響力計算,能夠準確區(qū)分不同度值的節(jié)點,并賦予差異較大的權(quán)重。

由于以電影知識圖譜構(gòu)成的網(wǎng)絡(luò)為無向網(wǎng)絡(luò),因此具體計算公式如下

(1)

在總數(shù)g為的節(jié)點所構(gòu)成的無向網(wǎng)絡(luò)中,單個節(jié)點i的度中心性使用CD(Ni)表示。最終得到的結(jié)果是一個比例,范圍在0.0～1.0之間。0.0表示其與任何一個節(jié)點都沒有關(guān)系,1.0表示與每一個節(jié)點都有直接關(guān)系。計算出知識圖譜網(wǎng)絡(luò)中所有節(jié)點的度中心性后,將其對應(yīng)在圖譜中的實體上,采用字典存取方式保存,記為C。介數(shù)中心性和緊密度中心性的保存方法同上。

1.3 聯(lián)合復(fù)雜網(wǎng)絡(luò)Cn-RippleNet模型

RippleNet是模擬水波紋的傳播方式,以用戶點擊歷史為種子,并在限定域知識圖譜上使用種子為初始點向外一圈一圈地擴散開來,這個過程稱為用戶的偏好傳播。該模型認為種子外圈的項目依然屬于用戶的潛在偏好,因此在刻畫時也要將其考慮。以下是對RippleNet模型進行改進的地方:

Cn-RippleNet的整體框架如圖2所示,通過上部分實驗得到當前Hop的Ripple set三元組中頭部head的度中心性,且作為對應(yīng)head的權(quán)值。然后在對Ripple set進行embedding時,將Ripple set的嵌入矩陣與head對應(yīng)的權(quán)值矩陣中對應(yīng)元素各自相乘,得到帶有權(quán)重的Ripple set embedding。之后按照RippleNet模型進行用戶embedding和項目embedding計算,根據(jù)Hop次數(shù)進行偏好傳播的迭代,最終得到帶有實體權(quán)重的最終結(jié)果。

圖2 聯(lián)合復(fù)雜網(wǎng)絡(luò)Cn-RippleNet模型

首先,在知識圖譜中表示用戶歷史點擊數(shù)據(jù)vu,由此來表示基于用戶歷史vu的偏好相關(guān)實體,在RippleNet中,通過循環(huán)遞歸的方法,為用戶u創(chuàng)建了偏好相關(guān)實體集,如下所示

(2)

這些實體可被視為用戶在知識圖譜中依據(jù)歷史點擊vu的偏好擴展。在給出相關(guān)實體的定義后,本文定義用戶u所有的K-hop Ripple set如下

k=1,2…,H

(3)

在每一次Hop中,都會將Ripple set中頭實體的度中心性Ci作為權(quán)值與Ripple set的嵌入矩陣ei進行矩陣對應(yīng)項乘積運算,得到帶有權(quán)重的hi。如下所示

hi=eiCi

(4)

(5)

(6)

(7)

最后,結(jié)合用戶embedding和項目embedding,輸出預(yù)測的點擊概率

(8)

2 實驗設(shè)置及結(jié)果分析

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

在本文的實驗中,利用以下2個數(shù)據(jù)集進行實驗:MovieLens-1M和Book-Crossing分別是在電影推薦和圖書推薦中經(jīng)常用到的數(shù)據(jù)集。其中電影數(shù)據(jù)集MovieLens-1M包含網(wǎng)站上真實用戶的上百萬個評分。Book-Crossing同樣也包含百萬本圖書,并且所有圖書都在圖書交流社區(qū)中獲得用戶的評分。本文采用RippleNet模型中為每個數(shù)據(jù)集所構(gòu)造的知識圖譜。

表1 2個數(shù)據(jù)集的基本統(tǒng)計

2.2 實驗環(huán)境

表2中給出了Cn-RippleNet模型完整的參數(shù)設(shè)置,其中d表示項目和知識圖的嵌入維數(shù),H表示Hop的次數(shù)，l表示學(xué)習(xí)率。

表2 Cn-RippleNet模型的超參數(shù)

本文將分別對每個數(shù)據(jù)集進行處理,將整個數(shù)據(jù)集分為訓(xùn)練集、評估集和測試集3個部分。數(shù)據(jù)占比為6∶2∶2。每個數(shù)據(jù)集進行5次實驗,并以其平均值作為最終結(jié)果。

2.3 評價指標

本文使用ACC(Accuracy)和AUC(Area Under Curve)作為實驗的評價指標。AUC來源于ROC,也就是ROC曲線圖下半部分的面積。其值小于1。ROC曲線圖用來判斷二值分類器的優(yōu)劣,得到的曲線圖橫坐標為FPR(false positive rate),縱坐標為TPR(true positive rate),將這些坐標對連接起來就形成了ROC曲線圖。最后計算AUC面積得到一個0.5～1的值,AUC越大分類效果就越好。

2.4 實驗結(jié)果

本文構(gòu)建了電影和書籍的知識圖譜,使用基于集合運算的子網(wǎng)抽取算法構(gòu)建了復(fù)雜網(wǎng)絡(luò)。下圖是最大聯(lián)通子網(wǎng)的部分三元組數(shù)據(jù)。head表示頭,rel表示關(guān)系,tail表示尾。為方便使用和統(tǒng)計,實體和關(guān)系都使用序號來表示。

表3 最大連通子網(wǎng)的部分數(shù)據(jù)

通過對節(jié)點影響力的計算,得到了子網(wǎng)中每一個實體的度中心性。部分電影知識圖譜實體的度中心性結(jié)果如下:

表4 最大連通子網(wǎng)的部分度中心性

本文測試了不同參數(shù)時得到的結(jié)果,Cn-RippleNet模型在參數(shù)d=16,l=0.02,λ2=0.02的時候表現(xiàn)最佳,得到的AUC和ACC都取得令人滿意的結(jié)果。如表5所示,相比其他主流基于知識圖譜的推薦模型,Cn-RippleNet在2個數(shù)據(jù)集上都取得了最好的性能。其原因在于Cn-RippleNet是將基于路徑和基于嵌入的方法相結(jié)合,利用知識圖譜的側(cè)面信息和節(jié)點影響力,且對網(wǎng)絡(luò)中的實體賦予了權(quán)重,能夠給予推薦系統(tǒng)更好的推薦,得到更加準確的推薦結(jié)果。

表5 不同模型的AUC和ACC的結(jié)果

通過表5的結(jié)果可以發(fā)現(xiàn),對比CKE的表現(xiàn)來看,Cn-RippleNet在AUC和ACC的評價指標下分別高出了13個百分點和12個百分點,這是因為CKE是將知識圖譜同協(xié)同過濾方法融合,只是利用了圖譜的結(jié)構(gòu)知識特征,沒有考慮圖譜的路徑。DKN在電影和圖書推薦方面表現(xiàn)不盡人意,被Cn-RippleNet模型分別高出28個百分點和26個百分點。這是因為DKN更注重文本內(nèi)容,需要有多個實體才能保證預(yù)測的準確率。對DKN來說數(shù)據(jù)集的實體名字不夠長,就無法提供有用的信息,得到的結(jié)果也更加不準確。Cn-RippleNet通過結(jié)合基于路徑的方法,得到了節(jié)點影響力克服了這個問題,因此Cn-RippleNet也能在數(shù)據(jù)長度不夠的情況下達到高性能。由于用戶定義的元路徑很難是最佳的,所以PER在電影和書籍改編上的表現(xiàn)并不令人滿意,而Cn-RippleNet融合知識圖譜實體的路徑,達到了更高的性能。在這2個數(shù)據(jù)集中,Cn-RippleNet的性能最好。對比RippleNet,在MovieLens-1M數(shù)據(jù)集中,改進后的Cn-RippleNet在AUC和ACC的評價指標下都高出了1個百分點,而在Book-Crossing數(shù)據(jù)集中,指標高出了2個百分點。這表明考慮節(jié)點影響力后的RippleNet的推薦效果更加準確。因此本文認為Cn-RippleNet在依據(jù)路徑融合節(jié)點影響力的方法后效果更好。

在實驗時,考慮到RippleNet和Cn-RippleNet可能由于模型超參數(shù)的不同導(dǎo)致實驗結(jié)果不嚴謹,因此本文將添加1組對照試驗,將2個模型的超參數(shù)按照表2設(shè)置,并將RippleNet的實驗結(jié)果記為SSP-RippleNet。通過表5的結(jié)果,發(fā)現(xiàn)在相同超參數(shù)下,Cn-RippleNet對比SSP-RippleNet的結(jié)果依然更優(yōu)。在MovieLens-1M數(shù)據(jù)集中,AUC和ACC的指標分別高數(shù)3個百分點和4個百分點,而Book-Crossing數(shù)據(jù)集中,AUC和ACC分別高出4個百分點和5個百分點。對比相同超參數(shù)的RippleNet模型,Cn-RippleNet依然能夠取得更好的結(jié)果。

同時由圖3可以看出,Hop的值在2或者3時,效果最佳,說明Hop數(shù)對與性能的影響并不是越高越好。從圖4可以看出,同樣Dim也不是值越高效果越好,Dim在16時模型性能最優(yōu)。表6可以看出在這2個數(shù)據(jù)集下,在度中心性、介數(shù)中心性、接近中心性的實驗對比中,度中心性的各項結(jié)果都優(yōu)于其他。這表明在確定權(quán)重的方法中,度中心性是最能體現(xiàn)2個數(shù)據(jù)集中網(wǎng)絡(luò)節(jié)點的重要程度。因此對節(jié)點影響力的評價選擇,需要根據(jù)具體網(wǎng)絡(luò)具體分析,并且要通過實驗來確定。

表6 不同中心性的AUC和ACC的結(jié)果

圖3 不同Hop的AUC值

圖4 不同Dim下的AUC值

3 結(jié) 論

本文提出了一種融合復(fù)雜網(wǎng)絡(luò)節(jié)點影響力的Cn-RippleNet推薦模型。對領(lǐng)域知識圖譜進行了網(wǎng)絡(luò)化,計算了知識圖譜中實體的影響力,并將其融入知識圖譜的網(wǎng)絡(luò)中,使得推薦結(jié)果更加符合人們的偏好,解決了RippleNet沒考慮關(guān)鍵節(jié)點對推薦結(jié)果的影響的問題,從而增加了推薦精度。實驗表明,通過節(jié)點影響力改進的Cn-RippleNet算法能夠提高推薦算法的結(jié)果。下一步可以考慮將知識圖譜的最大聯(lián)通子網(wǎng)的關(guān)系細化,對不同的關(guān)系賦予不同的權(quán)重。也可以考慮更加新穎的節(jié)點影響力算法。