融合時空信息的雙向GRU下一個地點推薦

李 全，李書明，許新華，向丹丹，曹雙雙

(湖北師范大學 計算機與信息工程學院，湖北 黃石 435002)

1 引 言

隨著計算機網絡的飛速發展，微博、微信和Facebook等社交網絡吸引數十億用戶相互交流和共享信息.近年來，基于定位的社交網絡服務的快速增長.這些服務已經吸引了許多人用戶可以通過大量的地理標記數據與用戶分享他們的位置和經驗.這些簽到數據可以讓我們更好的了解移動用戶的行為.例如，我們可以根據用戶的歷史足跡，預測他們下一步將要去哪[1].例如：博物館和咖啡廳等.地點推薦可以幫助用戶在位置社交網絡的海量數據中找到自己感興趣的信息，從而訪問新的地理區域，方便用戶的生活[2].

大多數基于機器學習的POI推薦的方法包括協同過濾的地點推薦和矩陣分解地點推薦，其中矩陣分解方法是將不同用戶的簽到數據轉化為用戶-位置矩陣，通過矩陣分解的方式，計算用戶和位置的特征向量表示，從而進行推薦.然而，用戶簽到的數據具有周期性和序列性.因此如何更好地分析用戶序列數據，成為了地點推薦算法有待解決的問題.隨著深度學習的發展，循環神經網絡(Recurrent Neural Network，RNN)可以很好地處理序列數據[3]，并成為建模序列數據的一種經典方法.但是RNN由于梯度消失的原因只能有短期記憶能力，長短期記憶(Long-Short Term Memory，LSTM)模型通過門控制技術在一定程度上解決了梯度消失的問題.而門控循環單元(Gated Recurrent Unit，GRU)模型作為LSTM的一種變體，將遺忘門和輸入門合成了一個更新門，具有參數少和效率高等優點，相比于LSTM模型要更簡單.因此，本文選擇GRU模型作為分析用戶簽到序列數據的基本模型.在用戶的簽到數據中，空間信息的經緯度坐標會影響到用戶的簽到行為.例如有些人在逛完商場之后，可能會去附近的電影院，而不會去距離較遠的網球場.另外，時間信息也是影響用戶簽到行為的重要因數.例如有些人中午下班之后會去餐廳，而在晚上下班之后會去酒吧.總之，如何根據用戶的時間和空間等上下文信息為用戶準確地推薦下一個地點，仍然是一個具有挑戰性的問題.為了解決以上問題，本文提出了一種融合時空信息的雙向GRU下一個地點推薦算法.

2 相關工作

地點推薦算法包括基于協同過濾的推薦、基于神經網絡的推薦和基于序列信息的推薦等.在基于協同過濾的推薦方法：Zhang 等人[4]提出了一種個性化的有效的地理位置推薦框架iGeoRec.該框架一方面可以為每個用戶計算個性化的位置概率分布.另一方面通過似然估計方法預測用戶訪問下一位置的概率.Lian 等人[5]提出了一種結合地理模型和加權矩陣分解的興趣點推薦算法.該算法認為人類的位置活動具有空間聚集現象.因此將地理信息融入矩陣分解模型中，并討論該模型中的用戶的區域向量和興趣點的區域向量的影響.Gao 等人[6]提出了一種融合時間影響和矩陣分解的興趣點推薦算法.該算法介紹了4種時間聚合策略，并將不同的時間狀態融入到用戶的簽到偏好中.

在基于神經網絡的推薦方面：Yang 等人[7]將協同過濾和半監督學習結合起來，采用神經網絡實現興趣點推薦.通過深度神經網絡學習用戶和興趣點的潛在特征，并預測用戶下一個興趣點的偏好.Xing 等人[8]結合卷積神經網絡和概率矩陣分解提出了一種基于卷積矩陣分解的興趣點推薦模型.該模型融合了用戶的簽到信息、社交關系和評論信息等.

