柴瑞敏，殷 臣

遼寧工程技術(shù)大學(xué) 電子與信息工程學(xué)院，遼寧 葫蘆島 125105

隨著移動(dòng)設(shè)備和GPS的普遍應(yīng)用，下一個(gè)興趣點(diǎn)推薦（next POI recommendation）正成為基于位置的社交網(wǎng)絡(luò)（location-based social network，LBSN）的一個(gè)重要任務(wù)，它不僅可以幫助用戶探索喜歡的地方，也有利于企業(yè)獲得更多的潛在客戶。然而，由于用戶的簽到數(shù)據(jù)非常稀疏，進(jìn)行準(zhǔn)確的下一個(gè)興趣點(diǎn)推薦極具挑戰(zhàn)性。研究表明[1-3]，由于人類的日常生活中表現(xiàn)出強(qiáng)烈的時(shí)序模式，POI簽到序列信息對(duì)下一個(gè)興趣點(diǎn)推薦起著至關(guān)重要的作用。

在很多研究中，通常將下一個(gè)興趣點(diǎn)推薦視為序列推薦問(wèn)題。文獻(xiàn)[4]提出了FPMC模型，通過(guò)將矩陣因子分解和馬爾科夫鏈相結(jié)合進(jìn)行下一個(gè)購(gòu)物車推薦，文獻(xiàn)[2]對(duì)FPMC模型進(jìn)行擴(kuò)展，增加了個(gè)性化馬爾科夫鏈和用戶的移動(dòng)距離限制進(jìn)行下一個(gè)興趣點(diǎn)推薦。最近，RNN已經(jīng)成功運(yùn)用于序列數(shù)據(jù)建模，成為目前主流的下一個(gè)興趣點(diǎn)模型。文獻(xiàn)[1]提出了一個(gè)LSTM變體，通過(guò)增加時(shí)間門和距離門對(duì)時(shí)間間隔和空間間隔信息建模進(jìn)行下一個(gè)興趣點(diǎn)推薦。文獻(xiàn)[5-8]也說(shuō)明了一些上下文信息（如時(shí)空信息、類別信息等）能夠提升興趣點(diǎn)推薦效果。

然而，在下一個(gè)興趣點(diǎn)推薦中，用戶關(guān)系還沒有被深入考慮，而實(shí)際上用戶關(guān)系能在一定程度上影響模型推薦效果[9-10]。本文將用戶關(guān)系分為兩類，分別是朋友關(guān)系和偏好相似關(guān)系。朋友關(guān)系是指在社交軟件中互為對(duì)方好友，如果兩個(gè)人具有朋友關(guān)系，則他們可能會(huì)具有相近的興趣偏好，比如在未來(lái)更可能一起去旅游或者聚餐。一些研究表明[11]，通過(guò)加入朋友關(guān)系，模型的推薦效果得到提高。對(duì)于偏好相似關(guān)系，可用兩個(gè)用戶共同訪問(wèn)過(guò)的興趣點(diǎn)個(gè)數(shù)衡量，兩個(gè)用戶共同訪問(wèn)過(guò)的興趣點(diǎn)越多說(shuō)明他們偏好越相近。為了學(xué)習(xí)用戶關(guān)系向量的表示，本文首次提出整合兩種用戶關(guān)系的模型User2Vec，該方法首先根據(jù)兩種用戶關(guān)系建立用戶關(guān)系圖，然后利用DeepWalk[12]方法學(xué)習(xí)用戶關(guān)系向量表示。

為了能夠同時(shí)對(duì)用戶簽到POI序列信息、用戶關(guān)系、簽到POI的上下文信息進(jìn)行建模，提出了一個(gè)整合用戶關(guān)系和其他上下文信息的GRU模型（GRU-R）。本文提出的GRU-R模型考慮的上下文信息包括時(shí)間上下文、空間上下文和興趣點(diǎn)類別信息，其中時(shí)間上下文包括興趣點(diǎn)的簽到時(shí)間和兩個(gè)相鄰簽到興趣點(diǎn)之間的時(shí)間間隔，空間上下文包括兩個(gè)相鄰簽到興趣點(diǎn)之間的距離間隔。

本文貢獻(xiàn)如下：

（1）本文提出一種新的用戶關(guān)系學(xué)習(xí)模型（User2Vec），該模型同時(shí)考慮朋友關(guān)系和偏好相似關(guān)系，并通過(guò)訓(xùn)練得到用戶關(guān)系的低維向量表示。

（2）本文提出GRU-R神經(jīng)網(wǎng)絡(luò)模型用于下一個(gè)興趣點(diǎn)推薦，該模型能夠同時(shí)考慮用戶的歷史簽到序列信息、用戶關(guān)系、時(shí)空信息和興趣點(diǎn)類別等信息用于下一個(gè)興趣點(diǎn)推薦。

（3）本文在兩個(gè)公開真實(shí)的數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明，本文提出的模型比現(xiàn)有主流的方法具有更高的下一個(gè)興趣點(diǎn)推薦準(zhǔn)確性。

1 相關(guān)工作

現(xiàn)有的下一個(gè)興趣點(diǎn)推薦方法主要可分為基于矩陣因子分解的方法、基于馬爾科夫鏈的方法、基于嵌入的方法和基于神經(jīng)網(wǎng)絡(luò)的方法。

