基于時空循環神經網絡的下一個興趣點推薦方法

柴瑞敏，殷臣，孟祥福，張霄雁，關昕，齊雪月

（遼寧工程技術大學 電子與信息工程學院，遼寧 葫蘆島 125105）

隨著基于位置的社交網絡發展，一些基于位置服務的社交軟件被廣泛使用，如Foursquare、Gowalla、Yelp等，人們可以輕松地通過簽到的形式分享他們的位置和記錄生活。同時，用戶大量的簽到信息也為探索人們的行為規律提供了機遇。下一個興趣點推薦已經成為基于位置的社交網絡的重要任務。

然而，與傳統的推薦系統(如音樂、視頻和圖書推薦等)不同，時空屬性對于興趣點推薦起著很強的約束性；并且，在興趣點的簽到信息中，用戶并沒有明確給出對興趣點的喜愛或偏好。用戶的隱式反饋信息以及地點簽到信息存在稀疏性問題，因此下一個興趣點的推薦極具挑戰性。為了提高興趣點的推薦效果，一些研究將序列信息[1-2]、時空信息[3-5]、社交關系[6-8]以及簽到興趣點的上下文信息[9-12]整合到模型中。本文主要利用簽到信息中的序列信息、時間信息和空間信息進行下一個興趣點推薦。

序列信息在下一個興趣點推薦中扮演著重要角色。一些研究通過整合用戶歷史簽到序列信息提升模型的效果，FPMC模型[1]通過結合矩陣分解和馬爾科夫鏈捕獲用戶連續簽到興趣點之間的序列影響。最近，一些研究采用RNN模型[13]用于序列信息分析，基于循環神經網絡(RNN)的方法能夠更有效地捕捉序列數據之間的關系，因此在興趣點推薦中得到了廣泛應用，并成為當前主流的推薦模型。然而，RNN存在梯度爆炸和梯度消失的問題，不能學習到較長序列內遠距離的依賴關系。為了解決這個問題，長短時記憶(LSTM)[14]和門控循環單元(GRU)[15]2種RNN變體被提出，使得循環神經網絡能夠學習到長序列內遠距離的依賴問題。

空間信息是基于位置服務的基本屬性[16]，對興趣點的推薦同樣起著重要作用。一些研究表明[17-18]，人們更傾向于訪問距離用戶當前位置較近的地點。這些模型通過將距離作為權重系數或者根據興趣點之間的距離進行聚類進而推薦位置較近的興趣點，限制了模型給用戶推薦遠距離的興趣點。通過對實驗數據集分析發現，在本文使用的Foursquare和CA數據集中,分別有24%和42%的相鄰簽到興趣點之間的距離間隔大于10 km，這說明用戶多數情況下偏好訪問距離較近的興趣點，但也有較大比例用戶依然偏好訪問距離較遠的興趣點。在現有的下一個興趣點推薦模型中，大多數模型傾向于推薦較近的地點限制了模型的表現，使得模型并不會自適應用戶需求和偏好的變化而進行推薦，這也意味著模型推薦的興趣點列表是固定不變的。為了解決上述問題，模型需要用戶提供其將要訪問下一個興趣點的距離間隔。這有兩方面的好處：首先根據用戶的距離間隔，能夠給用戶提供更靈活的推薦，如果當前的推薦列表用戶不滿意，用戶可以有更多的靈活性去調整不同的距離間隔而得到不同的推薦列表，使用戶能夠與模型進行交互而不是只能得到固定推薦列表；其次，根據用戶提供的距離間隔，能夠分析出用戶此時表現的偏好模式(即近距離偏好或者遠距離偏好)，進而根據用戶的偏好給出個性化的推薦列表。

時間信息在興趣點推薦中也具有較大作用。用戶偏好會隨時間發生變化，用戶在不同的時間間隔內會表現出不同的偏好。當用戶要訪問的下一個興趣點的時間點與當前用戶時間點的時間間隔較短時，模型應傾向于推薦用戶較近的一些地點。同時，利用相鄰時間間隔信息也能提供一些隱含的有價值信息。當用戶從當前景點緊接著去附近的下一個景點時，不同的用戶在這兩個興趣點通常有相似的訪問時間間隔。因此利用用戶在相鄰興趣點之間的轉移時間間隔有利于進行興趣點推薦。