在基于序列信息的推薦方面：Cheng等人[9]提出了FPMC-LR模型，該模型結合了位置轉移矩陣的馬爾科夫鏈和用戶地理距離從而實現地點推薦.Feng等人[10]提出了PRME模型，該模型采用個性化度量嵌入方法實現用戶的下一個地點推薦.隨著自然語言處理技術的發展，循環神經網絡已經被成功的應用于文本分類，情感分類和機器翻譯等領域.在循環神經網路中GRU模型具有訓練模型參數少，效率高等優點.另外，在人們的生活中，時空信息也會影響到用戶的簽到行為.因此，本文將簽到序列中兩個相鄰地點之間的時間間隙和距離間隔通過嵌入層映射為特征向量，然后采用雙向GRU模型從兩個方向提取序列信息和時空信息，從而提出了一種融合時空信息的雙向GRU下一個地點推薦算法.該算法可以更好的結合用戶的時空信息，提高下一個地點推薦的性能.

3 融合時空信息的雙向GRU興趣點推薦技術

3.1 問題的描述

3.2 GRU模型

循環神經網絡基礎模型RNN由于梯度消失等原因只有短期記憶能力，LSTM模型通過門控制技術在一定程度上解決了梯度消失的問題.而GRU模型作為LSTM的一種變體，具有參數少和效率高等優點，相比于LSTM模型更簡單.GRU具體結構如圖1所示.

圖1 GRU模型圖Fig.1 Model of GRU

由圖1可知，GRU模型的公式如下：

rt=σ(Wrhht-1+Wrxxt+br)

(1)

zt=σ(Wzhht-1+Wzxxt+bz)

(2)

(3)

(4)

3.3 融合時空信息的雙向GRU推薦模型

在進行地點推薦的過程中，將相鄰地點之間的時間間隙和距離間隔通過嵌入層投影為特征向量，通過GRU模型對用戶的簽到序列、時間信息和距離信息進行雙向的特征分析，從而更好的獲取用戶個性化潛在特征.本文提出了融合時空信息的雙向GRU(Spatiotemporal Bidirectional Gated Recurrent Unit，BiGRU+ST)推薦模型如圖2所示.

圖2 BiGRU+ST模型圖Fig.2 Model of BiGRU+ST

rt=σ(Wrhht-1+Wrxxp_ti+Wrddp_ti+Wrttp_ti)+br)

(5)

zt=σ(Wzhht-1+Wzxxp_ti+Wzddp_ti+Wzttp_ti)+bz)

(6)

(7)

(8)

3.4 目標函數和訓練方法

融合時空信息的雙向GRU的推薦模型將采用BPR算法定義目標函數.首先利用pair-wise的方法得到訓練集的正例樣本集和負例樣本集，構造模型參數的最大后驗概率函數，然后將最大化后驗概率函數轉換為最小化目標函數，最后采用隨機梯度下降法更新模型參數，如公式(9)、(10)、(11)和(12)所示[11].

max ln(p(Θ|?u，t))=ln(p(?u，t|Θ))+ln(p(Θ))

(9)

定義最小化目標函數如公式(10)所示.

(10)

模型參數為Θ={Wrh，Wrx，Wrd，Wrt，Wzh，Wzx，Wzd，Wzt，Whr，Whx，Whd，Wht，br，bz，bh，L，D，T}，其中權重矩陣包括Wrh，Wrx，Wrd，Wrt，Wzh，Wzx，Wzd，Wzt，Whr，Whx，Whd，Wht，偏置向量包括br，bz，bh，地點的潛在特征矩陣為L為.地點間距離間隔的潛在特征矩陣為D.地點間時間間隙的潛在特征矩陣為T.正則化的超參數為λ.目標函數對模型參數求偏導數的公式如公式(11)所示.

(11)

