基于矩陣分解的上下文感知興趣點推薦方法

李 旭，李景文,2+，姜建武,2，俞 娜

(1.桂林理工大學 測繪地理信息學院，廣西 桂林 541006；2.桂林理工大學 廣西空間信息與測繪重點實驗室，廣西 桂林 541006)

0 引 言

隨著智能移動設備和信息技術的飛速發(fā)展，利用用戶的簽到信息為用戶推薦心儀的興趣點(point-of-interest，POI)已成為眾多學者研究的重點內(nèi)容[1,2]。POI推薦是根據(jù)用戶的地理位置、訪問時間和簽到數(shù)據(jù)等一系列帶有用戶行為標簽的上下文信息為用戶推薦符合其個性化喜好的POI[3]，其不僅為學術界和工業(yè)界研究用戶的個性化喜好和行為模式提供了新的切入點，還能幫助商家挖掘用戶行為習慣，從而給商家?guī)砭薮蟮慕?jīng)濟效益[4]。然而，在實際應用中用戶的簽到記錄與時間、地理位置和評論信息等因素密切相關，這些因素來自不同的領域，有不同的組成結(jié)構(gòu)與表達方式，會對POI推薦造成不同程度的影響。因此，如何根據(jù)多種異構(gòu)類型的上下文信息挖掘用戶的潛在偏好，將時間、地理與用戶個人偏好等因素融入到POI推薦模型中，為用戶生成符合其個性化喜好的POI推薦列表，是POI個性化推薦服務的難點內(nèi)容。

為了解決以上問題，本文提出一種基于矩陣分解的上下文感知興趣點推薦方法，利用矩陣分解模型融合用戶偏好、地理位置和訪問時間等POI上下文信息，并通過隨機梯度下降法優(yōu)化矩陣分解模型的參數(shù)，從而提高POI推薦的準確度，滿足不同用戶的個性化喜好。

1 相關工作

近年來，已有大量學者對POI推薦技術進行了研究，大部分的POI推薦主要是利用各種推薦算法并結(jié)合上下文信息進行推薦。

在地理位置信息的應用方面，龔衛(wèi)華等[5]通過分析用戶的簽到數(shù)據(jù)，發(fā)現(xiàn)用戶的簽到行為具有空間聚類現(xiàn)象，因此在POI推薦中特別強調(diào)地理影響力的作用，并通過矩陣分解對其進行建模。Zhang等[6]通過引入社會正則化和使用歸一化函數(shù)來模擬社會影響和地理影響，并將其融入到矩陣分解模型中。在Zhang的基礎上，Lian等[7]提出一種聯(lián)合地理建模和基于隱式反饋的矩陣分解POI推薦模型，該模型利用二維核密度估計捕獲用戶移動數(shù)據(jù)中的空間聚類現(xiàn)象，有效緩解了POI數(shù)據(jù)的稀疏性，提高了POI推薦的準確性。Zhang等[8]提出一種對地理影響力進行建模的POI推薦方法，該方法考慮用戶和POI的位置來模擬地理影響，并使用概率因子模型對其進行建模，可以更準確地預測用戶在位置上的偏好，從而更好的對POI進行推薦。

在時間信息的利用方面，Ding等[9]為了研究評論文本中時間因素對用戶選擇POI的影響，提出了一種針對特定時間的時空距離度量嵌入模型(ST-DME)，該模型利用簽入的時間和地理順序?qū)傩詠碛行У亟Ｓ脩魧τ谔囟〞r間的偏好。Yin等[10]針對POI推薦中信息過載問題，在協(xié)同過濾算法中融入時間因素，通過對用戶進行聚類和建立時間遺忘曲線反映用戶個性化喜好，從而提高算法運行的效率。原福永等[11]提出了一種融合時間序列的動態(tài)POI推薦算法，將地理位置與時間流行度相結(jié)合，預測POI的評分，從而提高POI推薦的準確性。