基于矩陣因子分解的方法是目前最常用的協(xié)同過(guò)濾方法。矩陣因子分解的基本目標(biāo)是將用戶位置偏好矩陣分解為兩個(gè)低秩矩陣，每個(gè)低秩矩陣表示用戶或位置的潛在因子。文獻(xiàn)[11]提出了一種基于朋友關(guān)系的協(xié)同過(guò)濾的方法，根據(jù)朋友共同訪問(wèn)過(guò)的興趣點(diǎn)做興趣點(diǎn)推薦。文獻(xiàn)[13]提出了一種多中心高斯模型來(lái)捕獲用戶的地理影響，并結(jié)合矩陣分解模型進(jìn)行興趣點(diǎn)推薦。然而，基于矩陣因子分解的模型很難產(chǎn)生新用戶或新位置的表示，存在嚴(yán)重的冷啟動(dòng)問(wèn)題，也無(wú)法有效對(duì)序列數(shù)據(jù)進(jìn)行建模。

近年來(lái)，基于馬爾科夫和嵌入學(xué)習(xí)的推薦模型也被廣泛應(yīng)用于興趣點(diǎn)推薦中?；隈R爾科夫鏈（Markov chain，MC）的模型旨在基于用戶過(guò)去的連續(xù)簽到行為來(lái)預(yù)測(cè)用戶的下一個(gè)行為。文獻(xiàn)[2]提出FPMC-LR模型，是對(duì)基于馬爾科夫鏈方法的擴(kuò)展，基本思想是通過(guò)考慮連續(xù)簽到興趣點(diǎn)序列關(guān)系和地理距離限制進(jìn)行下一個(gè)興趣點(diǎn)推薦。文獻(xiàn)[14]利用個(gè)性化度量嵌入的方法對(duì)用戶簽到序列建模，從而進(jìn)行個(gè)性化興趣點(diǎn)推薦。文獻(xiàn)[15]提出了一種嵌入學(xué)習(xí)方法（GE），該方法利用二部圖對(duì)POI推薦上下文中的一對(duì)上下文進(jìn)行建模，并通過(guò)對(duì)四對(duì)嵌入模型進(jìn)行統(tǒng)一優(yōu)化進(jìn)行興趣點(diǎn)推薦。

近年來(lái)，基于神經(jīng)網(wǎng)絡(luò)的推薦方法被廣泛的應(yīng)用于多個(gè)領(lǐng)域[16-18]，如視頻推薦、廣告推薦和書籍推薦等，顯著提升了推薦效果。在神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)中，由于基于循環(huán)神經(jīng)網(wǎng)絡(luò)（RNN）的方法能夠有效地捕捉序列數(shù)據(jù)的影響，并且能夠在用戶簽到數(shù)據(jù)中自動(dòng)挖掘上下文信息之間的交互影響，因此在興趣點(diǎn)推薦中得到了廣泛應(yīng)用，并成為當(dāng)前主流的推薦模型。然而，RNN存在梯度爆炸和梯度消失的問(wèn)題[19]，使其不能學(xué)習(xí)到較長(zhǎng)序列內(nèi)遠(yuǎn)距離的依賴關(guān)系。為了解決這個(gè)問(wèn)題，長(zhǎng)短時(shí)記憶（LSTM）[19]和門控循環(huán)單元（GRU）[20]兩種RNN變體提出來(lái)解決該問(wèn)題，使得循環(huán)神經(jīng)網(wǎng)絡(luò)能夠?qū)W習(xí)到長(zhǎng)距離的序列依賴問(wèn)題。文獻(xiàn)[3]提出的ST-RNN模型整合了時(shí)空信息，通過(guò)在RNN的隱藏層之間應(yīng)用特定時(shí)間和特定距離的轉(zhuǎn)換矩陣描述動(dòng)態(tài)的時(shí)間間隔和距離間隔。文獻(xiàn)[1]提出了改進(jìn)的LSTM模型，該模型在LSTM模型中加入時(shí)間門和距離門，通過(guò)對(duì)相鄰簽到之間的時(shí)間間隔和距離間隔進(jìn)行建模來(lái)提取用戶長(zhǎng)期和短期興趣偏好進(jìn)行下一個(gè)POI推薦。文獻(xiàn)[7]提出NEXT模型，利用簡(jiǎn)單的前饋神經(jīng)網(wǎng)絡(luò)以一種統(tǒng)一的嵌入方式處理多種上下文信息進(jìn)行下一個(gè)POI推薦。

然而，以上的模型都存在不足。傳統(tǒng)的基于矩陣分解的方法無(wú)法對(duì)用戶簽到序列信息進(jìn)行有效建模。基于馬爾科夫鏈和基于嵌入模型的方法也很難同時(shí)考慮多種上下文信息以及多種上下文信息之間的交互作用?，F(xiàn)有的基于循環(huán)神經(jīng)網(wǎng)絡(luò)的方法通常對(duì)時(shí)空信息建模，缺乏對(duì)多種上下文信息的考慮。文獻(xiàn)[7]提出的NEXT模型與本文工作相似，由于它使用簡(jiǎn)單的前向神經(jīng)網(wǎng)絡(luò)進(jìn)行下一個(gè)POI推薦，因此無(wú)法對(duì)簽到POI序列關(guān)系有效建模，同時(shí)NEXT也沒有深入考慮用戶關(guān)系。與以上方法不同，本文提出的GRU-R能夠同時(shí)對(duì)用戶關(guān)系、簽到序列信息、多種上下文信息以及上下文信息之間的交互影響進(jìn)行建模。

2 相關(guān)定義

本文使用的符號(hào)定義如下。假設(shè)U={u1,u2,…,u M}是M個(gè)用戶的集合，P={p1,p2,…,p N}是N個(gè)興趣點(diǎn)的集合。

定義1（POI）POI定義為具有唯一標(biāo)識(shí)的特定地點(diǎn)，包含兩個(gè)屬性：標(biāo)識(shí)符和地理經(jīng)緯度坐標(biāo)。

