基于上下文感知和個(gè)性化度量嵌入的下一個(gè)興趣點(diǎn)推薦*

鮮學(xué)豐,陳曉杰,趙朋朋,楊元峰 ,Victor S.Sheng

(1.江蘇省現(xiàn)代企業(yè)信息化應(yīng)用支撐軟件工程技術(shù)研發(fā)中心，江蘇 蘇州 215104; 2.蘇州大學(xué)智能信息處理及應(yīng)用研究所，江蘇 蘇州 215006; 3.阿肯色中央大學(xué)計(jì)算機(jī)科學(xué)系,康威 72035)

1 引言

隨著全球定位系統(tǒng)和無(wú)線通信網(wǎng)絡(luò)等基礎(chǔ)設(shè)施的飛速發(fā)展以及手持、車載無(wú)線通信定位設(shè)備的廣泛應(yīng)用，特別是眾多移動(dòng)社交網(wǎng)絡(luò)的位置簽到、位置共享及位置標(biāo)識(shí)等功能的應(yīng)用普及，位置服務(wù)與社交網(wǎng)絡(luò)逐漸融合，形成了基于位置的社交網(wǎng)絡(luò)LBSN(Location-Based Social Networks)。例如，F(xiàn)oursquare、Gowalla和Yelp 等社交應(yīng)用通過(guò)移動(dòng)用戶的地理位置推行的簽到功能，把線上虛擬社會(huì)與線下真實(shí)世界聯(lián)結(jié)在一起，實(shí)現(xiàn)了用戶位置定位的同時(shí)，還實(shí)現(xiàn)了位置信息在虛擬網(wǎng)絡(luò)世界的共享與傳播，從而衍生出多種多樣的位置服務(wù)。

目前個(gè)性化推薦技術(shù)得到工業(yè)界和學(xué)術(shù)界的廣泛關(guān)注,在多個(gè)領(lǐng)域得到廣泛應(yīng)用，比如電子商務(wù)網(wǎng)站為用戶推薦商品，視頻網(wǎng)站為用戶推薦電影。日益成熟的推薦技術(shù)較好地解決了互聯(lián)網(wǎng)信息過(guò)載的問(wèn)題。在基于位置的社交網(wǎng)絡(luò)中，興趣點(diǎn)推薦作為熱門的研究課題，旨在為用戶推薦興趣點(diǎn)，方便用戶出行生活，并且提升平臺(tái)的用戶體驗(yàn)[1 - 6]。

在興趣點(diǎn)推薦的研究工作中，用戶個(gè)人偏好對(duì)推薦的結(jié)果起了主導(dǎo)作用。在個(gè)性化推薦領(lǐng)域，用戶個(gè)人偏好成為了必不可少的因素[7]。一些研究工作表明，用戶的時(shí)序性簽到行為可以反映出人類活動(dòng)的時(shí)序性模式[8]。在研究工作中得出的個(gè)性化的馬爾科夫鏈分解FPMC(Factorizing Personalized Markov Chains)方法[9]，主要使用矩陣分解的方法。然而，這并沒(méi)有挖掘出興趣點(diǎn)之間的潛在聯(lián)系。在下一個(gè)興趣點(diǎn)推薦的研究中，如何在一階馬爾科夫鏈模型中獲取用戶簽到記錄之間的轉(zhuǎn)移概率成為全新的挑戰(zhàn)。由于數(shù)據(jù)的稀疏性，馬爾科夫鏈模型難以評(píng)估未被觀察到的數(shù)據(jù)間的轉(zhuǎn)移概率。為了有效解決這個(gè)問(wèn)題，進(jìn)一步的研究提出了個(gè)性化排名度量嵌入法PRME(Personalized Ranking Metric Embedding)[10]，通過(guò)將每一個(gè)興趣點(diǎn)映射到低維空間計(jì)算興趣點(diǎn)之間的轉(zhuǎn)移概率。PRME模型結(jié)合考慮了用戶偏好和時(shí)序性轉(zhuǎn)移兩個(gè)影響因素。和FPMC模型相比，PRME模型更好地解決了數(shù)據(jù)稀疏性帶來(lái)的問(wèn)題。然而，PRME模型沒(méi)有深度挖掘簽到行為的上下文情境信息來(lái)進(jìn)行推薦。