除了地理位置信息與訪問時間信息，其它上下文信息對POI推薦也有著重要的影響。Yao等[12]利用高階張量來融合社會上下文信息，并通過基于Tensor因式分解的協(xié)作過濾方法建模用戶偏好。陳炯等[13]為提高POI推薦精度，綜合考慮了社交、內(nèi)容等多種POI上下文信息挖掘用戶行為偏好。Ma等[14]通過分析用戶的社交關系，提出一種具有社交正則化的矩陣分解框架，并取得了較好的推薦效果。

以上研究雖然在一定程度上考慮了上下文信息對POI推薦的影響，但只是通過協(xié)同過濾算法或者矩陣分解模型對上下文信息進行簡單的線性組合，未充分挖掘用戶之間的相互關系，并且缺乏對時間因素以及推薦多樣性的統(tǒng)一分析，不能最大程度體現(xiàn)個性化推薦結(jié)果。

2 POI上下文信息建模

2.1 問題描述

對于特定的POI點，POI網(wǎng)絡M表示POI點序列 ， 令U={u1,u2,…,u|u|} 表示一組用戶，其中 |·| 為各自集合的基數(shù)。POI上下文信息可定義為一個三元組C=(D,G,T)， 其中矩陣D為用戶偏好，G表示POI的地理位置，T為用戶訪問POI的時間。則POI個性化推薦問題可表述為在POI網(wǎng)絡M中發(fā)現(xiàn)基于POI情景特征(G,T)、滿足用戶游玩偏好(D)的特定興趣點集合。

2.2 融合時間序列的用戶協(xié)同過濾推薦

表1 用戶-POI偏好矩陣

傳統(tǒng)的基于用戶的協(xié)同過濾算法利用余弦相似度計算用戶之間訪問POI的相似性，本文在余弦相似度中引入時間變量，不同用戶在相同時間訪問同一興趣點的頻率越高，用戶之間的相似度越高。其計算公式如式(1)所示

(1)

其中，sim(ui,t,uj) 表示用戶ui與uj在t時間段訪問POI的相似度，Num(ui,t,p) 表示用戶ui在t時間段訪問興趣點p的次數(shù)，Num(uj,t,p) 表示用戶uj在t時間段訪問興趣點p的次數(shù)。

令兩個時間序列之間的相似性為所有用戶Num(u)在任意兩時刻之間相似度的平均值，時間ti與tj的相似度sim(ti,tj) 如式(2)所示

(2)

為了解決融入時間因素后帶來的數(shù)據(jù)稀疏問題，增強時間序列的使用效率，提高POI的推薦效果，引入時間間隔d，使用平滑技術對時間相似度sim(ti,tj) 進行處理。用戶ui在ti時刻訪問興趣點p的預測評分score(ui,ti,p) 如式(3)所示

(3)

根據(jù)式(1)、式(2)、式(3)，得到融合時間序列的用戶之間相似度sim(ui,dt,uj) 如式(4)所示

(4)

融合時間序列基于用戶的協(xié)同過濾算法的評分公式如式(5)所示

(5)

2.3 基于POI流行度的推薦

實際生活中用戶訪問POI時，熱門POI是最先吸引用戶關注的，只有在熱度相對較高的POI中根據(jù)用戶的喜好推薦相應的POI，才能更好達到個性化推薦效果。因此，本文提出POI流行度的概念，根據(jù)某個POI的用戶訪問人數(shù)及用戶分享的POI的照片計算其受歡迎程度。某興趣點pi的流行度計算公式如下

(6)

2.4 基于POI地理距離的推薦

在POI推薦的眾多上下文信息中，POI的地理信息是進行推薦的核心內(nèi)容。由地理學第一定律(Tobler’s First Law of Geography)可知：任何事物都有相關性，POI間距越小，用戶訪問的概率越大[15]。而在用戶實際的訪問軌跡中，發(fā)現(xiàn)用戶對于POI位置的訪問服從冪律分布。冪律分布如式(7)所示

f(x)=a×x-k

(7)

其中，f(x) 為概率密度函數(shù)，x為變量，a、k為參數(shù)。

基于冪律分布“POI離用戶越近，用戶訪問概率越大；POI離用戶越遠，用戶訪問概率越小”的原則，將式(7)變?yōu)橹笖?shù)函數(shù)，得到式(8)如下

