基于時序和距離的門控循環單元興趣點推薦算法

夏永生,王曉蕊,白 鵬,李夢夢,夏 陽,張 凱

(1.中國礦業大學 計算機科學與技術學院,江蘇 徐州 221116; 2.蘇寧易購集團股份有限公司,南京 210042)

0 概述

智能手機、手環等多功能移動終端的廣泛使用,使得用戶的地理位置信息可以被輕易地獲取到,因此,基于位置的移動社交網絡(Location Based Social Network,LBSN)也逐漸發展起來[1-2]。在LBSN中,用戶可以使用隨身攜帶的智能設備進行簽到,還可以對訪問過的地點進行評分或評價,為要訪問該地點的其他用戶提供參考意見。這類地點可以是飯店、酒店、名勝古跡等,專指那些用戶感興趣的位置地點,即興趣點(Point of Interest,POI)。

興趣點推薦分析用戶的簽到信息,挖掘用戶、興趣點、興趣點所在位置以及用戶訪問興趣點的時間等模型,為用戶推薦可能感興趣的位置地點[3]。興趣點推薦對于用戶和興趣點商家都有重要的現實意義。從用戶角度,興趣點推薦可以幫助用戶有效地探索符合用戶偏好的未訪問過的地點,為人們的日常生活帶來便利。從商家角度,興趣點可以為企業吸引更多的潛在客戶,為企業帶來更多的商業利益。因此,興趣點推薦算法研究具有一定的科研價值和實用價值。

相比于傳統推薦算法,興趣點推薦所包含的信息種類多種多樣,如興趣點的文本信息、興趣點的地理坐標、用戶的簽到時間、用戶的社會關系、興趣點的流行度等,興趣點的相關文本信息不同于傳統推薦系統,其信息具有不完整性、模糊性[4]。利用LBSN中用戶的多源異構簽到數據,對用戶進行興趣點推薦成為當前的研究熱點。

為捕捉地理因素影響,文獻[5]將用戶在某位置上簽到的概率建模為一個多中心高斯模型(MGM),按照概率值為用戶進行興趣點的推薦。文獻[6]從基于位置的社交網絡抓取用戶簽到數據進行分析,發現用戶會在不同的時間周期訪問不同類型的興趣點,并提出基于用戶簽到的時間分布來提取興趣點特征的方法。基于興趣點時間或距離的單維簽到數據進行推薦,一定程度上提高了興趣點推薦的準確性,但是沒有考慮到兩者之間的相關性,忽略了用戶所處的地理位置往往隨時間的變化而發生移動的特點。文獻[7]使用隱含狄利克雷分布(Latent Dirichlet allocation,LDA) 模型,并基于用戶的帖子或者興趣點的標簽來挖掘用戶和興趣點的主題屬性,其中每個主題也是詞的分布,然后利用主題屬性和詞分布來確定用戶對于興趣點的偏好分數。對于評分數據,一般采用協同過濾算法較多,文獻[8-9]對評分數據的處理都運用了協同過濾推薦算法來進行興趣點推薦。將用戶對興趣點的簽到評分數據和評價文本融合到興趣點推薦中,比僅利用用戶個人信息進行的興趣點推薦有更好的推薦性能,但是評分數據和評價文本大都非常稀疏,使得用戶的真實偏好難以被充分挖掘出來,很難達到理想的推薦效果。此外,也有學者利用好友關系和興趣點流行度進行興趣點推薦。文獻[10]提出基于朋友的協同過濾算法,其中用戶間的相似度采用軌跡相似度,即將用戶間的軌跡和距離作為冪函數計算,最后通過具有相似的簽到偏好向用戶進行位置的推薦。文獻[11]提出融入時間信息的用戶協同過濾興趣點推薦算法,得到用戶訪問興趣點的估算值;結合流行度和空間信息提出另一種估算方法,將2個估算值進行線性組合,作為用戶訪問興趣點的估算值。