由于RNN模型在序列建模中具有很好效果，本文采用RNN模型對序列信息建模，通過對RNN進行改進使其能夠滿足對用戶變化的時空偏好信息進行下一個興趣點推薦。現有模型通常將用戶的整個簽到序列作為RNN的輸入用于下一個興趣點推薦。而實際上，使用用戶的整個簽到記錄并不一定適用于實際的應用場景，隨著用戶簽到記錄數量快速地增加，計算開銷也隨之增加。因此，本文僅根據最后一次會話信息用于下一個興趣點推薦。為了對用戶簽到序列中用戶變化的復雜時空偏好進行建模，本文分別建立時間轉移矩陣和空間轉移矩陣。時空轉移矩陣由用戶相鄰簽到興趣點之間的時空間隔信息確定；為了進一步考慮用戶的時間偏好，用戶會話中的每個興趣點與推薦興趣點的時間間隔信息也被整合到模型中。本文通過同時考慮用戶的兩類時間信息(包括相鄰興趣點的時間間隔和會話中訪問過的興趣點與下一個興趣點的時間間隔)、空間信息、簽到序列信息和用戶偏好給出個性化的下一個興趣點推薦。

1 相關工作

傳統興趣點推薦通常采用協同過濾算法。矩陣分解[19-20]是協同過濾最常用的方法，其目標是將“用戶?興趣點”隱式評分矩陣分解為2個低維矩陣，分別表示用戶和興趣點的潛在因子。然而，矩陣分解方法不適用于用戶簽到序列信息的建模。

序列信息和時空信息是下一個興趣點推薦的最基本要素。為了提升下一個興趣點的推薦效果，一些模型，如基于MC模型的方法[21]、基于嵌入的方法[22-23]和基于神經網絡RNN的方法，通過整合序列信息和時空信息用于下一個興趣點推薦。文獻[1]提出了FPMC模型，該模型結合矩陣分解和馬爾科夫鏈對用戶偏好和序列信息建模。文獻[21]是FPMC模型的擴展，通過結合用戶的地理位置約束為用戶推薦下一個興趣點。文獻[24]提出了POI2vec，該模型應用二叉樹結構對附近的興趣點進行聚類，進而為用戶推薦下一個興趣點。文獻[17]提出了PRME-G，該模型利用嵌入的方法，通過度量嵌入的方法整合興趣點的序列信息和地理位置信息進行下一個興趣點推薦。文獻[22]提出了一種嵌入學習方法(GE)用于興趣點推薦，該方法利用二部圖對POI推薦上下文中的一對上下文進行建模，并通過對4對嵌入模型(POI-POI、POI-Time、POI-Regin和POIWord)進行統一優化。

然而，以上模型缺乏對用戶連續簽到的兩個興趣點之間的轉移時空信息的考慮，并且時間信息和空間信息之間復雜的交互也被忽略。最近，序列信息和時空信息也被廣泛地整合到RNN網絡中。文獻[25]提出了Distance2Pre模型，利用GRU模型首次整合用戶不同地理距離偏好進行下一個興趣點預測，提出線性和非線性方式整合用戶距離偏好分數的2種結構模型。文獻[4]通過對RNN改進，提出整合時空信息的RNN模型(ST-RNN)，然而它使用固定窗口的時空轉化信息，缺乏對相鄰的興趣點之間的轉移信息進行建模。文獻[26]提出了改進的LSTM模型，該模型在LSTM模型中加入時間門和距離門，通過對相鄰簽到地點之間的時間間隔和距離間隔進行建模來提取用戶長期和短期興趣偏好。

以上模型都是將用戶的歷史簽到記錄作為RNN的輸入，本文使用用戶最后一次的會話信息作為RNN的輸入。并且，上述模型都忽略了用戶歷史簽到興趣點與最終推薦的興趣點的時間間隔信息。與本文工作最為相似是Distance2Pre模型，該模型通過對用戶的不同距離偏好進行建模，但其忽略了用戶偏好與時間之間的關聯，這就意味著隨著時間的改變，無論是之后的1個小時還是2天內，Distance2Pre將始終為用戶預測相同的推薦列表。本文提出的模型與上述模型的不同之處體現在：1)模型只使用用戶最后的會話作為RNN的輸，具有更快的推薦速度；2)模型能夠根據用戶的查詢條件以及用戶的偏好變化情況進行自適應調整，為相同用戶推薦變化的個性化的興趣點推薦列表。