(8)

其中，simgeo(pi,pj) 表示興趣點pi與pj之間的相似性，lat、lng分別表示興趣點的緯度和經(jīng)度，δ為距離調(diào)節(jié)因子，調(diào)整興趣點間距離影響的大小。

2.5 基于POI最佳訪問時間的推薦

在用戶實際訪問POI的過程中，大部分POI都有著明確的訪問時間要求，并且不同的POI其訪問時間要求也不同。比如，某POI規(guī)定在9:00～17:00這一時間段內(nèi)用戶能夠訪問，超出這個時間段則禁止用戶訪問。因此，針對POI訪問時間的問題，本文提出了基于POI最佳訪問時間的推薦。

(9)

其中，tmax表示POI禁止用戶訪問時間，tmin表示POI允許用戶開始訪問的時間。

3 融合上下文信息的矩陣分解模型

POI的個性化推薦是一個受多種因素影響的復雜的決策過程，用戶的個性化偏好對于POI推薦的準確性起主導作用，但是用戶所處場景的情景信息也對POI推薦有著至關重要的影響。本節(jié)提出一個融合上下文信息的矩陣分解模型(context-aware matrix factorization model，CAMF)，在融合用戶偏好與情景信息對POI進行個性化推薦的同時，利用梯度下降法優(yōu)化CAMF模型參數(shù)，從而更好擬合用戶偏好和情景信息，提高POI推薦的準確性和個性化，為人們提供高效實時的智慧服務。

3.1 CAMF模型構(gòu)建

圖1為CAMF模型框架。CAMF模型將融合時間序列的協(xié)同過濾算法與基于POI流行度的推薦結(jié)合，體現(xiàn)用戶自身偏好，其計算公式如下

(10)

圖1 CAMF模型框架

根據(jù)用戶自身偏好和POI地理位置、訪問時間等情景信息，得到POI個性化評分如下

(11)

對于POI的個性化評分，利用CAMF模型對其進行求解，有效降低時間和空間上的復雜度。CAMF模型的目標函數(shù)如下

(12)

(13)

其中，yu,p為POI的真實評分。 Θ(U,P,T) 為正則表達式，防止目標函數(shù)L過擬合，U、P、T分別為用戶u、興趣點p和訪問時間t的隱含特征矩陣。

3.2 CAMF模型優(yōu)化

為了求得CAMF模型的最優(yōu)解，本文采用隨機梯度下降法來更新模型參數(shù)[16,17]。利用隨機梯度下降法更新模型參數(shù)的訓練過程如下

(14)

(15)

(16)

其中，γ是學習率，本文取0.001。

CAMF模型優(yōu)化過程中，首先要對隱藏特征矩陣U，P，T進行初始化，然后對POI的上下文信息進行建模，得到用戶偏好與POI情景信息的數(shù)學表示，最后利用矩陣分解模型融入用戶偏好與POI情景信息，并利用隨機梯度下降法得到最優(yōu)的模型參數(shù)，從而獲得POI的個性化推薦結(jié)果。CAMF模型具體的優(yōu)化過程如算法1所示。

算法1：CAMF優(yōu)化算法

輸入：POI數(shù)據(jù)集R，用戶-POI時間偏好矩陣D，照片數(shù)量N，學習率γ，調(diào)節(jié)因子α，β。

輸出：隱含特征矩陣U，P，T

(1)初始化隱含特征矩陣U，P，T

(2)Repeat

(3)//計算POI個性化評分

(4) for u from 1：|U| do

(5) for i from 1：|P| do

(6)scoreU(ui,ti,p)←式(5)

(7)pop(pi)←式(6)

(8)simgeo(pi,pj)←式(8)

(11)//更新模型參數(shù)

(12) update {U,P,T}

(13) end

(14) end

