融合相對(duì)評(píng)分的個(gè)性化興趣點(diǎn)推薦算法

單碩堂 陳廷偉 賈夢(mèng)威

(遼寧大學(xué)信息學(xué)院 遼寧 沈陽(yáng) 110036)

0 引 言

隨著人們對(duì)網(wǎng)絡(luò)社交需求的提高，誕生了一種新的基于位置的社交網(wǎng)絡(luò)[1](LBSN)?；谖恢玫纳缃痪W(wǎng)絡(luò)不僅指的是社會(huì)關(guān)系用戶，而且還包括興趣點(diǎn)(POI)簽到以及簽到時(shí)間戳和對(duì)地點(diǎn)的相關(guān)評(píng)論、描述。與其他社交網(wǎng)絡(luò)相比，LBSN不僅能夠反映用戶真實(shí)生活中所在的地理位置，而且將現(xiàn)實(shí)生活和虛擬世界進(jìn)行有效地結(jié)合，為研究者提供了機(jī)會(huì)和挑戰(zhàn)。

個(gè)性化推薦主要以用戶、信息以及用戶和信息之間的關(guān)系為研究對(duì)象，經(jīng)過(guò)對(duì)用戶的行為方式，獨(dú)特偏好等信息進(jìn)行剖析和學(xué)習(xí)，挖掘出用戶的興趣和特點(diǎn)，從而形成模型。如今的個(gè)性化推薦方法已經(jīng)應(yīng)用在生活中的各個(gè)領(lǐng)域，如日常所知的電影推薦、音樂(lè)推薦等。

經(jīng)過(guò)對(duì)目前個(gè)性化推薦的研究發(fā)現(xiàn)，在所涉及數(shù)據(jù)的維度方面可以分為同構(gòu)社交網(wǎng)絡(luò)的推薦和異構(gòu)社交網(wǎng)絡(luò)的推薦。同構(gòu)社交網(wǎng)絡(luò)下主流的個(gè)性化推薦方法有三種：協(xié)同過(guò)濾方法、基于上下文感知的方法和鏈路分析法[2]。目前應(yīng)用最廣泛的協(xié)同過(guò)濾算法以尋找與用戶相似度高的項(xiàng)目為原理，間接推斷目標(biāo)用戶的興趣，投其所好進(jìn)行推薦，亞馬遜的書(shū)籍推薦使用的就是協(xié)同過(guò)濾算法。協(xié)同過(guò)濾算法主要由三個(gè)階段構(gòu)成：首先根據(jù)相關(guān)歷史數(shù)據(jù)，計(jì)算出用戶之間的偏好相似度，其次以用戶所在位置為參照選擇top-n個(gè)用戶可能去的地點(diǎn)，最后對(duì)推薦的結(jié)果進(jìn)行評(píng)估。張俊等[3]提出了融合興趣和評(píng)分的協(xié)同過(guò)濾推薦算法，將用戶相似性和用戶評(píng)分相似性進(jìn)行兩次融合，通過(guò)專家信任度的概念對(duì)用戶未評(píng)分項(xiàng)目進(jìn)行評(píng)分預(yù)測(cè)填充，降低了數(shù)據(jù)的稀疏性。鏈路分析是將社交網(wǎng)絡(luò)抽象成拓?fù)浣Y(jié)構(gòu)，從中挖掘數(shù)據(jù)之間的關(guān)聯(lián)性，從而形成推薦。Cheng等[4]通過(guò)將用戶簽到信息抽象成馬爾科夫模型，通過(guò)區(qū)域的過(guò)濾推薦用戶附近的興趣點(diǎn)。上下文感知的推薦方法主要通過(guò)用戶的個(gè)人信息及位置屬性構(gòu)建推薦模型。Meng等[5]將LBSN和上下文推薦方法進(jìn)行結(jié)合，從而提高推薦精度。LBSN在同構(gòu)信息網(wǎng)絡(luò)下的個(gè)性化推薦已經(jīng)被許多學(xué)者進(jìn)行了廣泛的研究。近年來(lái)，LBSN異構(gòu)的特性也被發(fā)掘出來(lái)，只是研究還處在新興階段，其中曹玖新等[6]就從LBSN數(shù)據(jù)的異構(gòu)特性展開(kāi)研究，用元路徑的方法進(jìn)行個(gè)性化推薦，在一定程度上對(duì)數(shù)據(jù)存在的稀疏性有了緩解，并提升了推薦的準(zhǔn)確性，但仍然有一定的不足。

