基于LBSN動(dòng)態(tài)異構(gòu)網(wǎng)絡(luò)的時(shí)間感知興趣點(diǎn)推薦

李 全，許新華，劉興紅，林 松

湖北師范大學(xué) 教育信息與技術(shù)學(xué)院，湖北 黃石435002

1 引言

隨著移動(dòng)設(shè)備和全球定位系統(tǒng)（GPS）的快速發(fā)展，人們?nèi)粘Ｊ褂玫闹悄芙K端提供的位置定位功能越來(lái)越精確。在此背景下，基于位置的社交網(wǎng)絡(luò)（Location-Based Social Network，LBSN）服務(wù)得到迅速的發(fā)展，且受到了廣大用戶的喜愛(ài)，如國(guó)外比較主流的Gowalla、Yelp和Facebook Places等，國(guó)內(nèi)比較主流的嘀咕和街旁等[1]。相對(duì)于傳統(tǒng)的社交網(wǎng)絡(luò)，LBSN 優(yōu)勢(shì)在于用戶能夠以簽到的形式發(fā)布他們的地理簽到信息，并對(duì)已訪問(wèn)的興趣點(diǎn)（Point-Of-Interest，POI），例如咖啡廳、餐館和電影院等，與朋友分享他們的體驗(yàn)和經(jīng)驗(yàn)。在一個(gè)城市里可能包含成千上萬(wàn)的興趣點(diǎn)，但用戶可能只想訪問(wèn)它們的一小部分。因此興趣點(diǎn)推薦的任務(wù)就是幫助用戶推薦新的感興趣的位置[2]。

相對(duì)于傳統(tǒng)推薦系統(tǒng)，興趣點(diǎn)推薦系統(tǒng)的發(fā)展更加復(fù)雜。首先在基于位置的社交網(wǎng)絡(luò)中用戶訪問(wèn)興趣點(diǎn)只占非常小的比例，興趣點(diǎn)推薦面臨數(shù)據(jù)稀疏性問(wèn)題。然后用戶通常喜歡訪問(wèn)當(dāng)前所在位置附近的興趣點(diǎn)。最后隨著不同的時(shí)間，用戶的興趣是動(dòng)態(tài)變化的。例如，在日常生活中，有些人喜歡中午喝咖啡，有些人喜歡晚上去酒吧等。因此興趣點(diǎn)推薦系統(tǒng)應(yīng)該考慮位置影響、社會(huì)關(guān)系和時(shí)間影響等上下文信息[3-4]。基于以上考慮，本文提出了一種基于LBSN 動(dòng)態(tài)異構(gòu)網(wǎng)絡(luò)的時(shí)間感知興趣點(diǎn)推薦算法。本文的主要貢獻(xiàn)如下：首先在LBSN異構(gòu)網(wǎng)絡(luò)模式中增加了會(huì)話節(jié)點(diǎn)類型，通過(guò)動(dòng)態(tài)元路徑，在用戶和興趣點(diǎn)語(yǔ)義關(guān)系之間有效融入時(shí)間信息、位置信息和社交信息等。其次設(shè)置了用戶-興趣點(diǎn)之間的元路徑集，并提出了不同動(dòng)態(tài)元路徑對(duì)應(yīng)的路徑實(shí)例偏好度的計(jì)算方法。然后采用矩陣分解模型對(duì)不同動(dòng)態(tài)偏好矩陣進(jìn)行矩陣分解。最后根據(jù)不同動(dòng)態(tài)元路徑對(duì)應(yīng)的用戶特征矩陣和興趣點(diǎn)特征矩陣，獲取用戶在不同的時(shí)間訪問(wèn)興趣點(diǎn)的top-k 推薦列表，從而有效地豐富數(shù)據(jù)，解決數(shù)據(jù)稀疏性問(wèn)題，提高興趣點(diǎn)推薦的實(shí)時(shí)性和準(zhǔn)確性。

2 相關(guān)技術(shù)