然而，在大多數(shù)興趣點(diǎn)推薦的研究工作中，用戶訪問(wèn)的周期性習(xí)慣和伴隨著用戶偏好的上下文情境信息還沒(méi)有被深度挖掘出來(lái)。上下文情境信息包括每天的時(shí)間段、每周的星期、當(dāng)前簽到興趣點(diǎn)的分類等。例如，在工作日，人們通常習(xí)慣于在上班途中光顧一家咖啡店，我們可以把這個(gè)看作是一種周期性的行為習(xí)慣。據(jù)分析，下一個(gè)興趣點(diǎn)和當(dāng)前興趣點(diǎn)息息相關(guān)。例如，通常在健身結(jié)束后，人們傾向于選擇去餐廳補(bǔ)充高蛋白食物，而不是去酒吧。本文統(tǒng)計(jì)并分析了Foursquare中來(lái)自日本東京的用戶簽到記錄，圖1描述了4種熱門簽到地點(diǎn)類別在一天各個(gè)時(shí)間點(diǎn)的簽到幾率，圖2描述了4種熱門簽到地點(diǎn)類別在一周各天的簽到幾率?？梢园l(fā)現(xiàn)，按類別劃分用戶的活動(dòng)具有周期性。圖1中屬于Nightlife Spot類別的簽到通常發(fā)生在晚上十點(diǎn)到凌晨四點(diǎn)之間，而在白天則很少。圖2中屬于School類別的簽到通常發(fā)生在工作日，周末的幾率則很小。根據(jù)以上分析可以得出，用戶的周期性行為模式對(duì)下一個(gè)興趣點(diǎn)推薦有很大影響。

Figure 1 Periodic analysis of one day sign in behavior圖1 一天簽到行為周期性分析

Figure 2 Periodic analysis of one week sign in behavior圖2 一周簽到行為周期性分析

基于以上考慮，針對(duì)用戶簽到的數(shù)據(jù)稀疏性問(wèn)題，本文將用戶周期性行為模式歸結(jié)為上下文情境信息，提出了一種個(gè)性化度量嵌入的推薦算法，同時(shí)將用戶簽到的上下文情境信息考慮進(jìn)來(lái)，從而豐富有效數(shù)據(jù)，緩解數(shù)據(jù)稀疏性問(wèn)題，提高推薦的準(zhǔn)確率，并且進(jìn)一步優(yōu)化算法，降低時(shí)間復(fù)雜度。本文考慮的上下文情境信息包括每天的時(shí)間段、每周的星期、當(dāng)前簽到興趣點(diǎn)的分類等。通過(guò)將每一個(gè)興趣點(diǎn)映射到低維隱式空間，進(jìn)一步使用度量嵌入算法來(lái)計(jì)算興趣點(diǎn)之間的轉(zhuǎn)移概率。然后，使用度量排序嵌入的算法將隱式空間的候選推薦興趣點(diǎn)進(jìn)行排序。本文提出了基于上下文感知的個(gè)性化度量嵌入模型CPME(Context-aware Personalized Metric Embedding)，結(jié)合考慮了時(shí)序性影響、用戶個(gè)人偏好和上下文情境信息。最后，基于用戶更偏向于訪問(wèn)離自己更近的興趣點(diǎn)的事實(shí)，將地理影響因素考慮在內(nèi)，進(jìn)而提出了CPME-G(Context-aware Personalized Metric Embedding-Geo)模型。

本文第2節(jié)介紹興趣點(diǎn)研究的相關(guān)工作；在第3節(jié)中，將對(duì)下一個(gè)興趣點(diǎn)推薦進(jìn)行問(wèn)題定義；第4節(jié)詳細(xì)解釋所提出的模型；第5節(jié)深入剖析所提出模型的參數(shù)訓(xùn)練；在第6節(jié)中，本文將展示實(shí)驗(yàn)結(jié)果；最后，將在第7節(jié)中總結(jié)本文的工作。

2 相關(guān)工作

興趣點(diǎn)推薦所采用的數(shù)據(jù)集可以分為基于GPS的軌跡數(shù)據(jù)和LSBN中的簽到數(shù)據(jù)。利用基于GPS軌跡數(shù)據(jù)進(jìn)行推薦，其首要工作就是從軌跡數(shù)據(jù)中挖掘出興趣點(diǎn)并進(jìn)行推薦研究[11]。LSBN中的用戶簽到數(shù)據(jù)不僅包含興趣點(diǎn)語(yǔ)義描述信息，還包含興趣點(diǎn)地理位置信息，同時(shí)還具有豐富的用戶社交網(wǎng)絡(luò)信息，因此基于位置的興趣點(diǎn)推薦研究受到研究者的廣泛關(guān)注。興趣點(diǎn)推薦至今已取得不少成果，可以分為以下四類：

(1)基于地理位置影響因素的推薦，文獻(xiàn)[12]發(fā)掘了簽到記錄中的“地理聚類現(xiàn)象”，用來(lái)提高興趣點(diǎn)推薦的準(zhǔn)確率。(2)基于時(shí)序影響因素的推薦，文獻(xiàn)[13]充分利用了時(shí)序影響因素來(lái)提高興趣點(diǎn)推薦的性能。(3)基于社交關(guān)系因素的推薦，文獻(xiàn)[14]提出了一種新的推薦框架SoDimRec，它結(jié)合了社交關(guān)系的非均勻性和弱關(guān)系依賴來(lái)進(jìn)行推薦。(4)基于內(nèi)容的推薦，文獻(xiàn)[15]提出了一種考慮內(nèi)容的貝葉斯協(xié)同過(guò)濾框架，同時(shí)給出了一種可擴(kuò)展的優(yōu)化算法來(lái)學(xué)習(xí)潛在參數(shù)和超參數(shù)，特別是針對(duì)隱式反饋的挖掘。