本文首先對(duì)評(píng)分信息體現(xiàn)個(gè)性化問(wèn)題進(jìn)行了描述，接著對(duì)用戶的評(píng)分行為進(jìn)行研究，以效用模型和比較模型為依據(jù)提出用戶相對(duì)評(píng)分概念。通過(guò)相對(duì)評(píng)分來(lái)學(xué)習(xí)用戶個(gè)性化偏好，并將相對(duì)評(píng)分信息轉(zhuǎn)化為元路徑的權(quán)值進(jìn)而提出融合相對(duì)評(píng)分的個(gè)性化興趣點(diǎn)推薦算法MpgbCount(Bidirectional Meta-Path Grade Count)，最終形成一個(gè)效果理想的個(gè)性化興趣點(diǎn)推薦系統(tǒng)。該算法利用LBSN中的異構(gòu)性信息和相對(duì)評(píng)分信息，充分挖掘用戶的個(gè)性化，并在一定程度上緩解了數(shù)據(jù)的稀疏性，進(jìn)一步提升了推薦系統(tǒng)的準(zhǔn)確性和個(gè)性化程度。

1 相關(guān)理論基礎(chǔ)

1.1 基于雙向元路徑誘導(dǎo)的相似度度量算法

根據(jù)雙向路徑誘導(dǎo)模型，設(shè)計(jì)元路徑下兩個(gè)節(jié)點(diǎn)之間相似度的度量方法(MpgbSim算法)：

MpgbSim(A1,An|L)=

(1)

式中：元路徑L=A1A2…An，A為對(duì)象類型節(jié)點(diǎn)集合。MpgbSim(A1,An|L,Ai)表示按照正向誘導(dǎo)元路徑L從A1節(jié)點(diǎn)到Ai節(jié)點(diǎn)的抵達(dá)率和按照逆向誘導(dǎo)元路徑L-1從An節(jié)點(diǎn)到Ai節(jié)點(diǎn)的抵達(dá)率的乘積。ξ表示迭代計(jì)算節(jié)點(diǎn)的每個(gè)出度到目標(biāo)節(jié)點(diǎn)的概率累加和與出度數(shù)量相除的函數(shù)。

1.2 用戶專家的引入

定義1用戶專家[11]：用戶u評(píng)論過(guò)的興趣點(diǎn)大于閾值φ且對(duì)某類興趣點(diǎn)有過(guò)評(píng)論，稱用戶u為這類興趣點(diǎn)的專家。用函數(shù)表示:

(2)

(3)

式(2)中:rui表示用戶u對(duì)興趣點(diǎn)i的評(píng)分；g(rui)表示對(duì)某類興趣點(diǎn)是否評(píng)論過(guò)。式(3)中：m為系統(tǒng)中用戶的數(shù)量；n為系統(tǒng)中興趣點(diǎn)的數(shù)量。

1.3 各種興趣點(diǎn)推薦算法比較

(1) 基于內(nèi)容的推薦 系統(tǒng)在不用獲得用戶對(duì)興趣點(diǎn)評(píng)價(jià)意見(jiàn)的情況下，通過(guò)學(xué)習(xí)用戶對(duì)選擇過(guò)偏好地點(diǎn)的內(nèi)容信息，來(lái)完成對(duì)新的興趣點(diǎn)喜好程度預(yù)測(cè)。如今基于內(nèi)容的推薦系統(tǒng)對(duì)用戶的歷史信息建立配置文件，通過(guò)對(duì)配置文件相似性的比較進(jìn)行推薦?；趦?nèi)容的推薦優(yōu)點(diǎn)為不需要考慮用戶-項(xiàng)目評(píng)價(jià)矩陣的稀疏性問(wèn)題，對(duì)冷啟動(dòng)的問(wèn)題也有一定緩解作用，并且有一套完善的理論體系進(jìn)行支撐。但缺點(diǎn)是由于基于內(nèi)容的推薦僅可以向用戶推薦與其歷史信息有關(guān)的項(xiàng)目，推薦結(jié)果易出現(xiàn)針對(duì)特定數(shù)據(jù)產(chǎn)生特定結(jié)果的問(wèn)題，算法的擴(kuò)展性不好，缺乏潛在挖掘能力。