協(xié)同過(guò)濾推薦系統(tǒng)包括基于鄰域協(xié)同過(guò)濾和基于模型協(xié)同過(guò)濾?；卩徲騾f(xié)同過(guò)濾又可以分為基于用戶（User-based）協(xié)同過(guò)濾和基于項(xiàng)目（Item-based）協(xié)同過(guò)濾，但它們通常面臨著冷啟動(dòng)、數(shù)據(jù)稀疏、算法可擴(kuò)展性差等問(wèn)題[5]。隨著基于位置社交網(wǎng)絡(luò)的快速發(fā)展，興趣點(diǎn)推薦可為人們提供更好的基于位置的服務(wù)，受到學(xué)術(shù)界和工業(yè)界的廣泛關(guān)注。基于協(xié)同過(guò)濾的推薦技術(shù)被應(yīng)用到興趣點(diǎn)推薦中。由于興趣點(diǎn)推薦的簽到數(shù)據(jù)具有高稀疏性，因此基于協(xié)同過(guò)濾方法很容易遭受數(shù)據(jù)稀疏問(wèn)題。當(dāng)前許多研究試圖利用并融合地理影響和社會(huì)影響等來(lái)提高興趣點(diǎn)推薦的效果。

在融合社交信息方面：Zhang 等[6]將用戶間的相似性關(guān)系嵌入到基于用戶的協(xié)同過(guò)濾技術(shù)中；Ye等[7]利用用戶社交網(wǎng)絡(luò)中好友的協(xié)同評(píng)分以及通過(guò)距離衡量好友之間的相似性來(lái)進(jìn)行興趣點(diǎn)推薦。在融合地理位置信息方面：Lian 等[8]提出一種結(jié)合地理影響的加權(quán)矩陣分解方法；Hu等[9]基于非負(fù)矩陣分解模型融合用戶的興趣類別和地理位置信息進(jìn)行興趣點(diǎn)推薦，采用用戶的鄰居影響因素對(duì)地理位置信息進(jìn)行建模。在融合社交信息和地理位置信息方面：Ye等[10]關(guān)于興趣點(diǎn)推薦采用線性插值的方法結(jié)合地理與社會(huì)影響應(yīng)用到基于用戶的協(xié)同過(guò)濾框架中；Cheng等[11]將用戶社交關(guān)系和地理位置融入概率矩陣分解模型。通過(guò)建立用戶在位置上的簽到概率模型作為多中心高斯模型來(lái)捕獲地理影響力，繼而把社交信息和地理信息融入到一個(gè)概率的矩陣分解模型中。以上方法都是從融合社交信息和地理信息的角度解決興趣點(diǎn)推薦數(shù)據(jù)稀疏問(wèn)題，但用戶的興趣在不用的時(shí)間是動(dòng)態(tài)變化的，因此它們忽略了時(shí)間信息。

現(xiàn)有的基于時(shí)間感知的興趣點(diǎn)推薦系統(tǒng)主要將時(shí)間劃分為若干個(gè)時(shí)間間隙，并根據(jù)時(shí)隙將用戶簽到信息進(jìn)行劃分，最后融入時(shí)間信息和其他信息實(shí)現(xiàn)基于協(xié)同過(guò)濾的興趣點(diǎn)推薦。例如：Gao 等[12]提出了融合時(shí)間影響的興趣點(diǎn)推薦模型。該模型通過(guò)矩陣分解方法獲取某時(shí)隙的用戶潛在特征矩陣和位置潛在特征矩陣，最后將所有時(shí)隙的用戶潛在特征矩陣作為正則化項(xiàng)實(shí)現(xiàn)時(shí)間感知的興趣點(diǎn)推薦。Yuan 等[13]提出了一個(gè)名為UTE-SE的時(shí)間感知興趣點(diǎn)推薦模型。計(jì)算不同時(shí)隙簽到點(diǎn)的相似度，并采用平滑技術(shù)對(duì)簽到矩陣進(jìn)行處理，解決數(shù)據(jù)稀疏問(wèn)題。最后將時(shí)間信息和位置信息融入到基于用戶協(xié)同過(guò)濾推薦中。以上基于時(shí)間感知的興趣點(diǎn)推薦方法考慮了時(shí)間信息和地理信息，但它們的可擴(kuò)展性較差，在解決數(shù)據(jù)稀疏方面無(wú)法融合更多豐富的信息。

為了更好地解決簽到數(shù)據(jù)稀疏和用戶興趣動(dòng)態(tài)變化等問(wèn)題，本文提出了一種基于LBSN動(dòng)態(tài)異構(gòu)網(wǎng)絡(luò)的時(shí)間感知興趣點(diǎn)推薦算法。該算法優(yōu)勢(shì)在于：

（1）在LBSN 異構(gòu)網(wǎng)絡(luò)中增加時(shí)間感知層，定義會(huì)話節(jié)點(diǎn)的重要度，通過(guò)參數(shù)使得與目標(biāo)時(shí)間強(qiáng)相關(guān)的會(huì)話節(jié)點(diǎn)增加，并且與目標(biāo)時(shí)間越近的會(huì)話節(jié)點(diǎn)具有更大的權(quán)重，從而提高了興趣點(diǎn)推薦的實(shí)時(shí)性和準(zhǔn)確性。