本文借鑒門控循環單元對序列數據建模的有效性,對用戶訪問興趣點中的時序信息進行建模,利用用戶訪問興趣點之間的連續時間和連續地理位置信息,提出基于時序和距離的門控循環單元興趣點推薦方法TD-GRU。

1 相關研究

綜合興趣點推薦算法的相關文獻可以發現,與傳統推薦算法相比,興趣點推薦算法容易受地理位置、時間等因素的影響[12]。本節從地理位置因素和時間因素兩方面介紹相關研究,同時介紹門控循環單元模型。

1.1 基于地理位置因素的推薦算法

在興趣點推薦中,地理位置因素發揮著非常重要的影響。文獻[13]研究發現用戶的簽到位置與距離呈反比,即距離當前位置越近的興趣點,越容易被用戶簽到。因此,在位置推薦算法中設定了距離的閾值,過濾掉簽到位置距離超過閾值的興趣點,以此提高推薦性能。文獻[14]將地理位置近鄰引入偏向矩陣分解算法以提高興趣點推薦的準確性。針對空間聚類現象,文獻[15]利用用戶的活動區域向量和影響POI的區域向量來增加用戶和POI在矩陣分解模型中的潛在因素。文獻[16]將用戶簽到位置之間的距離視為高斯分布模型,其中主要將用戶簽到位置劃分為在家周圍和工作地點周圍2個狀態,采用二維的時間獨立的高斯模型,將地理因素和時間的階段性有效結合。除高斯分布模型外,對于地理位置因素,最常用的是冪律分布。文獻[17]假設用戶簽到位置之間相互獨立,將用戶簽到下一位置的意向轉換為距離的冪函數,以此進行位置的推薦。在此基礎上,研究人員從一維的距離函數轉向為二維的核密度估計,利用位置的經緯度坐標,進行非參數估計,避免了提前設定函數的局限性,更能體現用戶簽到的個性化和推薦的個性化特征[18]。

1.2 基于時間因素的推薦算法

在用戶的簽到信息中,時間因素往往起到非常重要的作用,用戶在不同時間點會在不同的興趣點簽到[19]。文獻[20]將用戶簽到矩陣劃分為各個時間下的子矩陣,并利用非負矩陣分解將各個子矩陣分解成相應時間狀態下的用戶簽到偏好矩陣和位置特征矩陣,再集成各個時間下的用戶簽到偏好,最終得到用戶對興趣點的簽到偏好。另外,還包括將用戶歷史評分數據的時間和預測目標興趣點簽到時間之間的時間間隔作為一個衰減因子[21]來衡量評分數據。文獻[22]提出基于馬爾可夫鏈模型的序列預測算法FPMC,在MC的基礎上將所有用戶的轉換矩陣的張量因式分解,并通過基于馬爾可夫鏈假設計算轉換概率來預測下一個位置。2013年,一種新的矩陣分解方法被提出,即FPMC-LR[23],該方法嵌入了個性化馬爾可夫鏈和局部區域,不僅在簽到序列中利用個性化馬爾可夫鏈,而且還考慮到用戶的移動約束,即在局部區域周圍移動。文獻[24]采用周期時間模式,將一天的時間按照一定的單位劃分為若干個相等的時間槽,根據時間槽對用戶簽到位置歷史進行劃分和研究,提出基于用戶簽到的時間分布來提取興趣點特征的方法。

1.3 門控循環單元模型

用戶訪問興趣點的時間信息反映了用戶行為的時間序列模式,引入時間信息有利于提升興趣點推薦系統的性能。循環神經網絡模型(Recurrent Neural Network,RNN)的提出正是被用于建模序列數據,因此很快被引入到用戶行為序列模式建模的研究中[25]。本文利用循環神經網絡對用戶訪問興趣點的時間信息進行處理獲得用戶偏好的隱表示,用作下一步對用戶興趣點的推薦。