定義2（歷史簽到序列）某一個(gè)用戶u在t i時(shí)刻前的歷史簽到序列可以表示為，其中表示用戶u在t i-1時(shí)刻訪問(wèn)了興趣點(diǎn)p。

定義3（下一個(gè)POI推薦）給定用戶在t i時(shí)刻之前的歷史簽到序列，下一個(gè)興趣點(diǎn)推薦的目標(biāo)是在t i時(shí)刻給用戶u推薦一組用戶將要訪問(wèn)的興趣點(diǎn)列表。用戶歷史簽到序列和下一個(gè)興趣點(diǎn)推薦如圖1所示。推薦列表中的興趣點(diǎn)的排名越靠前，說(shuō)明用戶在下一時(shí)刻t i將會(huì)更可能訪問(wèn)該興趣點(diǎn)。根據(jù)預(yù)測(cè)分?jǐn)?shù)，模型給出用戶top-k個(gè)推薦興趣點(diǎn)列表。文中用到的變量符號(hào)如表1所示。

圖1 用戶歷史簽到序列與下一個(gè)興趣點(diǎn)推薦Fig.1 User history check-in sequence and next POI recommendation

表1 符號(hào)表Table 1 Symbols table

3 GRU-R推薦模型

GRU-R模型包括三個(gè)主要模塊：用戶關(guān)系學(xué)習(xí)模塊、GRU模型的數(shù)據(jù)輸入模塊、基于GRU模型的預(yù)測(cè)模塊。本節(jié)將詳細(xì)闡述模型部分的具體細(xì)節(jié)，模型的整體框架如圖2所示。

3.1 用戶關(guān)系學(xué)習(xí)

本文將用戶關(guān)系分為朋友關(guān)系和偏好相似關(guān)系。偏好相似關(guān)系由用戶共同訪問(wèn)的興趣點(diǎn)數(shù)量衡量；朋友關(guān)系由用戶在社交軟件中的好友信息得到。為了能夠同時(shí)考慮用戶的相似偏好關(guān)系和朋友關(guān)系，提出了一種用戶關(guān)系學(xué)習(xí)模型（User2Vec）。該模型的學(xué)習(xí)過(guò)程分為兩步：第一步構(gòu)建用戶關(guān)系圖；第二步學(xué)習(xí)用戶關(guān)系的向量表示。

3.1.1 構(gòu)建用戶關(guān)系圖

為了表示偏好相似關(guān)系，首先需要根據(jù)用戶的訪問(wèn)歷史興趣點(diǎn)建立用戶-興趣點(diǎn)訪問(wèn)表（如表2所示），表中數(shù)值1表示用戶訪問(wèn)過(guò)該地點(diǎn)，0表示用戶沒有訪問(wèn)過(guò)該地點(diǎn)。同樣地，為了表示用戶的朋友關(guān)系，根據(jù)社交軟件中的朋友關(guān)系建立朋友關(guān)系表（如表3所示）。然后根據(jù)表2和表3信息建立用戶關(guān)系圖（如圖3所示）來(lái)綜合兩種不同關(guān)系。圖中邊的權(quán)重綜合了兩類用戶關(guān)系的緊密度，如果兩個(gè)用戶訪問(wèn)過(guò)同一地點(diǎn)或者兩個(gè)用戶是朋友就將圖中相應(yīng)兩個(gè)節(jié)點(diǎn)連接邊的權(quán)重加1。

表2 用戶-興趣點(diǎn)訪問(wèn)表Table 2 User-POI access table

表3 朋友關(guān)系表Table 3 Friendship table

圖3 用戶關(guān)系圖Fig.3 User relationship graph

3.1.2 用戶關(guān)系向量學(xué)習(xí)

本文使用DeepWalk圖嵌入的方法來(lái)學(xué)習(xí)用戶關(guān)系向量的表示。DeepWalk模型學(xué)習(xí)用戶關(guān)系圖中用戶（節(jié)點(diǎn)）向量表示需要兩步。首先通過(guò)在圖中每個(gè)節(jié)點(diǎn)上執(zhí)行隨機(jī)游走方法獲得訓(xùn)練的輸入序列，之后根據(jù)輸入序列信息使用Skip-Gram模型訓(xùn)練用戶（節(jié)點(diǎn)）關(guān)系向量的表示。

用戶關(guān)系圖中邊權(quán)重代表從一個(gè)用戶節(jié)點(diǎn)到另一個(gè)用戶節(jié)點(diǎn)的轉(zhuǎn)移概率，從一個(gè)用戶u i到另一個(gè)用戶u j隨機(jī)游走的概率可定義為：

其中f(u i,u j)表示從u i到u j邊的權(quán)重，u m表示與u i有邊相連的節(jié)點(diǎn)。比如在圖3中，和u2（ID為2）相連接的邊的權(quán)重總和為4，u2和u4相連邊的權(quán)重為2，可得到u2到u4的轉(zhuǎn)移概率為2/4（注意，從u4到u2的轉(zhuǎn)移概率是2/5）。在采樣過(guò)程中，從圖中的一個(gè)節(jié)點(diǎn)出發(fā)開始重復(fù)進(jìn)行50次隨機(jī)游走，每次游走的步長(zhǎng)設(shè)置為20，對(duì)圖中所有的節(jié)點(diǎn)都執(zhí)行同樣的操作。執(zhí)行上述步驟之后，就可以獲得用于模型訓(xùn)練的序列輸入數(shù)據(jù)。

