一種基于用戶關系和用戶偏好的下一個興趣點推薦方法

方 金 鳳，孟 祥 福,2

(1.遼寧工程技術大學測繪與地理科學學院，遼寧 阜新 123000；2.遼寧工程技術大學電子與信息工程學院，遼寧 葫蘆島 125105)

0 引言

隨著無線通信設備的快速普及以及GPS定位技術的快速發展，海量基于位置服務數據能真實反映用戶的行為規律，使得對用戶行為模式的探索成為可能[1-4]。下一個興趣點推薦作為基于位置服務數據最典型的應用之一，旨在根據用戶行為習慣準確推測出用戶下一時刻將要訪問的興趣點，為用戶的決策行為提供幫助，為商家的營銷活動提供參考，因此，研究下一個興趣點推薦方法具有重要的現實意義和應用價值。

與一般興趣點推薦不同，用戶的序列訪問行為對其要訪問的下一個興趣點具有重要影響，推薦列表會隨簽到信息時刻變化，且用戶的每次移動均會導致推薦列表明顯變化,因此，下一個興趣點推薦本質上是行為序列數據分析與推薦[5,6]。馬爾科夫鏈是解決序列分析問題的有效手段，學者們最初?；隈R爾科夫鏈進行用戶的下一個行為推薦[7-9]，但隨著馬爾科夫階數(記憶步長)的增加，計算量會以指數形式增長，限制了該方法的應用。詞嵌入模型可將詞的特征映射到低維空間中，從而縮短計算維度,有學者據此提出基于嵌入的下一個興趣點推薦方法[10,11]，通過將興趣點嵌入低維空間中可捕獲興趣點間的相關性并減少計算量，但該方法無法有效獲取興趣點間的序列影響。為此，在采用嵌入方式進行下一個興趣點推薦時，通常結合其他能夠捕獲興趣點序列關系的方法，如Venue2Vec[12]基于用戶對興趣點的序列簽到信息與興趣點之間的距離構建興趣點轉移圖，然后將興趣點的序列信息輸入詞嵌入模型中學習，進而獲得興趣點的向量表示。循環神經網絡(Recurrent Neural Network,RNN)能在序列數據中自動挖掘上下文信息之間的交互影響，在下一個興趣點推薦中也得到廣泛應用，并成為當前主流的推薦模型[13-15]，但RNN模型在長序列建模中存在梯度爆炸和梯度消失問題，為此，提出長短時記憶(Long Short-Term Memory,LSTM)[16,17]和門控循環單元(Gated Recurrent Unit,GRU)[18,19]兩種RNN變體，形成了基于LSTM和GRU網絡的下一個興趣點推薦算法。

綜上，下一個興趣點推薦方法已取得一定進展，且多依據用戶偏好進行推薦。研究表明，具有相似偏好的用戶往往具有相似的行為[20]，可通過與某用戶具有相似偏好的用戶間接預測該用戶的行為，此外，朋友間的信息分享會影響用戶的決策[20-23]，因此，對用戶關系(包括用戶偏好相似關系和用戶朋友關系)的挖掘和分析在下一個興趣點推薦中至關重要。K近鄰最初用于解決分類問題，后逐漸應用于各類預測問題，在基于位置的服務、空間分析等領域應用廣泛[24]。鑒于此，本文應用K近鄰算法，基于用戶關系和歷史簽到記錄，由當前序列的近鄰序列挖掘當前序列的隱含信息，共同實現對用戶下一個興趣點的推薦。通過在真實數據集上展開實驗，對本文方法進行效果與性能實驗評價，以驗證方法的有效性和優越性。

1 下一個興趣點推薦方法

本文下一個興趣點推薦方法(Relationships and Preferences-Gated Recurrent Unit，RP-GRU)的具體實現流程如圖1所示。首先，對用戶的訪問記錄進行分段處理，由此獲取不同時段的用戶偏好；其次，將用戶關系引入下一個興趣點推薦中，通過構建的用戶關系圖獲取用戶關系向量，并將用戶關系向量同當前偏好向量與周期偏好向量進行拼接，由此得到用戶向量，將用戶向量與興趣點向量相乘可獲得興趣點的近期得分；然后，采用用戶長期訪問序列的K近鄰序列獲取用戶的長期偏好，計算出興趣點的長期得分；最后，將興趣點的近期得分與長期得分相加得到興趣點的總得分，據此進行下一個興趣點推薦。

圖1 下一個興趣點推薦的解決方案Fig.1 Solutions for next POI recommendation