（2）設(shè)置了用戶-興趣點(diǎn)之間的動(dòng)態(tài)元路徑集。在此基礎(chǔ)上，通過(guò)計(jì)算動(dòng)態(tài)路徑實(shí)例的偏好度構(gòu)造用戶-興趣點(diǎn)動(dòng)態(tài)偏好矩陣，從而有效融入時(shí)間信息、位置信息和社交信息，緩解興趣點(diǎn)推薦中數(shù)據(jù)稀疏問(wèn)題。

（3）提出了一種基于LBSN動(dòng)態(tài)異構(gòu)網(wǎng)絡(luò)的興趣點(diǎn)推薦算法，對(duì)不同動(dòng)態(tài)偏好矩陣進(jìn)行矩陣分解，根據(jù)不同動(dòng)態(tài)元路徑的用戶特征矩陣和興趣點(diǎn)特征矩陣，獲取用戶在目標(biāo)時(shí)間訪問(wèn)興趣點(diǎn)的推薦列表，從而實(shí)現(xiàn)更加人性化的興趣點(diǎn)推薦任務(wù)。

3 問(wèn)題定義

3.1 LBSN動(dòng)態(tài)異構(gòu)網(wǎng)絡(luò)

異構(gòu)網(wǎng)絡(luò)是指由不同類型節(jié)點(diǎn)的集合和不同類型邊的集合構(gòu)成的有向圖?；谖恢蒙缃痪W(wǎng)絡(luò)是一種典型異構(gòu)信息網(wǎng)絡(luò)。由于用戶簽到偏好是動(dòng)態(tài)變化的，因此為了表示用戶在不同時(shí)間簽到偏好，在LBSN異構(gòu)信息網(wǎng)絡(luò)中加入會(huì)話節(jié)點(diǎn)，其定義如下。

定義1（LBSN動(dòng)態(tài)異構(gòu)網(wǎng)絡(luò)）LBSN動(dòng)態(tài)異構(gòu)網(wǎng)絡(luò)被定義為四元組G ＜Us,Ss,Ls,Es＞，其中Us表示網(wǎng)絡(luò)中所有用戶節(jié)點(diǎn)的集合，其中Us={u1,u2,…,un} 。 Ss表示網(wǎng)絡(luò)中所有會(huì)話節(jié)點(diǎn)的集合，其中Ss={sij|1 ≤i ≤n,1 ≤j ≤24}。Ls表示網(wǎng)絡(luò)中所有興趣點(diǎn)節(jié)點(diǎn)的集合，其中Ls={l1,l2,…,lm}。Es表示網(wǎng)絡(luò)中所有邊的集合，其中Es=EUU?EUS?ESL?ELL。EUU={(ui,uj)|ui,uj∈Us}表示用戶ui和用戶uj之間的好友關(guān)系，EUS={(ui,sij)|ui∈Us,sij∈Ss}表示用戶ui在時(shí)間tj有簽到行為，ESL={(sij,lk,)|sij∈Ss,lk∈Ls}表示用戶ui在時(shí)間tj訪問(wèn)興趣點(diǎn)lk，ELL={(li,lj)|li,lj∈Ls}表示興趣點(diǎn)li和興趣點(diǎn)lj之間的位置關(guān)系。LBSN動(dòng)態(tài)異構(gòu)網(wǎng)絡(luò)如圖1所示。

圖1 LBSN動(dòng)態(tài)異構(gòu)網(wǎng)絡(luò)圖

3.2 LBSN動(dòng)態(tài)網(wǎng)絡(luò)模式

網(wǎng)絡(luò)模式概念類似于數(shù)據(jù)庫(kù)中E-R圖，它是由不同實(shí)體型和聯(lián)系類型構(gòu)成的有向圖，其定義如下。

定義2（LBSN動(dòng)態(tài)網(wǎng)絡(luò)模式）LBSN動(dòng)態(tài)網(wǎng)絡(luò)模式被定義為四元組G ＜U,S,L,R ＞，其中U 表示用戶節(jié)點(diǎn)類型，S 表示會(huì)話節(jié)點(diǎn)類型，L 表示興趣點(diǎn)節(jié)點(diǎn)類型。聯(lián)系類型為R={RUU,RUS,RSL,RLL}，其中RUU表示用戶之間的好友關(guān)系，RUS表示用戶與時(shí)間之間的會(huì)話關(guān)系。 RSL表示用戶在某時(shí)間和興趣點(diǎn)的簽到關(guān)系。RLL表示興趣點(diǎn)之間的位置關(guān)系。LBSN動(dòng)態(tài)網(wǎng)絡(luò)模式如圖2所示。