本文使用基于Hierarchical Softmax的Skip-Gram語(yǔ)言模型學(xué)習(xí)用戶關(guān)系嵌入向量表示，用戶關(guān)系向量學(xué)習(xí)過(guò)程類似于自然語(yǔ)言處理中詞向量的訓(xùn)練過(guò)程。用戶關(guān)系向量訓(xùn)練過(guò)程是在采樣序列中最大化預(yù)測(cè)其鄰近用戶的概率?；贖ierarchical Softmax的Skip-Gram語(yǔ)言模型的每個(gè)輸入樣本形式為(v,context(v))，其中v表示序列中的一個(gè)用戶，context(v)是序列中與v鄰近的用戶，v的嵌入向量表示為x v，l v表示為根節(jié)點(diǎn)到葉節(jié)點(diǎn)v路徑中包含的節(jié)點(diǎn)個(gè)數(shù)，∈{1,0}表示路徑中第j個(gè)節(jié)點(diǎn)對(duì)應(yīng)v的哈夫曼樹編碼。在此基礎(chǔ)上，用v預(yù)測(cè)context(v)的可能性表示為：

其中p(w|v)可表示為：

之后，用對(duì)數(shù)似然形式得到語(yǔ)料庫(kù)中所有用戶的聯(lián)合概率為：

其中V是數(shù)據(jù)集中所有用戶的集合，σ(·)是sigmoid函數(shù)，是對(duì)應(yīng)于的參數(shù)。為了得到v的最優(yōu)向量表示，需要將上述目標(biāo)L最大化。因此，需要用函數(shù)L對(duì)和x v分別求偏導(dǎo)：

用戶關(guān)系嵌入向量x v的更新方式可以寫成：

其中，η為模型訓(xùn)練時(shí)的學(xué)習(xí)率，根據(jù)文獻(xiàn)[21]，將η設(shè)置為0.025。在用Skip-Gram模型的訓(xùn)練過(guò)程中，滑動(dòng)窗口大小設(shè)置為5，用戶關(guān)系向量的長(zhǎng)度設(shè)置為64維。

3.2 輸入向量處理

如圖2所示，GRU的輸入由歷史序列簽到數(shù)據(jù)表示，序列中給定用戶某一時(shí)刻t的輸入包括7類信息S t=＜u,p,c,ct,Δt,Δd,r＞。

u、p和c分別表示64維的用戶向量、128維的興趣點(diǎn)向量和16維的類別向量，在程序開始訓(xùn)練階段，u、p和c向量被隨機(jī)初始化，在模型的訓(xùn)練過(guò)程中會(huì)被更新，最終模型會(huì)學(xué)習(xí)到u、p和c的向量表示。由于一個(gè)地點(diǎn)的類別標(biāo)簽可能有多個(gè)，比如興趣點(diǎn)的類別標(biāo)簽為{‘Shop’，‘Food’，‘Gym’，‘Office’}，為了獲得興趣點(diǎn)的語(yǔ)義表示，最終POI的類別表示（c）是每種興趣點(diǎn)類別標(biāo)簽向量的平均值。

時(shí)間間隔（Δt）由兩個(gè)相鄰簽到興趣點(diǎn)的時(shí)間差表示（單位為天），距離間隔（Δd）由兩個(gè)相鄰簽到興趣點(diǎn)的距離差表示（單位為km），距離間隔計(jì)算是由Harversine公式得到，Δt和Δd都用原始的連續(xù)數(shù)值表示。簽到時(shí)間ct被分為簽到時(shí)刻（hour）和簽到周（week），如2010-07-24T13：44：46Z表示用戶在星期六的13點(diǎn)進(jìn)行了簽到，分別用7位和24位one-hot向量表示，對(duì)應(yīng)一周的7天和一天中24小時(shí)。

用戶關(guān)系向量（r）為64維的向量，是基于DeepWalk的方法對(duì)用戶關(guān)系進(jìn)行預(yù)訓(xùn)練得到的結(jié)果，在模型訓(xùn)練的過(guò)程中無(wú)法更新。以上所有向量的拼接結(jié)果將作為GRU在i時(shí)刻的輸入向量。

3.3 基于GRU模型的興趣點(diǎn)訪問(wèn)概率預(yù)測(cè)

GRU是LSTM網(wǎng)絡(luò)的一種變體，可以解決RNN網(wǎng)絡(luò)中的長(zhǎng)依賴問(wèn)題，它較LSTM網(wǎng)絡(luò)的結(jié)構(gòu)更加簡(jiǎn)單。LSTM利用三個(gè)門控單元和一個(gè)存儲(chǔ)單元控制信息流動(dòng)。LSTM也被廣泛應(yīng)用于涉及序列建模的不同任務(wù)中[22-23]。GRU是LSTM的最新變種，包括重置門（rt）和更新門（zt）兩種類型的門控單元，它們共同控制信息在神經(jīng)網(wǎng)絡(luò)中的流動(dòng)狀態(tài)，因此GRU在進(jìn)行數(shù)據(jù)訓(xùn)練時(shí)需要更少的時(shí)間花費(fèi)，GRU的狀態(tài)更新公式如下：

其中[]表示向量拼接操作，*表示矩陣的哈達(dá)瑪積，x t表示t時(shí)刻的輸入數(shù)據(jù)，h t-1表示上一時(shí)刻的隱層狀態(tài)，σ表示sigmoid激活函數(shù)，W r，W z和W h?表示權(quán)重參數(shù)，h t表示t時(shí)刻的輸出向量。

本文將GRU模型的最后時(shí)刻的輸出向量h t作為用戶訪問(wèn)下一個(gè)興趣點(diǎn)的偏好向量。之后h t被送入分類層（一層全連接層）得到用戶訪問(wèn)每一個(gè)興趣點(diǎn)的偏好分?jǐn)?shù)，全連接神經(jīng)網(wǎng)絡(luò)的計(jì)算過(guò)程如下：

