基于聯合復雜網絡Cn-RippleNet模型的推薦方法

羅宇泰, 徐濤, 徐章博

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

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

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

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

1 聯合復雜網絡的Cn-RippleNet算法

1.1 構建基于知識圖譜的復雜網絡

本文使用RippleNet中的電影和書籍知識圖譜[7],這個圖譜數據文件是一個純文本文件,構成該文件的數據是實體——關系——實體的三元組。以電影知識圖譜為例,構建電影圖譜復雜網絡時,將所有實體抽象為為網絡的節點,實體之間的關系作為連邊,表示節點之間的關聯。建立的電影圖譜復雜網絡是一種無向非加權網絡,具有如下特征:

1) 網絡規模巨大,包含169 366個節點和333 543條邊,因此建立非加權網絡以減少計算復雜度,便于特征分析。

2) 只描述實體與實體之間的關聯及關聯間的距離,忽略關系的方向。

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

算法過程如下:

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

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

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

4) 返回MaxSubNet。

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

找到最大連通子網的所有實體,即MaxSubNet之后,再根據MaxSubNet從電影知識圖譜文件Graph中提取出最大子網的邊的集合,并且存儲在GraphLink中,最后由MaxSubNet和GraphLink生成如圖1所示結構的最大連通子網,存儲格式依然是三元組形式。可以看見,中心層是由2個點構成,層層擴散,2個點的相鄰實體作為第二層,第二層的相鄰實體作為第三層,層層遞歸得到整個子網,直到沒有新的相鄰實體為止。

圖1 最大連通子網的模型結構

1.2 節點影響力計算

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

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

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

由于以電影知識圖譜構成的網絡為無向網絡,因此具體計算公式如下

(1)

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

1.3 聯合復雜網絡Cn-RippleNet模型

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

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

圖2 聯合復雜網絡Cn-RippleNet模型

首先,在知識圖譜中表示用戶歷史點擊數據vu,由此來表示基于用戶歷史vu的偏好相關實體,在RippleNet中,通過循環遞歸的方法,為用戶u創建了偏好相關實體集,如下所示

(2)

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

k=1,2…,H

(3)

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

hi=eiCi

(4)

(5)

(6)

(7)

最后,結合用戶embedding和項目embedding,輸出預測的點擊概率

(8)

2 實驗設置及結果分析

2.1 數據集

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

表1 2個數據集的基本統計

2.2 實驗環境

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

表2 Cn-RippleNet模型的超參數

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

2.3 評價指標

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

2.4 實驗結果

本文構建了電影和書籍的知識圖譜,使用基于集合運算的子網抽取算法構建了復雜網絡。下圖是最大聯通子網的部分三元組數據。head表示頭,rel表示關系,tail表示尾。為方便使用和統計,實體和關系都使用序號來表示。

表3 最大連通子網的部分數據

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

表4 最大連通子網的部分度中心性

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

表5 不同模型的AUC和ACC的結果

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

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

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

表6 不同中心性的AUC和ACC的結果

圖3 不同Hop的AUC值

圖4 不同Dim下的AUC值

3 結 論

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