循環神經網絡是一類專門用于處理時序數據樣本的神經網絡,具體的表現形式為:網絡對前面的信息進行記憶并應用于當前輸出的計算中,即隱藏層之間的節點是有連接的,并且隱藏層的輸入不僅包括輸入層的輸出,還包括上一時刻隱藏層的輸出。文獻[26]采用循環神經網絡建模用戶偏好和項目特征的演化,提出了一種循環推薦網(Recurrent Recommender Network,RRN)來預測用戶未來的行為軌跡。理論上,RNN可以對任意長度的時間序列進行記憶,但是隨著時間跨度的不斷增大,RNN會喪失對遠處單元的記憶能力。這樣會導致提取到的用戶興趣點偏好更多地依賴用戶近期訪問的興趣點,不能全面刻畫用戶興趣點偏好。長短期記憶網絡(Long Short Term Memory,LSTM)和門控循環單元(Gated Recurrent Unit,GRU)作為RNN的變種,通過使用門結構來改善RNN短期記憶的缺點,在保留長期序列信息下減少梯度消失問題。文獻[27]提出一種深度遞歸神經網絡的文本推薦方法,利用GRU 學習文本內容的向量表示,對改善數據稀疏性和冷啟動問題很有幫助。文獻[28-29]對比了 LSTM 和 GRU 以及傳統的 RNN 的異同,探討了上述結構的優點,另外通過實驗證明了在個數參數相同的情況下,GRU 優于 LSTM。因此,本文利用GRU來處理用戶訪問興趣點的時間信息,GRU模型的基本結構如圖1所示。

圖1 GRU模型基本結構

rt=σ(xtWxr+ht-1Whr+br)

(1)

zt=σ(xtWxz+ht-1Whz+bz)

(2)

(3)

(4)

其中,Wxr和Whr是重置門的權重參數,Wxz和Whz是更新門的權重參數,Wxh和Whh是候選隱藏狀態的權重參數,br、bz、bh是偏置參數,⊙是元素乘法符。將用戶訪問興趣點的時間序列作為GRU的輸入,提取用戶的興趣點偏好特征,并以此進行興趣點推薦。

2 TD-GRU推薦模型

在興趣點推薦算法中,基于連續時間因素的研究較少。在興趣點推薦中,所有的POI都具有位置屬性,而且用戶行為具有時序性,將時序信息和距離信息融入興趣點推薦算法,有利于提高推薦的準確性。針對循環神經網絡可以建模序列數據的優勢,將門控循環神經網絡引入興趣點推薦算法,提出基于時序和距離的門控循環單元興趣點推薦算法,以提高興趣點推薦的準確性。

2.1 TD-GRU模型描述

用戶訪問興趣點之間的連續地理位置距離和時間間隔對于推薦用戶將要去的興趣點是十分重要的,如用戶在昨天去了電影院,那么很有可能需要去電影院附近的餐廳就餐;用戶連續幾個周日去了教堂,那么下周日可能還會去教堂。因此,將用戶訪問興趣點序列中的時間和地理位置加入興趣點推薦算法是十分必要的。通過對用戶訪問興趣點時間序列中的局部時間間隔和興趣點之間的距離進行建模,可以得到用戶在局部時間的興趣偏好和連續時間中用戶的周期性偏好行為,進而進行興趣點推薦。

由于GRU是RNN的一種,不可將連續的時間間隔加入到模型中,因此需要對時間序列進行一些處理,本文將時間離散化,用時間間隔ω作為時間因子,代入GRU模型,提出TD-GRU興趣點模型,如圖2所示。

圖2 TD-GRU模型

在圖2中,C表示興趣點集合,U表示用戶集合,ult表示用戶u在t時刻訪問興趣點l的嵌入表示,用戶訪問過的興趣點歷史Ul={ul1,ul2,…},S和T分別表示特定距離轉換矩陣和特定時間轉換矩陣。

根據GRU的基本結構,在t時刻,新的候選狀態為:

(5)

