多源異構簽到數據中改進RNN的POI推薦

高 麗，楊立身

(1.鄭州經貿學院 計算機與人工智能學院，河南 鄭州 451191； 2.河南理工大學 計算機科學與技術學院，河南 焦作 454003)

0 引 言

在基于位置的社交網絡(location-based social networks，LBSNs)[1]中，興趣點(point-of-interest，POI)推薦已逐漸成為推薦系統(tǒng)領域的活躍學術研究重點[2]。很多現(xiàn)有POI推薦方法主要考慮某一個或者某幾個影響因素[3]，很少綜合考慮社交、順序、地理、時間對POI推薦的影響，限制了POI取得更好的推薦效果。此外，日常生活中簽到行為的稀疏性也在一定程度上制約了POI推薦精度[4]。

為了實現(xiàn)智能化、可擴展的多源異構信息，進行更加準確的POI推薦，基于多源異構簽到數據，提出了一種利用改進型RNN的POI推薦方法。創(chuàng)新點總結如下：

(1)引入因子分解機對多源異構簽到數據進行處理，有效降低了數據稀疏性帶來的POI推薦不準確問題。

(2)提出了MMBE模型融合社交關系、順序、時間、地理位置4種因素的矩陣，計算出多源異構數據的POI影響因子。

(3)將時間、順序、地理位置、社交關系因子用于循環(huán)神經網絡選定候選狀態(tài)，避免了傳統(tǒng)RNN對較遠時間記憶能力的喪失，同時將其它影響POI推薦的重要因子也考慮進來，提高推薦POI的質量。

1 相關工作

本節(jié)從影響推薦的多源重要因素(社交關系、順序、地理位置、時間)介紹相關的興趣點POI推薦，同時介紹RNN算法。

1.1 考慮因素

文獻[5]將用戶相似性信息作為正則化項并入矩陣分解或張量模型中，取得了不錯的POI推薦效果，同時也驗證了社交關系對POI的影響。文獻[6]將順序對POI的推薦的影響考慮進來，提升了推薦效果。文獻[7]將地理影響納入加權的正規(guī)化MF模型中，取得了不錯的POI推薦效果。文獻[8]中首先提出了不均勻性，這種不均勻性表示用戶的簽到偏好隨時間的變化，將時間因素考慮進來，也驗證了時間對POI推薦的影響，提升了推薦效果。

綜合上述研究可以看到，影響POI推薦的主要因素有社交、順序、地理位置和時間。現(xiàn)有方法主要考慮上述兩種或者3種因素進行融合以此進行興趣點推薦。文獻[9]融合社交關系和位置影響的地點推薦算法(location recommendation algorithm combined with social relationships and geographic influences，LRACWSRAGI)將社交關系和地理位置進行融合，推薦精度優(yōu)于傳統(tǒng)單一因素的推薦；文獻[10]基于地理-社會-評論關系的典型化興趣點推薦方法(geo-social-comment relationship-based typical point-of-inte-rest recommendation approach，GRTPRA)，融合了地理位置、社會、評論關系信息，推薦多樣性和準確率都有較大提高。文獻[11]融合多因素的興趣點協(xié)同推薦方法研究(study on point-of-interest collaborative recommendation method fusing multi-factors，SOPCRMFM)，融合了地理位置、社交關系、情感等因素，準確率和召回率也都一定程度有所提高。所提方法主要與上述3種方法進行對比實驗。

1.2 循環(huán)神經網絡

循環(huán)神經網絡是特意用來處理時序數據樣本的一種神經網絡，其主要的表現(xiàn)形式是記憶網絡在簽名時的信息，并用于當前所輸出的計算中，也就是說隱藏層之間的節(jié)點是相互連接的，且隱藏層的輸入中包含有輸入層的輸出以及上一時刻隱藏層的輸出。

文獻[12]通過存儲時間信息，獲得更長的信息，獲得了較好的推薦準確度。文獻[13]采用循環(huán)神經網絡建模用戶偏好和項目特征化的演化，提出了一種循環(huán)推薦網絡來預測用戶軌跡。取得了較好的預測效果。文獻[14]用門控循環(huán)單元模型對時間和相關距離信息進行建模，提取用戶興趣特征偏好，對用戶進行推薦，取得了較好的推薦效果。

可見，循環(huán)神經網絡不僅能處理時間序列的樣本，而且能融合其它影響因子，共同提升推薦精度。

1.3 本文工作與以前的研究之間的區(qū)別