隨著興趣點(diǎn)推薦的熱度上升，基于序列的下一個(gè)興趣點(diǎn)推薦已成為興趣點(diǎn)推薦的熱點(diǎn)研究問(wèn)題。文獻(xiàn)[16]提出了一個(gè)統(tǒng)一的基于張量的隱式模型，為了更好地進(jìn)行下一個(gè)興趣點(diǎn)的個(gè)性化推薦，它將潛在可被觀察的連續(xù)簽到行為融合到一種用戶的隱式傾向中。詞嵌入和成分嵌入模型在自然語(yǔ)言處理領(lǐng)域已經(jīng)取得了很好的效果。有研究者將度量嵌入的算法應(yīng)用在下一個(gè)興趣點(diǎn)推薦領(lǐng)域。為了解決數(shù)據(jù)稀疏性問(wèn)題，文獻(xiàn)[10]使用了度量嵌入算法并提出了個(gè)性化排名度量嵌入模型。文獻(xiàn)[17]提出了基于圖的度量嵌入模型來(lái)表示低維隱式空間的興趣點(diǎn)，并且他們提出了一種事件衰減的方法來(lái)挖掘表示動(dòng)態(tài)的用戶偏好。為了提取關(guān)系特征，文獻(xiàn)[18]提出了多特征成分嵌入模型。在上述相關(guān)工作的基礎(chǔ)上，本文進(jìn)一步挖掘了用戶行為的周期性和伴隨著用戶偏好的上下文情境信息，并采用度量嵌入的方法來(lái)進(jìn)行下一個(gè)興趣點(diǎn)推薦。

3 問(wèn)題定義

下一個(gè)興趣點(diǎn)推薦的目的是根據(jù)用戶的當(dāng)前地點(diǎn)推薦下一個(gè)興趣點(diǎn)。當(dāng)兩個(gè)連續(xù)的簽到點(diǎn)發(fā)生在一個(gè)很短的時(shí)間段內(nèi)時(shí)，他們之間就存在馬爾科夫鏈的性質(zhì)[7]。馬爾科夫鏈描述了從一個(gè)狀態(tài)轉(zhuǎn)換到另一個(gè)狀態(tài)的隨機(jī)過(guò)程。這個(gè)過(guò)程具有無(wú)記憶性的特點(diǎn)，也就是說(shuō)，下一個(gè)狀態(tài)的概率分布只能由當(dāng)前狀態(tài)決定，在時(shí)間序列中它前面的時(shí)間均與之無(wú)關(guān)?？梢缘贸霎?dāng)需要考慮一個(gè)短時(shí)間段內(nèi)的興趣點(diǎn)轉(zhuǎn)移關(guān)系時(shí)，意味著下一個(gè)興趣點(diǎn)受當(dāng)前興趣點(diǎn)的影響。本文研究的下一個(gè)興趣點(diǎn)推薦是在過(guò)濾掉用戶訪問(wèn)過(guò)的興趣點(diǎn)的前提下給用戶推薦新的興趣點(diǎn)，問(wèn)題定義如下：

給定一個(gè)LBSN的用戶集合U={u1,u2,…,ui,…,uX}，以及地理位置點(diǎn)的集合L={l1,l2,…,lj,…,lY},即興趣點(diǎn)集合。其中X和Y分別是用戶的個(gè)數(shù)和興趣點(diǎn)的個(gè)數(shù)。每個(gè)地理位置點(diǎn)可以用〈longitude,latitude〉來(lái)描述具體定位。給定一個(gè)用戶的當(dāng)前興趣點(diǎn)lc以及歷史訪問(wèn)記錄Lu，下一個(gè)興趣點(diǎn)推薦問(wèn)題就是基于用戶的當(dāng)前興趣點(diǎn)lc給用戶u推薦一系列將要訪問(wèn)的下一個(gè)興趣點(diǎn)集合Recu,lc，Recu,lc={l∈LLu}。文中涉及符號(hào)的定義如表1所示。

Table 1 Symbol definition表1 符號(hào)定義

4 基于上下文感知的個(gè)性化度量嵌入推薦方法

4.1 度量排序嵌入