1.1 用戶關系向量

1.1.1 用戶關系圖構建

(1)用戶關系圖由節點(代表用戶)、邊(代表用戶關系)和權重(代表用戶關系的緊密度)組成。用戶關系包括朋友關系和偏好相似關系，兩個用戶訪問的共同興趣點越多，說明其偏好越相似，如果兩個用戶存在朋友關系或兩者訪問過同一興趣點，則兩者之間邊的權重加1。以4個用戶對3個興趣點的訪問情況及用戶之間的朋友關系為例(表1)，可構建出用戶關系圖(詳見圖1)。

表1 用戶對興趣點的訪問記錄及其朋友關系Table 1 Users′ check-in records for POIs and friend relationships

(2)重啟隨機游走算法通過迭代方式探索網絡圖的整體結構以捕捉兩個節點之間的關系，進而得到節點間的接近度[25]。本文根據用戶關系構建用戶關系圖，將計算兩個用戶之間的相似性問題轉化為計算用戶關系圖中兩個節點之間的接近度問題，進而通過重啟隨機游走算法評估兩個用戶之間的相關性。用戶關系圖中兩節點之間連線的權重代表從一個用戶到另一個用戶的轉移強度，如與u2相連邊的權重總和為4，u2與u4相連邊的權重為2，則從u2到u4的轉移概率為2/4(從u4到u2的轉移概率為2/6)。由此，用戶ui到uj隨機游走的概率可由式(1)計算。從用戶關系圖中的一個節點出發，選取模型訓練表現最優對應的步長和次數進行隨機游走，并對圖中所有節點重復此操作即可獲得模型訓練的序列輸入數據。本文中步長為20，次數為50次。由于不同數據集下參數的取值各異，對于較大的數據集需適量增加步長和隨機游走次數以提升模型性能，使得依賴短隨機游走得到的信息能夠在不需全局重新計算的情況下適應網絡出現的小變化。

(1)

式中：f(ui,uj)為以ui和uj為頂點的邊的權重，f(ui,uj)與f(uj,ui)不一定相同；F(ui)為用戶關系圖中與ui有邊相連的節點集合。

(2)

(3)

(4)

(5)

式中：η為學習率，根據文獻[26]取值為0.025。

1.2 周期偏好與當前偏好

按照用戶對興趣點的簽到時間將用戶偏好劃分為長期偏好(用戶所有簽到記錄)、周期偏好(包括當前偏好和月偏好)和當前偏好。

1.2.1 當前偏好與月偏好 當前偏好指用戶最后一次簽到1天之內的簽到記錄(日偏好)，月偏好指與用戶最后一次簽到相距1個月內的簽到記錄,兩者均用GRU模型建模，以簽到興趣點和簽到時間為輸入，區別在于輸入數據的時間間隔不同。簽到時間包括簽到星期和簽到時刻，分別用獨熱編碼(one-hot encoding)表示，簽到星期分為7 d，如周一表示為[1,0,0,0,0,0,0]，簽到時刻分為24 h，如0點表示為[1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]。模型在t時刻的輸入St由當前時刻簽到興趣點向量pt、簽到星期向量Weekt與簽到時刻向量Hourt組成，記做St=[pt:Weekt:Hourt]。通過GRU模型對月偏好和當前偏好建模(圖2)，其計算方法為：

圖2 當前偏好建模Fig.2 Current preference modeling

ht=f(St,Wht-1,b)

(6)

uc=σ(Wo·ht+bo)

(7)

式中：ht為GRU模型的輸出；uc為當前偏好向量；ht-1為GRU模型上一時刻的輸出；W、Wo和b、bo分別為神經網絡的權重和偏置。

1.2.2 周期偏好 受DeepMove模型[18]的啟發，用戶的周期偏好對其訪問下一個興趣點存在一定影響。DeepMove模型以日為單位對用戶的簽到記錄進行劃分，以用戶每日簽到興趣點向量的平均值表示用戶當日的信息。本文利用分層注意力機制通過用戶的月偏好和當前偏好得到用戶的周期偏好(式(8)-式(10))。通過用戶的當前偏好uc與向量ot得到月偏好模型每一時刻對用戶周期偏好貢獻的注意力權重αt，將ht與其對應注意力權重αt相乘作為月偏好每一時刻對用戶周期偏好的貢獻，月偏好所有時刻的貢獻之和up即為用戶的周期偏好(圖3)。

圖3 周期偏好建模Fig.3 Periodic preference modeling

ot=tanh(Wht+bw)

(8)