使用更加異構的信息來構建智能POI推薦模型已經成為推薦系統(tǒng)領域的科學共識，盡管這使模型變得更加復雜。先前的大多數研究都利用上述一種或多種因素來構成它們的POI推薦模型。但是，它們缺乏對這些因素對用戶簽到行為的共同影響的綜合分析，這可能是由于難以對異構信息進行建模以及難以以統(tǒng)一的方式發(fā)現(xiàn)跨異構工作流活動的多種類型的行為模式所致。此外，影響用戶興趣點的因素還存在稀疏性問題，RNN能夠對簽到的時間序列進行記憶，但是隨著時間的變化，記憶會喪失。因此，使本文的工作與以往的大多數研究區(qū)別最大的地方在于利用因子分解機，緩解數據稀疏性對POI推薦的影響，提出了融合上述4個因素的統(tǒng)一框架即MMBE框架，學習了他們之間的內在聯(lián)系，得到多源異構數據的影響因子。傳統(tǒng)方法改進RNN網絡，一般只考慮時序、距離以及上一個時刻候選狀態(tài)對候選狀態(tài)的影響，很少考慮到社會關系。本文通過MMBE模型，統(tǒng)一對上述4種因素建模，改進RNN(將得到的多源異構因素以及上一個時刻的候選狀態(tài)，共同作用于候選狀態(tài)的選定)，所得推薦更加可靠。

2 問題描述

首先，表1列出了模型中使用的所有參數符號。

其次，將一些初步概念定義如下：

定義1 POI：POI是與地理位置相關的項，例如餐廳或電影院。

定義2 網絡：網絡G=(U,E) 被定義為基于位置的社交網絡的拓撲結構，其中U是用戶的集合，E是用戶之間的關系的集合。

定義3 簽到活動：簽到活動是一個四元組 (u，v，lv，t)， 表示用戶u在時間t訪問POIv。為了調查這項工作中嵌入在日常模式中的功能，將一天劃分為多個時隙，這些時隙的持續(xù)時間以小時為單位。

定義4 用戶文檔：對于每個用戶u，定義一個用戶文檔Du，該文檔是與該用戶關聯(lián)的一組簽到活動。

定義5 主題：對于Du中的每個簽到活動，使用相應的主題z來建模用戶的興趣或偏好，該主題z是簽到時間t。

表1 模型中使用的參數符號

定義6 區(qū)域：對于Du中的每個簽到活動，均使用相應的區(qū)域r對用戶的空間移動性模式進行建模，該區(qū)域r是POIs位置上的多項分布。

第三，對POI推薦問題影響因子進行了定義。

給定一組用戶簽到活動D和目標用戶u(u∈U) 及其當前位置lu和時間tu，所提模型能夠預測t時刻，用戶u對興趣點v(v|u，lu，tu) 的興趣度p(v|u，lu，tu)v∈V)。 該因子能夠反映社交、順序、地理位置、時間協(xié)同對興趣點的影響。

3 提出的POI推薦方法

為了模擬社會、順序、地理和時間因素對用戶簽到行為的協(xié)同影響，針對POI推薦提出了一種多模態(tài)貝葉斯嵌入模型(MMBE)。

3.1 模型框架