本文采用興趣點(diǎn)之間的轉(zhuǎn)移概率來(lái)描述當(dāng)前興趣點(diǎn)對(duì)下一個(gè)興趣點(diǎn)的影響，由于數(shù)據(jù)稀疏性對(duì)計(jì)算興趣點(diǎn)之間的轉(zhuǎn)移概率帶來(lái)了巨大的困擾，基于度量嵌入的方法很好地緩解了該問(wèn)題。該方法將每一個(gè)興趣點(diǎn)映射到一個(gè)低維空間，通過(guò)計(jì)算興趣點(diǎn)之間的歐氏距離來(lái)描述轉(zhuǎn)移概率，本文采用的歐氏距離是業(yè)界最常用的度量方式。兩個(gè)興趣點(diǎn)之間的距離越近，說(shuō)明它們之間的轉(zhuǎn)移概率越高。當(dāng)所有的興趣點(diǎn)都嵌入到低維空間中后，可以挖掘出未被觀察到的興趣點(diǎn)之間的轉(zhuǎn)移概率。在度量嵌入模型中，每一個(gè)興趣點(diǎn)在一個(gè)K維空間都存在一個(gè)位置E(l)。一對(duì)候選興趣點(diǎn)〈li,lj〉之間的轉(zhuǎn)移概率的定義如下：

(1)

度量嵌入的方法可以很好地挖掘興趣點(diǎn)間的關(guān)系，并且將這些關(guān)系通過(guò)距離展現(xiàn)出來(lái)。因此，基于度量嵌入的方法在模擬時(shí)序關(guān)系的轉(zhuǎn)移上有很大的優(yōu)勢(shì)。所謂興趣點(diǎn)間的聯(lián)系，即：假設(shè)有三個(gè)連續(xù)的簽到點(diǎn)li，lj和lk。依據(jù)馬爾科夫鏈描述的過(guò)程，可以得到兩組可觀察到的序列l(wèi)i→lj和lj→lk。不可避免地，li對(duì)lk也會(huì)產(chǎn)生影響，即：li→lk是一個(gè)隱式的轉(zhuǎn)移關(guān)系。如果這個(gè)轉(zhuǎn)移關(guān)系更緊密，那么在低維空間上E(li)和E(lk)之間的距離會(huì)更加接近它們和E(lj)之間的距離。

對(duì)于單獨(dú)一個(gè)用戶，他所有的個(gè)人簽到記錄所涉及的簽到點(diǎn)總是有限的，即他不可能對(duì)所有的興趣點(diǎn)進(jìn)行過(guò)訪問(wèn)，換句話說(shuō)，從任意一個(gè)用戶獲得的可觀察到的數(shù)據(jù)是稀疏的。需要更充分地利用這些已被觀察到的數(shù)據(jù)來(lái)進(jìn)行參數(shù)學(xué)習(xí)。相比于未觀察到的興趣點(diǎn)，已觀察到的下一個(gè)興趣點(diǎn)和當(dāng)前興趣點(diǎn)更接近。例如，存在一個(gè)已被觀察到的轉(zhuǎn)移關(guān)系lc→li和一個(gè)未被觀察到的轉(zhuǎn)移關(guān)系lc→lj，從當(dāng)前興趣點(diǎn)lc轉(zhuǎn)移到興趣點(diǎn)li比轉(zhuǎn)移到興趣點(diǎn)lj概率更大。我們可以得出以下排序：

(2)

本文將兩個(gè)興趣點(diǎn)之間的歐氏距離表示為‖E(li)-E(lj)‖2，并縮寫(xiě)為Dli,lj。對(duì)興趣點(diǎn)的排序方法如下：

?

e-‖E(li)-E(lc)‖2>e-‖E(lj)-E(lc)‖2?

‖E(li)-E(lc)‖2<‖E(lj)-E(lc)‖2?

Dlc,lj-Dlc,li>0

(3)

4.2 上下文感知度量排序嵌入

4.2.1 用戶偏好空間

4.2.2 時(shí)序關(guān)系空間

4.2.3 上下文感知空間

Table 2 Spatial time segment classificationdescription to Time-of-Day space表2 Time-of-Day空間時(shí)間段分類描述

Figure 3 Points of interest map to Time-of-Day space圖3 興趣點(diǎn)映射到Time-of-Day空間

Figure 4 Points of interest map to Day-of-Week space圖4 興趣點(diǎn)映射到Day-of-Week空間

Figure 5 Points of interest map to Category space圖5 興趣點(diǎn)映射到Category空間

根據(jù)以上分析，本文將用戶個(gè)人偏好、時(shí)序轉(zhuǎn)移關(guān)系和上下文感知信息綜合考慮來(lái)衡量一個(gè)候選興趣點(diǎn)的轉(zhuǎn)移概率。給定一個(gè)用戶u以及他的當(dāng)前位置lc，我們使用線性插值函數(shù)來(lái)衡量這三個(gè)度量。最后，綜合距離的定義由以下公式給出：

(4)

其中a,b,c,d,e分別代表不同隱式空間上對(duì)應(yīng)的歐氏距離的權(quán)重，且滿足a,b,c,d,e∈[0,1]以及a+b+c+d+e=1。

