王興源

（南京郵電大學(xué) 計算機學(xué)院,南京 210046）

隨著移動設(shè)備,全球定位系統(tǒng)（Global Position System,GPS）和Web 2.0技術(shù)的迅速發(fā)展,基于位置的社交網(wǎng)絡(luò)（Location-Based Social Network,LBSN）逐漸在人們的日常生活中普及.與傳統(tǒng)的社交網(wǎng)絡(luò)相比,LBSN不僅包括了人與人之間的聯(lián)系,還可以共享人們之間的位置信息,使得線上社交和線下社交相結(jié)合,用戶可以隨時分享自己或瀏覽他人的足跡.目前主流的社交應(yīng)用（如Twitter、Foursquare、Gowalla等）都滿足LBSN的主要特性.這樣的應(yīng)用每天都在產(chǎn)生TB級別的時空數(shù)據(jù),其通常以GPS數(shù)據(jù)或簽到數(shù)據(jù)（check-ins）的形式記錄.這些信息既是個人行為習(xí)慣與偏好的體現(xiàn)[1],也在一定程度上反映了一座城市里人們的生活方式和移動模式.基于以上數(shù)據(jù),多種類型的推薦被提出[2],其中興趣點推薦為其重要研究方向之一.

如圖1所示,興趣點推薦模型的方法主要分為傳統(tǒng)推薦方法和深度學(xué)習(xí)推薦方法.其中傳統(tǒng)推薦方法可分為以下5種:（1）協(xié)同過濾,其基本思想為相似的用戶有相似的興趣,通過相似度計算進行推薦.Ference等[3]綜合考慮用戶偏好,社交因素以及地理位置,在協(xié)同過濾的基礎(chǔ)上提出了UPS-CF算法,將本地居民和外地居民分開推薦.（2）概率模型,其認為用戶-POI簽到矩陣分布符合特定的概率分布模型.Cheng等[4]基于對用戶簽到數(shù)據(jù)的觀測,發(fā)現(xiàn)其有家、公司等多個分布中心,基于此提出了一個多中心高斯分布模型來進行推薦.（3）矩陣分解,其將用戶簽到矩陣分解為用戶矩陣U和興趣點矩陣V,從U和V中可以分別得到所有用戶和興趣點的潛在表示向量,通過兩種表示向量內(nèi)積計算推薦評分.Cheng等[5]提出的基于矩陣分解和馬爾科夫鏈的FPMC-LR模型,依據(jù)矩陣分解學(xué)習(xí)所有用戶的整體偏好,通過興趣點轉(zhuǎn)移矩陣的馬爾科夫鏈來挖掘出人們在時間維度的移動模式.（4）基于鏈接的模型,此類模型考慮用戶與用戶,興趣點與興趣點,用戶與興趣點之間的聯(lián)系,據(jù)此構(gòu)建對應(yīng)圖進行推薦.Ying等[6]通過構(gòu)建一個HITS（Hyperlink Induced Topic Search）為基礎(chǔ)的模型,將興趣點推薦問題轉(zhuǎn)化用戶-興趣點的相關(guān)度問題.（5）混合模型,即綜合考慮各個模型的優(yōu)缺點,一般采用兩個模型進行聯(lián)合推薦.Ye等[7]的USG模型中,一方面通過協(xié)同過濾處理用戶偏好以及朋友關(guān)系,另一方面又采用冪律分布概率模型對地理因素進行建模,最后將推薦的結(jié)果線性相加進行混合推薦.張岐山等[8]提出的SoGeoCat模型將協(xié)同過濾和矩陣分解算法相結(jié)合,根據(jù)用戶相似性與潛在興趣點進行建模,克服了單一模型的不足,緩解了數(shù)據(jù)稀疏的問題.

圖1 興趣點推薦方法分類