式中向量y表示用戶訪問(wèn)每一個(gè)興趣點(diǎn)的偏好分?jǐn)?shù)，向量y的長(zhǎng)度為興趣點(diǎn)總數(shù)。W和b分別表示全連接神經(jīng)網(wǎng)絡(luò)的參數(shù)矩陣和偏置值，使用Relu作為激活函數(shù)。

最終，通過(guò)Softmax函數(shù)將y映射到[0-1]區(qū)間的概率值，根據(jù)概率給用戶推薦其感興趣的top-k個(gè)將要訪問(wèn)的下一個(gè)興趣點(diǎn)列表。Softmax函數(shù)的計(jì)算方法如下：

式中y?i表示用戶訪問(wèn)下一個(gè)興趣點(diǎn)ID為i的概率值，N表示興趣點(diǎn)的總數(shù)。

4 實(shí)驗(yàn)

4.1 模型實(shí)驗(yàn)

這一部分主要介紹本文使用的數(shù)據(jù)集、對(duì)比算法、模型的參數(shù)設(shè)置以及實(shí)驗(yàn)結(jié)果。

數(shù)據(jù)稀疏性處理不同于一般的商品（如電影、圖書、音樂等）數(shù)據(jù)集，興趣點(diǎn)由經(jīng)緯度表示，并且受到地理位置的影響，用戶只偏好于訪問(wèn)一些距離家和公司附近的一些地方，因此相比于一般的商品數(shù)據(jù)集更為稀疏。針對(duì)于數(shù)據(jù)稀疏問(wèn)題，有很多模型使用不同的上下文來(lái)解決數(shù)據(jù)稀疏性問(wèn)題。比如一些研究利用類別、時(shí)間和文本信息等多上下文來(lái)解決數(shù)據(jù)稀疏性問(wèn)題[7，18]。本文通過(guò)同時(shí)考慮用戶的序列信息、用戶關(guān)系、兩類時(shí)間信息（簽到時(shí)間和時(shí)間間隔）以及類別信息進(jìn)行下一個(gè)興趣點(diǎn)推薦。為了能夠有效地評(píng)價(jià)模型的效果，首先需要對(duì)數(shù)據(jù)集做預(yù)處理，預(yù)處理的方法是賽選掉在大數(shù)據(jù)集中不活躍的用戶和興趣點(diǎn)，這樣的目的是為了能夠從稀疏的大數(shù)據(jù)集中得到較為稠密的子集。

數(shù)據(jù)集本文使用兩個(gè)公開真實(shí)的數(shù)據(jù)集，包括CA數(shù)據(jù)集和Gowalla數(shù)據(jù)集。CA數(shù)據(jù)集[24]包括生活在美國(guó)加利福尼亞州的4 163名使用者在Foursquare應(yīng)用上的簽到記錄，包括483 813個(gè)簽到信息、12 1142個(gè)不同的興趣點(diǎn)。Gowalla數(shù)據(jù)集包括2009年2月至2010年10月期間的196 591個(gè)用戶的6 442 890條簽到記錄，本文提取在加利福尼亞州和內(nèi)華達(dá)州兩個(gè)地點(diǎn)的簽到數(shù)據(jù)用于實(shí)驗(yàn)，因?yàn)檫@兩個(gè)相鄰的地區(qū)沒有顯著的文化差異，由于Gowalla不含有類別標(biāo)簽，因此在Gowalla數(shù)據(jù)集實(shí)驗(yàn)中沒有用到類別信息。沿著常用的數(shù)據(jù)集的處理方式[2，7]，本文移除了不活躍的用戶和興趣點(diǎn)，保留每個(gè)興趣點(diǎn)至少被10個(gè)不同用戶訪問(wèn)過(guò)，并且保證每個(gè)用戶至少有10次簽到記錄。表4給出了處理后的數(shù)據(jù)集信息。使用用戶歷史簽到記錄的前70%作為訓(xùn)練集，后20%作為測(cè)試集，其余的10%作為驗(yàn)證集數(shù)據(jù)用于模型調(diào)參。

表4 實(shí)驗(yàn)數(shù)據(jù)集統(tǒng)計(jì)信息（數(shù)據(jù)處理后）Table 4 Statistics of experimental datasets（after data processing）

對(duì)比算法本文提出的模型主要與以下幾個(gè)主流算法進(jìn)行比較，其中BPR、FPMC-LR和PRME-G模型的嵌入向量維度都為20，GRU、NEXT和GRU-R隱藏層神經(jīng)元個(gè)數(shù)都設(shè)置為128，選擇模型迭代100次的最優(yōu)結(jié)果作為實(shí)驗(yàn)評(píng)價(jià)結(jié)果。本文沒有對(duì)比較模型的其他參數(shù)進(jìn)行調(diào)優(yōu)，都使用原模型默認(rèn)的參數(shù)設(shè)置。

BPR[25]利用矩陣分解算法和BPR損失對(duì)“用戶-興趣點(diǎn)”的隱式反饋矩陣進(jìn)行優(yōu)化。BPR認(rèn)為用戶對(duì)交互過(guò)的興趣點(diǎn)偏好大于未交互的興趣點(diǎn)。

FPMC-LR[2]該模型結(jié)合了個(gè)性化馬爾科夫鏈和用戶在局部區(qū)域的移動(dòng)約束。它將所有用戶的興趣點(diǎn)轉(zhuǎn)移矩陣分解，并通過(guò)計(jì)算轉(zhuǎn)移概率來(lái)預(yù)測(cè)下一個(gè)位置。