通過(guò)把每一個(gè)興趣點(diǎn)映射到創(chuàng)建的三個(gè)空間：Time-of-Day空間、Day-of-Week空間和Category空間，我們將每一個(gè)興趣點(diǎn)按組分配到對(duì)應(yīng)的具體空間。根據(jù)第3節(jié)的論述，如果兩個(gè)連續(xù)興趣點(diǎn)之間的時(shí)間差小于τ，時(shí)序性所帶來(lái)的影響就應(yīng)當(dāng)被考慮。如果兩個(gè)連續(xù)簽到點(diǎn)的時(shí)間差很大，就認(rèn)為他們?cè)跁r(shí)序性上相互之間不受影響，因此就僅僅考慮用戶偏好帶來(lái)的影響。根據(jù)以上分析，本文給出以下函數(shù)：

對(duì)于l,lc∈LT,W，且a,b,c,d,e∈[0,1],a+b+c+d+e=1，

(5)

4.2.4 結(jié)合地理影響因素

據(jù)分析，當(dāng)給定當(dāng)前的位置時(shí)，用戶偏向于訪問(wèn)更近的興趣點(diǎn)而不是離他們更遠(yuǎn)的興趣點(diǎn)。因此，地理位置的遠(yuǎn)近對(duì)用戶的訪問(wèn)行為有很大的影響。根據(jù)這些分析，本文考慮了地理影響因素，提出了CPME-G模型，該模型是在CPME的基礎(chǔ)上加入了地理影響因素。本文引入一個(gè)變量來(lái)描述地理影響因素的權(quán)重并通過(guò)地理位置的經(jīng)緯度來(lái)描述地理距離。對(duì)于給定一對(duì)興趣點(diǎn)之間的地理距離dlc,l和權(quán)重函數(shù)g(lc,l)={(1+dlc,l)0.25}，它們之間的混合度量距離就可以表示為Du,lc,l·wlc,l。當(dāng)興趣點(diǎn)之間的距離很小時(shí)，它們之間的混合度量距離也會(huì)很小，這意味著這個(gè)興趣點(diǎn)很有可能被推薦。最后，結(jié)合地理影響因素的度量可以被定義為：

對(duì)于l,lc∈LT,W，且a,b,c,d,e∈[0,1]，a+b+c+d+e=1,

(6)

5 參數(shù)學(xué)習(xí)

本文使用一種近似于貝葉斯個(gè)性化排名的方法BPR(Baysian Personalized Ranking)[19]，假設(shè)用戶和他們的簽到歷史記錄是獨(dú)立的，我們可以用極大后驗(yàn)假設(shè)來(lái)評(píng)估本文提出的基于上下文感知個(gè)性化度量嵌入模型：

(7)

其中Θ={ES(L),EP(L),EP(U),EC(L)}是參數(shù)的集合。

類似于文獻(xiàn)[12],本文使用邏輯回歸函數(shù)σ(z)=1/(1+e-z)進(jìn)行歸一化操作，得到的排名概率可表示為：

P(>u,lc|Θ)=

P((Du,lc,lj-Du,lc,li)>0|Θ)=σ(Du,lc,lj-Du,lc,li)

(8)

假設(shè)模型參數(shù)服從高斯分布，那么可以得到最后的目標(biāo)函數(shù)，λ是一個(gè)正則項(xiàng)的參數(shù)：

Du,lc,li))-λ‖Θ‖2

(9)

緊接著B(niǎo)PR方法，本文使用隨機(jī)梯度下降的方法來(lái)更新參數(shù)。根據(jù)歷史簽到記錄，我們可以獲得一組可被觀察到的數(shù)據(jù)〈u,lc,li〉，其中l(wèi)c是指用戶u的當(dāng)前位置，li是下一個(gè)興趣點(diǎn)。對(duì)于每一組觀察到的數(shù)據(jù)，本文通過(guò)隨機(jī)生成一個(gè)興趣點(diǎn)lj，并且它滿足不在用戶的歷史記錄中。給定一組訓(xùn)練數(shù)據(jù)〈u,lc,li,lj〉，那么這個(gè)更新的過(guò)程可以被描述為：

(10)

其中z=Du,lc,lj-Du,lc,li，γ是學(xué)習(xí)速率因子。