深度學(xué)習(xí)的興趣點推薦方法主要有以下4種:（1）基于RNN（Recurrent Neural Networks）的方法.由于近來RNN在自然語言處理領(lǐng)域表現(xiàn)優(yōu)秀,研究人員就嘗試著將其應(yīng)用在任務(wù)相似的興趣點推薦領(lǐng)域.Liu等[9]提出了ST-RNN（Spatial-Temporal RNN）時空循環(huán)神經(jīng)網(wǎng)絡(luò)模型,此模型在普通的RNN基礎(chǔ)上增加了時間轉(zhuǎn)移矩陣和距離轉(zhuǎn)移矩陣,通過此方法,ST-RNN能夠捕捉時間因素和距離因素對人們移動軌跡的影響.（2）基于LSTM（Long Short-Term Memory）的方法.LSTM在其網(wǎng)絡(luò)結(jié)構(gòu)中引入了輸入門,遺忘門和輸出門的概念,解決了RNN在處理較長序列時產(chǎn)生的梯度消失問題.Zhao等[10]提出的SLSTM模型,采用了堆疊LSTM和Embedding嵌入層來進行興趣點推薦.王立等[11]提出的POI-LSTM推薦框架,將用戶信息、好友關(guān)系、POI信息和評論信息進行Embedding化以后輸入到LSTM神經(jīng)網(wǎng)絡(luò)中捕捉用戶的興趣變化趨勢來進行推薦.Huang等[12]提出的AT-LSTM模型,將時空信息融入模型中,同時引入了注意力機制,實現(xiàn)了高效的興趣點推薦.Zhao等[13]提出的STGN模型,基于LSTM與時空數(shù)據(jù),對LSTM每個cell的內(nèi)部結(jié)構(gòu)進行了修改優(yōu)化,使得推薦效果大幅度提高.（3）基于GRU（Gated Recurrent Unit）的模型.相比于LSTM,GRU因使用同一門控來控制需要遺忘和記憶的信息而大大減少了網(wǎng)絡(luò)結(jié)構(gòu)所需要的參數(shù),使得其計算代價變低了.（4）基于圖嵌入（Graph Embedding,GE）的模型.GE通過對類似于用戶-興趣點這樣的二分圖進行學(xué)習(xí),得到低維的特征表示用作后續(xù)步驟的推薦.Xie等[14]通過對興趣點-興趣點圖,興趣點-區(qū)域圖,興趣點-時間圖,興趣點-文字圖進行學(xué)習(xí),分別研究了序列因素、地理因素、時間因素和語義因素對用戶移動軌跡的影響,通過計算用戶移動軌跡之間的相似性來進行興趣點推薦.

雖然上述的傳統(tǒng)方法和深度學(xué)習(xí)方法在興趣點推薦領(lǐng)域中取得了不錯的成績,但是他們沒有對興趣點本身附帶的輔助信息進行很好的使用和融合,如興趣點的種類,興趣點的品牌等.本文提出了一種基于圖嵌入的GRU興趣點推薦方法GE-GRU.該模型首先利用GE方法對POI本身及其輔助信息進行融合,得到了信息豐富的深層興趣點Embedding表示信息,再將此Embedding信息輸入到GRU網(wǎng)絡(luò)中進行訓(xùn)練,最后利用用戶Embedding和通過GE模型學(xué)習(xí)到的興趣點Embedding進行推薦.相比于現(xiàn)有的模型,GE-GRU一方面吸收了GE可以通過從圖中學(xué)習(xí)出低維特征表示的優(yōu)點,另一方面運用了GRU網(wǎng)絡(luò)擅長捕捉序列依賴信息的特點,兩者相結(jié)合,使得其在興趣點推薦上表現(xiàn)良好.

本文的貢獻點如下:

（1）在數(shù)據(jù)預(yù)處理階段,為了緩解數(shù)據(jù)稀疏問題,采用了擴充用戶移動序列的數(shù)據(jù)增強方法.

（2）對興趣點及其輔助信息進行了融合處理,使得興趣點表征信息更加豐富.

（3）將GE圖嵌入模型與GRU門控循環(huán)單元模型相結(jié)合,吸取了二者的優(yōu)點,提高了興趣點推薦效果.

后文組織如下:第1節(jié)介紹興趣點推薦的問題定義以及GE和GRU的簡介; 第2節(jié)介紹GE-GRU興趣點推薦模型的具體實現(xiàn)細節(jié); 第3節(jié)介紹數(shù)據(jù)集、數(shù)據(jù)預(yù)處理以及實驗結(jié)果及分析; 第4節(jié)總結(jié)概括全文.

1 相關(guān)背景