通過設置學習率為α.最后采用隨機梯度下降法更新相關參數，使目標函數最小化，直至目標函數收斂，如公式(12)所示.

(12)

融合時空信息的雙向GRU的地點推薦算法的學習率為α，正則化系數為λ，具體步驟如下：

輸入：簽到數據C，時間間隙tt，距離間隔dd.

輸出：模型參數Θ={Wrh，Wrx，Wrd，Wrt，Wzh，Wzx，Wzd，Wzt，Whr，Whx，Whd，Wht，br，bz，bh，L，D，T}.

//構造訓練數據

1.for each user u inUdo

4.time_index=f(Δtti，tt)，dis_index=Δdti*1000/dd

7. end for

8. Add a user training listDutoD

9.end for

//訓練模型參數

10.Initialize the parameter set Θ

11.Randomly choose a user u inU

12.Get training listDuof the user u fromD

15.Util minimizing the objective(10)

16.Saving the learned parameter set Θ

4 實驗和結果分析

4.1 數據集

文本選擇了兩種公開的基于位置社交網絡的數據集.在數據集中，每一行都包括用戶標識符，簽到點標識符，簽到時間和簽到點的經緯度坐標等信息[12].其中Foursquare是來自于美國的地理位置簽到數據集，Gowalla是來自于美國斯坦福大學SNAP實驗室公布的數據集.我們首先對兩個數據集進行預處理.對每個用戶，將簽到次數小于4的用戶刪除.對每個簽到點，將被簽到次數小于4的簽到點刪除.將每個數據集80%的數據作為訓練集，剩余的20%的數據作為測試集.兩個數據集統計特性如表1所示.

表1 兩個數據集統計信息Table 1 Statistical information of two datasets

4.2 評價標準

為了評價本文提出的融合時空信息的雙向GRU模型(BiGRU+ST)與其他基本baselines模型的性能，我們使用3個標準的評價指標，即準確率(Precision@K)、召回率(Recall@K)和F1@K值，其中K表示待推薦的地點總數.準確率表示在推薦列表中正確的地點數與已推薦總數的比率.召回率表示在推薦列表中正確的地點數與用戶應該訪問地點總數的比率.F1值將準確率和召回率進行了綜合.以上3個評價指標如公式(13)所示.

(13)

其中R(u)表示為用戶u推薦的地點的集合，T(u)表示用戶u實際訪問的地點的集合.

4.3 實驗結果分析

本文選定了6種地點推薦算法與所提的BiGRU+ST算法進行對比.MF 是將每個用戶的簽到點序列轉換為用戶-位置矩陣，然后該矩陣被分解為用戶潛在特征矩陣和位置潛在特征矩陣，最后預測用戶對待推薦地點的評分[13].FPMC-LR是結合了位置轉移矩陣的馬爾科夫鏈和用戶地理距離從而實現地點推薦.PRME采用個性化度量嵌入方法實現用戶的下一個地點推薦.RNN是將用戶的簽到數據轉化為簽到序列，然后通過循環神經網絡對簽到序列進行分析，得到用戶的潛在特征表示，最后對待推薦的地點進行預測.GRU是基于門控循環單元的地點推薦方法.GRU+ST是指門控循環單元在分析用戶的簽到序列的時候，將位置信息和時空信息進行了融合，從而得到用戶的潛在特征表示.

本文選擇Python作為實驗的編程語言，選擇Theano作為深度學習框架.在訓練模型的過程中，將學習率α設置為0.001，正則化系數λ設置為0.01，嵌入向量的維度latent_size設置為60.模型推薦的列表長度K分別取5、10和20.當K取不同值時，地點推薦算法的準確率、召回率和F1值是不同的，實驗結果如表2所示.

表2 兩個數據集上的準確率和召回率實驗結果Table 2 Experimental results of precision and recall on two datasets

4.3.1 性能的比較

