關注點推薦算法的霍克斯過程法

張國明，王俊淑，江 南，盛業(yè)華

1. 南京大學計算機科學與技術系，江蘇 南京 210023； 2. 江蘇省衛(wèi)生統(tǒng)計信息中心，江蘇 南京 210008； 3. 南京師范大學虛擬地理環(huán)境教育部重點實驗室，江蘇 南京 210023； 4. 江蘇省地理信息資源開發(fā)與利用協(xié)同創(chuàng)新中心，江蘇 南京 210023

隨著智能手機的普及，以及Web2.0和定位技術的發(fā)展，地理位置信息在人們的生活中發(fā)揮越來越重要的作用。位置服務(LBS)與在線社交網絡(OSN)相結合的基于位置社交網絡(location-based social network,LBSN)[1]迅速興起。用戶可以在訪問關注點(如超市、餐館、景點、酒店等)的同時進行簽到。利用海量簽到數據能夠挖掘用戶的訪問偏好，幫助用戶決策，催生了基于位置社交網絡的個性化關注點推薦。關注點推薦不僅可以幫助用戶探索新的區(qū)域和發(fā)現(xiàn)新的關注點，也可以通過智能位置服務為商家增加收入，近幾年來吸引了學術界和工業(yè)界越來越多的關注[2-4]。

推薦系統(tǒng)是緩解信息過載的重要方法，得到了廣泛的研究和應用[5-8]。與傳統(tǒng)的推薦系統(tǒng)相比，關注點推薦更加復雜。除了用戶偏好、地點屬性之外，還需要考慮距離、時間、社交、類別、流行度等多種信息[9]。相對于傳統(tǒng)推薦系統(tǒng)中的用戶-物品矩陣，用戶簽到矩陣具有更高的稀疏度[10]。位置信息是LBSN中最重要的一個特征，目前大部分推薦研究僅利用了位置信息的某個方面，位置上下文信息沒有被充分利用。此外，現(xiàn)有關注點推薦算法對用戶訪問偏好的時空變化情況考慮不足。針對上述問題，本文提出一種基于霍克斯過程(Hawkes process)的上下文感知協(xié)同過濾關注點推薦算法(HWCF)，通過融合空間聚類信息、空間距離信息和空間序列變換信息等多個與位置相關的因素，結合時間信息、用戶偏好、關注點流行度等多種上下文信息，提高推薦性能。

1 關注點推薦概述

隨著基于位置社交網絡的快速發(fā)展，關注點推薦受到學術界和工業(yè)界的廣泛關注。相關研究方法包括協(xié)同過濾算法(collaborative filtering，CF)[11]、矩陣分解算法、空間距離分布建模、基于好友關系、基于文本信息等。不同方法適用于不同的簽到數據集，如協(xié)同過濾算法的適用范圍最廣，它通過計算用戶-用戶相似度或關注點-關注點相似度進行推薦。空間距離分布建模方法適用于具有精確地理位置的數據集，根據用戶和關注點之間的距離建模?；诤糜殃P系的關注點推薦方法適用于包含用戶好友列表的數據集，通過挖掘用戶與好友之間的相似度進行推薦。下面對主流關注點推薦算法進行闡述。

(1) 協(xié)同過濾法?，F(xiàn)有的關注點推薦大部分是基于協(xié)同過濾算法[11-12]。該方法認為愛好相似的用戶訪問的地點也大多相同。協(xié)同過濾算法分為兩種：基于用戶(user-based)[12-13]的協(xié)同過濾和基于物品(item-based，將關注點看作物品)[11]的協(xié)同過濾，前者計算用戶之間的相似度，后者計算關注點之間的相似度。

(2) 基于地理空間關系的方法。地理位置是關注點推薦的重要影響因素，距離用戶位置越近的地點被訪問的概率越大[14-15]。根據用戶簽到地點的距離分布進行數據建模，結果表明簽到位置呈現(xiàn)冪律分布或者高斯分布[16-17]。結合地理空間聚集現(xiàn)象，對用戶活動區(qū)域與關注點影響區(qū)域建模，可以緩解稀疏性問題[18]。文獻[19]利用核密度估計分析關注點的二維地理坐標對用戶行為的影響，并結合用戶社會關系提高了推薦性能。