其中,Wc1、Wc2為模型參數,Ult為在lt位置點的嵌入表示,ft是重置門開關,ht-1為上一個輸出的嵌入表示,bc為偏置向量。由于GRU不能很好地處理連續時間內用戶的訪問歷史,因此需要對時間序列進行巧妙處理,將時間劃分為時間間隔,此時用戶訪問的興趣點歷史被劃分為時間跨度相同的若干個興趣點集合Ul={{ul1,ul2,ulω},{…},{ult-ω,…,ult}},引入特定時間轉換矩陣,則有:

(6)

其中,ω為時間窗口長度,窗口內的每一個元素在模型內建模,Tt-ti則為當前時間t之前的時間間隔為t-ti的特定時間轉換矩陣。矩陣Tt-ti捕捉了用戶訪問興趣點歷史中最新元素的影響,也將連續的時間間隔考慮入內。同時,考慮到距離因素對于興趣點推薦的影響,對用戶訪問興趣點的連續距離進行建模,將特定距離轉換矩陣引入TD-GRU算法。特定距離轉換矩陣用以衡量不同地點位置之間的地理距離,用來捕捉用戶行為軌跡的地理屬性,t時刻的候選隱藏狀態表示為:

(7)

其中,SUlt-Ulti是根據坐標下2個地理距離Ul-Uli的特定距離轉換矩陣,Ult表示在時間t下用戶u正在訪問位置的坐標,地理距離用歐幾里得距離公式:

(8)

(9)

其中,h0表示初始狀態,所有用戶的初始狀態相同,且在該狀態下不存在任何用于個性化預測的行為數據。

(10)

其中,it表示更新門開關,*代表分素乘積。更新門和重置門開關計算公式如下:

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

(11)

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

(12)

其中,Wi1、Wi2、Wf1、Wf2分別為更新門和重置門參數,bi、bf表示更新門和重置門的偏置向量。t時刻的輸出表示為:

ht=tanh(Ct)

(13)

ht捕捉了用戶u在特定時間特定空間下動態的興趣點變化,至此,本文使用TD-GRU模型提取出用戶訪問興趣點的局部偏好和連續時間序列中的周期性變化特征。

2.2 基于TD-GRU的推薦算法

在提取到用戶訪問興趣點的特征偏好后,對于一個給定的興趣點l,使用TD-GRU模型的輸出值ht來計算用戶訪問該興趣點的預測值:

(14)

其中,l是興趣點的潛在向量表示,對于興趣點集合L中的興趣點進行訪問預測值的計算,選取預測值高的興趣點推薦給用戶構成推薦結果集,由于在ht的計算過程中,引入了局部時間內用戶訪問興趣點的特定時間轉換矩陣和特定距離轉換矩陣,因此其推薦的興趣點符合用戶的興趣點偏好,且興趣點集中在一定范圍內。

算法1TD-GRU算法

輸入記錄用戶信息的數據集M

輸出推薦結果集R′

1.For each u∈U do//對某一個用戶

2.For each ti∈(t-ω,t) do//設定時間窗口長度閾值

3.Strai=SUlt-Ulti//特定距離轉換矩陣

4.Ttrai=Tt-ti//特定時間轉換矩陣

5.A=A+StraiTtraiWc1Ult

6.End For

9.ht=tanh(Ct) //t時刻的輸出

11.ltopN→R′//選取預測值高的興趣點加入推薦集

12.End For

3 實驗結果與分析

3.1 數據集

本文選取了2個LBSN數據集來驗證算法的有效性,分別是最常用的Foursquare數據集和通過爬蟲軟件抓取的美團網數據集。首先對數據集進行預處理,將少于5條簽到記錄的用戶和興趣點剔除,Foursquare數據集和美團網數據集的具體統計信息如表1所示。

表1 Foursquare數據集和美團網數據集的統計信息

Table 1 Statistics information of Foursquare dataset and Meituan datasets

數據統計Foursquare數據集美團網數據集簽到記錄數332 778 683456 967用戶數266 90910 162興趣點數3 680 126242 371每個用戶的平均興趣點個數13.7923.85