2 相關定義

令U={u1,u2,···,u|U|} 表示所有用戶組成的集合，P={p1,p2,···,p|P|} 和G={gp1,gp2,···,g|P|} 分別表示興趣點的集合及其對應興趣點的地理坐標的集合，其中 |U| 和 |P| 分別表示用戶數量和興趣點數量。本文中用戶和興趣點的標識都用連續的整數編碼，編碼值從1開始。

定義1 興趣點(POI)。興趣點是具有唯一標識(編碼)的地點，它包含經緯度信息。

3 基于時空循環神經網絡的興趣點推薦模型

3.1 模型的輸入信息

圖1中p7(Q) 表示用戶在興趣點p7發出的查詢。S(t) 的取值為0或1，用于判斷用戶簽到興趣點是否屬于同一個會話。S(t) 的值根據用戶2個相鄰簽到興趣點之間的時間差得到，如果用戶在ti時刻簽到與ti?1時 刻簽到的差大于 πs，即S(t)=0，表示用戶在ti和ti?1時刻的簽到興趣點不屬于同一個會話。

用戶的偏好是隨時間變化的，同時用戶所處地點也有可能發生變化，因此利用用戶整個歷史簽到記錄進行下一個興趣點推薦并不一定合適。在下一個興趣點推薦中，用戶最近的簽到地點通常對于下一個興趣點的推薦具有較大影響，因此本文僅使用用戶最后一次會話信息作為RNN的輸入，用戶的簽到會話表示為相鄰的簽到興趣點之間的最大間隔不超過 πs的一段連續簽到序列。從圖1可以看出用戶的歷史簽到記錄被分成了多個會話，session1和session2是已完成會話，session3是用戶最后一次會話。圖1中用戶歷史簽到序列上面的0和1數值表示相鄰的兩個興趣點之間是否屬于一個會話。本文將用戶的每一次簽到記錄作為訓練目標，每個用戶將會得到s?1訓練序列，s為用戶歷史簽到總數。下面舉例說明模型的訓練和推薦過程。如果一個用戶在t3時刻之前已訪問過p1、p2兩個興趣點，用戶訪問p1和p2之間的時間間隔小于 πs， 那么p1和p2屬于同一個會話，假如用戶在t3(t3?t2≤πs)時刻在p3興趣點提出一個查詢Q，此用戶最后的會話信息{p1,p2,p3} 將會作為序列輸入用于推薦，興趣點p4將會作為目標興趣點進行訓練。假如用戶在t4(t4?t3>πs) 時刻在p4地點提出查詢Q，由于當前用戶的會話信息不屬于上一會話，模型將在t4時刻新建一個只包括當前用戶查詢位置的會話信息作為輸入，用戶下一個訪問的興趣點p5將會被作為訓練目標。在模型的訓練中，用戶每次訪問的下一個興趣點被當成目標興趣點，由于它的地理信息和簽到時間是已知的，用戶訪問下一個興趣點的時空間隔信息也可以通過計算得到。本文使用用戶訪問下一個興趣點的時空信息作為用戶的查詢信息在模型中進行訓練。通過大量用戶歷史簽到數據集來學習，用戶訪問下一個興趣點的遠近距離偏好、長短時間偏好和時空信息的交互作用。

圖1 基于會話的下一個興趣點推薦模型的訓練與推薦過程Fig.1 Training and recommendation process of the next POI recommendation model based on session

在模型的推薦過程中，模型根據用戶的查詢條件進行動態推薦，用戶最后的一個會話信息被用于推薦。例如，當用戶在p7地點提出查詢時，模型將會根據用戶在p7的簽到時間判斷是否上一個會話已結束，當用戶的前一個會話結束時(即S(t)=0 )，用戶最后一次簽到的p7地點將作為一個新的會話用于推薦下一個興趣點，當S(t)=1，說明p7地點的簽到屬于上一個會話信息，此時p6和p7將共同作為一個會話信息用于推薦下一個興趣點。

3.2 序列建模