(2) 基于協(xié)同過(guò)濾的推薦 基于協(xié)同過(guò)濾的興趣點(diǎn)推薦技術(shù)是根據(jù)使用者對(duì)興趣點(diǎn)的打分來(lái)預(yù)測(cè)興趣點(diǎn)對(duì)使用者的相關(guān)程度。其優(yōu)點(diǎn)有[7]：避免了基于內(nèi)容推薦時(shí)，項(xiàng)目關(guān)鍵詞提取準(zhǔn)確度不夠的問(wèn)題，可以發(fā)現(xiàn)用戶潛在興趣偏好；自適應(yīng)性好，能夠獲得用戶充分的隱式反饋。如今將協(xié)同過(guò)濾算法主要分為基于內(nèi)存和基于模型兩類?；趦?nèi)存的推薦核心思想是通過(guò)將使用者對(duì)項(xiàng)目的打分形成的矩陣進(jìn)行分析，確定與用戶相似度最高的最相關(guān)集合，進(jìn)而通過(guò)最相關(guān)集合內(nèi)用戶對(duì)某個(gè)項(xiàng)目的評(píng)分，來(lái)預(yù)測(cè)被推薦人對(duì)那些沒(méi)有評(píng)過(guò)分項(xiàng)目的評(píng)分?；谀Ｐ偷耐扑]算法，通過(guò)訓(xùn)練用戶-興趣點(diǎn)的評(píng)分矩陣形成決策模型，將貝葉斯網(wǎng)絡(luò)、聚類、降維等技術(shù)與基于模型的推薦進(jìn)行融合，從而對(duì)高維矩陣數(shù)據(jù)稀疏性問(wèn)題進(jìn)行處理[8]。

1.4 推薦系統(tǒng)評(píng)價(jià)指標(biāo)

定義2準(zhǔn)確率：準(zhǔn)確率為在所有推薦結(jié)果中用戶會(huì)感興趣的概率。推薦系統(tǒng)所推薦的興趣點(diǎn)會(huì)產(chǎn)生四種情況：用N1表示系統(tǒng)測(cè)算后推薦的興趣點(diǎn)用戶正好喜歡；N2表示系統(tǒng)測(cè)算后推薦的興趣點(diǎn)用戶不喜歡；N3表示用戶喜歡的推薦系統(tǒng)沒(méi)有進(jìn)行推薦；N4用戶不喜歡的興趣點(diǎn)并且系統(tǒng)沒(méi)有推薦。按照分?jǐn)?shù)高低的推薦數(shù)N=N1+N2，用M代表用戶喜歡的興趣點(diǎn)數(shù)，則M=N1+N3，則計(jì)算方法為：

(4)

定義3召回率：召回率表示為系統(tǒng)最終推薦給用戶喜歡的興趣點(diǎn)占全部興趣點(diǎn)的比例，則計(jì)算公式為：

(5)

2 融合相對(duì)評(píng)分的個(gè)性化興趣點(diǎn)推薦

2.1 評(píng)分描述個(gè)性化問(wèn)題

傳統(tǒng)的異構(gòu)社交網(wǎng)絡(luò)只考慮了節(jié)點(diǎn)類型和關(guān)系類型，而個(gè)性化推薦算法不僅僅要在用戶與興趣點(diǎn)的相似度度量準(zhǔn)確性上努力，還需要充分體現(xiàn)個(gè)性化程度[9]。目前大部分研究異構(gòu)信息網(wǎng)絡(luò)的個(gè)性化推薦中，都忽略了元路徑上的屬性值或者權(quán)重信息，然而在實(shí)際生活中，元路徑中帶有相關(guān)屬性信息的異構(gòu)社交網(wǎng)絡(luò)是非常普遍的[10]。我們?cè)赮elp數(shù)據(jù)集中通過(guò)用戶專家對(duì)商家的喜好不同，打出1～5分的評(píng)分來(lái)反映用戶本身的個(gè)性化信息。

當(dāng)出現(xiàn)相同的興趣點(diǎn)相似度時(shí)，傳統(tǒng)的相似度算法只能并行推薦，不能按照優(yōu)先順序進(jìn)行推薦。如果將用戶專家的評(píng)分作為權(quán)值引入到原路徑中去，通過(guò)權(quán)值大小為好友推薦，即使興趣點(diǎn)相似，也能通過(guò)權(quán)值更精確地推薦。為了能夠更精確地反映用戶的個(gè)性化信息，引入了帶權(quán)異構(gòu)社交網(wǎng)絡(luò)和帶權(quán)元路徑的概念。