本節(jié)主要介紹模型的問題定義,和模型架構(gòu)相關(guān)的基于圖嵌入的模型和GRU網(wǎng)絡(luò)結(jié)構(gòu).

1.1 問題定義

1.2 圖嵌入簡介

圖廣泛存在于真實世界的多種場景中,圖即節(jié)點和邊的集合,如社交網(wǎng)絡(luò)中人與人之間的聯(lián)系,興趣點與興趣點之間的關(guān)聯(lián).

圖嵌入技術(shù)[15]是一種將圖數(shù)據(jù),通常為高維稠密矩陣映射為低微稠密向量的過程,其習(xí)得的向量不僅能夠保留圖模型的結(jié)構(gòu)信息和潛在的特征,還能夠很好地解決圖數(shù)據(jù)難以高效輸入機器學(xué)習(xí)算法的問題.圖嵌入將屬性圖轉(zhuǎn)換為向量或者向量集,學(xué)習(xí)得到的嵌入數(shù)據(jù)捕捉了圖的拓撲結(jié)構(gòu)、頂點到頂點的關(guān)系以及關(guān)于圖、子圖和頂點的其他相關(guān)信息.

圖嵌入技術(shù)的基礎(chǔ)是Word2Vec算法[16],其思想為:利用海量的文本序列,根據(jù)上下文單詞預(yù)測目標單詞共同出現(xiàn)的概率,構(gòu)造出一個最優(yōu)化的神經(jīng)網(wǎng)絡(luò),此網(wǎng)絡(luò)中的特定參數(shù)矩陣即單詞的向量.Skip-gram為Word2Vec的模型之一,如圖2所示,其網(wǎng)絡(luò)有輸入層、隱層和輸出層.網(wǎng)絡(luò)的輸入即每個單詞的獨熱編碼（one-hot）,獨熱編碼是一個長度與單詞字典相同的向量,除了其在字典的對應(yīng)位置為1以外,其他都為0,隱層沒有激活函數(shù),其輸出為單詞的嵌入表示,輸出層為與預(yù)測單詞鄰域單詞的Softmax分類器.由圖2可以看出,Word2Vec本質(zhì)上是一種將單詞從高維冗長的獨熱編碼形式降維到含義豐富的低維表示向量.

圖2 Skip-gram模型

圖嵌入的方法主要分為3類[15]:1）基于因子分解的方法; 2）基于隨機游走的方法; 3）基于深度學(xué)習(xí)的方法.DeepWalk[17]是典型的基于隨機游走的方法,其受Word2Vec啟發(fā),首先選取某特定的點作為起點,接著隨機游走一定的步數(shù),得到序列,將此序列視為句子輸入到Word2Vec模型中進行訓(xùn)練,得到圖中每個點的表示向量,該向量反映的是該點在途中的局部結(jié)構(gòu),兩個點在圖中的共有近鄰點越多,其對應(yīng)的兩個向量之間的相似度就越高.

1.3 GRU簡介

GRU是循環(huán)神經(jīng)網(wǎng)絡(luò)的一種,其網(wǎng)絡(luò)結(jié)構(gòu)與LSTM類似,都是為了解決長期記憶和反向傳播中的梯度等問題而提出的,而前者與后者不同之處在于,GRU在使用了更少的門控單元的情況下能夠達到與LSTM網(wǎng)絡(luò)十分相當(dāng)?shù)男Ч?因此GRU相比之下更加容易訓(xùn)練,很大程度上提高了訓(xùn)練效率.

GRU的每個cell結(jié)構(gòu)如圖3所示,包括重置門（reset gate）,更新門（update gate）和隱藏層.重置門用來控制當(dāng)前cell需要保留多少上個cell傳遞的記憶,更新門在功能上實現(xiàn)了LSTM中遺忘門和輸入門的功能,其控制了需要從上個cell的隱藏層中遺忘多少信息,和需要從當(dāng)前cell的隱藏層中加入多少信息,兩者結(jié)合得到最后輸出的隱藏層信息.GRU的前向傳播公式如下:

圖3 GRU模塊結(jié)構(gòu)

其中,σ表示Sigmoid函數(shù),W表示GRU網(wǎng)絡(luò)結(jié)構(gòu)中的各權(quán)重矩陣,h表示隱藏層信息,b表示偏置項,tanh表示輸出的激活函數(shù).

