基于異構(gòu)信息網(wǎng)絡(luò)的模糊貼近度推薦算法

朱 元，張九根，盧佳樂，陳 鑫

(南京工業(yè)大學(xué) 電氣工程與控制科學(xué)學(xué)院，江蘇 南京 211816)

0 引 言

目前，在個(gè)性化網(wǎng)絡(luò)推薦領(lǐng)域[1,2]，傳統(tǒng)協(xié)同過濾方法存在數(shù)據(jù)稀疏性、冷啟動(dòng)和可信度[3]等問題，相關(guān)國(guó)內(nèi)外學(xué)者也就此提出了許多方法，包括矩陣降維、數(shù)據(jù)稀疏性填充、相似性度量改進(jìn)等[4]。異構(gòu)信息網(wǎng)絡(luò)結(jié)構(gòu)因其出色的拓?fù)浣Y(jié)構(gòu)搭建、屬性關(guān)系連接多元化受到廣大研究學(xué)者的關(guān)注[5]。文獻(xiàn)[6]通過考慮用戶與項(xiàng)目維度的相互作用關(guān)系，提出了一種基于資源分配過程的加權(quán)方法，在一定程度上可以提升推薦質(zhì)量。文獻(xiàn)[7]提出PathSim相似性度量方法，該算法的核心是通過異構(gòu)網(wǎng)絡(luò)的屬性聯(lián)系優(yōu)化相似度計(jì)算方式，提高了推薦的可靠性。文獻(xiàn)[8]基于異構(gòu)信息網(wǎng)絡(luò)，結(jié)合用戶的隱式反饋信息和提出的信任相關(guān)性開發(fā)了用于推薦的隨機(jī)游走算法，有效改善了數(shù)據(jù)稀疏性問題。但上述方法都只關(guān)注了異構(gòu)信息網(wǎng)絡(luò)中的部分信息，并未考慮到用戶個(gè)體評(píng)分偏好以及時(shí)間維度對(duì)整個(gè)異構(gòu)網(wǎng)絡(luò)中元路徑關(guān)系的權(quán)重影響。鑒于此，本文從用戶屬性角度考慮，在運(yùn)用k-means[9]進(jìn)行聚類的基礎(chǔ)上搭建新的異構(gòu)信息網(wǎng)絡(luò)，采用模糊貼近度計(jì)算用戶間相似度，提出了一種基于異構(gòu)信息網(wǎng)絡(luò)的模糊貼近度推薦算法。

1 異構(gòu)信息網(wǎng)絡(luò)

1.1 異構(gòu)推薦系統(tǒng)

推薦網(wǎng)絡(luò)中用戶及項(xiàng)目是對(duì)象類型節(jié)點(diǎn)，對(duì)象及鏈接具有豐富的關(guān)系，如用戶間和項(xiàng)目間可通過近鄰關(guān)系有效鏈接、用戶與項(xiàng)目間以行為從屬關(guān)系進(jìn)行連接等。令U和I分別表示用戶和項(xiàng)目集合,其中U={U1,U2,…,Un}，I={I1,I2,…,Im}，n表示用戶數(shù)量，m表示項(xiàng)目數(shù)量。G=〈V,E〉 表示用戶和項(xiàng)目節(jié)點(diǎn)及鏈接關(guān)系構(gòu)成的異構(gòu)推薦網(wǎng)絡(luò)模型。其中V(G)=U∪I,E(G)={〈oi,oj〉} 且oi,oj∈U∪I，V表示推薦網(wǎng)絡(luò)中的對(duì)象類型，E表示關(guān)系鏈接，不同的鏈接對(duì)象具有不同的關(guān)系鏈接。以電影評(píng)分為例，用戶與電影彼此間用實(shí)線鏈接，表示用戶對(duì)項(xiàng)目的評(píng)分行為；用戶間或電影間用短虛線鏈接，表示用戶間或電影間的關(guān)系鏈接。由圖1可知，用戶a已評(píng)分電影為b、c，用戶b已評(píng)分電影為a、b、e，用戶c已評(píng)分電影為a、c、d，用戶d已評(píng)分電影d、e，用戶與電影的評(píng)分關(guān)系用實(shí)線連接。因?qū)ο蠊?jié)點(diǎn)較少，通過觀察可以得到具有共同評(píng)分的用戶關(guān)系對(duì)： 〈a,b〉、〈a,c〉、〈b,c〉、〈b,d〉、〈c,d〉， 此時(shí)認(rèn)為上述用戶關(guān)系對(duì)中的元素互為近鄰用戶，在圖1中用長(zhǎng)虛線進(jìn)行連接，同理可得近鄰項(xiàng)目關(guān)系對(duì)。