本文將提出的CPME模型的學(xué)習(xí)算法總結(jié)在算法1 中。該算法的描述如下：首先，初始化模型參數(shù)，使其服從高斯分布(Line 1)。然后從訓(xùn)練集中讀取并存儲(chǔ)〈u,lc,li〉，其中l(wèi),lc∈LT,W(Line 3)。對(duì)于每一個(gè)訪問(wèn)過(guò)的元組〈u,lc,li〉，本文從興趣點(diǎn)集中隨機(jī)產(chǎn)生一個(gè)興趣點(diǎn)lj，且滿足用戶u沒(méi)有訪問(wèn)過(guò)這個(gè)興趣點(diǎn)(Line 4)。接著，算法將Δ(lc,li)的時(shí)間差和設(shè)定的時(shí)間閾值τ進(jìn)行比較。如果Δ(lc,li)<τ，那么就更新這些參數(shù)(Line 6～Line 10)。本算法綜合考慮了用戶個(gè)人偏好、時(shí)序轉(zhuǎn)移關(guān)系和上下文感知。當(dāng)我們要訓(xùn)練CPME-G模型時(shí)，需加上地理影響權(quán)重g(lc,l)={(1+dlc,l)0.25}，并使用相似的算法進(jìn)行參數(shù)學(xué)習(xí)?？偨Y(jié)發(fā)現(xiàn)，本算法的時(shí)間復(fù)雜度為O(KI|H|)，其中，K是空間維數(shù)，I是迭代訓(xùn)練的次數(shù)，并且H是觀察到的數(shù)據(jù)的集合。

算法1基于上下文感知個(gè)性化度量嵌入算法

輸入：簽到數(shù)據(jù)集H，學(xué)習(xí)速率因子γ，權(quán)重a,b,c,d和e，時(shí)間閾值τ。

輸出：模型參數(shù)Θ=ES(L),EP(L),EP(U),ET(L),EW(L),EC(L)。

1. 初始化Θ使其服從高斯分布N(0,0.01);

2. repeat

3. for Each Observation 〈u,lc,li〉,l,lc∈LT,Wdo

4. Randomly generate an unobserved POIlj

5. ifΔ(lc,li)<τthen

6. UpdateEP(u),EP(li),EP(lj);

7. UpdateES(lc),ES(li),ES(lj);

8. UpdateET(lc),ET(li),ET(lj);

9. UpdateEW(lc),EW(li),EW(lj);

10. UpdateEC(lc),EC(li),EC(lj);

11. end if

12. ifΔ(lc,li) then

13. UpdateEP(u),EP(li),EP(lj);

14. end if

15. end for

16. until convergence;

17. returnΘ=ES(L),EP(L),EP(U),ET(L),EW(L),EC(L).

6 實(shí)驗(yàn)設(shè)計(jì)

6.1 數(shù)據(jù)集

本實(shí)驗(yàn)使用的數(shù)據(jù)集是來(lái)源于Foursquare的用戶真實(shí)簽到記錄，分別為紐約和東京兩個(gè)城市。該數(shù)據(jù)集記錄了從2012年4月到2013年2月的10個(gè)月間的用戶簽到記錄，該數(shù)據(jù)集被使用于文獻(xiàn)[16]的實(shí)驗(yàn)驗(yàn)證。本實(shí)驗(yàn)通過(guò)以下步驟對(duì)數(shù)據(jù)集進(jìn)行預(yù)處理。首先過(guò)濾掉無(wú)效的簽到數(shù)據(jù)，并且選取了在紐約和東京兩個(gè)城市間總簽到個(gè)數(shù)不少于90次的用戶簽到記錄。經(jīng)預(yù)處理后統(tǒng)計(jì)如表3所示，紐約的數(shù)據(jù)集中共有1 083個(gè)用戶和38 471個(gè)興趣點(diǎn)，總簽到記錄有227 482條。東京的數(shù)據(jù)集中有2 293個(gè)用戶和61 886個(gè)興趣點(diǎn)，總簽到記錄有573 703條。紐約和東京的數(shù)據(jù)集密度分別為0.545 861%和0.404 288%。Foursquare上的數(shù)據(jù)集類別可以分為9個(gè)根類別和417個(gè)子類別，9個(gè)根類別主要包括餐廳、車站、辦公、戶外運(yùn)動(dòng)等等。根據(jù)這10個(gè)月的簽到數(shù)據(jù)，實(shí)驗(yàn)將前7個(gè)月的簽到記錄作為訓(xùn)練集，第8個(gè)月作為驗(yàn)證集來(lái)調(diào)整參數(shù)，并且將最后2個(gè)月作為測(cè)試集。根據(jù)驗(yàn)證集，實(shí)驗(yàn)得出空間維數(shù)K為60，標(biāo)準(zhǔn)化因子λ為0.03，以及權(quán)重a,b,c,d和e的取值分別為0.2，0.4，0.05，0.05和0.3。

Table 3 Foursquare datasets description表3 Foursquare數(shù)據(jù)集描述

6.2 評(píng)估指標(biāo)