(3) 基于歷史簽到記錄的方法。用戶簽到記錄呈現(xiàn)一定的規(guī)律性，通過分析用戶歷史簽到記錄，可以預測下一個關注點[20-24]。如基于一階[22-23]和n階馬爾科夫鏈[24]來計算用戶的時空序列，僅考慮用戶的最后一個簽到地點，來推測下一個可能被訪問的關注點。

(4) 基于社會關系的方法。用戶與用戶之間的社交關系(好友關系)是基于位置社交網絡的重要特性，好友比陌生人更有可能分享共同的偏好。如基于好友的協(xié)同過濾方法[25]利用好友的共同簽到記錄進行推薦。但由于用戶之間較少分享關注點簽到信息，單純利用社會關系對推薦性能提高有限[26]。

(5) 基于文本挖掘的方法。在LBSN中，用戶可以對關注點打分和評論。通過文本挖掘方法建模用戶對商家的點評行為[27-28]，能夠更準確了解用戶的興趣偏好進行推薦。

(6) 多因素融合方法。考慮到關注點推薦受多種因素影響，僅使用單一因素的推薦算法，性能往往不高。大部分研究試圖融合地理空間信息、時間效應、社會關系、內容信息、流行度等多種因素來提高推薦效果[28-29]。

2 基于霍克斯過程的上下文感知關注點推薦算法

2.1 用戶簽到行為相似度計算

為進行關注點推薦，本文使用基于用戶的協(xié)同過濾算法，根據用戶的簽到行為計算用戶之間的相似度。根據用戶簽到關注點的地理空間聚集現(xiàn)象[18]分析用戶行為，提取用戶特征進行相似度比較。

首先，通過基于密度的空間聚類算法DBSCAN(density-based spatial clustering of applications with noise)將一定地理范圍之內的關注點聚類為簇。聚類的結果除了得到簇以外，還會得到一些不屬于任何簇的噪聲點。然后，根據用戶Ui對興趣簇的簽到頻率將用戶Ui的特征表示為

Pi=A0,A1,A2,A3,…,Am(0≤i≤N)

(1)

式中，A0表示用戶Ui在噪聲點的簽到頻率；Ai到Am表示用戶Ui在m個簇中各自的簽到頻率。用戶Ui在第j個簇中的簽到頻率被定義為

(2)

它表示用戶Ui的所有n條簽到記錄中，有k條記錄屬于第j號簇。類似的，用戶Ui在噪聲點的活躍度定義為

(3)

最后，根據用戶的行為特征，可以計算出用戶之間的相似度。如果用戶i和用戶j有一些簽到地點屬于相同的簇，例如二者在第q號簇中均有簽到，則有

(4)

式中，Sij表示用戶i和用戶j的相似度；Q表示用戶i和用戶j都訪問過的簇的集合。索引q必須為正數，因此，噪聲點將不會被考慮在內。根據式(4)計算的用戶相似度為每個用戶找出相似用戶列表，從相似用戶的歷史訪問記錄中提取關注點，作為用戶的候選關注點。

2.2 霍克斯過程及其適應性分析

霍克斯過程是一種點過程，是1972年由Hawkes提出的一種特殊的線性自激模型[30]。該模型被廣泛應用于各種領域的建模，如經濟分析預測[31-32]、地震預測[33]、社交網絡建模[34-35]等?；艨怂惯^程認為過去的事件會影響未來事件發(fā)生的概率，過去事件的激勵是正的、可加的并隨時間衰減的。本文將霍克斯過程引入到用戶簽到記錄的時空序列關系分析中，公式如下

(5)

式中，λk(t)表示當前事件k(點過程)的發(fā)生強度(概率)；μk≥0表示該自激過程的基礎強度；αik≥0表示歷史事件i對當前事件k的激勵程度；δ為歷史事件激勵的時間衰減系數；t為當前事件k發(fā)生的時間；ti為歷史事件i發(fā)生的時間。

利用霍克斯過程建模關注點推薦的適應性分析。為進行關注點推薦，可以將霍克斯過程中的事件k定義為：用戶u訪問了關注點lk，其發(fā)生強度為λk(t)。μk可表示為：用戶u訪問關注點lk的基礎概率。αik可表示為：用戶u訪問過關注點lj這一歷史事件對用戶訪問新關注點lk的激勵程度。e-δ(t-ti)表示歷史事件激勵的時間衰減程度。每個用戶可以根據自己的歷史訪問事件，建模個性化的霍克斯過程來估計訪問新關注點的發(fā)生強度(概率)，將發(fā)生強度λk(t)按大小排序后即可得到top-k推薦列表。下面詳細描述霍克斯過程相關參數的求解過程。