圖1 異構(gòu)推薦網(wǎng)絡(luò)模型

1.2 異構(gòu)信息網(wǎng)絡(luò)

信息網(wǎng)絡(luò)[10]一般采用有向加權(quán)圖G=〈V,E,W〉 的形式表示，其中V表示網(wǎng)絡(luò)中的對(duì)象節(jié)點(diǎn)，E表示對(duì)象間鏈接關(guān)系，W：E→R+是從邊e∈E到實(shí)數(shù)w∈R+的權(quán)重映射。在網(wǎng)絡(luò)中，有一個(gè)對(duì)象類型映射函數(shù)φ：V→A和一個(gè)鏈接類型映射函數(shù)φ：E→R, 即每個(gè)對(duì)象v∈V屬于一個(gè)特定的對(duì)象類型φ(v)∈A， 每條鏈接e∈E屬于特定的關(guān)系φ(e)?R。 當(dāng)對(duì)象類型數(shù)|A|>1或關(guān)系類型數(shù)|R|>1， 稱該網(wǎng)絡(luò)為異構(gòu)信息網(wǎng)絡(luò)。

異構(gòu)信息網(wǎng)絡(luò)中，兩個(gè)對(duì)象之間鏈接關(guān)系可以有多條不同路徑，且對(duì)象之間的不同對(duì)應(yīng)關(guān)系可以通過不同路徑進(jìn)行表示，如“用戶-項(xiàng)目-用戶”連接方式表示用戶之間的共同評(píng)分聯(lián)系，而更換鏈接方式為“用戶-職業(yè)-項(xiàng)目-職業(yè)-用戶”連接，表示共同職業(yè)的用戶對(duì)同一項(xiàng)目的評(píng)分。上述能夠?qū)?duì)象間關(guān)系鏈接映射表示出來(lái)的路徑鏈接稱為元路徑，形式定義如下：

P的路徑長(zhǎng)度表示在路徑上組合關(guān)系的數(shù)量。若僅突出關(guān)系連接而忽略連接屬性權(quán)重，可將用路徑的類型名稱對(duì)元路徑屬性關(guān)系鏈接簡(jiǎn)單表示。例如，元路徑可用于表示評(píng)分鏈接中的用戶-項(xiàng)目的評(píng)分關(guān)系，記為UIU。在網(wǎng)絡(luò)G中，設(shè)a1和al+1之間存在元路徑鏈接關(guān)系p=(a1a2…al+1)， 如果對(duì)于?i，φ(ai)=Ai且每條路徑鏈接ei=〈aiai+1〉 屬于P中的每個(gè)關(guān)系Ri， 則稱路徑p嚴(yán)格遵循元路徑P，并稱這些路徑是元路徑P的路徑實(shí)例，表示為p∈P。

如果在TG中，若p是P的反向路徑，則稱p是P的反元路徑，表示為P-1， 它定義了P的反向關(guān)系。類似的，p的反路徑實(shí)例被定義為p的反向路徑，表示為p-1。 當(dāng)且僅當(dāng)Al=A1時(shí)，元路徑P1=(A1A2…Al) 與P2=(A1A2…Ak) 可以直接進(jìn)行連接，連接組合后新的元路徑記為P=(P1P2)， 該路徑的屬性關(guān)系鏈接記為 (A1A2…AlA2…Ak)。 得到元路徑的鏈接后，采用PathSim算法[11]來(lái)進(jìn)行兩個(gè)對(duì)象x和y之間的相似性

(1)

其中，px∶y是x和y之間的路徑實(shí)例，px∶x是x和x之間的路徑實(shí)例，py∶y是y和y之間的路徑實(shí)例。