根據(jù)每一個(gè)用戶的簽到行為分析，給出一個(gè)按興趣點(diǎn)轉(zhuǎn)移概率從高到低進(jìn)行排序的推薦列表Recu,N，N表示推薦列表中所推薦的興趣點(diǎn)個(gè)數(shù)。為了評(píng)價(jià)本文提出的下一個(gè)興趣點(diǎn)推薦算法的效果，我們選用推薦問(wèn)題通用的指標(biāo)：準(zhǔn)確率、召回率和F1-score。準(zhǔn)確率指推薦結(jié)果中用戶將來(lái)真正訪問(wèn)的數(shù)量占推薦總數(shù)的比例，反映了推薦的準(zhǔn)確性。召回率指推薦結(jié)果中用戶將來(lái)真正訪問(wèn)數(shù)量占用戶將來(lái)訪問(wèn)興趣點(diǎn)總量的比例，反映了推薦的全面性。F1-score是準(zhǔn)確率和召回率的綜合，F(xiàn)1-score越高，說(shuō)明推薦模型越穩(wěn)健。對(duì)用戶進(jìn)行下一個(gè)興趣點(diǎn)推薦的準(zhǔn)確率和召回率定義如下：

(11)

(12)

(13)

其中，Lvisited表示用戶u訪問(wèn)過(guò)的興趣點(diǎn)集合，|Lvisited|表示用戶u訪問(wèn)過(guò)的興趣點(diǎn)的總數(shù)，|U|表示用戶的總數(shù)，N表示下一個(gè)興趣點(diǎn)推薦列表中所推薦的興趣點(diǎn)個(gè)數(shù)。準(zhǔn)確率和召回率相互制約，F(xiàn)1-score總體評(píng)估，綜合利用三者可以對(duì)預(yù)測(cè)結(jié)果做出客觀的評(píng)價(jià)。

6.3 性能與實(shí)驗(yàn)對(duì)比

本文主要將提出的模型CPME和PRME進(jìn)行比較。CPME和PRME的性能比較結(jié)果如圖7～圖9所示。從圖中可以看出，我們提出的模型比PRME性能更優(yōu)，性能提高了12.35%左右。

圖6描述了不同時(shí)間閾值對(duì)紐約和東京數(shù)據(jù)集TOP10準(zhǔn)確率的影響，其中τ分別為3 h，6 h，12 h和24 h。CPME和CPME-G的準(zhǔn)確率高于PRME和PRME-G。

Figure 6 Precision of the two city datasets varies with time threshold圖6 兩個(gè)城市數(shù)據(jù)集的準(zhǔn)確率隨時(shí)間閾值變化的結(jié)果

同時(shí)，這些方法的準(zhǔn)確率都隨著τ的增大而降低，分析得出：時(shí)間閾值越大，興趣點(diǎn)之間的時(shí)序轉(zhuǎn)移關(guān)系就越小。統(tǒng)籌權(quán)衡用戶個(gè)人偏好、時(shí)序轉(zhuǎn)移關(guān)系、上下文感知和地理位置四個(gè)因素的影響，實(shí)驗(yàn)將時(shí)間閾值設(shè)定為6 h。由圖7和圖8可知，無(wú)論N取何值，本文所提出的CPME在2個(gè)數(shù)據(jù)集上的準(zhǔn)確率和召回率普遍優(yōu)于PRME的。同時(shí)，CPME和PRME模型性能都遠(yuǎn)高于PMF(Probabilistic Matrix Factorization)。由圖7～圖9可知，當(dāng)在同一個(gè)N下進(jìn)行比較時(shí)，考慮的上下文信息種類越多，推薦精度越高。同時(shí)我們發(fā)現(xiàn)，不同上下文信息種類之間的組合不同，實(shí)驗(yàn)的結(jié)果也不同，圖例中的W(Day-of-Week)、T(Time-of-Day)、C(Catagory)、W+T、C+W、T+C、T+W+C是指CPME考慮的上下文信息的種類及組合。由于Time-of-Day對(duì)一天中的簽到點(diǎn)的分類更為精細(xì)，而Day-of-Week把一周七天分為工作日和周末兩大類導(dǎo)致數(shù)據(jù)整體稀疏性緩解，可以發(fā)現(xiàn)單獨(dú)考慮Time-of-Day比單獨(dú)考慮Day-of-Week的效果更好。實(shí)驗(yàn)通過(guò)考慮Time-of-Day和Day-of-Week，同時(shí)加入興趣點(diǎn)類別的考慮，實(shí)驗(yàn)的推薦精度得到了顯著提升。

Figure 7 Precision of the two city datasets varies with N圖7 兩個(gè)城市數(shù)據(jù)集的準(zhǔn)確率隨N變化的結(jié)果

Figure 8 Recall of the two city datasets varies with N圖8 兩個(gè)城市數(shù)據(jù)集的召回率隨N變化的結(jié)果

Figure 9 F1-score of the two city datasets varies with N圖9 兩個(gè)城市數(shù)據(jù)集的F1-score隨N變化的結(jié)果

本文分析了上下文信息的類型對(duì)推薦的影響，我們選取了Time-of-Day、Day-of-Week以及Category三個(gè)空間。從圖中可以得出考慮上下文信息比不考慮的性能更優(yōu)?？傮w來(lái)看，隨著上下文信息的加入，性能越來(lái)越好。更精細(xì)地分析可以得出不同的上下文信息對(duì)性能的提高也不同。