圖2 LBSN動(dòng)態(tài)網(wǎng)絡(luò)模式圖

3.3 LBSN動(dòng)態(tài)元路徑與路徑實(shí)例

元路徑用來(lái)描述網(wǎng)絡(luò)模式中兩類對(duì)象之間的連接路徑[14]。不同的元路徑代表了對(duì)象類型之間可以通過(guò)不同節(jié)點(diǎn)類型和聯(lián)系類型建立不同的語(yǔ)義關(guān)系。LBSN動(dòng)態(tài)元路徑和動(dòng)態(tài)路徑實(shí)例定義如下。

定義3（LBSN動(dòng)態(tài)元路徑）在LBSN動(dòng)態(tài)網(wǎng)絡(luò)模式G ＜U,S,L,R ＞中，LBSN 動(dòng)態(tài)元路徑定義為如下形式：

定義4（LBSN動(dòng)態(tài)路徑實(shí)例）在LBSN動(dòng)態(tài)異構(gòu)網(wǎng)絡(luò)G ＜Us,Ss,Ls,Es＞中，對(duì)于元路徑An，若存在真實(shí)的路徑p=(v1,v2,…,vn)，其中，vi∈{Us,Ss,Ls}，vi和vi+1之間的類型為Es。那么動(dòng)態(tài)路徑p稱為動(dòng)態(tài)元路徑P 的一條動(dòng)態(tài)路徑實(shí)例。

例如，在LBSN 動(dòng)態(tài)網(wǎng)絡(luò)模式G ＜U,S,L,R ＞中存在一條動(dòng)態(tài)元路徑U →S →L →L。該元路徑表示用戶可能喜歡與某個(gè)時(shí)間訪問(wèn)過(guò)的興趣點(diǎn)位置相關(guān)的興趣點(diǎn)。該動(dòng)態(tài)元路徑對(duì)應(yīng)的動(dòng)態(tài)路徑實(shí)例如圖3所示。

圖3 動(dòng)態(tài)路徑實(shí)例圖

4 基于LBSN動(dòng)態(tài)異構(gòu)網(wǎng)絡(luò)興趣點(diǎn)推薦

4.1 LBSN動(dòng)態(tài)元路徑集

基于LBSN動(dòng)態(tài)網(wǎng)絡(luò)模式，確定起始于用戶節(jié)點(diǎn)類型且終止于興趣點(diǎn)節(jié)點(diǎn)類型的元路徑集。已有大量研究表明[15-16]，相距3 度之內(nèi)的是強(qiáng)連接，超過(guò)則為弱連接，通常研究長(zhǎng)度在3 以內(nèi)的路徑。但考慮LBSN 中時(shí)間信息對(duì)興趣點(diǎn)推薦的實(shí)時(shí)性以及簽到數(shù)據(jù)的稀疏性，結(jié)合實(shí)際情況，本文的動(dòng)態(tài)元路徑集包括2 條3 度以內(nèi)的元路徑和3條4度以內(nèi)的元路徑，具體如表1所示。

表1 用戶-興趣點(diǎn)之間動(dòng)態(tài)元路徑集表

4.2 基于LBSN動(dòng)態(tài)元路徑的偏好度計(jì)算

已知LBSN 動(dòng)態(tài)異構(gòu)網(wǎng)絡(luò)G ＜Us,Ss,Ls,Es＞，則在目標(biāo)時(shí)間td，以v1(v1∈Us)為起點(diǎn)、vn(vn∈Ls)為終點(diǎn)的基于動(dòng)態(tài)元路徑P 的偏好度為該元路徑對(duì)應(yīng)的動(dòng)態(tài)實(shí)例路徑集P′偏好度之和，計(jì)算公式如公式（1）所示：