PRME-G[14]該模型利用個(gè)性化度量嵌入的方法對(duì)興趣點(diǎn)的簽到序列信息建模，同時(shí)使用權(quán)重的方法整合地理位置信息進(jìn)行下一個(gè)興趣點(diǎn)推薦。

GRU[20]最新的RNN模型的變體，是LSTM的簡(jiǎn)化版本，通過(guò)兩個(gè)門控單元控制信息的流動(dòng)。

NEXT[7]利用簡(jiǎn)單的前向神經(jīng)網(wǎng)絡(luò)進(jìn)行推薦的模型，通過(guò)以一種統(tǒng)一的方式整合簽到序列、過(guò)渡信息和朋友關(guān)系等多種上下文信息進(jìn)行下一個(gè)興趣點(diǎn)推薦。

GRU-R本文提出的方法，綜合考慮用戶關(guān)系、簽到序列、時(shí)空信息和地點(diǎn)類別信息等進(jìn)行下一個(gè)興趣點(diǎn)推薦。

評(píng)價(jià)指標(biāo)本文采用的評(píng)價(jià)指標(biāo)是Accuracy@N（ACC@N），它通常用于評(píng)估推薦任務(wù)的準(zhǔn)確性。在ACC@N中，如果用戶下一個(gè)訪問(wèn)的興趣點(diǎn)出現(xiàn)在top-k的推薦列表中，就認(rèn)為預(yù)測(cè)正確，結(jié)果為1，否則結(jié)果為0，整個(gè)ACC@N是所有測(cè)試實(shí)例的平均值，這里選擇k={1，5，10}進(jìn)行實(shí)驗(yàn)比較。平均倒數(shù)排名（mean reciprocal rank，MRR）是衡量推薦列表中興趣點(diǎn)排名的標(biāo)準(zhǔn)，它根據(jù)真實(shí)值在下一個(gè)興趣點(diǎn)的索引位置計(jì)算得到，如果用戶訪問(wèn)下一個(gè)興趣點(diǎn)在在推薦列表的位置越靠前，MRR的得分就會(huì)越高。

模型參數(shù)設(shè)置本文使用tensorflow框架實(shí)現(xiàn)提出的GRU-R模型。GRU隱藏層的神經(jīng)元的個(gè)數(shù)設(shè)為128個(gè)，學(xué)習(xí)率設(shè)為0.001。為了防止模型出現(xiàn)過(guò)擬合和梯度爆炸，模型應(yīng)用了dropout技術(shù)和梯度裁剪的方法，其中dropout設(shè)置為0.1，反向誤差傳播的梯度被限制在[-1，1]之間。實(shí)驗(yàn)結(jié)果如表5和表6所示。

表5 Gowalla數(shù)據(jù)集的下一個(gè)興趣點(diǎn)推薦結(jié)果準(zhǔn)確性比較Table 5 Accuracy comparison of next POI recommendation results on Gowalla dataset %

表6 CA數(shù)據(jù)集的下一個(gè)興趣點(diǎn)推薦結(jié)果準(zhǔn)確性比較Table 6 Accuracy comparison of next POI recommendation results on CA dataset %

從實(shí)驗(yàn)結(jié)果可以得出如下結(jié)論：

（1）BPR在兩個(gè)數(shù)據(jù)集上ACC@1和MRR指標(biāo)上的都表現(xiàn)出最差的結(jié)果。BPR是基于協(xié)同過(guò)濾矩陣分解的算法，只考慮用戶的偏好信息，認(rèn)為用戶訪問(wèn)過(guò)得興趣點(diǎn)大于未訪問(wèn)過(guò)得興趣點(diǎn)，該算法常用于商品推薦或者一般的興趣點(diǎn)推薦算法中，但是BPR并不適合用于下一個(gè)興趣點(diǎn)推薦，因?yàn)樗皇菃渭兛紤]用戶偏好信息，并沒有考慮用戶的序列關(guān)系和距離信息。從兩個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果可以發(fā)現(xiàn)，其他基于序列推薦的方法（FPMC-LR、PRME-G、GRU和NEXT）在ACC@1和MRR指標(biāo)上都顯著優(yōu)于BPR算法，說(shuō)明在下一個(gè)興趣點(diǎn)推薦中序列信息要比用戶偏好更加重要。通過(guò)在CA數(shù)據(jù)集上的實(shí)驗(yàn)也可以發(fā)現(xiàn)，盡管BPR算法在ACC@10指標(biāo)上優(yōu)于FPMC-LR和PRME-G模型，但是BPR算法在MRR評(píng)價(jià)指標(biāo)上效果較差。BPR在ACC@10較好的原因是它可以提供用戶更多用戶感興趣的地點(diǎn)，這是由于用戶具有頻繁的訪問(wèn)諸如家和公司附近的一些場(chǎng)所的偏好導(dǎo)致的。但是這不適用于用戶下一個(gè)興趣點(diǎn)推薦模型中，在下一個(gè)興趣點(diǎn)推薦中用戶會(huì)受到當(dāng)前位置的約束，給用戶推薦更多的滿足用戶偏好的興趣點(diǎn)并不一定是符合用戶下一個(gè)訪問(wèn)興趣點(diǎn)的真實(shí)目的，這也解釋了BRP模型具有較低的MRR值的原因。