2.2 概念擴(kuò)展

定義4帶權(quán)值的異構(gòu)社交網(wǎng)絡(luò)[11](WHSN)：已知由G=(V,E,A,W,S,φ，ψ)組成的社交網(wǎng)絡(luò)，其中：V是對(duì)象的集合，V={v1，v2，…,vn}，vi(1≤i≤n)代表網(wǎng)絡(luò)中的節(jié)點(diǎn)，n是節(jié)點(diǎn)的數(shù)量;E是鏈接的集合;A是對(duì)象類型的集合且φ:V→A是對(duì)象類型集合之間的映射函數(shù)，其中每個(gè)對(duì)象類型v∈V屬于一個(gè)特定的對(duì)象類型φ(v)∈A；W表示節(jié)點(diǎn)間屬性值的集合[11]。當(dāng)對(duì)象類型的數(shù)量|A|>1或者鏈接類型數(shù)|S|>1且|W|>0時(shí)，這個(gè)社交網(wǎng)絡(luò)為帶權(quán)值的異構(gòu)社交網(wǎng)絡(luò)；當(dāng)對(duì)象類型的數(shù)量|A|>1或者鏈接類型數(shù)|S|>1且|W|=0時(shí)為非帶權(quán)值的異構(gòu)社交網(wǎng)絡(luò)。

定義5帶權(quán)元路徑：帶權(quán)元路徑是節(jié)點(diǎn)間路徑上存在屬性值的一種元路徑，其符號(hào)表示：

其中：αi(si)表示元路徑關(guān)系S上的屬性值，若元路徑上屬性值取值為空，則這條路徑為非帶權(quán)元路徑，反之，這條元路徑為帶權(quán)元路徑。

2.3 用戶評(píng)分行為分析

如果用戶專家U1在帶權(quán)路徑下，同時(shí)對(duì)不同類型的商家A和商家B都打了4分，從直觀上無(wú)法確定U1更喜歡哪一個(gè)商家，這就需要從相對(duì)的角度去判斷，比如歷史的評(píng)分，同類商家的評(píng)分等發(fā)現(xiàn)用戶的偏好。為了提高對(duì)用戶興趣點(diǎn)推薦的準(zhǔn)確性，針對(duì)用戶在帶權(quán)異構(gòu)社交網(wǎng)絡(luò)下評(píng)分差異的問(wèn)題，我們從以下三個(gè)性質(zhì)對(duì)用戶評(píng)分行為進(jìn)行剖析[12]：

(1) 相對(duì)性 從用戶專家對(duì)興趣點(diǎn)的評(píng)分，僅能很局限地預(yù)測(cè)用戶的偏好，因?yàn)樵u(píng)分具有相對(duì)性，所以預(yù)測(cè)結(jié)果會(huì)產(chǎn)生一定的差異。例如，用戶專家U1對(duì)興趣點(diǎn)A的評(píng)分是4分，而他的歷史評(píng)分平均值在4.3分，我們可以分析出相對(duì)其他興趣點(diǎn)而言，U1不太喜歡興趣點(diǎn)A。由于評(píng)分存在相對(duì)性，為了更好地獲取用戶的偏好，不能僅僅使用單一絕對(duì)的評(píng)分值。為了更好地進(jìn)行個(gè)性化推薦，我們必須從相對(duì)的角度看待用戶的評(píng)分行為，用用戶評(píng)分的相對(duì)順序代替原來(lái)的具體數(shù)值，盡可能地學(xué)習(xí)用戶的偏好。

(2) 比較性 用戶對(duì)興趣點(diǎn)評(píng)分的過(guò)程，其實(shí)是一個(gè)比較的過(guò)程，與歷史評(píng)分進(jìn)行比較，與去過(guò)的興趣點(diǎn)進(jìn)行比較。所以用戶的評(píng)分并不是隨心所欲，互不影響的，是由心情、時(shí)間、回憶等多種因素影響的過(guò)程。為此本文通過(guò)對(duì)比篩選的過(guò)程來(lái)模擬。