圖1顯示了MMBE的圖形表示，其中N、K和R分別表示用戶、主題和區(qū)域的數量。MMBE的輸入數據(即用戶的簽到記錄，包括用戶嵌入、POIs嵌入、簽到時間和簽到位置被設置為觀察到的隨機變量(請參見圖1中的4個灰色圓圈)。在MMBE的圖形表示中，方框是復制品的“板”。最大的板塊表示用戶文檔，而最大的板塊中的內部標牌表示文檔中潛在變量(即z和r)和觀察變量(即t，fv和lv)的重復選擇。此外，外板代表Dirichlet分布或正伽瑪分布的參數，如本節(jié)稍后部分所述。(模型參數的符號請參見表1)。

圖1 MMBE模型

為了對社會因素和順序因素進行建模，MMBE學習一個共享的潛在主題空間，以在兩個不同的嵌入空間中生成基于網絡的用戶嵌入和基于序列的POI嵌入。更具體地說，在本文使用Skip-gram[15]模型和DeepWalk[16]分別學習編碼順序影響的基于序列的POI嵌入和編碼社會影響的基于網絡的用戶嵌入。然后，MMBE將預先訓練的用戶嵌入和POI嵌入作為輸入。

受早期用戶興趣和空間移動性建模的啟發(fā)[17]，假設用戶的簽到行為主要受其興趣和空間移動性模式的影響。為了對地理影響和時間影響建模，MMBE定義了兩種類型的潛在變量，即主題和區(qū)域，分別表征用戶興趣和空間移動性模式。更具體地來說，即用主題z和區(qū)域r共同定義主題變量(即POI主題z和用戶主題y)和區(qū)域變量r，以形成與POIs上的分布相關聯(lián)的聯(lián)合潛在因子主題區(qū)域。它們負責同時生成用戶的簽到時間，連續(xù)的POI嵌入和POI位置。同時，用于生成基于網絡的用戶嵌入的潛在變量yu(用于用戶u)是從Du中所有POIs主題中統(tǒng)一提取的。式(1)是用戶u關于主題z和主題y在區(qū)域r的聯(lián)合概率計算公式

(1)

式中：Mu表示Du中簽到活動的數量， 1(·) 表示指標函數，s是拉普拉斯平滑的平滑參數。

在MMBE中，使用Dirichlet分布[18](由Dirichlet()表示)作為變量z、r和t的先驗，這與LDA(潛在Dirichlet分布)中使用的多模態(tài)技術相似。對于用戶嵌入和POIs嵌入，本文的模型擴展了高斯LDA以對多個模態(tài)進行建模，并通過使用先驗的正態(tài)伽馬分布(由NormalGamma()表示)在兩個單獨的空間中生成連續(xù)的嵌入。盡管有可能從多元高斯分布中提取嵌入量，但本文還是從單變量高斯分布中分別提取每個嵌入維數。該處理更實用且更具成本效益。根據LBCPSNs上的空間聚類現(xiàn)象，即用戶最有可能訪問僅限于某些特定地理區(qū)域的大量POIs，所有討論的POIs在地理位置和簽到密度方面都屬于R區(qū)域。本文假設每個區(qū)域r的高斯分布和POIv的位置正態(tài)分布并用lv～N(μl,λl) 表示，其概率正態(tài)分布公式如式(2)所示

(2)

3.2 因子分解機(FM)

上一節(jié)介紹了MMBE模型，考慮了社交關系、順序、時間、地理位置對興趣點的協(xié)同影響，但是影響興趣點的因素存在稀疏性，例如，使用熱碼方式對時間進行特征編碼，一年有12個月，1月可以表示為 <1,0,0,0,0,0,0,0,0,0,0,0>， 傳統(tǒng)方法對這種高維稀疏的矩陣，無法很好地處理，因子分解機(FM)的出現(xiàn)改變了這種情況，F(xiàn)M算法是一種很高效的模型，可以在線性時間內完成模型的訓練，最大的優(yōu)勢是能夠對稀疏數據進行很好的學習。通過交互項可以學習特征之間的關聯(lián)關系。

因子分解機能夠對高度稀疏的數據進行參數學習

(3)

式中：w0是全局偏量，wi表示第i個變量的強度， 表示第i和第j個變量之間的相互作用。由式(3)可知，因子分解機邏輯回歸模型與特征分量間的相互關系組成。但是，當輸入的數據稀疏時titj很可能為0，這將造成Wi,j無法學習的問題。因此，利用因子分解機學習特征間相互關系的參數，如式(4)和式(5)所示

W=V·Vt

(4)

其中，W為系數矩陣，且滿足正定性。

(5)

使用兩個矢量的點乘來替代Wi,j， 其中v為N*K大小的矩陣。通過這樣的處理，即可以解決數據稀疏帶來的參數難以學習的問題。

3.3 改進循環(huán)神經網絡

在興趣點推薦算法中，對于連續(xù)時間因素方面的研究并不多。在興趣點推薦中，每一個POI都有自己的地理位置屬性，且用戶的行為是擁有時序性的，即具有時間和順序性。循環(huán)神經網絡(RNN)能夠對序列模式進行建模。但是僅僅考慮用戶時間和順序影響是不夠的，因為興趣點還被當前地理位置以及社交關系影響。在興趣點推薦算法中，一個用戶訪問興趣點，易受好友影響，同時訪問興趣點具有時間規(guī)律以及存在先后順序。此外當前所在地理位置也會對接下來要訪問的興趣點產生影響，因此在進行興趣點推薦時需要綜合考慮社交影響、時間影響、順序影響以及地理位置影響。本文借鑒RNN模型的變種模型，提出了改進循環(huán)神經網絡(relation-order-situation-time neural network，ROSTNN)，模型結構如圖2所示。

圖2 改進型ROSTNN模型

新候選狀態(tài)在t時刻的表示為

(6)

式中：Wc1、Wc2均表示的是模型參數，在lt位置點的嵌入由Ult進行表示，重置門開關記為ft， 上個輸出的嵌入記為ht-1， 偏置矢量記作bc。

首先，通過MMBE模型可以得到社交關系、順序、地理位置、時間的影響因子Prost(社交關系R、順序O、地理位置S、時間T)，則上述公式可變換為

(7)

若用戶訪問歷史的時間較短，或是需要在歷史最開始的部分對隱藏狀態(tài)進行計算時，則t時刻的候選隱藏狀態(tài)更改為

(8)

式中：初始狀態(tài)由h0表示，每個用戶都具有相同的初始狀態(tài)，并且在這種狀態(tài)下是不會有用于進行個性化預測的行為數據的。

(9)

式中：更新門的開關用it來表示，分素乘積記為*。以下為更新門與重置門開關的計算公式

it=σ(Wi1Ult+Wi2hlt-1+bi)

(10)

ft=σ(Wf1Ult+Wf2hlt-1+bf)

(11)

其中，更新門與重置門的參數分別由Wi1、Wi2、Wf1、Wf2來進行表示，更新門的偏移矢量記為bi，重置門的偏移矢量記為bf，在t時刻的輸出表示為

ht=tanh(Ct)

(12)

用戶u在特定時間和空間下動態(tài)的興趣點所發(fā)生的變化由ht進行捕獲。直到現(xiàn)在，本文對用戶訪問興趣點的局部偏好和連續(xù)時間序列中的周期性變化特征的提取，是通過采用TD-GRU模型來完成的。

通過提取用戶訪問特征點的偏好，對于給定興趣點l計算出用戶對該興趣點的預測值

(13)

3.4 基于改進RNN的推薦算法

圖3為改進RNN算法的流程，首先通過因子分解機，構建時間矩陣T、地理位置矩陣S、順序矩陣O和社交關系矩陣R，使用因子分解機的思想對稀疏數矩陣進行處理，去除數據的稀疏化。然后，使用MMBE模型對多源異構因素(社交、順序、地理位置、時間)進行建模，得到影響權重，將影響權重協(xié)同上一時刻的狀態(tài)，獲得該時刻的狀態(tài)，使用式(12)和式(13)求得給定任意興趣點l的預測值p。最后，將其最高的前K個興趣點推薦給用戶。

圖3 改進RNN算法的流程

4 實驗與結果

4.1 實驗數據集

實驗使用兩個公開可用的LBSN數據集，即Gowalla和Brightkite。這兩個數據集提供了用戶關系和用戶簽到記錄。其中簽到記錄包含位置ID和相應的簽到時間戳。這兩個數據集中的所有簽到記錄均被視為用戶序列。兩條連續(xù)的簽到記錄之間的間隔大于6個小時的每條軌跡都被細分為多個部分。還對兩個數據集執(zhí)行了預處理步驟，以過濾掉不活躍的用戶和不受歡迎的POIs。例如，從Gowalla原始數據集中排除了簽到記錄少于16個且位置覆蓋少于21次訪問的用戶。由于Brightkite中數據集的大小很小，因此，僅刪除了簽到少于11個好友的用戶和簽到少于16個位置的用戶。表2列出了預處理數據集的統(tǒng)計信息。

表2 預處理數據集的統(tǒng)計信息

4.2 性能指標

利用兩種廣泛使用的指標，即Recall@k(召回率)、Precision@k(精度)，同時使用了F1指標，來衡量不同POI推薦方法的性能。其中F1指標是準確率和召回率的加權平均和，能夠避免準確率和召回率相互制約的缺點，更好評價算法穩(wěn)定性。這3個性能指標定義為

(14)

(15)

(16)

其中，Su(k) 是推薦給用戶u的前k個POIs的集合，而vu是用戶在測試集中訪問的位置的集合。

4.3 實驗描述

為了驗證所提方法的有效性，將其與3種對比方法進行比較。每個數據集都被劃分為一個訓練集和一個關于簽到時間的測試集，即，先前簽到記錄的80%被用作訓練集，其余的為測試集。實驗中所有程序都使用C++實現(xiàn)。嘗試了運行Windows Server 2012的服務器，該服務器配置了Intel GRTPRA i7 CPU(3.6 GHz)和32 GB存儲器。

4.4 參數分析

調整模型參數(例如主題數(即K)和區(qū)域數(即R))對于ROSTNN的性能至關重要。因此，以Gowalla為例，研究調整模型參數對ROSTNN性能的影響。首先，本文測試了超參數α、β、η、tu和tv改變時ROSTNN的性能，并且ROSTNN對超參數的變化不敏感。根據經驗，為這些超參數設置固定值，即α=50/K，β=50/R，η=0.01，μu=μv=0和λu=λv=1E-3。 其次，進行了一個額外的實驗來測量嵌入維數對POI推薦的影響。當嵌入維數為50～200時，模型的性能相對穩(wěn)定。此外，嵌入維度越多，表達能力越強，也可能導致過度擬合。因此，嵌入維數被設置為100。

通過改變主題和區(qū)域的數量，隨后進行了測試ROSTNN推薦前十個POIs的性能。如表3和表4所示，ROSTNN的推薦精度和召回率隨著K的增加呈類似的上升趨勢，當K大于50時趨于穩(wěn)定。值得注意的是，對于R有類似的觀察，即ROSTNN的推薦精度和召回率也隨著區(qū)域數的增加而增加，當R大于40時趨于穩(wěn)定。

表3 Gowalla上的POI推薦精度@10

表4 Gowalla上的POI推薦召回@10

從主題和區(qū)域兩個方面本文都獲得了一致結果，這在很大程度上歸因于K和R對模型復雜性。因此，僅僅增加K和R來改善模型性能沒有太大幫助。換句話說，當預測使用ROSTNN的簽到行為時，應該考慮是有效性優(yōu)先還是效率優(yōu)先。

4.5 對比結果與分析

將所提ROSTNN方法與LRACWSRAGI、GRTPRA、SOPCRMFM方法進行對比，在精度、召回率和F值方面的對比結果如圖4～圖9所示。

圖4 ROSTNN在Gowalla上精確度對比實驗

圖5 ROSTNN在Gowalla上召回率對比實驗

圖6 ROSTNN在Brightkite上精確度對比實驗

圖7 ROSTNN在Brightkite上召回率對比實驗

圖8 幾種方法在Gowalla數據集上F值對比結果

圖9 幾種方法在Brightkite數據集上F值對比結果

從圖4到圖7可以看到，所有方法在兩個數據集上的精確度都比較低，這是由于兩個數據集中用戶的簽到數據比較稀疏，因此，所討論的所有4種方法的推薦準確性都相對較低。在兩個數據集，本文的方法(ROSTNN)在評估指標方面優(yōu)于其它3種對比方法。一方面，ROSTNN和SOPCRMFM的性能優(yōu)于LRACWSRAGI、GRTPRA，這表明綜合多源異構數據的優(yōu)勢。另一方面，ROSTNN比SOPCRMFM更好，因為本文的方法還考慮訪問興趣點的順序，考慮順序能夠縮小興趣點的范圍，減小無用興趣點。本文的方法對于兩個數據集的精度值平均都有較大幅度增加。同樣，本文方法的召回率值平均也都是最大的。在兩個數據集上，本文方法更優(yōu)，這是由于ROSTNN融合了社交、順序、地理、時間4種主要的影響興趣點推薦的因子，所以精度和穩(wěn)定性最好。

從圖8和圖9可以看到，4種對比方法，在Gowalla數據集上推薦長度為15時F值達到最高。在Brightkite數據集上推薦長度為10時F值達到最高。表明不同數據集上，不同推薦長度對推薦結果也有影響。

綜上可知，所提方法在兩種數據集上都能取得最好的推薦效果，這是由于所提方法融入了多源異構數據，綜合考慮了影響POI推薦的4個重要因子，避免了僅考慮單一或者某幾個因子而忽視其它重要影響因子，帶來的推薦準確性問題，較大程度上提高了推薦的精度。此外，使用的因子分解機，緩解了數據稀疏性帶來的問題。實驗結果表明，所提方法的性能更加穩(wěn)定，同時推薦效果更好。

5 結束語

為了向LBSNs系統(tǒng)中的目標用戶推薦更多相對準確的POIs，在異構工作流活動中，綜合考慮了社交、順序、地理和時間因素對單個用戶簽到行為的共同影響，提出了一種改進RNN的POI推薦方法。該方法通過因子分解機降低了各個維度數據稀疏性的問題，通過MMBE對4種影響POI推薦的因素進行融合，最終和改進RNN結合計算出興趣點的預測值，有效提升了推薦性能。實驗結果表明，所提方法在評估指標(精度和召回率)以及F1值方面優(yōu)于其它3種對比方法。

未來將通過整合語義信息和隱式反饋等信息來擴展和豐富所提模型，以提高其預測性能和可擴展性。