（2）下面比較FPMC-LR、PRME-G和NEXT模型，這些模型都對(duì)用戶的序列信息和距離信息進(jìn)行建模。FPMC-LR使用一階馬爾科夫鏈的方法對(duì)序列信息建模，同時(shí)根據(jù)用戶移動(dòng)距離的限制進(jìn)行推薦。PRME-G使用度量嵌入的方法對(duì)用戶序列簽到行為建模根據(jù)位置距離控制權(quán)重系數(shù)進(jìn)行推薦。PRME-G在兩個(gè)指標(biāo)上相比于FPMC-LR均具有輕微的提升，這也表明表示基于嵌入模型的方法要優(yōu)于基于一階馬爾科夫鏈的方法?？梢园l(fā)現(xiàn)NEXT模型顯著優(yōu)于FPMC-LR和PRME-G模型，NEXT是基于神經(jīng)網(wǎng)絡(luò)的方法，該模型同時(shí)整合用戶偏好、序列信息、時(shí)空信息和朋友關(guān)系等進(jìn)行推薦，說(shuō)明用戶訪問(wèn)下一個(gè)興趣點(diǎn)偏好通常由多個(gè)因素影響，整合多個(gè)上下文信息有利于更為清晰地表明用戶訪問(wèn)下一個(gè)興趣點(diǎn)的潛在意圖，能夠提升下一個(gè)興趣點(diǎn)的推薦效果。

（3）GRU模型優(yōu)于FPMC-LR和PRME-G模型。GRU模型是最新的基于循環(huán)神經(jīng)網(wǎng)絡(luò)的變體，能夠捕獲長(zhǎng)序列的依賴問(wèn)題。盡管GRU模型并沒有整合地理位置信息，但是GRU模型依然表現(xiàn)出較好的推薦效果，可能的原因是FPMC-LR和PRME-G這兩個(gè)模型沒有對(duì)序列信息進(jìn)行充分建模，因?yàn)檫@兩個(gè)模型都只用到了用戶最后一次簽到來(lái)推薦用戶下一個(gè)訪問(wèn)的興趣點(diǎn)，這導(dǎo)致用戶之前的簽到序列信息被忽略。同時(shí)也說(shuō)明了GRU模型使用非線性變換對(duì)于序列建模的有效性，能夠挖掘用戶歷史簽到興趣點(diǎn)的潛在偏好信息進(jìn)行有效的序列推薦。

（4）本文提出的整合用戶序列信息、用戶關(guān)系信息、時(shí)空信息和類別信息的模型優(yōu)于表現(xiàn)最好的NEXT模型。盡管NEXT也通過(guò)整合序列信息、時(shí)空信息和其他上下文信息進(jìn)行推薦，但是它有幾個(gè)方面的不足，NEXT只用到了用戶上一個(gè)興趣點(diǎn)的簽到信息進(jìn)行推薦，同時(shí)它只使用了一層簡(jiǎn)單的神經(jīng)網(wǎng)絡(luò)整合這些上下文，因此NEXT不能有效對(duì)序列信息進(jìn)行建模。而本文提出的GRU-R模型使用最新的GRU模型，能夠有效對(duì)序列信息建模，深入考慮用戶關(guān)系、時(shí)空信息和類別信息等進(jìn)行下一個(gè)推薦點(diǎn)推薦。

4.2 模型參數(shù)及性能分析

本節(jié)實(shí)驗(yàn)?zāi)康氖怯懻撃Ｐ蛥?shù)和不同上下文信息對(duì)于推薦準(zhǔn)確性的影響。

模型參數(shù)影響：對(duì)隱層神經(jīng)元個(gè)數(shù)和dropout進(jìn)行調(diào)參，討論模型參數(shù)對(duì)于推薦準(zhǔn)確性的影響。

從表7的實(shí)驗(yàn)結(jié)果可以看出，當(dāng)隱層神經(jīng)元個(gè)數(shù)為128時(shí)兩個(gè)數(shù)據(jù)集在ACC@10和MRR指標(biāo)上都達(dá)到較高的準(zhǔn)確率。當(dāng)模型隱層神經(jīng)元個(gè)數(shù)很少時(shí)，模型的效果會(huì)變得很差，這是由于隱層神經(jīng)元個(gè)數(shù)的限制，導(dǎo)致模型無(wú)法對(duì)用戶簽到序列進(jìn)行有效建模，限制了模型能力的表達(dá)。另外，隱層神經(jīng)元個(gè)數(shù)太多時(shí)，程序的效率也會(huì)有所下降，這是因?yàn)殡S著隱層神經(jīng)元個(gè)數(shù)的增加會(huì)導(dǎo)致訓(xùn)練參數(shù)極劇增加，增加了模型的訓(xùn)練難度，也會(huì)使模型更容易出現(xiàn)過(guò)擬合現(xiàn)象。

表7 隱層神經(jīng)元個(gè)數(shù)對(duì)數(shù)據(jù)集的影響Table 7 Influence of number of hidden neurons on datasets %

確定隱層神經(jīng)元個(gè)數(shù)后，本文分別嘗試dropout值為0.1、0.2、0.3和0.4。經(jīng)過(guò)實(shí)驗(yàn)發(fā)現(xiàn)當(dāng)dropout為0.1和0.2時(shí)模型表現(xiàn)較好，當(dāng)dropout為0.1時(shí)模型表現(xiàn)出最優(yōu)的效果，因此選擇dropout為0.1。

上下文信息影響：下面本實(shí)驗(yàn)主要討論每種上下文信息對(duì)于模型推薦效果提升作用影響，這里只選用了ACC@10指標(biāo)用于測(cè)試。使用標(biāo)準(zhǔn)的GRU模型作為基線。GRU+表示只整合單一的上下文信息，GRU-R是本文提出的綜合用戶關(guān)系和其他上下文的模型。