其中，simp,td(v1,vn)表示在目標(biāo)時(shí)間td基于動(dòng)態(tài)實(shí)例路徑p 得到的用戶和興趣點(diǎn)之間偏好度。simp,td(v1,vn)=，其中為動(dòng)態(tài)實(shí)例路徑p 中節(jié)點(diǎn)vi和節(jié)點(diǎn)vi+1邊的權(quán)重。LBSN動(dòng)態(tài)異構(gòu)網(wǎng)絡(luò)一共有4種類型邊的權(quán)重，分別為WUU、WUS、WSL和WLL，其中WUU={wui,uj|(ui,uj)∈EUU}表示用戶和用戶邊的權(quán)值集合，WUS={wui,sij|(ui,sij)∈EUS} 表示用戶和會(huì)話邊的權(quán)值集合，WSL={wsij,lk|(sij,lk)∈ESL}表示會(huì)話和興趣點(diǎn)邊的權(quán)值集合，WLL={wli,lj|(li,lj)∈ELL}表示興趣點(diǎn)和興趣點(diǎn)邊的權(quán)值集合。異構(gòu)網(wǎng)絡(luò)中邊權(quán)值有計(jì)數(shù)計(jì)量、二值計(jì)量和對(duì)數(shù)計(jì)量等方法，其中二值表示權(quán)值一般獲得較好的推薦結(jié)果。因此，對(duì)于用戶與用戶邊，如果用戶之間存在好友關(guān)系，則權(quán)值均為1，否則為0。對(duì)于會(huì)話與興趣點(diǎn)邊，如果用戶于某時(shí)間在興趣點(diǎn)有過(guò)簽到行為，則權(quán)值均為1，否則為0。但是，為了更好地反映用戶興趣變化的時(shí)間屬性和興趣點(diǎn)的距離屬性，用戶和會(huì)話邊的權(quán)值及興趣點(diǎn)和興趣點(diǎn)邊的權(quán)值采用如下方法確定。

4.2.1 用戶和會(huì)話邊的權(quán)值

時(shí)間感知興趣點(diǎn)推薦的任務(wù)是為目標(biāo)用戶ui在目標(biāo)時(shí)間td推薦其感興趣的興趣點(diǎn)。由文獻(xiàn)[17]可知，當(dāng)用戶ui在時(shí)間tj有簽到行為時(shí)，與目標(biāo)時(shí)間td越近的會(huì)話節(jié)點(diǎn)對(duì)推薦任務(wù)就越重要。因此，將會(huì)話節(jié)點(diǎn)的重要度定義如公式（2）所示，并將用戶和會(huì)話邊的權(quán)值設(shè)置為會(huì)話節(jié)點(diǎn)的重要度，即wuisij( )tj,td=f( )tj,td。

其中，H 是一個(gè)控制會(huì)話節(jié)點(diǎn)時(shí)間影響度的參數(shù)。當(dāng)|tj-td|≤12 時(shí)，兩個(gè)時(shí)間的距離為 |tj-td|；當(dāng) |tj-td|＞12 時(shí)，兩個(gè)時(shí)間的距離為24- ||tj-td。

4.2.2 興趣點(diǎn)和興趣點(diǎn)邊的權(quán)值

用戶一般喜歡訪問(wèn)距離較近的興趣點(diǎn)。本文采用如下方法確定用戶從一個(gè)位置轉(zhuǎn)移到另一個(gè)位置的偏好度。首先獲取位置之間的空間距離樣本Y ，如公式（3）所示[18]：

其中l(wèi)i，lj為兩個(gè)位置的經(jīng)度和緯度坐標(biāo)，Haversine 是一個(gè)空間距離函數(shù)，用于計(jì)算兩個(gè)位置之間的空間距離。然后，采用距離dis(dis ∈Y)的冪律函數(shù)表示位置轉(zhuǎn)移的偏好度，如公式（4）所示：

其中，γ 是冪律函數(shù)的參數(shù)，它可以通過(guò)公式（5）得到：

本文將興趣點(diǎn)間邊的權(quán)值設(shè)置為位置轉(zhuǎn)移的偏好度，且wlilj=pr(dis)。

4.3 基于動(dòng)態(tài)元路徑的興趣點(diǎn)推薦

在LBSN 動(dòng)態(tài)異構(gòu)網(wǎng)絡(luò)G ＜Us,Ss,Ls,Es＞中，已知?jiǎng)討B(tài)元路徑Pk∈{P1,P2,P3,P4,P5}和目標(biāo)時(shí)間td，構(gòu)造用戶-興趣點(diǎn)動(dòng)態(tài)偏好矩陣MPk,td，該矩陣的元素MPk,td(i,j)表示用戶ui∈Us和興趣點(diǎn)lj∈Ls在元路徑Pk下所有路徑實(shí)例的權(quán)重之和，且MPk,td(i,j)=simPk,td(ui,lj)。五個(gè)元路徑對(duì)應(yīng)的動(dòng)態(tài)偏好矩陣分別為MP1,td，MP2,td，MP3,td，MP4,td，MP5,td。采用矩陣分解模型對(duì)每一個(gè)動(dòng)態(tài)偏好矩陣進(jìn)行矩陣分解，得到五組用戶特征矩陣和簽到點(diǎn)特征矩陣，分別為UP1,td，LP1,td，UP2,td，LP2,td，UP3,td，LP3,td，UP4,td，LP4,td，UP5,td，LP5,td。因此，用戶ui在目標(biāo)時(shí)間td訪問(wèn)興趣點(diǎn)lj的預(yù)測(cè)偏好度，其中θk為第k 條元路徑的權(quán)重。為第k 組用戶特征矩陣的用戶ui的特征向量，為第k 組簽到點(diǎn)特征矩陣的興趣點(diǎn)lj的特征向量。在此基礎(chǔ)上，將預(yù)測(cè)偏好值最高的前N 個(gè)興趣點(diǎn)作為推薦結(jié)果。