1.3 屬性聚類及元路徑關(guān)系抽取

1.3.1 異構(gòu)信息網(wǎng)絡(luò)屬性聚類

異構(gòu)信息網(wǎng)絡(luò)中對(duì)象類型或鏈接類型呈現(xiàn)多樣化，對(duì)聚類結(jié)果有很大影響。例如針對(duì)兩個(gè)不同對(duì)象節(jié)點(diǎn)而言，選擇不同的元路徑關(guān)系鏈接在語(yǔ)義層面的解釋意義將大不相同，聚類結(jié)果也將具有很大誤差。具體實(shí)例如下：

如圖2所示該異構(gòu)信息網(wǎng)絡(luò)實(shí)例中包含3種類型對(duì)象：職業(yè)(occupation，O)、用戶(user，U)以及評(píng)分項(xiàng)目產(chǎn)生的時(shí)間(time，T)。此外，包含兩種鏈接類型：用戶和職業(yè)之間的從屬關(guān)系用實(shí)線表示，用戶和評(píng)分時(shí)間的關(guān)系用虛線表示。用戶彼此間聯(lián)系采用不同的元路徑連接表示。如用戶之間(屬于同一職業(yè))通過職業(yè)進(jìn)行連接可表示為元路徑U-O-U，而根據(jù)用戶評(píng)分時(shí)間段進(jìn)行連接(同一時(shí)間區(qū)間內(nèi)對(duì)項(xiàng)目的評(píng)分)可表示為元路徑U-T-U。在用戶聚類過程中選擇何種連接方式進(jìn)行聚類是解決問題的關(guān)鍵。

圖2 職業(yè)、用戶和時(shí)間的一個(gè)異構(gòu)信息網(wǎng)絡(luò)實(shí)例

用戶間的鏈接方式可通過不同元路徑連接，必將導(dǎo)致不同的聚類結(jié)果。圖3(a)以職業(yè)作為關(guān)系鏈接權(quán)重將用戶聚類結(jié)果分為兩組： {1,2,3,4} 和 {5,6,7,8}； 圖3(b)中以評(píng)分時(shí)間段作為關(guān)系鏈接權(quán)重將用戶連接分為不同于圖3(a)的兩組； {1,3,5,7} 和 {2,4,6,8}； 圖3(c)將職業(yè)和評(píng)分時(shí)間段關(guān)系權(quán)重共同考慮將聚類結(jié)果分為4組： {1,3}、 {2,4}、 {5,7}、 {6,8}。

圖3 元路徑權(quán)重劃分聚類

不同聚類方式都具有其合理性，但語(yǔ)義解釋層面卻大不相同。用戶選取元路徑或元路徑的權(quán)重組合時(shí)需要以聚類結(jié)果為選擇依據(jù)，但由用戶自己篩選聚類依據(jù)難以實(shí)現(xiàn)，因此在聚類過程中為用戶提供指導(dǎo)信息將提升結(jié)果的準(zhǔn)確性。例如，用戶指定聚類結(jié)果中分別包含為{1}和{5}兩個(gè)元素且目標(biāo)聚類數(shù)劃分為兩類，若將元路徑關(guān)系鏈接權(quán)重A-O-A作為聚類標(biāo)準(zhǔn)，可將聚類結(jié)果分為 {1,2,3,4} 和 {5,6,7,8}； 當(dāng)聚類目標(biāo)要求劃分為4類，且要求4類結(jié)果分別含有對(duì)象 {1}，{2}，{5}，{6} 時(shí)，提供選擇元路徑A-O-A和A-T-A參考，聚類結(jié)果為 {1,3}， {2,4}， {5,7}， {6,8}。