當推薦列表長度K取不同值時，本文選定的6個不同推薦算法與所提的BiGRU+ST推薦算法分別對2個數據集進行評估，它們的準確率和召回率結果如表2所示.RNN推薦算法在準確率和召回率方面都要優于MF、FPMC-LR和PRME算法.GRU推薦算法可以產生比上述推薦算法，特別是RNN算法更好的推薦性能，說明了GRU模型在分析簽到序列數據方面存在明顯的優勢.GRU+ST推薦算法與GRU算法相比在準確率和召回率方面分別提高了4%-6%.說明了當將位置信息和時空信息進行融合之后，該模型可以更好的提取用戶的特征，從而提高推薦算法的效果.BiGRU+ST相比于 GRU+ST算法在P@5，P@10，P@20，R@5，R@10和R@20等方面平均提高了3%，4%，6%，3%，5%和6%，說明該模型通過雙向分析簽到序列和時空信息又能進一步有效的提高地點推薦算法的性能.

4.3.2 參數對BiGRU+ST的影響

在基于BiGRU+ST的地點推薦中，推薦算法的性能會隨距離間隔和時間間隙的不同而不同.該部分主要在Foursquare數據集的基礎上進行實驗分析，并將該數據集劃分為80%的訓練集和20%的測試集.本文設置了不同的距離間隔和時間間隙的實驗，驗證距離間隔和時間間隙對推薦算法性能的影響，其中dd表示距離間隔，tt表示時間間隙.

1)距離間隔dd的實驗分析

本實驗在保持時間間隙不變的情況下，將兩個地點的距離間隔分別設置為50m，100m，150m，200m，250m，300m，350m和400m.通過調節不同的距離間隔，觀察BiGRU+ST算法在R@5，R@10，R@20，F1@5，F1@10和F1@20等性能指標的變化.不同距離間隔的BiGRU+ST算法實驗結果如圖3所示.

圖3 距離間隔dd的對比實驗Fig.3 Comparsion of distance interval dd

由圖3可知，當距離間隔50≤dd<200時，BiGRU+ST地點推薦算法性能先逐漸增加，當距離間隔200≤dd≤400時，該推薦算的性能又逐漸減少.說明當地點之間的距離間隔為200m時，BiGRU+ST推薦算法的Recall和F1值達到最大值，所以本文設置地點間的距離間隔為200m比較合理.

2)時間間隙tt的實驗分析

本實驗在距離間隔不變的情況下，將兩個地點的時間間隙分別設置為8min，15min，30min，60min，120min，240min，480min和720min.通過調節時間間隙。觀察BiGRU+ST算法在R@5，R@10，R@20，F1@5，F1@10和F1@20等性能指標的變化.不同時間間隙的BiGRU+ST算法實驗結果如圖4所示.

圖4 時間間隙tt的對比實驗Fig.4 Comparsion of time interval tt

由圖4可知，當時間間隙8≤tt<30時，BiGRU+ST地點推薦算法的性能先逐漸增加，當時間間隙30≤tt<720時，該推薦算法的性能逐漸減少.當地點之間的時間間隙為30min，BiGRU+ST地點推薦算法的召回率和F1值達到最佳值，所以本文設置時間間隙的取值為30min比較合理.

5 結束語

本文主要研究通過雙向GRU模型分析地點的簽到序列、時間和距離等上下文信息，獲取用戶的個性化偏好.首先將兩個地點之間的時間間隙和距離間隔通過嵌入層投影為潛在特征向量，然后采用雙向GRU模型提取簽到序列、時間序列和距離序列的信息，獲取用戶的特征向量表示.最后，通過貝葉斯個性化排序算法構造目標函數并學習模型參數.對兩個數據集進行實驗分析，表明本文所提的算法相比其他相關的地點推薦算法在地點推薦性能上有了較大的提高，證明了該模型的有效性.在未來的工作中，基于圖神經網絡的學習模型融合多種上下文信息將是一個非常值得關注的方向.