本文采用RNN模型對用戶的簽到序列信息進行建模。在RNN中，用戶在tk時刻簽到的隱藏層向量htk表示為

3.3 時空偏好建模

一些模型在對空間信息建模時，通常認為用戶更傾向于訪問位置較近的地點，通過利用空間距離作為參數控制用戶的空間偏好。然而，這些模型無法對用戶的遠距離偏好的興趣點進行推薦。傳統的RNN模型對近距離和遠距離的用戶偏好建模存在困難，因此需要對RNN模型進行改進。本文通過設置2個空間轉移矩陣W1、W2對用戶的空間偏好進行建模，W1用于捕獲用戶的短距離偏好，W2用于捕獲用戶長距離偏好。為了能夠讓轉移矩陣W1自然過渡到轉移矩陣W2，設置了一個最大距離間隔 πd。當興趣點轉換距離在最大距離間隔內時，用戶的空間偏好轉移矩陣由距離間隔對W1和W2轉移矩陣進行加權計算得到。當興趣點轉換距離在最大距離間隔外時，用戶表現出遠距離的偏好，此時W2將作為空間轉移矩陣。在訓練時，用戶訪問下一個興趣點的轉換距離( Δd)由用戶歷史簽到興趣點相鄰的下一個簽到興趣點的距離相減得到，即

同理，為了考慮用戶的時間偏好，本文也設置兩個時間轉移矩陣W3、W4和最大時間間隔 πt來捕獲用戶的短時間偏好和長時間偏好。兩個相鄰簽到興趣點之間的時間間隔由用戶歷史簽到興趣點與相鄰的下一個興趣點的簽到時間差得到，表示為

為了同時考慮用戶的時間轉移偏好和距離轉移偏好，本文使用時間轉移矩陣和空間轉移矩陣乘積的形式作為用戶的時空偏好轉移矩陣。因此RNN公式可以改寫為

最后，將用戶簽到序列信息和用戶偏好作為用戶訪問下一個興趣點的最終推薦向量，表示為

3.4 模型推薦

本文將興趣點推薦問題看成分類問題，根據用戶訪問每個興趣點的偏好分數xp,利用softmax函數計算用戶訪問每個興趣點的概率：

4 模型實驗及結果

4.1 實驗設置

1）數據集

本文使用2個公開數據集，即Foursquare和CA數據集。2個數據集中，用戶的每次簽到記錄都包括4個屬性：用戶ID、興趣點ID、簽到時間和GPS位置。Foursquare數據集[27]，包括用戶在Foursquare應用軟件上2010年8月—2011年1月在新加坡的352 850條簽到記錄；CA數據集包括生活在美國加利福尼亞州的4 163名使用者的483 813個簽到信息、121 142個不同的興趣點。遵循常用的下一個興趣點預處理方式[21,26,28]，在這2個數據集中，移除了少于5次簽到信息的用戶以及少于5個用戶訪問的興趣點。數據預處理結果如表1所示。本文選擇用戶歷史簽到數據集的最后一次簽到記錄作為測試集，其余作為訓練集，以前的大多數工作[9,25,29]也都采用這種方法對數據集進行分割。

表1 數據預處理結果Table 1 Data preprocessing results

2）參數設置

實驗中，SST-RNN模型采用PyTorch編程實現，設置用戶向量、興趣點向量和時間間隔向量的嵌入維度為20，隱藏層神經元個數為20。向量嵌入過程是通過PyTorch提供的“nn.Embedding”嵌入查找表的方法實現。時間轉移矩陣和空間轉移矩陣的大小為R20x20， πs為8 h。在Foursquare數據集中，最優的參數值為 πt= 24 h， πd=14 km，在CA數據集中，最優的參數值為 πt= 16 h， πd=12 km，參數的確定將在之后的“參數分析”部分進行說明。學習率設置為0.001，激活函數選擇ReLU。本文使用交叉熵損失函數和BPTT算法進行誤差的計算和誤差的反向傳播，使用SGD優化器對參數進行優化。

3）評價方法