2 模型介紹

現(xiàn)有的興趣點推薦模型存在著數(shù)據(jù)稀疏與冷啟動問題,針對此問題,本文提出了融合興趣點與其輔助信息的思路.興趣點輔助信息指的是興趣點名稱,興趣點品牌以及興趣點種類這些和興趣點本身密切相關(guān)的信息.現(xiàn)有的基于深度學(xué)習(xí)的興趣點推薦模型只考慮對興趣點本身進行學(xué)習(xí),而忽略了興趣點輔助信息中所蘊含的信息.通常,有著相似輔助信息的興趣點在Embedding空間中也會有著相似的Embedding表示.基于這樣的前提,本文提出了采用GE方法學(xué)習(xí)出融合輔助信息的興趣點Embedding表示,再將融合了Embedding表示的用戶序列信息輸入到GRU神經(jīng)網(wǎng)絡(luò)中得到用戶Embedding表示,此用戶Embedding和興趣點Embedding進行內(nèi)積運算,得到該用戶下一個可能去的興趣點列表排序,據(jù)此進行推薦.

本節(jié)將從興趣點基礎(chǔ)Embedding生成模型、改良Embedding生成模型,GE-GRU模型網(wǎng)絡(luò)結(jié)構(gòu)3方面進行介紹.

2.1 基礎(chǔ)Embedding生成模型

基于GE的Embedding生成模型主要采用了隨機游走與Word2Vec的思想,本小節(jié)將分4個步驟介紹該模型.

（1）提取用戶訪問序列.如圖4所示,對同一個用戶來說,如果其連續(xù)訪問兩個興趣點的時間不超過ΔT,則這兩次連續(xù)訪問在同一個用戶訪問序列中.

圖4 提取用戶序列

（2）興趣點-興趣點有向圖構(gòu)造.如圖5所示,根據(jù)步驟（1）已經(jīng)提取完成的用戶訪問序列,建立興趣點-興趣點有向圖G.

圖5 構(gòu)建有向圖

（3）隨機游走.本步驟采用了DeepWalk[13]的思想,如圖6所示,根據(jù)步驟（2）已經(jīng)建立好的有向圖進行隨機游走:從一個節(jié)點出發(fā),按照一定的概率隨機移動到其鄰居節(jié)點,并將該節(jié)點作為新的當(dāng)前節(jié)點,執(zhí)行數(shù)次這樣的步驟,得到一條游走路徑,其中每次從當(dāng)前節(jié)點vi移動到其鄰居節(jié)點vj的概率如式（6）所示.

圖6 隨機游走

（4）生成興趣點Embedding.此處采用了Word2Vec中skip-gram模型的思想,將步驟（3）得到的游走序列看作文本數(shù)據(jù)輸入到模型中,其目的是最大化同一序列中兩個節(jié)點之間共現(xiàn)的概率,因此訓(xùn)練得出的這兩個節(jié)點在Embedding空間中很接近.如圖7所示,通?？梢圆捎胦utput matrix作為所有節(jié)點的Embedding集合.

圖7 生成興趣點Embedding

2.2 改良Embedding生成模型

本小節(jié)主要介紹針對2.1節(jié)步驟（4）生成興趣點Embedding的改良工作,主要分為以下兩點:

（1）興趣點與其輔助信息融合.在2.1節(jié)步驟（4）中,模型只利用了興趣點本身的信息輸入到網(wǎng)絡(luò)中,并沒有利用到類似于興趣點種類這樣的輔助信息,如此學(xué)習(xí)得出的興趣點Embedding蘊含的信息比較單一,不能夠很好地緩解冷啟動問題.加入興趣點輔助信息后,神經(jīng)網(wǎng)絡(luò)能夠挖掘出深層次的興趣點信息,讓Embedding含義變得更加豐富.

Eq為融合后的興趣點 q的Embedding,通過這樣的方式,在Embedding空間中,輔助信息相似的興趣點之間的距離就會比較相近,緩解了興趣點推薦中的冷啟動問題.