在2個數據集中隨機選擇70%作為訓練集,20%用于測試集,10%留作驗證數據。為便于實驗,將數據集進行預處理,整理用戶集為U,興趣點集為PPOI,時間集為T,位置坐標集為L。為便于計算興趣點之間的距離,將其坐標化,每個地點l包含其坐標{xl,yl}。符號表示如表2所示。

表2 符號描述

3.2 對比算法

為驗證本文提出的興趣點推薦算法的有效性,選取如下的興趣點推薦算法作為對比算法,以比較算法的性能。

1)TOP算法:是較早的基于位置推薦算法,直接為每個用戶選擇訓練集中最受歡迎的位置作為預測。

2)MF算法:由MNIH和 SALAKHUTDINOV提出的基于用戶位置矩陣協同過濾推薦算法,是傳統的協同過濾方法之一。

3)FPMC算法:RENDLE等人提出的基于馬爾可夫鏈模型的矩陣分解(Factorized Personalized MC,FPMC)算法。在基于馬爾可夫鏈模型(Markov Chains,MC)推薦算法的基礎上,將所有用戶的轉換矩陣的張量因式分解,并通過基于馬爾可夫鏈假設計算轉換概率來預測下一個位置,這也是目前最先進的推薦算法之一。

4)PRME算法:FENG等人考慮到學習嵌入需要將目標位置和最近的遠程位置之間的距離納入考量,提出個性化排名度量嵌入(Personalized Ranking Metric Embedding,PRME)方法。

3.3 評價指標

采用興趣點推薦常用的準確率和召回率作為評價指標,然而,由于準確率和召回率往往相互制約,本文為評測算法的穩定性,采用了F1指標。F1指標是一種綜合指標,為Precision和Recall的加權調和平均數,計算公式如下:

(15)

(16)

(17)

其中,R(u)表示對用戶u進行推薦的興趣點集合,T(u)表示用戶u在測試集上實際的簽到集合,N表示推薦列表的大小。

3.4 實驗結果

本文在Foursquare數據集和美團網數據集進行了對比實驗。對比算法包括TOP算法、MF算法、FPMC算法和PRME算法。評價指標為準確率Precision@N、召回率Recall@N和F1值,N取值為1、5、10、20。

圖3和圖4表示Foursquare數據集上TD-GRU算法、TOP算法、MF算法、FPMC算法、PRME算法之間不同推薦列表長度的準確率和召回率。在Foursquare數據集上,當推薦列表長度N取10時,TD-GRU算法準確率為8.7%,召回率為12.1%,而經典的矩陣分解MF算法的準確率為2.3%,召回率為5.1%,FPMC算法的準確率為5.3%,召回率為9.2%,PRME算法的準確率為5.9%,召回率為10.3%。相比之下,TD-GRU算法的準確率約是MC算法的3倍多,比FPMC算法、PRME算法分別高3.4%和2.8%。而TD-GRU算法的召回率是MC算法的2.3倍,比FPMC算法和PRME算法分別高2.9%和1.8%。

圖3 Foursquare數據集上不同算法推薦列表長度的準確率

Fig.3Precision rates of different algorithms and recommended list lengths on Foursquare dataset

圖4 Foursquare數據集上不同算法推薦列表長度的召回率

Fig.4 Recall rates of different algorithms and recommended list lengths on Foursquare dataset

圖5、圖6表示美團網數據集上TD-GRU算法與TOP算法、MF算法、FPMC算法、PRME算法之間不同推薦列表長度的準確率和召回率。在美團網數據集上,當推薦列表長度N取5時,TD-GRU算法準確率為5.2%,召回率為5.9%,而經典的矩陣分解MC算法的準確率為2.9%,召回率為2.9%,FPMC算法的準確率為3.7%,召回率為3.1%。PRME算法的準確率為4.3%,召回率為3.5%。相比之下,TD-GRU算法的準確率約是MC算法的2倍,比FPMC算法高1.5%,比PRME算法高0.9%。而TD-GRU算法的召回率是MC算法的2倍,比FPMC算法和PRME算法分別高2.8%和2.4%。