選用兩個常用的度量標準Accuracy@K(ACC@K)和MAP作為實驗評價指標。ACC@K是推薦系統中常用衡量推薦效果好壞的指標，對于用戶的一次推薦，如果用戶訪問的下一個興趣點出現在推薦列表中，則認為預測正確，其值為1，否則為0。ACC@K的值是取所有測試實例的平均值，值越高表示模型的推薦效果越好。MAP是衡量推薦列表中興趣點排名的標準，如果用戶訪問下一個興趣點在推薦列表的位置越靠前，MAP的得分就會越高。

4）對比模型

本文使用基線算法和最新的算法進行對比，對比模型中的所有用戶和興趣點的向量維度均為20。對比模型的參數設置采用原論文默認的參數，實驗結果是模型訓練迭代100次中的最優結果。

①BPR[29]：利用矩陣分解算法和BPR損失對“用戶?興趣點”的隱式反饋矩陣進行優化。作為基線模型，BPR認為用戶對交互過的興趣點偏好大于未交互的興趣點。

②RNN：通過標準的循環神經網絡結構對用戶歷史訪問興趣點的時序信息建模。作為基線模型，RNN只使用最后一次會話信息作為輸入。

③GRU[15]：RNN的最新變體，通過2個門控單元控制信息的流動，能夠處理長序列依賴問題，解決RNN存在的梯度消失和梯度爆炸問題。作為基線模型，該模型使用用戶的全部歷史簽到記錄作為輸入。

④FPMC-LR[21]：利用個性化馬爾科夫鏈對用戶簽到序列建模，結合用戶的地理位置限制進行下一個興趣點推薦。

⑤PRME-G[17]：利用度量嵌入的方法對用戶序列信息建模，將空間距離作為權重控制用戶的距離偏好。

⑥POI2Vec[24]：該模型使用二叉樹將距離相近的興趣點聚為一類。為了增強興趣點的空間影響，一個興趣點可以分配到多個類中。

⑦Distance2Pre[25]：利用GRU模型根據用戶簽到歷史序列信息和距離偏好進行推薦。提出了Distance (linear)和Distance (non-linear)兩種模型，本文使用效果表現最好的Distance (non-linear)模型，其默認的隱藏層神經元個數為20。

⑧SST-RNN：本文提出的模型，通過改進RNN模型使其能夠對用戶訪問下一個興趣點的遠近距離偏好和長短時間偏好建模，根據用戶的會話信息進行個性化的下一個興趣點推薦。

4.2 實驗結果和分析

4.2.1 實驗結果

Foursquare和CA數據集在不同模型的實驗結果如表2、3所示，其中Improvement表示本文提出的模型相對于對比模型中的最好性能提升的效果，模型提升效果的計算公式為

表2 Foursquare數據集上ACC@K和MAP表現對比Table 2 Performance comparison on the Foursquare dataset by ACC@K and MAP %

式中：R表示SST-RNN模型的實驗結果；C表示最好的對比模型實驗結果。

表3 CA數據集上ACC@K和MAP的表現對比Table 3 Performance comparison on the CA dataset by ACC@K and MAP %

4.2.2 實驗結果分析

首先，比較BPR和GRU這2個基線算法，它們只用到單一的信息進行推薦，表現效果較差。BPR利用用戶的偏好進行推薦，而GRU模型使用用戶歷史簽到的序列信息。從2個數據集的實驗結果可以看出，GRU模型的表現優于使用BPR損失的矩陣分解算法，說明在下一個興趣點推薦中，序列信息比用戶偏好更重要。BPR模型更適合一般的興趣點推薦，然而GRU更適合于下一個興趣點推薦。

其次，從兩個數據集上的實驗結果可以看出整合興趣點的地理位置信息和序列信息的FPMCLR、PRME-G、POI2Vec、Distance2Pre和SSTRNN模型優于BPR和GRU算法。反映出序列信息和地理位置信息是下一個興趣點推薦的重要指標，同時整合序列信息和地理位置信息通常能提高下一個興趣點推薦的準確率。POI2Vec模型優于PRME-G和FPMC-LR模型，說明用戶在訪問下一個興趣點中更傾向于訪問較近的興趣點。PRME-G在兩個數據集的表現均優于FPMC-LR模型。