(3) 時(shí)限性 根據(jù)心理學(xué)中的短期記憶效應(yīng)，考慮歷史評(píng)分要有一定的時(shí)間限制，不能把用戶所有的歷史簽到行為都考慮進(jìn)來(lái)。所以在比較模型中引入時(shí)間閾值的思想將用戶比較的歷史評(píng)分記錄限定在一定范圍內(nèi)。

通過(guò)上面對(duì)用戶評(píng)分行為的分析，本文提出了一種新的模型來(lái)學(xué)習(xí)以用戶評(píng)分來(lái)預(yù)測(cè)用戶的興趣偏好的問(wèn)題，這個(gè)模型是以效用理論作為基礎(chǔ)的選擇模型當(dāng)作參考而引出的。在時(shí)間閾值范圍內(nèi)，收集一個(gè)用戶專家的所有對(duì)興趣點(diǎn)的簽到評(píng)分記錄并形成一個(gè)評(píng)分矩陣，所有用戶專家評(píng)分矩陣形成一個(gè)數(shù)據(jù)集，每個(gè)集合中全部的興趣點(diǎn)都會(huì)有相應(yīng)的評(píng)分，并且將興趣點(diǎn)按照評(píng)分大小進(jìn)行排序后形成偏序關(guān)系集。用戶專家對(duì)某個(gè)興趣點(diǎn)評(píng)分高，可以推出他可能對(duì)這一類興趣點(diǎn)都感興趣。為了更好地預(yù)測(cè)用戶個(gè)性化偏好，可以在偏序關(guān)系的基礎(chǔ)上對(duì)于用戶的評(píng)分行為進(jìn)行學(xué)習(xí)。

2.4 相對(duì)評(píng)分問(wèn)題定義

我們?cè)赮elp數(shù)據(jù)集獲取了N個(gè)用戶專家和M個(gè)興趣點(diǎn)，定義U={u1，u2，…，un}為用戶集合，P={p1，p2，…，pn}為興趣點(diǎn)集合，U和P形成了一個(gè)用戶-興趣點(diǎn)的評(píng)分矩陣R，一個(gè)用戶ui會(huì)對(duì)一個(gè)興趣點(diǎn)pj進(jìn)行簽到評(píng)分rij。針對(duì)基于位置的異構(gòu)社交網(wǎng)絡(luò)進(jìn)行研究，要求用戶專家的評(píng)分記錄在設(shè)定的時(shí)間戳內(nèi)，按照先后順序進(jìn)行排序，并將評(píng)分集合形成的屬性集稱為時(shí)限簽到集合。

定義6時(shí)限簽到集合：時(shí)限簽到集合記錄了用戶專家在時(shí)間閾值T內(nèi)，在相應(yīng)的時(shí)間對(duì)相應(yīng)的興趣點(diǎn)的評(píng)分信息，于是有：

(6)

式中：t(i，pj)表示ui對(duì)pj的簽到時(shí)間，是指用戶i所有的簽到評(píng)分記錄中以興趣點(diǎn)j為起點(diǎn)以時(shí)間閾值T為約束的所有簽到評(píng)分的集合，其中pk、pj代表興趣點(diǎn)，rik是用戶i對(duì)興趣點(diǎn)k的評(píng)分。

為了更好地解決數(shù)據(jù)稀疏性問(wèn)題，找到合適的時(shí)間閾值，我們用用戶專家評(píng)分的前K次記錄來(lái)模擬時(shí)間閾值。按照時(shí)間順序，將用戶-興趣點(diǎn)評(píng)分矩陣中的每一行用戶評(píng)分信息進(jìn)行排列，在時(shí)間閾值的范圍內(nèi)形成一個(gè)集合，也可根據(jù)用戶專家對(duì)興趣點(diǎn)信息打分的分值由高到低進(jìn)行排列，從而構(gòu)成一個(gè)偏序關(guān)系，用符號(hào)表示為：

(7)

2.5 用戶評(píng)分行為建模

pj?phIIFZ(ui,pj)≥Z(ui,ph)

(8)

式中：Zij表示Z(ui，pj)的簡(jiǎn)化形式。興趣點(diǎn)j的效用值比h的效用值高時(shí)，證明用戶相對(duì)于h來(lái)說(shuō)更喜歡j。

根據(jù)隨機(jī)效用模型RUM(Random Utility Model)[14]，效用由以下兩部分構(gòu)成，其公式化表示為：

Z(ui,pj)=Q(ui，pj)+εij

(9)