4.4 算法描述

基于LBSN 動(dòng)態(tài)異構(gòu)網(wǎng)絡(luò)的興趣點(diǎn)推薦算法（PRDHN）步驟如下：

輸入：動(dòng)態(tài)異構(gòu)網(wǎng)絡(luò)G ＜Us,Ss,Ls,Es＞，動(dòng)態(tài)元路徑M={P1,P2,P3,P4,P5}，用戶ui，目標(biāo)時(shí)間td。

輸出：興趣點(diǎn)推薦結(jié)果LR。

1. for each meta-path Pk∈M do

2. Pk′=findInstancePathSet(Pk)

3. for each instance-path p ∈P′do

4. simPk,td(u,l)+=simp,td(u,l)，u ∈Us，l ∈Ls

5. end for

6. Generate MPk,tdbased on Pk

7. end for

8. for each matrix MPk,td，Pk∈M do

9. Decompose MPk,tdto UPk,tdand LPk,td

10.end for

11.Lc=initializeCandidateSet(ui)

12.for each lj∈Lcdo

14.end for

15.LR=TOP-N(Lc)

假設(shè)LBSN動(dòng)態(tài)異構(gòu)網(wǎng)絡(luò)G ＜Us,Ss,Ls,Es＞有n 個(gè)用戶，r 興趣點(diǎn)，m 條邊。第1步的for循環(huán)時(shí)間復(fù)雜度為O(c)，c 為元路徑集的大小。第3 步的for 循環(huán)時(shí)間復(fù)雜度為O(m) 。第8 步的for 循環(huán)時(shí)間復(fù)雜度為O(c)。第9 步對(duì)每個(gè)元路徑對(duì)應(yīng)的矩陣進(jìn)行分解的主要開銷主要來(lái)自于目標(biāo)函數(shù)E 和對(duì)應(yīng)的梯度下降函數(shù)。目標(biāo)函數(shù)的時(shí)間復(fù)雜度為O(ntˉk)，其中tˉ表示用戶的平均簽到數(shù)量，k 表示特征向量的維度。梯度下降函數(shù)的時(shí)間復(fù)雜度為。第12 步的時(shí)間復(fù)雜度為O(r)。所以該算法的總時(shí)間復(fù)雜度是O(cm+cntˉk+r)。因?yàn)閏 為常數(shù)5，且ntˉk ?m,r ，所以O(shè)(cm+cntˉk+r)≈O(ntˉk)。由文獻(xiàn)[12]可知，典型的LRT時(shí)間感知興趣點(diǎn)推薦算法時(shí)間復(fù)雜度為O(nrk)。因?yàn)閠ˉ＜r，所以PRDHN算法的時(shí)間復(fù)雜度小于LRT算法。

5 實(shí)驗(yàn)設(shè)計(jì)與分析

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

本文選擇了兩種公開簽到數(shù)據(jù)集進(jìn)行算法測(cè)試，分別為Gowalla 和Brightkite。這兩個(gè)數(shù)據(jù)集都同時(shí)包含了用戶信息、興趣點(diǎn)信息、簽到信息和時(shí)間信息等。首先對(duì)兩個(gè)數(shù)據(jù)集進(jìn)行預(yù)處理。把一天24小時(shí)劃分為24個(gè)時(shí)隙，將數(shù)據(jù)的時(shí)間信息取整劃分到24 個(gè)時(shí)隙中。將每個(gè)數(shù)據(jù)集70%的數(shù)據(jù)作為訓(xùn)練集，剩余30%的數(shù)據(jù)作為測(cè)試集。兩個(gè)數(shù)據(jù)集統(tǒng)計(jì)特性如表2所示。

表2 數(shù)據(jù)集統(tǒng)計(jì)特性表