元路徑關(guān)系鏈接權(quán)重差異性使得異構(gòu)信息網(wǎng)絡(luò)的結(jié)構(gòu)模式呈現(xiàn)多元化，不同選擇結(jié)果對(duì)聚類結(jié)果的影響巨大。此外，大多情況下僅通過一種屬性鏈接權(quán)重作為衡量標(biāo)準(zhǔn)無(wú)法滿足用戶的聚類需求，會(huì)直接影響后續(xù)推薦工作。例如在社交網(wǎng)絡(luò)中，不同用戶所具有的朋友數(shù)量差異明顯，某些用戶朋友數(shù)量基數(shù)龐大而相應(yīng)的一些用戶朋友數(shù)量較少。針對(duì)這種情況，僅使用某一特定的元路徑連接方式將造成聚類結(jié)果的偏差，此外，用戶朋友數(shù)量隨時(shí)間變化也呈動(dòng)態(tài)變化趨勢(shì)。因此，在聚類階段，首先采用k-means聚類算法，對(duì)用戶屬性的依賴性及時(shí)間維度進(jìn)行聚類，基于此再對(duì)元路徑的關(guān)系進(jìn)行選擇。k-means算法步驟如下：

(1)定義一個(gè)用戶數(shù)據(jù)集合Ω(n為樣本數(shù)，xi為一個(gè)m維向量，表示第i個(gè)數(shù)據(jù)m個(gè)屬性)

Ω={xi|xi=(xi1,xi2,xi3,…xim),i=1,2,…,n}

(2)

用C表示簇中心，k為簇中心個(gè)數(shù)

C={ci|ci=(cj1,cj2,cj3,…cjm),j=1,2,…,k}

(3)

(2)計(jì)算各用戶到簇中心的歐式距離

(4)

(3)迭代更新n簇的中心至其不再變化，最后將用戶分為n簇。

1.3.2 元路徑關(guān)系抽取

在k-means聚類算法的基礎(chǔ)上，對(duì)用戶相關(guān)屬性的聯(lián)系及時(shí)間維度進(jìn)行過濾篩選，構(gòu)建異構(gòu)信息網(wǎng)絡(luò)模型，之后采用線性回歸的多關(guān)系抽取算法對(duì)不同社區(qū)內(nèi)的元路徑關(guān)系進(jìn)行選取，算法的基本步驟如下：

(1)建立新的目標(biāo)關(guān)系矩陣。采用k-means聚類算法對(duì)用戶進(jìn)行聚類后，建立異構(gòu)網(wǎng)絡(luò)模型并以此構(gòu)建新的目標(biāo)關(guān)系矩陣，為了衡量不同屬性的元路徑權(quán)重把權(quán)重值標(biāo)準(zhǔn)化到[0,1]區(qū)間

(5)

(6)

(7)

(3)系數(shù)向量的解表示不同元路徑關(guān)系鏈接的權(quán)重高低。用W來(lái)表示權(quán)重向量矩陣。

2 基于異構(gòu)信息網(wǎng)絡(luò)的模糊貼近度推薦算法

2.1 模糊貼近度

模糊數(shù)學(xué)作為一門學(xué)科從數(shù)學(xué)角度對(duì)客觀事物的類屬不確定性進(jìn)行研究并加以引用。模糊數(shù)學(xué)并非把數(shù)學(xué)概念變得模糊不堪，而是應(yīng)用合理的數(shù)學(xué)分析、統(tǒng)計(jì)學(xué)等方法完成必然性現(xiàn)象到偶然性領(lǐng)域的跨越。推薦算法中用戶對(duì)某個(gè)物品或項(xiàng)目的評(píng)價(jià)值，以5個(gè)階梯評(píng)價(jià)劃分可分為(討厭，不喜歡，一般，較為喜歡，很喜歡)，而這種評(píng)價(jià)往往帶有模糊的不確定性。因此，選擇用模糊數(shù)學(xué)來(lái)衡量?jī)蓚€(gè)用戶的偏好相似度，對(duì)尋找目標(biāo)用戶的近鄰相似用戶具有很大幫助且具備技術(shù)的可行性和科學(xué)性。

根據(jù)上述分析，先計(jì)算相似度的測(cè)量，對(duì)于用戶間相似度進(jìn)行排序，選出相似度最高的近鄰用戶之后進(jìn)行推薦。對(duì)相似度進(jìn)行計(jì)算時(shí)，根據(jù)元路徑關(guān)系權(quán)重矩陣，來(lái)進(jìn)行指標(biāo)量化，即基本測(cè)算思路如圖4所示：確立異構(gòu)網(wǎng)絡(luò)→元路徑權(quán)重值→計(jì)算相似度。