式中：Q(ui，pj)=rij表示顯示效用，即可以通過(guò)某種方式觀察到的，例如對(duì)興趣點(diǎn)的相對(duì)評(píng)分；而εij代表隱式效用，例如一些偶然事件。為了方便研究，本文用矩陣分解中常用的隱式因子來(lái)表示評(píng)分rij。由于用戶在對(duì)興趣點(diǎn)評(píng)分時(shí)會(huì)受到一定的隱性因素影響，而一部分對(duì)評(píng)分產(chǎn)生影響的隱因子可以成為用戶對(duì)興趣點(diǎn)的興趣維度。

基于效用的用戶興趣偏好度表示為：

Pro(pj?ph)=Pro(Z(ui,pj)≥Z(ui,ph))

(10)

將式(10)代入式(11)得：

Pro(pj?ph)=Pro(Q(ui，pj)+εij≥Q(ui，ph)+εih)=

Pro(Q(ui，pj)-Q(ui，ph)+εij≥εih)

(11)

根據(jù)Logit模型，按照雙重指數(shù)表示更為準(zhǔn)確，于是推導(dǎo)出用戶對(duì)兩個(gè)興趣點(diǎn)的偏好度形式化為：

(12)

(2) 用戶評(píng)分選擇模型 在Yelp數(shù)據(jù)集中，存在大量的評(píng)分?jǐn)?shù)據(jù)和近期簽到集合，集合的整體興趣偏好度公式可表示為：

(13)

式中：Q(u)代表用戶專家u所有的興趣點(diǎn)簽到集合。和前面一樣使用隱性因子Z、Q來(lái)表示效用，為了避免過(guò)擬合現(xiàn)象，對(duì)Z和Q進(jìn)行先驗(yàn)，即一個(gè)球形多變量的高斯先驗(yàn)：

Pro(Z,Q|Θ)=N(Z,Q|0,σ2I)

(14)

圖1是基于比較的用戶評(píng)分行為對(duì)應(yīng)圖模型。其中:≥T表示觀測(cè)變量，即為有時(shí)間閾值約束的興趣點(diǎn)簽到集合，Zi和Qj表示需要學(xué)習(xí)的未知變量。根據(jù)矩陣分解理論，當(dāng)Zi和Qj獲得后，用戶對(duì)興趣點(diǎn)的效用值可以被近似地算出，兩個(gè)參數(shù)σZ和σQ是先驗(yàn)超參，M和N分別代表興趣點(diǎn)數(shù)目和用戶的數(shù)目。

圖1 用戶比較模型圖

根據(jù)貝葉斯原理，求得后驗(yàn)概率為：

Pro(Z,Q|?T)∝Pro(?T|Z,Q)Pro(Z|Θ)Pro(Q|Θ)

(15)

同樣，我們將目標(biāo)函數(shù)化成對(duì)數(shù)形式：

{Z,Q}= arg min-[logPro(?T|Z,Q)+

logPro(Z,Q|Θ)]

(16)

式中:第二項(xiàng)可以看作是消除過(guò)擬合問(wèn)題的正則化項(xiàng)，并且{Z，Q}服從高斯先驗(yàn)。根據(jù)隨機(jī)梯度下降原理[16]每次優(yōu)化時(shí)隨機(jī)選取一個(gè)用戶專家對(duì)興趣點(diǎn)的評(píng)分，只針對(duì)于該評(píng)分相關(guān)的用戶和興趣點(diǎn)的隱式因子進(jìn)行優(yōu)化，由于使用ZQT來(lái)度量rij,則對(duì)Z和Q的推導(dǎo)公式為：

(17)

(18)

最終基于比較的用戶相對(duì)評(píng)分預(yù)測(cè)值為：

(19)

2.6 融合相對(duì)評(píng)分的個(gè)性化推薦

通過(guò)前面的學(xué)習(xí)，形成了用戶-興趣點(diǎn)的相對(duì)評(píng)分矩陣β∈RN×M，其中相對(duì)評(píng)分矩陣β中的每個(gè)元素β(u,p)代表用戶專家u對(duì)特定興趣點(diǎn)p的相對(duì)評(píng)分。把基于位置的社交網(wǎng)絡(luò)模型中元路徑的權(quán)值用用戶u對(duì)興趣點(diǎn)p的相對(duì)評(píng)分來(lái)表示，從而提出MpgbCount推薦算法，用公式表示為：

(20)