7 結(jié)束語(yǔ)

本文提出一種基于個(gè)性化上下文感知度量嵌入的方法來(lái)推薦下一個(gè)興趣點(diǎn)，并且使用了排名度量嵌入算法計(jì)算隱式空間的興趣點(diǎn)轉(zhuǎn)移概率。在此基礎(chǔ)上進(jìn)一步提出了CPME-G模型，該模型融合四種影響因素：用戶個(gè)人偏好、時(shí)序轉(zhuǎn)移關(guān)系、上下文感知和地理位置影響。最后，在Foursquare的兩個(gè)數(shù)據(jù)集上驗(yàn)證了本文算法的可行性。為了提高本模型下一個(gè)興趣點(diǎn)推薦的性能，未來(lái)的工作中將考慮更多的上下文信息。

參考文獻(xiàn):

[1] Chen S,Moore J L,Turnbull D,et al.Playlist prediction via metric embedding[C]∥Proc of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,2012:714-722.

[2] Cho E,Myers S A,Leskovec J.Friendship and mobility:User movement in location-based social networks[C]∥Proc of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,2011:1082-1090.

[3] Li X,Cong G,Li X L,et al.Rank-geofm:A ranking based geographical factorization method for point of interest recommendation[C]∥Proc of the 38th International ACM SIGIR Conference on Research and Development in Information Retrieval,2015:433-442.

[4] Lian D,Zhao C,Xie X,et al.GeoMF:Joint geographical modeling and matrix factorization for point-of-interest recommendation[C]∥Proc of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,2014:831-840.

[5] Ye M,Yin P,Lee W C,et al.Exploiting geographical influence for collaborative point-of-interest recommendation[C]∥Proc of the 34th International ACM SIGIR Conference on Research and Development in Information Retrieval,2011:325-334.

[6] Yuan Q, Cong G, Ma Z,et al.Time-aware point-of-interest recommendation[C]∥Proc of the 36th International ACM SIGIR Conference on Research and Development in Information Retrieval,2013:363-372.

[7] Cheng C,Yang H,Lyu M R,et al.Where you like to go next:Successive point-of-interest recommendation[C]∥Proc of the 22th International Joint Conference on Artificial Intelligence,2013:2605-2611.

[8] Ye J,Zhu Z,Cheng H.What's your next move:User activity prediction in location-based social networks[C]∥Proc of the 2013 SIAM International Conference on Data Mining,2013:171-179.

[9] Rendle S, Freudenthaler C,Schmidt-Thieme L.Factorizing personalized Markov chains for next-basket recommendation[C]∥Proc of the 19th International Conference on World Wide Web,2010:811-820.

[10] Feng S,Li X,Zeng Y,et al.Personalized ranking metric embedding for next new POI recommendation[C]∥Proc of the 24th International Joint Conference on Artificial Intelligence,2015:2069-2075.

[11] Zheng Y,Zhang L,Xie X,et al.Mining interesting locations and travel sequences from GPS trajectories[C]∥Proc of the 18th International Conference on World Wide Web,2009:791-800.

[12] Liu B,Fu Y,Yao Z,et al.Learning geographical preferences for point-of-interest recommendation[C]∥Proc of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,2013:1043-1051.

[13] Yang D,Zhang D,Zheng V W,et al.Modeling user activity preference by leveraging user spatial temporal characteristics in LBSNs[J].IEEE Transactions on Systems,Man,and Cybernetics:Systems,2015,45(1):129-142.

[14] Tang J,Aggarwal C,Liu H.Recommendations in signed social networks[C]∥Proc of the 25th International Conference on World Wide Web,2016:31-40.

[15] Lian D,Ge Y,Zhang F,et al.Content-aware collaborative filtering for location recommendation based on human mobility data[C]∥Proc of the 15th IEEE International Conference on Data Mining,2015:261-270.

[16] He J,Li X,Liao L,et al.Inferring a personalized next point-of-interest recommendation model with latent behavior patterns[C]∥Proc of the 30th AAAI Conference on Artificial Intelligence,2016:137-143.

[17] Xie M,Yin H,Xu F,et al.Graph-based metric embedding for next POI recommendation[C]∥Proc of the 17th International Conference on Web Information Systems Engineering,2016:207-222.

[18] Gormley M R,Yu M,Dredze M.Improved relation extraction with feature-rich compositional embedding models[C]∥Proc of 2015 Conference on Empirical Methods on Natural Language Processing,2015:1-12.

[19] Rendle S,Freudenthaler C,Gantner Z,et al.BPR:Bayesian

personalized ranking from implicit feedback[C]∥Proc of the 25th Conference on Uncertainty in Artificial Intelligence,2009:452-461.