圖4 異構(gòu)網(wǎng)絡(luò)模糊貼近度應(yīng)用

2.2 用戶屬性指標(biāo)的隸屬度計(jì)算

設(shè)用戶集合U=(u1,u2,…,un) 中每個(gè)用戶均存在m個(gè)固有屬性，據(jù)此可確定用戶固有屬性集U(Pi,Xm)， 其中Xm為用戶的具體屬性。由式(7)可得，元路徑權(quán)重集合W，表示異構(gòu)網(wǎng)絡(luò)中元路徑邊的權(quán)重程度；由此得到U和W這兩個(gè)非空集合的直積

μR∶=U×W→[0，1]

(8)

μR表示序偶 〈u,w〉 的隸屬權(quán)重程度映射到隸屬區(qū)間。不同元路徑連接的鏈接權(quán)重值都可以用隸屬度來(lái)進(jìn)行表示且鏈接權(quán)重符合概率分布，即元路徑連接權(quán)重隸屬函數(shù)。

對(duì)于數(shù)值中權(quán)重越高的元路徑權(quán)重邊，代表該屬性權(quán)重邊在異構(gòu)網(wǎng)絡(luò)模型中占有更高的權(quán)重影響，隸屬權(quán)重函數(shù)采用中間型梯形分布函數(shù)。

將m項(xiàng)評(píng)分的各級(jí)臨界值表示為

B=(bij)m×n

(9)

則可計(jì)算異構(gòu)網(wǎng)絡(luò)中每個(gè)用戶各項(xiàng)屬性的元路徑隸屬值權(quán)重矩陣

F=(fij)m×nF=μR·B

(10)

其中，bij和fij分別為矩陣B和F在i行j列的取值。在運(yùn)用式(10)所計(jì)算出的隸屬權(quán)重矩陣F中，不同元路徑鏈接關(guān)系權(quán)重取值均在[0,1]，而n個(gè)用戶的元路徑鏈接隸屬權(quán)重向量則分別為F1,F2,…,Fn。

2.3 用戶貼近度計(jì)算

模糊貼近度計(jì)算一般采用最大值最小值貼近度，計(jì)算公式如下

(11)

其中，σ(U1,U2) 表示模糊集U1和U2的貼近度，UU1(u)和UU2(u)分別為U1和U2的固有屬性集的隸屬權(quán)重程度。在這里隸屬權(quán)重程度表示異構(gòu)網(wǎng)絡(luò)中不同的元路徑關(guān)系鏈接權(quán)重邊屬于該用戶的隸屬程度，權(quán)重值大小刻畫了屬性對(duì)用戶所屬的隸屬程度的高低。

對(duì)于某數(shù)據(jù)集內(nèi)n個(gè)用戶的屬性隸屬權(quán)重向量F1,F2,…,Fn， 隸屬權(quán)重矩陣如下所示

(12)

其中，fnm表示第n個(gè)用戶的第m個(gè)屬性的隸屬權(quán)重值。

將關(guān)系權(quán)重矩陣代入式(11)，即可得到任意兩個(gè)用戶之間的貼近度，即用戶間相似程度。對(duì)得出的用戶間相似度進(jìn)行Top-N排序，得到最近鄰用戶，之后采用評(píng)分預(yù)測(cè)方式進(jìn)行項(xiàng)目推薦，并驗(yàn)證推薦結(jié)果的準(zhǔn)確性。

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

3.1 實(shí)驗(yàn)環(huán)境搭建

實(shí)驗(yàn)硬件環(huán)境為：Intel(R) Core(TM) i5-5257U處理器，Windows10，64位操作系統(tǒng)；所使用的軟件環(huán)境為：Pycharm平臺(tái)開發(fā)環(huán)境，數(shù)據(jù)庫(kù)選取Mysql。

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