2.3 自激過程的基礎強度μk

在關注點推薦中，用戶對關注點的訪問概率與用戶到關注點的距離以及關注點流行度相關。本文使用改進的哈夫模型對距離和流行度進行建模，計算用戶訪問關注點的基礎概率。

哈夫模型[36]由美國零售學者戴維哈夫提出，該模型將一個商場對顧客的吸引力歸功于兩個因素[37]：①商場的規(guī)模；②商場與消費者的地理距離。原始哈夫模型表示如下

(6)

式中，Sj表示商場j的規(guī)模，可以通過營業(yè)面積算出；dij為顧客i到商場j的距離；γ為距離衰減系數。在日本通商產業(yè)省的修正哈夫模型中，把γ值確定為2[37]。這意味著，用戶訪問某商場的概率，與營業(yè)面積成正比，與距離的平方成反比。哈夫模型在商場選擇、商業(yè)中心和零售業(yè)布局規(guī)劃、購物中心市場份額預測中得到了大量應用[38-39]。本文對哈夫模型進行改進，使其適應LBSN簽到數據集的特點，進而計算用戶訪問關注點的基礎概率。

變量2：地理距離變量dij。原哈夫模型需要提供消費者和商業(yè)設施的坐標。在簽到數據集中，用戶的坐標是時常變化的，將用戶最后一次簽到記錄所在的地理位置設為用戶當前坐標。

用半正矢空間距離(Haversine distance)[40]來計算用戶位置與候選關注點兩個坐標在地平線上的距離。得到改進后的哈夫模型表示如下

(7)

進一步對哈夫模型通過sigmod函數進行歸一化處理，得到自激過程的基礎強度

(8)

2.4 歷史事件i對事件k的激勵程度αik與時間衰減系數δ

歷史事件j對當前事件k的激勵程度αjk可以通過關注點轉移圖來計算。

定義1：關注點轉移圖[41]。(POI to POI Transition Graph)Graph=(L,E)，它包含一系列的頂點L和邊E。每個頂點li(li∈L)表示一個關注點，每個關注點都有一個出度，定義為OutDegree(li)，它表示從li出發(fā)訪問其他關注點的頻率。每條邊(li,lj)∈E表示從關注點li到關注點lj的一次轉移，每條邊包含的轉移次數的數據，定義為EdgeWeight(li,lj)。

關注點轉移圖描述了每個關注點轉移到其他關注點及相應的數據，包括邊的轉移頻率和頂點的出度，以及一個關注點到其他各個關注點的訪問概率值。

定義2：轉移概率。當關注點li的出度不為0時，即OutDegree(li)>0，則li→lj的轉移概率定義為TP(li→lj)，計算如下

TP(li→lj)=

(9)

根據式(9)即可求得歷史事件j對當前事件k的激勵程度αik=TP(li→lk)。歷史事件激勵的時間衰減系數δ為自由參數，試驗部分將詳細介紹該參數的調整方法并對其取值進行分析。

3 試驗分析

3.1 數據集描述

3.1.1 Gowalla數據集

本試驗使用的Gowalla數據集來自斯坦福大學公開的大型網絡數據集收集網站(http:∥snap.stanford.edu/data/loc-gowalla.html.)。簽到數據Gowalla的源數據范圍覆蓋了全世界，每個地方的數據密度不一，不便于數據的挖掘工作。試驗選取用戶簽到較為密集、數據質量較高的紐約市曼哈頓區(qū)作為研究區(qū)域。地理范圍為：40.60°N—40.85°N，73.89°W—75.05°W。在Gowalla數據集中，紐約市曼哈頓區(qū)共計簽到75 940次，簽到時間跨度為2009年2月至2010年10月。該數據集中每個簽到記錄的存儲形式為：用戶ID、關注點ID、關注點坐標位置、簽到時間。過濾掉簽到少于5次的用戶，并保證每個關注點至少被訪問過10次。過濾后的試驗數據集中包含59 336條簽到記錄，有1612個用戶共訪問了2299個關注點。