式中：pro(i,j)表示特定元路徑L下節(jié)點(diǎn)i到達(dá)節(jié)點(diǎn)j的概率；βij為節(jié)點(diǎn)i到節(jié)點(diǎn)j的路徑權(quán)值，即用戶專家i對(duì)興趣點(diǎn)j的相對(duì)評(píng)分。

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

本節(jié)將MpgbCount算法與其他個(gè)性化推薦算法進(jìn)行對(duì)比，驗(yàn)證本文所提方法的優(yōu)越性。實(shí)驗(yàn)環(huán)境為聯(lián)想筆記本，Intel i5，內(nèi)存為8 GB，采用Java語(yǔ)言編寫(xiě)。

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

本文通過(guò)Yelp數(shù)據(jù)集、FoursquareAll全球數(shù)據(jù)集和FoursquareNY紐約數(shù)據(jù)集對(duì)MpgbCount算法進(jìn)行評(píng)估。Foursquare數(shù)據(jù)集是通過(guò)公開(kāi)的API抓取的，如表1所示。

表1 Foursquare數(shù)據(jù)集整理

用戶可以在Yelp網(wǎng)站對(duì)自己感興趣的地點(diǎn)進(jìn)行簽到，分享給好友，對(duì)商家進(jìn)行打分或者添加評(píng)論信息，所以可通過(guò)Yelp數(shù)據(jù)集對(duì)MpgbCount算法進(jìn)行評(píng)估。由于存在低頻用戶，使得數(shù)據(jù)存在稀疏性，為了不影響個(gè)性化推薦的結(jié)果，我們對(duì)數(shù)據(jù)進(jìn)行了一定的預(yù)處理，篩選出符合用戶專家標(biāo)準(zhǔn)的用戶數(shù)據(jù)進(jìn)行測(cè)驗(yàn)。經(jīng)過(guò)篩選，得到20 166個(gè)用戶和39 104個(gè)興趣點(diǎn)信息，總計(jì)評(píng)分?jǐn)?shù)為152 721個(gè)。為了方便進(jìn)行實(shí)驗(yàn)，將數(shù)據(jù)分成訓(xùn)練集和測(cè)試集兩部分，并將整體數(shù)據(jù)的90%最為訓(xùn)練集，剩余的10%作為測(cè)試集。表2為Yelp數(shù)據(jù)集整理。

表2 Yelp數(shù)據(jù)集整理

通過(guò)圖2所展示的用戶對(duì)興趣點(diǎn)評(píng)分的分類，我們發(fā)現(xiàn)大部分用戶對(duì)自己喜歡的興趣點(diǎn)都打了4～5分，而且很多用戶在對(duì)興趣點(diǎn)簽到時(shí)就會(huì)對(duì)興趣點(diǎn)進(jìn)行評(píng)分。

圖2 用戶評(píng)分直方圖

在實(shí)驗(yàn)方面，將MpgbCount推薦算法與其他經(jīng)典的算法進(jìn)行對(duì)比，通過(guò)準(zhǔn)確率和召回率的高低來(lái)衡量個(gè)性化推薦系統(tǒng)的好壞。

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

在基于元路徑的個(gè)性化興趣點(diǎn)推薦方面，目前只有曹玖新等[6]發(fā)表了一篇文章，但其并沒(méi)有考慮到元路徑的權(quán)值信息和元路徑節(jié)點(diǎn)間相遇的問(wèn)題。本文采用雙向元路徑誘導(dǎo)相似度的方式，將用戶評(píng)分信息作為元路徑的權(quán)值，解決了文獻(xiàn)[6]的M算法中存在的元路徑相遇和權(quán)值信息的問(wèn)題。在Yelp數(shù)據(jù)集所組成的帶權(quán)異構(gòu)社交網(wǎng)絡(luò)下，將本文所提出的MpgbCount算法與文獻(xiàn)[6]的M算法以及文獻(xiàn)[17]中所提到的常見(jiàn)的算法進(jìn)行對(duì)比。