（2）在上述（1）中,式（2）的融合方式是基于這樣一個前提:所有的輔助信息對于興趣點Embedding的重要程度都是一致的.這顯然不符合實際,例如某用戶要前往健身房運動,此時健身房的興趣點種類（運動）要比健身房的品牌更加趨近于用戶訪問該興趣點的原因.因此,不同的輔助信息對于興趣點的重要程度是不一致的,針對此,本文提出了基于注意力機制的興趣點輔助信息融合方法.

2.3 GE-GRU模型網(wǎng)絡(luò)結(jié)構(gòu)

如圖8所示,GE-GRU模型網(wǎng)絡(luò)的整體架構(gòu)分為GE和GRU所示,首先通過GE訓(xùn)練出興趣點的Embedding表示,再將此Embedding表示當(dāng)作基于GRU的網(wǎng)絡(luò)中的Embedding層的初始化參數(shù),這一步橋接了模型的兩個部分,使得蘊含深層次信息的興趣點Embedding能夠順利輸入到GRU網(wǎng)絡(luò)中進行訓(xùn)練,從而使得后續(xù)的神經(jīng)網(wǎng)絡(luò)能夠擁有良好的輸入,提高了訓(xùn)練的質(zhì)量.

圖8 GE-GRU整體模型

具體的GE結(jié)構(gòu)如圖9所示,SI0,SI1,…,SIn表示興趣點本身及其n個輔助信息,第1步對興趣點及其輔助信息進行簡單Embedding表示,第2步將各Embedding表示采用注意力機制,按式（2）的方式結(jié)合成新的興趣點Embedding.模型的最后一層是sampled Softmax,Softmax函數(shù)的一種變體.訓(xùn)練完成后,采用模型輸出層的output matrix作為所有興趣點Embedding的矩陣集合.

圖9 GE模塊框架

2.4 損失函數(shù)

可將模型最終的任務(wù)看作一個多分類任務(wù),即若該任務(wù)中共有N個興趣點,每次推薦都是在進行一次N分類,挑選出評分排名最靠前的k個興趣點進行推薦,而多分類的損失函數(shù)通常使用交叉熵損失函數(shù)來表示.

交叉熵能夠衡量同一個隨機變量中的兩個不同概率分布的差異程度,在機器學(xué)習(xí)中就表示為真實的概率分布和預(yù)測的概率分布之間的差異,交叉熵的值越小,其模型預(yù)測效果就越好.在多分類問題中,交叉熵通常與Softmax函數(shù)一起出現(xiàn),Softmax函數(shù)將模型輸出的結(jié)果進行處理,使其所有分類的預(yù)測值和為1,再通過交叉熵來計算損失.最終損失函數(shù)如式（9）所示.

其中,q 為模型預(yù)測的概率分布,而 p為真實的概率分布,模型的目的就是不斷縮小預(yù)測的概率分布與真實的概率分布之間的差異,差異越小,實驗效果就越好.

2.5 訓(xùn)練方法

GE-GRU每次單獨處理一條分割好的序列,采用mini-batch梯度下降的方法對模型進行訓(xùn)練.batch_size即每次訓(xùn)練的樣本數(shù)量,當(dāng)batch_size太小比如1時,每一個訓(xùn)練數(shù)據(jù)都要進行權(quán)值更新,這樣就舍棄了向量化處理帶來的加速; 當(dāng)batch_size太大如全部樣本都算為一個batch,全部數(shù)據(jù)訓(xùn)練完才進行一次權(quán)值更新,在數(shù)據(jù)量大時,單次迭代時間太長.綜合考慮,本實驗將batch_size定為512,采用Adam優(yōu)化器對損失函數(shù)進行優(yōu)化.

Adam優(yōu)化器結(jié)合了AdaGrad和RMSProp兩種優(yōu)化器的優(yōu)點,其實現(xiàn)簡單,計算高效,對內(nèi)存需求少;參數(shù)更新不受梯度伸縮變換的影響,并且非常適用于大規(guī)模的數(shù)據(jù)以及參數(shù)的場景,十分符合本文的需求.

3 實驗

3.1 數(shù)據(jù)集介紹

本文使用的Foursquare數(shù)據(jù)集[18]是一個典型的基于位置的社交網(wǎng)絡(luò)數(shù)據(jù)集,時間跨度從2010年4月至2011年9月,地理范圍集中在美國加利福尼亞州.具體數(shù)據(jù)如表1所示.

表1 Foursquare數(shù)據(jù)集參數(shù)