圖5 美團網數據集上不同算法推薦列表長度的準確率

Fig.5Precision rates of different algorithms and recommended list lengths on the Meituan dataset

圖6 美團網數據集上不同算法推薦列表長度的召回率

Fig.6 Recall rates of different algorithms and recommended list lengths on the Meituan dataset

從圖3～圖6可以看出,無論在Foursquare數據集上還是在美團網數據集上,TD-GRU算法的準確率和召回率都是5個算法中最高的。由此可見,相比于TOP算法、MF算法、FPMC算法、PRME算法,TD-GRU算法性能明顯優于其他算法,說明該算法相比其他算法有效性更好,推薦更準確。整體上而言,無論在Foursquare數據集上還是在美團網數據集上,興趣點推薦算法的準確率隨著推薦列表長度N的不斷增大而減小,而召回率則表現為隨著N的不斷增大而增大。為更直觀地觀察TD-GRU算法的整體性,本文還采用了F1指標,結果如圖7和圖8所示。從圖7、圖8可以看出,TD-GRU算法的F1指標隨著推薦列表長度N的增大,均高于其他算法,說明其在整體性上明顯優于其他算法。另外,在Foursquare數據集上,F1指標在N=10時出現最大值,表明為Foursquare網站的用戶最好推薦10個興趣點。而在美團網數據集上,F1指標在N=5時出現最大值,表明給美團網站用戶推薦的興趣點個數最好為5個。

圖7 Foursquare數據集上不同算法推薦列表長度的F1值

Fig.7F1 indicator with different algorithms and recommended list lengths on Foursquare dataset

圖8 美團數據集上不同算法推薦列表長度的F1值

Fig.8F1 indicator with different algorithms and recommended list lengths on the Meituan dataset

上述實驗結果驗證了TD-GRU算法的推薦性能最優。本文針對不同的時間窗口ω值以及不同的列表長度N,以召回率Recall值為參考進行實驗,實驗結果如表3、表4所示。

表3 Foursquare數據集上不同推薦列表長度時間窗口值的召回率

Table 3 Recall of different recommendation list lengths and time window values on the Foursquare dataset

ω/d Recall@1/%Recall@5/%Recall@10/%Recall@20/%0.51.35.49.610.91.01.86.210.712.03.02.26.811.512.95.02.47.111.913.67.02.88.112.117.210.02.36.911.913.414.01.96.211.112.3

表4 美團網數據集上不同推薦列表長度時間窗口值的召回率

Table 4 Recall rate of different recommendation list lengths and time window values on the Meituan dataset

ω/dRecall@1/%Recall@5/%Recall@10/%Recall@20/%0.51.12.35.38.31.01.43.47.09.73.01.74.78.510.95.02.15.49.311.67.01.95.910.212.410.01.55.79.811.814.00.94.27.210.6

由表3、表4可知,當ω值取7 d時(見粗體),TD-GRU算法無論在Foursquare數據集上還是在美團網數據集上,召回率都是最高的,這就意味著將用戶訪問興趣點的時間序列劃分成7 d的時間間隔,推薦效果最優,較好地覆蓋了用戶訪問興趣點的長序列,推薦結果具有更高的可信度和參考價值。

4 結束語

為便于對時序信息建模,本文將深度學習領域的門控循環神經網絡引入興趣點推薦算法,對連續的時間因素離散化處理,給出特定時間轉換矩陣,而對于距離信息采用了特定距離轉換矩陣,提出基于時序和距離的門控循環單元興趣點推薦算法(TD-GRU)。實驗結果表明,與傳統的興趣點推薦算法相比,該算法推薦結果具有較高的可靠性。在實際中,影響興趣點推薦的因素較多,本文只考慮了時間和地理位置,下一步將結合影響興趣點推薦的興趣點流行度、用戶好友關系等因素,進一步完善本文推薦算法。