(9)

(10)

式中：ht為月偏好模型每一時刻的輸出;W和bw分別為神經網絡的權重和偏置；ot為ht經過一層全連接神經網絡后的向量；uc為周期偏好的輸入，文獻[27]中uc向量被隨機初始化，然而本文以當前偏好模型在最后一個時刻得到的輸出向量作為uc。

1.3 興趣點近期得分

wi=eiW

(11)

式中：ei為嵌入之前的向量；wi為嵌入之后的向量；W∈Rm×d為模型需要訓練的權重矩陣。

(12)

式中：l(P,Qt)用于判斷在輸入序列為Qt的條件下模型能否正確預測興趣點P，能正確預測，l(P,Qt)=1，否則l(P,Qt)=0；θ為模型所有可訓練的參數；λ為正則化系數。

1.4 興趣點長期得分

現有下一個興趣點推薦算法通常只利用用戶自身的偏好信息進行推薦，忽略了相鄰序列(指與該用戶的歷史簽到序列相似的序列)中的潛在協作信息(即兩序列之間的共性)，相鄰序列存在類似的行為模式，反映與當前序列相似的用戶意圖。例如，當前用戶的歷史訪問序列為[公園1，公園2，博物館1，公園3]，序列1為[公園1，公園2，博物館2，公園3，賓館]，序列2為[動物園1，公園2，動物園2，公園3，飯店]，相比序列2，序列1與當前用戶的歷史訪問序列更接近，由此可以推斷當前用戶的意圖與序列1較相似，該用戶離開公園3后，要訪問的興趣點大概率是序列1中的賓館，而非序列2中的飯店。

采用K近鄰序列對用戶長期偏好進行挖掘，主要通過當前用戶歷史訪問序列的相似序列探索該用戶可能訪問的下一個興趣點。序列之間的相似性由兩個序列共同訪問過興趣點的數量與兩個序列分別訪問過興趣點的總數量的比值表示。首先，通過式(13)計算當前序列s與數據集中其他序列n之間的相似性，根據相似性結果在數據集中找出與當前序列最相似的K個序列,構成當前序列的K近鄰序列集合Ns；然后，通過每個興趣點在K個近鄰序列中的存在情況為興趣點賦分值，作為興趣點的長期得分Score2(i)(式(14))，由此可得興趣點的總分值Score(i)=Score1(i)+Score2(i)；最后，對Score(i)進行排序，將分值較大的前K個興趣點推薦給用戶。

sim(s,n)=|s∩n|/|s∪n|

(13)

(14)

式中：ln(i)為檢驗興趣點i是否存在于當前序列的K近鄰序列中的標記，如果序列n包含興趣點i，則ln(i)=1，否則ln(i)=0。

2 實驗結果與分析

2.1 實驗設置