本次實(shí)驗(yàn)數(shù)據(jù)集選用Epinions數(shù)據(jù)集[12]作為實(shí)驗(yàn)數(shù)據(jù)源，Epinions是一個(gè)著名的產(chǎn)品評(píng)論網(wǎng)，其中包括49 290名用戶，139 738個(gè)不同的項(xiàng)目，用戶可以對(duì)產(chǎn)品進(jìn)行評(píng)分并提交他們的個(gè)人評(píng)論, 評(píng)分標(biāo)準(zhǔn)通過1至5之間的整數(shù)值表示。隨機(jī)從數(shù)據(jù)集中抽取80%作為訓(xùn)練集，其余作為測(cè)試集。為了驗(yàn)證該推薦算法在不同稀疏程度數(shù)據(jù)集上的效果，本文對(duì)數(shù)據(jù)集以單個(gè)用戶信任記錄數(shù)T和單個(gè)商品評(píng)分?jǐn)?shù)為標(biāo)準(zhǔn)進(jìn)行數(shù)據(jù)篩選，得到稀疏性不同的Epinions-A(T>11,I>11)和Epinions-B(T>21,I>21)。數(shù)據(jù)集的相關(guān)統(tǒng)計(jì)見表1。

表1 Epinions數(shù)據(jù)集信息

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

本次實(shí)驗(yàn)對(duì)提出推薦算法的有效性評(píng)估以平均絕對(duì)誤差(mean absolute error，MAE)以及均方根誤差(root mean square error，RMSE)為度量標(biāo)準(zhǔn)，具體公式如下

(13)

(14)

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

常用的相似度計(jì)算包括余弦相似性(Cosine)和皮爾森相似性(Pearson)，在異構(gòu)信息網(wǎng)絡(luò)中HeteSim[13]算法也尤為經(jīng)典，為驗(yàn)證本文所提出算法的有效性，將本文提出的算法(HNCR)分別與這3種算法進(jìn)行對(duì)比，同時(shí)以MAE和RMSE值為度量標(biāo)準(zhǔn)，近鄰用戶數(shù)量為自變量，實(shí)驗(yàn)結(jié)果如圖5、圖6所示。

圖5 Epinions數(shù)據(jù)集MAE結(jié)果

圖6 Epinions數(shù)據(jù)集RMSE結(jié)果

由圖5圖6可以看出：

(1)算法的MAE值和RMSE值隨著近鄰用戶數(shù)的增加大致呈減小的趨勢(shì)，即算法精度隨近鄰用戶數(shù)先增大而有所提高。

(2)相比其它3種算法，基于異構(gòu)網(wǎng)絡(luò)貼近度的推薦算法HNCR在MAE和RMSE兩種指標(biāo)上的值均達(dá)到最小，具有最優(yōu)推薦效果。

圖7～圖9是稀疏程度存在差異的數(shù)據(jù)集上4種算法的實(shí)驗(yàn)結(jié)果，以近鄰用戶數(shù)為自變量，MAE值為準(zhǔn)確度度量標(biāo)準(zhǔn)?？梢钥闯?，數(shù)據(jù)集稀疏程度的差異同樣對(duì)準(zhǔn)確度也有一定的影響，Epinions-B上的準(zhǔn)確度達(dá)到最大?？傮w而言，數(shù)據(jù)集越稀疏，準(zhǔn)確度越低；越稠密，準(zhǔn)確度越高。

圖7 Epinions數(shù)據(jù)集

圖8 Epinions-A數(shù)據(jù)集

圖9 Epinions-B數(shù)據(jù)集

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

本文首先對(duì)推薦系統(tǒng)中基于異構(gòu)信息網(wǎng)絡(luò)的算法進(jìn)行了總結(jié)，為解決推薦算法數(shù)據(jù)稀疏性等問題，在引入異構(gòu)信息網(wǎng)絡(luò)的基礎(chǔ)上，采用模糊數(shù)學(xué)貼近度的方式來(lái)進(jìn)行用戶之間相似度的計(jì)算，從而提出了基于異構(gòu)信息網(wǎng)絡(luò)的模糊貼近度推薦算法。通過與其它算法進(jìn)行對(duì)比，實(shí)驗(yàn)結(jié)果表明基于異構(gòu)網(wǎng)絡(luò)的推薦算法具有更低的MAE和RMAE值，推薦準(zhǔn)確性更高。此外，關(guān)于異構(gòu)信息網(wǎng)絡(luò)推薦算法如何降低時(shí)間復(fù)雜度以及與真實(shí)網(wǎng)絡(luò)的實(shí)時(shí)交互將是下一步研究的方向。