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

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

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

1 引 言

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

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

2 相關(guān)工作

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

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

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

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

3.1 問題的描述

3.2 GRU模型

循環(huán)神經(jīng)網(wǎng)絡(luò)基礎(chǔ)模型RNN由于梯度消失等原因只有短期記憶能力，LSTM模型通過門控制技術(shù)在一定程度上解決了梯度消失的問題.而GRU模型作為LSTM的一種變體，具有參數(shù)少和效率高等優(yōu)點，相比于LSTM模型更簡單.GRU具體結(jié)構(gòu)如圖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推薦模型

在進(jìn)行地點推薦的過程中，將相鄰地點之間的時間間隙和距離間隔通過嵌入層投影為特征向量，通過GRU模型對用戶的簽到序列、時間信息和距離信息進(jìn)行雙向的特征分析，從而更好的獲取用戶個性化潛在特征.本文提出了融合時空信息的雙向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 目標(biāo)函數(shù)和訓(xùn)練方法

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

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

(9)

定義最小化目標(biāo)函數(shù)如公式(10)所示.

(10)

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

(11)

通過設(shè)置學(xué)習(xí)率為α.最后采用隨機梯度下降法更新相關(guān)參數(shù)，使目標(biāo)函數(shù)最小化，直至目標(biāo)函數(shù)收斂，如公式(12)所示.

(12)

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

輸入：簽到數(shù)據(jù)C，時間間隙tt，距離間隔dd.

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

//構(gòu)造訓(xùn)練數(shù)據(jù)

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

//訓(xùn)練模型參數(shù)

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 實驗和結(jié)果分析

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

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

表1 兩個數(shù)據(jù)集統(tǒng)計信息Table 1 Statistical information of two datasets

4.2 評價標(biāo)準(zhǔn)

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

(13)

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

4.3 實驗結(jié)果分析

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

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

表2 兩個數(shù)據(jù)集上的準(zhǔn)確率和召回率實驗結(jié)果Table 2 Experimental results of precision and recall on two datasets

4.3.1 性能的比較

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

4.3.2 參數(shù)對BiGRU+ST的影響

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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