3.1.2 Foursquare數據集

Foursquare是基于用戶地理位置信息的手機服務網站，鼓勵手機用戶同他人分享自己當前所在地理位置等信息。試驗使用文獻[42]所提供的Foursquare數據集中的日本東京簽到數據集，簽到時間跨度為2012年4月至2013年2月，包含573 703條簽到記錄。該數據集的每條簽到記錄存儲形式為：用戶ID、關注點ID、關注點類別ID、關注點類別名稱、關注點坐標位置、簽到時間，試驗沒有使用關注點類別相關信息。過濾掉簽到少于10次的用戶，并要求每個關注點被至少訪問過10次。過濾后的試驗數據集中包含357 147條簽到記錄，有2293個用戶共訪問了7866個關注點。兩個數據集的統(tǒng)計情況如表1所示。

表1 數據集統(tǒng)計

3.2 評價指標

在試驗中，根據每個用戶簽到記錄的時間順序選擇前80%的簽到數據作為訓練數據集，其余20%的簽到數據作為測試數據集。根據算法計算用戶到候選關注點的訪問概率，并按概率大小排序后得到top-k個關注點推薦給用戶。為評價推薦效果，采用推薦算法中常用的兩個標準[43]：準確率(precision)和召回率(recall)作為評價指標。

準確率(precision)定義了推薦算法得出的關注點與用戶實際訪問的關注點相符的個數在推薦結果中所占的比例。對于某個用戶u，Ru代表推薦算法的結果(result)集合，Tu代表測試集中用戶u所實際簽到(test)的關注點集合，準確率表示如下

(10)

召回率定義了推薦算法得出的關注點集合Ru與用戶實際訪問的關注點集合Tu中相同的關注點個數在用戶測試集中所占的比例，召回率表示如下

(11)

3.3 對比算法

為了驗證霍克斯過程模型(HWCF)的推薦效果，試驗將與以下算法進行對比：

(1) HFCF。該算法對應本文所提出的霍克斯過程模型基礎強度部分，利用了關注點的距離信息和流行度信息。

(2) AMC。該算法對應本文所提出的霍克斯過程模型時間影響部分，通過加和馬爾可夫挖掘用戶歷史簽到記錄的時序影響。

(3) ASVD++[44]。該算法通過分解簽到矩陣，挖掘用戶和關注點的隱含特征，獲取用戶的訪問偏好。計算時采用隱式評分，即將簽到次數通過函數f(x)=x/K歸一化到(0,1]范圍內作為評分，K是用戶的最大簽到次數。

(4) AOBPR[45]。該算法通過排序學習從隱式反饋中挖掘用戶興趣，并向用戶推薦top-k個關注點，是比較先進的排序推薦算法。

(5) LORE[41]。該算法融合了社會關系、空間距離、流行度、用戶偏好、時間信息等多種上下文信息，并取得了比其他模型更好的效果。如CoRe[19]、USG[46]等。Foursquare數據集不包含社會關系信息， 將使用2.1節(jié)計算的相似用戶代替朋友關系。

3.4 參數調整

DBSCAN聚類算法的兩個參數鄰域半徑和密度閾值，試驗中取值分別為100和2。求解霍克斯過程模型自激強度的哈夫模型有兩個參數：距離衰減系數γ和關注點流行度的彈性系數β。γ根據日本通商產業(yè)省的修正哈夫模型，取值為2，自由參數β在Gowalla數據集中設為3.5，在Foursquare中設為5?；艨怂惯^程模型中歷史事件i對事件k的激勵程度αik根據2.2節(jié)的方法計算得出。歷史事件激勵的時間衰減系數δ是自由參數，在Gowalla數據集中設為-0.5，在Foursquare中設為-0.001，δ越小說明衰減越低，歷史事件與當前事件的時間差按小時計算。

對于霍克斯過程模型(HWCF)的兩個自由參數β和δ，采用交替調參的方法來求取最佳參數：首先固定β，調整δ使推薦準確率達到最好，然后固定δ，調整β使推薦準確率達到最好，一般迭代上述過程3至5次即可達到較好的效果。

3.5 試驗結果

3.5.1 方法對比