下面比較RNN、GRU、Distance2Pre、SSTRNN，它們都是基于循環神經網絡的模型。GRU是最新RNN的變體，通過門控單元控制信息流動，解決了RNN存在的梯度消失和梯度爆炸問題。標準的RNN模型使用用戶最后的會話信息用于推薦，而GRU使用用戶的整個歷史簽到信息。通過實驗結果可以看出，相比于GRU模型，RNN模型在兩個數據集上的表現有極大的提升，表明用戶訪問下一個興趣點的行為主要受當前用戶所在環境的影響，使用整個用戶的簽到記錄可能導致增加更多的干擾信息以及無法捕獲用戶變化的偏好。通過Distance2Pre、SST-RNN與其他模型對比，可以看出Distance2Pre和SST-RNN優于其他比較算法。其原因是：其他模型更傾向于給用戶推薦近距離的地點，從而限制模型給用戶推薦較遠的地點，而且這些模型也忽略用戶訪問下一個興趣點的不同距離偏好。Distance2Pre使用GRU模型根據用戶對空間距離的偏好進行建模，通過在GRU隱藏層上應用一層全連接神經網絡對用戶的不同距離偏好進行建模，提升了模型的推薦效果，說明用戶訪問下一個興趣點受不同距離偏好的影響。可以看出，結合用戶時空偏好和序列信息的SST-RNN模型在各個評價標準中均表現出最優的結果，顯著優于其他所有比較的模型。這是因為SST-RNN能夠對用戶訪問下一個興趣點的遠近距離偏好和長短時間偏好進行建模，充分利用時間信息、序列信息和用戶偏好進行個性化的下一個興趣點推薦。

4.2.3 參數分析

本文的SST-RNN模型中的參數主要包括神經元個數、會話長度 (πs)、控制用戶訪問下一個興趣點的遠近距離偏好( πd)和長短時間偏好(πt)4個參數變量。為了保持模型對比的公平性，本文設置神經元個數與之前提到的基于GRU對比模型的算法保持一致，神經元個數設置為20。πs參數用于控制輸入的會話信息，較長的2個相鄰興趣點時間間隔將導致2個興趣點之間的序列依賴性降低[21]。本文首先在2個數據集上測試πs= 6 h、 πs= 8 h、 πs=10 h模型的效果，發現在2個數據集上 πs的取值對于模型的表現有很微弱的影響，因此本文固定會話長度 πs=8 h。主要探索用戶訪問下一個興趣點的遠近距離偏好 πd和長短時間偏好(πt)的影響。由于 πt和 πd參數取值之間相互影響，找出最優的參數值將需要大量的計算。本文首先隨機初始化一些 πd={6，8，10，12，14}km和 πt={8，16，24，32，40} h的參數組合，當πd=10 km，πt=8 h，時，模型在2個數據集中表現較好。為了進一步探索較優的參數值，本文首先固定 πt= 8 h，探索最優的 πd取值，實驗結果如表4所示。找到最優的 πd參數值后，再固定 πd的值，之后找出最優 πt參數值，實驗結果如表5所示。最終得到的較優的 πt和 πd參數將作為2個數據集上最終的實驗參數設置。實驗中，ACC@5和MAP指標被選為評價標準，。

從表4、5的實驗結果可以看出：當 πd=14 km, πt=24 h時，模型在Foursquare數據集上表現最好；當 πd=12 km, πt=16 h時，模型在CA數據集上表現最好。

表4 π d 參數對于Foursquare和CA數據集影響Table 4 Influence of πd parameters on Foursquare and CA datasets %

5 結束語

本文研究了下一個興趣點推薦的問題，提出了一種新的基于會話的時空循環神經網絡模型，該模型能夠同時考慮序列信息、兩類時間信息、空間信息以及用戶偏好進行個性化的下一個興趣點推薦。為了解決用戶不同的時空偏好問題，本文對RNN神經網絡進行改進，提出利用時空轉移矩陣對用戶不同的時空偏好進行建模，使RNN模型能夠捕獲用戶簽到行為的時空信息。通過在真實的數據集上對模型進行性能測試，結果表明，提出的模型顯著優于當前主流相關模型。下一步工作將探索更豐富的數據集，進一步結合用戶基本屬性、地點基本屬性來解決興趣點推薦中出現的冷啟動問題，并且整合其他輔助的信息(如圖像、用戶評分和文本評論等)作更精確的下一個興趣點推薦。