5.2 評(píng)價(jià)標(biāo)準(zhǔn)

為了評(píng)價(jià)興趣點(diǎn)推薦算法的性能，本文使用準(zhǔn)確率（Precision@N）和召回率（Recall@N）作為評(píng)價(jià)指標(biāo)，其中N 表示興趣點(diǎn)推薦的個(gè)數(shù)。準(zhǔn)確率指推薦結(jié)果中用戶將來(lái)真正去的數(shù)量占推薦總數(shù)的比例。召回率指推薦結(jié)果中用戶將來(lái)真正去的數(shù)量占用戶將來(lái)訪問(wèn)興趣點(diǎn)總數(shù)的比例。用戶進(jìn)行興趣點(diǎn)推薦的準(zhǔn)確率和召回率定義如公式（6）所示：

其中，R(u)為對(duì)用戶u 進(jìn)行推薦的興趣點(diǎn)集合，T(u)為用戶u 在測(cè)試集上實(shí)際的簽到集合。

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

為了驗(yàn)證基于LBSN 動(dòng)態(tài)異構(gòu)網(wǎng)絡(luò)的興趣點(diǎn)推薦算法的推薦效果，將它與7種興趣點(diǎn)推薦算法進(jìn)行比較和分析。各對(duì)比算法介紹如表3所示。

表3 興趣點(diǎn)推薦算法對(duì)比表

實(shí)驗(yàn)1 會(huì)話參數(shù)H 對(duì)準(zhǔn)確率和召回率的影響

在兩個(gè)數(shù)據(jù)集中，通過(guò)調(diào)整會(huì)話節(jié)點(diǎn)參數(shù)H 分析本文會(huì)話節(jié)點(diǎn)對(duì)推薦算法準(zhǔn)確率和召回率的影響。在進(jìn)行推薦TOP-5 興趣點(diǎn)實(shí)驗(yàn)中，會(huì)話節(jié)點(diǎn)參數(shù)H 對(duì)準(zhǔn)確率（Precision@5）和召回率（Recall@5）的影響如圖4所示。

由圖4 可知，當(dāng)1 ≤H ≤2 時(shí)，兩個(gè)數(shù)據(jù)集準(zhǔn)確率和召回率都比較低，因?yàn)檩^小的H 值使得與目標(biāo)時(shí)間強(qiáng)相關(guān)的會(huì)話節(jié)點(diǎn)減少，從而產(chǎn)生了數(shù)據(jù)稀疏問(wèn)題。當(dāng)3 ≤H ≤4 時(shí)，兩個(gè)數(shù)據(jù)集的推薦效果最好，因?yàn)檩^大的H 值使得與目標(biāo)時(shí)間強(qiáng)相關(guān)的會(huì)話節(jié)點(diǎn)增加，并且與目標(biāo)時(shí)間越近的會(huì)話節(jié)點(diǎn)具有更大的權(quán)重，從而驗(yàn)證了會(huì)話節(jié)點(diǎn)對(duì)推薦性能的影響。當(dāng)5 ≤H ≤8 時(shí)，兩個(gè)數(shù)據(jù)集準(zhǔn)確率和召回率逐漸降低，因?yàn)殡S著H 值的繼續(xù)增加，導(dǎo)致了時(shí)間信息對(duì)推薦系統(tǒng)的影響降低。

實(shí)驗(yàn)2 基于時(shí)間感知興趣點(diǎn)推薦算法的實(shí)驗(yàn)分析

人們的生活一般都具有規(guī)律性，即他們?cè)谔囟ǖ臅r(shí)間喜歡去感興趣的位置活動(dòng)。因此時(shí)間信息影響著興趣點(diǎn)推薦算法推薦結(jié)果的實(shí)時(shí)性。該部分實(shí)驗(yàn)在兩個(gè)數(shù)據(jù)集的基礎(chǔ)上分別測(cè)試了5 種推薦算法的準(zhǔn)確率和召回率，實(shí)驗(yàn)結(jié)果如圖5所示。