各推薦算法在Gowalla數據集和Foursquare數據集上的推薦準確率和召回率分別如圖1和圖2 所示。可以發(fā)現(xiàn)，準確率隨k值的增加而下降，召回率隨k值的增加而上升。如果為用戶返回更多的關注點(即k值較大)，就可以從中發(fā)現(xiàn)更多用戶可能訪問的關注點，但由于推薦的其余關注點的訪問概率會隨k值的增加而逐漸降低，導致這些關注點被用戶訪問的可能性也會減小，并且由于Foursquare數據集的測試數據更多，召回率會更低，從而導致算法差別不明顯。

從圖1和圖2可以看出，霍克斯過程模型(HWCF)在兩個試驗數據集上的推薦效果遠遠優(yōu)于基于矩陣分解的算法ASVD++和基于排序學習的算法AOBPR。這兩種算法僅考慮了簽到次數，沒有利用空間和時間信息。雖然在Gowalla數據集中本文算法的top-1推薦性能略低于HFCF算法，但總體來看，霍克斯過程模型(HWCF)明顯優(yōu)于僅考慮距離和流行度信息的HFCF算法和僅考慮時序相關信息的AMC算法。盡管LORE算法利用了距離、流行度、時間、社會關系等信息，但本文算法取得了更好的效果，尤其在Gowalla數據集上的優(yōu)勢更為明顯。

圖1 Gowalla數據集上的top-k推薦性能對比Fig.1 The performance comparison of top-k recommendation on Gowalla data set

圖2 Foursquare數據集上的top-k推薦性能對比Fig.2 The performance comparison of top-k recommendation on Foursquare data set

3.5.2 參數影響

本文算法有兩個自由參數：流行度彈性系數并β和時間衰減系數δ。圖3和圖4分別顯示了Gowalla與Foursquare數據集上兩個參數的取值對推薦性能的影響，試驗對比了參數取值不同時top-k(k=1，2，3，4，5)推薦的平均準確率和召回率。

當參數β≤2時兩個數據集的效果都較差，這是因為距離衰減系數γ被固定為2。在Gowalla數據集中，當2.5≤β≤4時效果最好，此后平均準確率和召回率略有下降；在Foursquare數據集中，當5≤β≤6時，效果最好，此后變化并不明顯。因此，一般情況下流行度彈性系數β可選取范圍為3至5，表明用戶簽到概率與關注點流行度成指數關系，這也反映了一些實際現(xiàn)象，比如知名度高的景點游客數量可能達到普通景點游客數量的幾十倍。

參數δ在兩個數據集中差異較大。在Gowalla數據集中，當δ>-0.1時，推薦效果下降明顯，當δ=0(無衰減)時效果最差，當δ≤-0.3 時差別不大。而在Foursquare數據集中，當δ=-0.001時取得最大值，當δ=0(無衰減)時，效果略低于最大值，當δ值減小時推薦效果變化不明顯。這是因為Foursquare數據集中歷史簽到影響的時間衰減程度遠遠低于Gowalla數據集。因此，在時間衰減越小的數據集中，δ取值應越小。

4 總 結

針對關注點推薦本文提出了基于霍克斯過程模型的上下文感知協(xié)同過濾推薦算法HWCF，綜合利用了空間聚類信息、空間距離信息、空間序列變換信息、時間信息、用戶個性化歷史偏好、全體用戶偏好、關注點流行度信息等多個上下文信息，在一定程度上緩解了數據稀疏的問題，并在真實的LBSN數據集中進行了試驗驗證。與其他關注點推薦方法相比，HWCF算法的推薦質量有顯著提高。

圖3 Gowalla數據集上的參數β(a)和參數δ(b)的影響Fig.3 The influence of β and δ on Gowalla data set

圖4 Foursquare數據集上的參數β(a)和參數δ(b)的影響Fig.4 The influence of β and δ on Foursquare data set

HWCF算法仍有很大改進空間，在未來工作中，將進一步融合其他上下文信息，如關注點類別信息、用戶文本評論信息、評分信息、時間周期規(guī)律等進一步提高推薦質量。本文提出的霍克斯模型的參數本質上是基于馬爾可夫決策過程計算得出的，在線上推薦時，可以嘗試引入深度強化學習建模用戶的動態(tài)轉移概率對該參數進行優(yōu)化。