2.運用有效方法，銜接算理和算法。處理算理與算法的關系注意：一是算理與算法是計算教學中有機統(tǒng)一的整體，算理和算法并重；二是算理教學需借助直觀，引導學生經(jīng)歷自主探索、充分感悟的過程，要把握好算法提煉的時機和教學的“度”；三要防止算理與算法間出現(xiàn)斷痕或硬性對接，必要時進行指導。

(15)Until 模型收斂

(16)ReturnU，P，T

4 實驗與結(jié)果分析

4.1 實驗數(shù)據(jù)集與預處理

從去哪兒網(wǎng)攻略庫中爬取桂林的POI數(shù)據(jù)(http://travel.qunar.com/travelbook/list.htm?order=hot_heat)，數(shù)據(jù)集包括POI地理位置數(shù)據(jù)(經(jīng)緯度)、用戶分享的POI照片、用戶訪問時間數(shù)據(jù)和帶有情感色彩的POI評論信息。

為使實驗數(shù)據(jù)更加真實可靠，對實驗數(shù)據(jù)集進行以下預處理：①刪除分享照片數(shù)量少于5張和用戶評論數(shù)少于2條的用戶；②刪除與評論信息不一致的照片；③構(gòu)建用戶-POI時間偏好矩陣。預處理后的實驗數(shù)據(jù)集包含了2536位用戶訪問5676個POI分享的136 592條評論數(shù)據(jù)和252 327張照片，見表2。

4.2 推薦性能評價指標

本文采用推薦算法中最常用的評價指標準確率(precision@k)和召回率(recall@k)作為衡量算法推薦POI的性能。但是，僅根據(jù)準確率和召回率來判斷算法推薦性能的優(yōu)劣，具有一定的片面性。例如，推薦的POI集合中存在多個屬于同一類型的POI，即使推薦的準確率和召回率較高，用戶的個性化滿意程度也不會太高。因此，為了避免推薦的景點重復，提高用戶的個性化需求，在準確率和召回率之外，本文引入多樣性(diversity@k)對推薦POI的類型進行評價。推薦性能評價指標定義如下

(17)

表2 預處理后的實驗數(shù)據(jù)集

(18)

(19)

其中，pr表示推薦的POI集合，pu表示用戶訪問的POI集合。準確率和召回率的值越大，表明推薦的效果越好。typepr表示推薦POI集合中POI的種類，k為推薦POI集合中POI的數(shù)量。在準確率和召回率相差不大的情況下，POI多樣性值越大，推薦的效果越好，用戶對推薦的POI滿意度越高。

4.3 調(diào)節(jié)因子的確定

由4.1節(jié)可知，POI個性化評分是由基于用戶偏好與地理位置、訪問時間等情景信息的評分公式融合得到的，而這種評分公式融合的關鍵在于調(diào)節(jié)因子α和β的取值。圖2表示不同的α取值對基于用戶需求的評分值的影響。從圖2可知，α取值的變化對基于用戶需求的評分值產(chǎn)生的影響并沒有一定的規(guī)律性，不能準確判斷出α取值對評分影響的優(yōu)劣性。并且，若α取值過大，而用戶的相似性又很低時，就會產(chǎn)生過度偏置；若α取值過小，用戶對某POI分享的照片數(shù)量又很少時，也會對用戶相似性很高的用戶不公平。因此，本文采用式(20)對α的取值進行動態(tài)調(diào)整，以保證用戶需求的合理性

(20)

其中，Num(pi) 表示用戶訪問興趣點pi的次數(shù)，N(pi) 表示用戶分享的照片數(shù)量。

圖2 不同α值對POI得分的影響

調(diào)節(jié)因子β用來確定POI推薦時用戶偏好與情景信息的權重分配。在推薦個數(shù)、調(diào)節(jié)因子α不變的情況下，不同β值對推薦準確率與召回率的影響如圖3所示。

圖3 β值對推薦性能的影響

β=0時表示只考慮POI情景信息的推薦，β=1時表示只考慮用戶偏好的推薦。從圖3可以看出，當β從0到1逐漸變化時，POI推薦的準確率和召回率會逐漸升高，達到一個最高值后又逐漸降低，這說明進行POI推薦時綜合考慮用戶偏好與POI情景信息比單純只考慮其中一方面的推薦效果都好。隨著β值的不斷變化，推薦準確率與召回率的下降趨勢比上升趨勢要平緩一些，這說明隨著生活質(zhì)量的提高，用戶的個性化需求在POI推薦中占據(jù)著越來越重要的地位，且當β=0.6時，POI推薦的準確率與召回率達到最大值，即用戶偏好的權重值為0.6，POI情景信息的權重值為0.4時推薦效率最佳。

4.4 實驗結(jié)果

4.4.1 影響因素分析

本文提出的CAMF模型融合了用戶偏好、POI流行度、地理位置和時間等上下文信息，為了驗證本文提出的CAMF模型的先進性，詳細說明用戶偏好、POI流行度、地理位置和時間這4種因素對POI推薦性能的影響程度大小，設計了4個簡化的CAMF模型，分別移除其中一個影響因素對POI進行推薦，具體如下：

(1)CAMF-U：從CAMF模型中移除用戶偏好特征；

(2)CAMF-P：從CAMF模型中移除POI流行度特征；

(3)CAMF-E：從CAMF模型中移除地理位置特征；

(4)CAMF-T：從CAMF模型中移除時間特征。

將這4個模型與CAMF模型在數(shù)據(jù)集上進行實驗，設置POI推薦個數(shù)N為3、5、7、10，使用準確率和召回率作為評價指標來判斷各個模型的推薦效果。實驗結(jié)果如圖4和圖5所示。

圖4 不同上下文因素推薦準確率對比

圖5 不同上下文因素推薦召回率對比

從圖4和圖5可以看出，在POI推薦個數(shù)確定的情況下，CAMF模型的推薦效果好于其它4種模型，這說明融合用戶偏好和其它上下文信息有助于提高POI的推薦性能。并且，用戶偏好、POI流行度、地理位置和時間這4種因素對POI推薦的影響程度為：用戶偏好>地理位置>POI流行度>時間。具體地說，雖然地理位置、POI流行度等上下文信息都能影響用戶的簽到行為，提高POI的推薦效果，但隨著國民經(jīng)濟和通訊技術的飛速發(fā)展，用戶自身偏好已成為POI推薦的決定性因素，對POI推薦準確率和召回率的提高有著至關重要的影響，因此用戶偏好對POI推薦的影響最大。其次，由于POI推薦的特殊性，地理位置會極大限制用戶對于POI的訪問，用戶會傾向于訪問活動范圍之內(nèi)的POI，這也與地理學第一定律[15]得出的結(jié)論一致。由于用戶對于POI的訪問并沒有嚴格的時間限制，并且可能因為某些用戶故意錯開一些高峰的時間點，從而使CAMF模型學習時間特征時產(chǎn)生偏差，因此，POI時間因素對POI推薦性能的影響最小。

4.4.2 算法性能比較

為了更好地展現(xiàn)CAMF模型的推薦效果，將CAMF模型與下列主流POI的推薦算法進行對比：

(1)PMF[18]：根據(jù)用戶的評分數(shù)據(jù)，利用概率矩陣分解模型對興趣點進行推薦。

(2)Rank-geoFM[7]：同時考慮時間上下文和地理影響，并將其融入到排序的矩陣分解模型中對興趣點進行推薦。

(3)UTPG[11]：將基于用戶的協(xié)同過濾算法與地理位置和時間流行度相結(jié)合，預測POI的評分，從而提高POI推薦的準確性。

(4)GSRT[13]：綜合考慮了社交、內(nèi)容、地理和時間等多種POI上下文信息挖掘用戶行為偏好，并采用乘法法則進行融合從而對興趣點進行推薦。

本文數(shù)據(jù)集中用戶一天訪問的POI大多在10個以下，因此設定推薦POI個數(shù)N為3、5、7、10。圖6和圖7給出了5個算法在推薦不同數(shù)量POI時準確率和召回率的變化情況。整體而言，隨著POI推薦個數(shù)的增加，各種算法的推薦準確率會降低，這是因為POI推薦數(shù)量的增多會增加用戶與時間的復雜性和POI地理位置的多樣性；但POI推薦的召回率會提高，這是因為雖然POI推薦數(shù)量的增多了，但用戶訪問過POI的數(shù)量卻沒變。

圖6 不同算法準確率對比

從圖6和圖7可以看出，在推薦POI個數(shù)確定的情況下，PMF模型的推薦準確率和召回率都最低，因為其只通過用戶的評分數(shù)據(jù)進行POI推薦，沒有充分考慮上下文信息。Rank-geoFM模型融合了時間上下文和地理位置影響，但由于未充分學習用戶偏好，導致其推薦效果不佳。GSRT模型融合了社交、內(nèi)容、地理和時間等多種POI上下文信息挖掘用戶行為偏好，重現(xiàn)了用戶訪問POI時的情景，但其采用乘法法則對上下文信息進行融合，限制了其推薦性能。UTPG模型不僅融合了時間上下文和地理影響，還基于用戶的協(xié)同過濾算法來學習用戶和POI的特征矩陣，充分考慮了用戶偏好在POI推薦中的影響。因此，UTPG模型相對于PMF、Rank-geoFM和GSRT模型，有著更好的推薦效果。

本文提出的CAMF模型無論在準確率還是召回率上都高于其它的POI推薦算法，并且在推薦個數(shù)逐漸增多時，其優(yōu)勢更加明顯。這是因為CAMF模型成功地利用矩陣分解模型將用戶的個性化偏好和地理位置、訪問時間等情景因素結(jié)合起來，緩解了數(shù)據(jù)稀疏性，能夠捕捉到興趣點靜特征之間的潛在關聯(lián)，使得為用戶推薦的POI更加的科學準確。

圖7 不同算法召回率對比

4.4.3 推薦結(jié)果多樣性評估

為了對多樣性評估式(19)進行說明，本文假定從桂林火車站(25.2670,110.2898)出發(fā)，設置推薦個數(shù)k=5，距離調(diào)節(jié)因子δ=0.7，β=0.6。根據(jù)表2中的實驗數(shù)據(jù)，得到各POI的類別和評分見表3。

表3 POI類別與得分

根據(jù)為用戶推薦得分最高的POI的算法規(guī)則，可以得到為用戶u1推薦的POI集合為G1={獨秀峰王城景區(qū)，漓江，蘆笛巖，銀子巖，陽朔西街}，G2={獨秀峰王城景區(qū)，漓江，銀子巖，圖騰古道，陽朔西街}。 從表3可知，這兩個POI集合的評分只相差0.0095分，很難通過得分的高低判斷哪個POI集合更能符合用戶需求，因此需要對POI集合進行多樣性分析。根據(jù)POI多樣性計算公式(19)，得到POI集合的多樣性得分如下：

diversity(G1)@5=-(1/5×log51/5+1/5×log51/5+2/5×log52/5+1/5×log51/5)=0.8277

diversity(G2)@5=-(1/5×log51/5+1/5×log51/5+1/5×log51/5+1/5×log51/5+1/5×log51/5)=1

因為diversity(G2)@5>diversity(G1)@5， 所以我們認為第二個POI集合更符合用戶的個性化需求，為用戶推薦的POI集合為G2={獨秀峰王城景區(qū)，漓江，銀子巖，圖騰古道，陽朔西街}。

5 結(jié)束語

本文提出一種基于矩陣分解的上下文感知興趣點推薦方法，在基于用戶的協(xié)同過濾算法中融入時間序列，有效緩解了數(shù)據(jù)的稀疏性。通過利用CAMF模型融合不同的上下文信息，能更好建模用戶的個人偏好和訪問情景，并利用隨機梯度下降法更新CAMF的模型參數(shù)，提高了模型的運行效率。最后，在去哪兒網(wǎng)獲取的數(shù)據(jù)集中進行了實驗，結(jié)果表明本文提出模型比其它主流的POI推薦算法有著更高的準確率和召回率，能滿足用戶的不同需求。在未來的工作中，將對上下文信息的提取與融合做進一步研究，以便提高推薦的準確性與滿意度。