由于評(píng)分具有時(shí)效性，需要分析時(shí)間閾值對(duì)算法產(chǎn)生的影響。我們用所記評(píng)分之前k次來(lái)代替時(shí)間閾值T，代表用戶通過(guò)短期記憶能夠?qū)⒍嗌賯€(gè)以前的評(píng)分進(jìn)行綜合考慮。圖3顯示了時(shí)間閾值k的取值對(duì)Recall的影響?？梢钥闯觯?dāng)用戶專家在評(píng)分時(shí)考慮相對(duì)較少的歷史評(píng)分時(shí)，短期記憶占了主導(dǎo)地位，這時(shí)算法隨k的升高而有所下降，所以時(shí)間閾值T的選取需要具體衡量。在與其他算法進(jìn)行比較時(shí)，需根據(jù)實(shí)驗(yàn)結(jié)果的具體情況選擇相對(duì)應(yīng)的k值進(jìn)行計(jì)算。

圖3 時(shí)間閾值對(duì)Recall的影響

本文在同等情況下對(duì)表3中的算法進(jìn)行對(duì)比，并通過(guò)準(zhǔn)確率和召回率來(lái)度量算法的優(yōu)劣。由于MpgbCount算法綜合考慮了用戶與用戶之間、興趣點(diǎn)與興趣點(diǎn)之間、用戶與興趣點(diǎn)之間的各種關(guān)聯(lián)情況，進(jìn)而對(duì)各節(jié)點(diǎn)之間潛在的相關(guān)性進(jìn)行挖掘，該算法相較于其他未充分考慮節(jié)點(diǎn)關(guān)系及單純考慮用戶評(píng)分分值的算法推薦效果提升明顯。

表3 各種算法簡(jiǎn)單描述

各算法的準(zhǔn)確率如圖4所示，召回率如圖5所示。不難發(fā)現(xiàn)，本文所提到的MpgbCount算法在準(zhǔn)確率和召回率兩個(gè)方面都有很好的表現(xiàn)，本文算法相比M算法在推薦方面具有一定的優(yōu)勢(shì)，相比其他算法優(yōu)勢(shì)更加明顯。所以在帶權(quán)值的異構(gòu)社交網(wǎng)絡(luò)的研究中，本文所提出的MpgbCount的算法對(duì)興趣點(diǎn)的個(gè)性化推薦有著很好的效果。

圖4 Yelp數(shù)據(jù)集中各算法推薦結(jié)果的準(zhǔn)確率

圖5 Yelp數(shù)據(jù)集中各算法推薦結(jié)果的召回率

針對(duì)LBSN常見(jiàn)的數(shù)據(jù)稀疏性問(wèn)題，將MpgbCount算法和表3中的各種算法在Foursquare兩種稀疏性不同的數(shù)據(jù)集上進(jìn)行準(zhǔn)確性測(cè)試，結(jié)果如表4所示。本文所提出的MpgbCount算法在準(zhǔn)確性上降低的范圍在10%～15%之間，而其他算法的降低范圍都在15%以上，甚至有很多在20%以上。由此可以證明本文所提出的MpgbCount算法對(duì)數(shù)據(jù)的稀疏性有一定程度的緩解。

表4 各算法在Foursquare不同數(shù)據(jù)集準(zhǔn)確率對(duì)比

4 結(jié) 語(yǔ)

本文針對(duì)LBSN中基于雙向元路徑的興趣點(diǎn)推薦問(wèn)題，在完成異構(gòu)社交網(wǎng)絡(luò)下對(duì)不同類型節(jié)點(diǎn)間進(jìn)行相似度測(cè)量的前提下，提出了融合相對(duì)評(píng)分的個(gè)性化推薦算法。對(duì)興趣點(diǎn)推薦系統(tǒng)中以用戶對(duì)興趣點(diǎn)評(píng)分的形式描述個(gè)性化的問(wèn)題，并就單純的評(píng)分分值在一定程度上存在用戶偏好誤差的問(wèn)題進(jìn)行深入研究。從評(píng)分的時(shí)效性和相對(duì)性角度出發(fā)，對(duì)用戶的評(píng)分行為進(jìn)行分析，基于比較模型和效用理論提出相對(duì)評(píng)分概念，構(gòu)建用戶相對(duì)評(píng)分選擇模型。將相對(duì)評(píng)分轉(zhuǎn)化為元路徑的權(quán)值，構(gòu)成帶權(quán)元路徑，可以更好地度量用戶與興趣點(diǎn)間的相似度，最后通過(guò)個(gè)性化推薦算法生成推薦列表。實(shí)驗(yàn)顯示，本文算法相比其他推薦算法推薦效果更佳，并且對(duì)數(shù)據(jù)稀疏性由一定的緩解作用。