3.2 數(shù)據(jù)預(yù)處理

本文采用了Cheng等[5]的方法對用戶訪問序列做了分割處理,即將同一用戶訪問序列中,如果連續(xù)兩次訪問之間的時間間隔不超過6 h,則將其編入同一序列之中,若超過6 h,則編入不同序列中.同時,為了防止不活躍用戶與不活躍興趣點對數(shù)據(jù)集的影響,本文還過濾掉了總check-ins數(shù)少于5條的用戶和興趣點,以及對用戶序列分割后少于5條訪問序列的用戶.

如表2所示,在數(shù)據(jù)增強前,數(shù)據(jù)集提取出的有效用戶移動序列數(shù)為13 830條,數(shù)據(jù)增強后,序列總數(shù)擴充到了119 142條.深度學(xué)習(xí)的特性是樣本數(shù)量越多,其效果越明顯.在數(shù)據(jù)增強前,總樣本數(shù)量僅有13 830條,用于訓(xùn)練的樣本數(shù)量僅有9681條,樣本太少的情況下,神經(jīng)網(wǎng)絡(luò)幾乎無法學(xué)習(xí)出隱藏于序列中的知識,所以實驗效果很差.

表2 樣本數(shù)量對比

3.3 Baseline方法介紹

（1）FPMC-LR[5]:基于矩陣分解和馬爾科夫鏈的興趣點推薦模型,依據(jù)矩陣分解學(xué)習(xí)所有用戶的整體偏好,通過興趣點轉(zhuǎn)移矩陣的馬爾科夫鏈來挖掘出人們在時間維度的移動模式.

（2）LSTM[20]:長短期記憶網(wǎng)絡(luò),通過遺忘門來選擇性遺忘上個cell傳入的信息,通過輸入門來選擇需要記憶多少當(dāng)前cell中新的信息,通過輸出門輸出隱層信息.

（3）GRU[21]:門控循環(huán)單元,整體結(jié)構(gòu)與LSTM類似,不同之處在于其將遺忘門和輸入門合二為一成更新門.

3.4 評價指標

本文采用了興趣點推薦中常用的Accuracy@k指標來評價實驗結(jié)果,具體定義如下:

在某一次推薦中,計算所有興趣點的排序分數(shù),按照從高到底編入一個列表,其中真實標簽興趣點所在的排序位置為,如果m≤k,則稱該次推薦命中,記為hit=1,否則hit=0.最終結(jié)果如式（10）所示.

3.5 實驗結(jié)果分析

本文采用Accuracy@1,Accuracy@5,Accuracy@10,Accuracy@15,Accuracy@20五種評價標準.實驗結(jié)果如表3所示.

表3 對比實驗

相較于傳統(tǒng)推薦方法FPMC-LR與深度學(xué)習(xí)推薦方法LSTM、GRU,GE-GRU在Foursquare數(shù)據(jù)集上效果最優(yōu),在Accuracy@10這一指標上,GE-GRU的效果為0.467,優(yōu)于GRU 3%,優(yōu)于LSTM 7%.在其他Accuracy指標上,僅在Accuracy@20上,GE-GRU效果稍遜于FPMC-LR,且相差不多.在k越來越大時,其同時推薦的興趣點個數(shù)也增加了,推薦成本也增加了.這說明在將序列數(shù)據(jù)輸入到GRU網(wǎng)絡(luò)之前,通過GE學(xué)習(xí)得出的興趣點Embedding,在很好地融合了其輔助信息后,挖掘出了興趣點深層次的信息,使得興趣點Embedding蘊含的內(nèi)容更加豐富,從而讓用戶訪問序列表示更加準確.

4 結(jié)論

本文在基于位置的社交網(wǎng)絡(luò)背景下,采用了數(shù)據(jù)增強方法,豐富了用戶訪問序列數(shù)量,通過圖嵌入技術(shù)對興趣點及其輔助信息在注意力機制下融合,得到的興趣點Embedding挖掘出了深層次的信息,將此Embedding輸入到GRU中能夠捕捉到用戶近期偏好.實驗結(jié)果表明,本文的GE-GRU方法能夠有效地提升興趣點推薦的準確率,并且能夠緩解數(shù)據(jù)稀疏與冷啟動的問題.