從表8可以看出，興趣點(diǎn)不同的上下文信息對(duì)于下一個(gè)興趣點(diǎn)的推薦準(zhǔn)確性有不同程度影響，距離間隔對(duì)于下一個(gè)興趣點(diǎn)推薦的效果影響最大，表明在下一個(gè)興趣點(diǎn)中，用戶的偏好會(huì)受到地理因素強(qiáng)烈的影響。實(shí)驗(yàn)結(jié)果也表明，用戶關(guān)系在下一個(gè)興趣點(diǎn)推薦中同樣具有重要作用，說(shuō)明在下一個(gè)興趣點(diǎn)推薦中，用戶關(guān)系越緊密的用戶通常會(huì)表示相似的用戶偏好，訪問(wèn)下一個(gè)興趣點(diǎn)也越相似。然而，其他上下文信息（如簽到時(shí)間、相鄰兩個(gè)興趣點(diǎn)的過(guò)渡時(shí)間、興趣點(diǎn)的類別信息等）對(duì)于提升推薦準(zhǔn)確性效果并不明顯。但是綜合以上所有信息的輸入，可以看出本文提出的GRU-R的推薦效果得到顯著提升，說(shuō)明用戶訪問(wèn)的下一個(gè)興趣點(diǎn)往往由不同的上下文信息共同導(dǎo)致，整合不同的上下文信息能夠給用戶提供更準(zhǔn)確的推薦。

表8 上下文信息對(duì)推薦準(zhǔn)確性的影響Table 8 Influence of context information on recommendation accuracy %

注意力機(jī)制近年來(lái)，注意力機(jī)制已經(jīng)被證明能夠有效提升模型的推薦效果，有很多注意力模型被提出應(yīng)用于各種任務(wù)中。文獻(xiàn)[26]通過(guò)在RNN模型上使用分層注意力模型已經(jīng)成功的應(yīng)用于文檔分類中，顯著提升了文檔分類效果。因此，本文嘗試使用分層注意力機(jī)制進(jìn)一步捕獲用戶的潛在的簽到行為特征。分層注意力模型的計(jì)算公式如下：

其中h t表是神經(jīng)網(wǎng)絡(luò)模型的t時(shí)刻的輸出，u t是h t經(jīng)過(guò)一層全連接神經(jīng)網(wǎng)絡(luò)后的向量表示。u w表示被隨機(jī)初始化的上下文向量，v表示整合用戶所有時(shí)刻簽到信息的最終偏好向量表示。在增加注意力機(jī)制的模型中，最終的偏好v將會(huì)替代循環(huán)神經(jīng)網(wǎng)絡(luò)的最后時(shí)刻的輸出用于興趣點(diǎn)預(yù)測(cè)。增加分層注意力機(jī)制的模型在兩個(gè)數(shù)據(jù)集的的實(shí)驗(yàn)結(jié)果如圖4～7所示。

圖4 Gowalla數(shù)據(jù)集上ACC@10隨迭代次數(shù)變化Fig.4 ACC@10 of Gowalla dataset varies with number of iterations

圖5 Gowalla數(shù)據(jù)集上MRR隨迭代次數(shù)變化Fig.5 MRR of Gowalla dataset varies with number of iterations

圖6 CA數(shù)據(jù)集上ACC@10隨迭代次數(shù)變化Fig.6 ACC@10 of CA dataset varies with number of iterations

圖7 CA數(shù)據(jù)集上MRR隨迭代次數(shù)變化Fig.7 MRR of CA dataset varies with number of iterations

從圖4～7上兩個(gè)數(shù)據(jù)集實(shí)驗(yàn)結(jié)果可以看出，是否增加注意力模型對(duì)于模型的迭代收斂速度幾乎沒有影響，兩者的收斂趨勢(shì)一致。可以發(fā)現(xiàn)引入注意力機(jī)制后的模型在ACC@10和MRR指標(biāo)上均得到了輕微的提升，說(shuō)明使用注意力機(jī)制有利于提升模型的推薦效果。注意力能夠影響模型的推薦效果的原因可能是由以下方面造成，使用注意力機(jī)制能夠通過(guò)控制權(quán)重的方式控制用戶簽到信息對(duì)于下一個(gè)興趣點(diǎn)推薦重要性的影響，從而自動(dòng)篩選掉對(duì)于用戶下一個(gè)興趣點(diǎn)影響較弱的簽到信息，同時(shí)使用注意力機(jī)制能夠捕獲用戶更深層的簽到行為特征，比如用戶簽到行為的周期性影響等。

5 總結(jié)

本文研究了下一個(gè)興趣點(diǎn)推薦的問(wèn)題，提出了利用用戶關(guān)系和多個(gè)上下文信息進(jìn)行下一個(gè)興趣點(diǎn)推薦的模型（GRU-R）。首次提出了一種新用戶關(guān)系嵌入模型User2Vec，并將其應(yīng)用到循環(huán)神經(jīng)網(wǎng)絡(luò)中。為了提高下一個(gè)興趣點(diǎn)推薦的效果，本文同時(shí)考慮了用戶簽到序列信息、用戶關(guān)系、興趣點(diǎn)時(shí)空信息和類別信息等方面。本文在真實(shí)的數(shù)據(jù)集上測(cè)試了模型的性能，實(shí)驗(yàn)結(jié)果表明，通過(guò)增加用戶關(guān)系等信息模型的準(zhǔn)確性得到了進(jìn)一步的提升。盡管本文提出GRU-R模型具有很好的推薦準(zhǔn)確性，但是該模型依然存在改進(jìn)的地方來(lái)獲得更好的效果，比如尋找描述更豐富的數(shù)據(jù)集，進(jìn)一步結(jié)合用戶基本屬性、地點(diǎn)基本屬性來(lái)解決興趣點(diǎn)推薦中出現(xiàn)的冷啟動(dòng)問(wèn)題，或者整合其他輔助的信息如圖像、用戶評(píng)分和描述文本信息等，給出更精確的下一個(gè)興趣點(diǎn)推薦。