由圖5 可知，在基于協(xié)同過(guò)濾的興趣點(diǎn)推薦算法中，User-based CF和MF CF算法在進(jìn)行興趣點(diǎn)推薦時(shí)沒(méi)有考慮時(shí)間信息，因此它們的興趣點(diǎn)推薦效果最差。在進(jìn)行推薦TOP-5興趣點(diǎn)實(shí)驗(yàn)中，LRT和UTE算法相對(duì)于User-based CF算法在兩個(gè)數(shù)據(jù)集的準(zhǔn)確率上提高了43%～55%。它們相對(duì)于MF CF算法在兩個(gè)數(shù)據(jù)集的準(zhǔn)確率上提高了32%～45%。此結(jié)果表明，時(shí)間感知的興趣點(diǎn)推薦算法可以提高推薦系統(tǒng)的準(zhǔn)確率和召回率。本文PRDHN 算法相對(duì)于LRT 和UTE 算法在兩個(gè)數(shù)據(jù)集的準(zhǔn)確率上平均提高了8%～15%。因?yàn)榛趧?dòng)態(tài)異構(gòu)網(wǎng)絡(luò)PRDHN算法在融入時(shí)間信息的同時(shí)又融入位置信息和社交信息等，進(jìn)一步地提高時(shí)間感知興趣點(diǎn)推薦算法的推薦精度。

實(shí)驗(yàn)3 融合情景的興趣點(diǎn)推薦算法實(shí)驗(yàn)分析

由于興趣點(diǎn)推薦系統(tǒng)中簽到數(shù)據(jù)非常稀疏，因此融合情景信息有助于提高興趣點(diǎn)推薦算法的準(zhǔn)確率和召回率。該部分實(shí)驗(yàn)在兩個(gè)數(shù)據(jù)集的基礎(chǔ)上分別測(cè)試了4 種融合情景的興趣點(diǎn)推薦算法，實(shí)驗(yàn)結(jié)果如圖6所示。

圖4 會(huì)話參數(shù)H 對(duì)準(zhǔn)確率和召回率的影響

圖5 基于時(shí)間感知興趣點(diǎn)推薦算法對(duì)比圖

圖6 融合情景的興趣點(diǎn)推薦算法對(duì)比圖

由圖6可知，US和UG在進(jìn)行興趣點(diǎn)推薦時(shí)分別只融合了社會(huì)信息及地理信息，因此它們的興趣點(diǎn)推薦效果最差。在進(jìn)行推薦TOP-5 興趣點(diǎn)實(shí)驗(yàn)中，USG 算法相對(duì)于US 算法和UG 算法在Gowalla 數(shù)據(jù)集上的準(zhǔn)確率分別提高了17.2%和13.3%，同理在Brightkite 數(shù)據(jù)集上的準(zhǔn)確率分別提高了23.1%和18.5%。本文PRDHN算法相對(duì)于USG算法在兩個(gè)數(shù)據(jù)集的準(zhǔn)確率分別提高了11.7%和18.7%。因此該方法的興趣點(diǎn)推薦效果最好。實(shí)驗(yàn)結(jié)果表明，以LBSN 動(dòng)態(tài)異構(gòu)網(wǎng)絡(luò)為基礎(chǔ)，融合地理位置、社會(huì)關(guān)系和用戶偏好的時(shí)間感知的興趣點(diǎn)推薦算法可以進(jìn)一步地提高推薦系統(tǒng)的推薦精度和召回率。

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

針對(duì)基于位置社交網(wǎng)絡(luò)提出了一種基于LBSN 動(dòng)態(tài)異構(gòu)網(wǎng)絡(luò)的時(shí)間感知興趣點(diǎn)推薦算法。首先在LBSN異構(gòu)網(wǎng)絡(luò)模式中增加了會(huì)話節(jié)點(diǎn)類型，并通過(guò)動(dòng)態(tài)元路徑，在用戶和興趣點(diǎn)之間語(yǔ)義關(guān)系中融入時(shí)間信息、位置信息和社交信息。其次設(shè)置了用戶-興趣點(diǎn)之間的動(dòng)態(tài)元路徑集，并提出了動(dòng)態(tài)路徑實(shí)例偏好度的計(jì)算方法。然后采用矩陣分解模型對(duì)不同動(dòng)態(tài)偏好矩陣進(jìn)行矩陣分解。最后結(jié)合不同動(dòng)態(tài)元路徑對(duì)應(yīng)的用戶特征矩陣和興趣點(diǎn)特征矩陣，獲取用戶在不同的目標(biāo)時(shí)間訪問(wèn)興趣點(diǎn)的top-k 推薦列表。實(shí)驗(yàn)結(jié)果表明本文算法的精確度相比其他相關(guān)的興趣點(diǎn)推薦技術(shù)有了較好的提高。在未來(lái)的工作中，將在推薦系統(tǒng)中融入文本信息等其他信息，并通過(guò)神經(jīng)網(wǎng)絡(luò)和表示學(xué)習(xí)技術(shù)，進(jìn)一步提高興趣點(diǎn)推薦的性能。