選取真實的CA數據集和Gowalla數據集進行算法驗證：CA數據集采用Fousquare點評網站(https://foursquare.com/about)上2010年1月至2011年8月4 163名加利福尼亞用戶的483 813條簽到信息，興趣點的緯度范圍為[-33.94°,52.31°]，經度范圍為[-159.35°,151.17°]；Gowalla數據集是興趣點推薦廣泛使用的公開數據集(http://snap.stanford.edu/data/loc-gowalla.html)，包括2009年2月至2010年10月196 591名用戶的6 442 890條簽到信息，興趣點的緯度范圍為[32.65°,40.59°]，經度范圍為[-122.87°，-114.04°]。為緩解數據的稀疏性，移除簽到次數少于10的用戶和興趣點。用戶簽到數據集的格式如表2所示，選擇用戶歷史簽到數據集的最后一次簽到記錄作為測試集，其余為訓練集。

表2 實驗數據集格式Table 2 Format of experimental datasets

選擇常用的Accuracy@k(ACC@k(式(15)))和MRR@k(式(16))作為實驗評價指標：ACC@k可衡量推薦列表中興趣點的準確程度，如果用戶訪問的下一個興趣點真實出現在推薦列表中，則認為預測正確，其值為1，否則為0，ACC@k取所有測試實例的平均值，值越高表示模型的推薦效果越好；MRR@k可衡量推薦列表中興趣點的排名，用戶訪問下一個興趣點在推薦列表的位置越靠前，則MRR@k的得分越高。

(15)

(16)

2.2 實驗結果

為驗證本文模型引入用戶關系的有效性，分別在CA和Gowalla數據集上將未引入用戶關系和引入用戶關系后得到的推薦結果進行對比，結果如表3所示。由表3可以看出，引入用戶關系的算法要顯著優于未引入用戶關系的算法，這是因為朋友之間會分享相關信息，也會結伴訪問相同的興趣點；同時，歷史訪問行為相似的用戶很可能未來也會訪問相似的興趣點。以ACC@10評價指標為例，引入用戶關系的算法在CA和Gowalla數據集上分別比未引入用戶關系的算法準確度提升了25.17%和18.13%，說明用戶關系對預測用戶的決策行為至關重要，引入用戶關系的算法可顯著提升推薦結果的準確性。

表3 用戶關系對推薦性能的影響Table 3 Impact of user relationship on recommendation performance

為驗證本文采用K近鄰方法分析用戶長期序列偏好的有效性，分別在CA和Gowalla數據集上將未采用K近鄰方法和采用K近鄰方法得到的推薦結果進行對比，通過測試K不同取值的實驗得出，在CA和Gowalla數據集上K分別取100和300。由表4可知，無論是推薦準確性指標ACC@k還是索引值指標MRR@10，采用K近鄰序列挖掘用戶的長期興趣點偏好均優于未采用K近鄰算法，表明K近鄰序列對挖掘當前序列的隱含信息具有積極作用，由此可以證明本文添加K近鄰序列的有效性，但添加K近鄰長期序列分析法對實驗結果的提升不明顯。以ACC@10指標為例，采用K近鄰算法后的模型比未采用K近鄰的模型在CA和Gowalla兩數據集上分別高出4.20%和1.27%，這是因為用戶的下一個行為主要受當前偏好和周期偏好的影響較大，長期偏好對用戶決策的影響力較小。

表4 K近鄰序列對推薦性能的影響Table 4 Impact of K-nearest neighbor sequences on recommendation performance

為進一步驗證本文算法的有效性，分別與5種經典的下一個興趣點推薦算法進行對比，結果如表5所示。1)FPMC-LR[9]：基于馬爾科夫鏈并結合矩陣分解對序列建模獲取用戶偏好，進而實現下一個興趣點的推薦；2)PRME-G[10]：采用個性化度量嵌入的方法進行下一個興趣點推薦，將空間距離作為權重控制用戶的距離偏好，同時整合用戶偏好信息、序列信息和地理位置信息；3)POI2Vec[11]：典型的基于嵌入模型的方法，將Word2Vec應用于興趣點預測，將每個興趣點看作Word2Vec中的一個word，實現下一個興趣點的預測；4)Distance2Pre[19]：利用GRU模型獲取用戶簽到歷史序列信息和距離偏好進行推薦，提出線性和非線性兩種整合模型，本文使用效果更好的非線性模型進行對比；5)CSRM[15]：一種新穎的興趣點推薦方法，不僅對用戶的簽到信息進行建模，還考慮相似用戶的會話簽到信息。

表5 不同算法推薦性能對比Table 5 Comparison of different algorithms in recommendation performance

由表5可知，基于GRU對用戶歷史簽到數據建模的Distance2Pre和RP-GRU模型顯著優于只基于當前興趣點進行推薦的FPMC-LR和PRME-G模型，從側面說明GRU模型對于序列建模的有效性，同時也反映出當前簽到興趣點序列較短，無法有效預測用戶偏好信息，應考慮更長期的序列信息，以免誤解用戶的訪問意圖。整體看，與5種對比算法相比，兼顧用戶關系以及用戶不同階段偏好的RP-GRU模型在兩數據集上的效果均最好，證明該方法有效。

3 結論

本文對用戶的訪問記錄進行分段處理，根據簽到時間劃分為長期偏好、周期偏好和當前偏好，通過GRU模型對用戶的周期偏好和當前偏好建模，采用用戶歷史簽到序列的K近鄰序列挖掘用戶的長期偏好，同時引入用戶關系，為下一個興趣點推薦提供了新的解決方案，并通過在真實數據集上進行實驗以及與現階段主流的下一個興趣點推薦方法進行對比，驗證了本文方法的有效性。

下一個興趣點推薦是基于位置服務的典型應用，具有重要的研究價值和良好的發展前景，未來將從以下兩方面進行研究：1)K近鄰算法中K值的確定，雖然本文方法可應用于不同數據集中，但K近鄰的取值需依據不同數據集而定，下一步將考慮在更多的數據集上進行實驗，尋找K近鄰取值與數據集之間的關聯性，爭取自適應確定K近鄰數量；2)用戶關系的界定，需重點探索朋友關系和偏好相似關系建模的側重點。