潘 曉 馬 昂 閆曉倩 吳 雷

(石家莊鐵道大學(xué) 河北 石家莊 050043)

0 引 言

隨著無人駕駛、智能汽車和車聯(lián)網(wǎng)等技術(shù)的發(fā)展，大量的軌跡數(shù)據(jù)迅速積累[1-5]。同時，伴隨社交媒體應(yīng)用的流行普及，地理位置與文本數(shù)據(jù)的融合，大量外部信息被嵌入到軌跡中，形成了多屬性軌跡，軌跡上的每一個點同時包括位置、時間戳、活動和其他描述性多屬性。多屬性軌跡數(shù)據(jù)中包含了反映移動特征、個性化偏好等豐富信息[6]?；跉v史多屬性軌跡制定出行計劃可以為用戶提供更加友好和個性化的出行體驗[7]。本文從用戶歷史多屬性軌跡中自動學(xué)習(xí)用戶個性化的行為偏好，為用戶提供滿足行為偏好的路線推薦。

目前已經(jīng)存在了一些在多屬性軌跡上的推薦研究[6-15]。文獻(xiàn)[10]通過用戶簽到數(shù)據(jù)，提出了一個時間敏感的路徑推薦方法，通過構(gòu)建三維張量進(jìn)行用戶偏好估計得到候選位置點，結(jié)合位置點的合適訪問時間，以及位置點之間的路程時間，對經(jīng)典的最短路徑算法進(jìn)行擴(kuò)展，提出了路線生成算法。文獻(xiàn)[8]利用Flickr中的數(shù)據(jù)，提出一種基于興趣點(Points of interest,POI)流行度和基于時間的用戶興趣偏好的個性化旅游路線推薦算法PTIR，在給定旅行時間限制、起點和終點的情況下，結(jié)合用戶興趣偏好設(shè)計最優(yōu)旅游路線。雖然，文獻(xiàn)[8]和文獻(xiàn)[10]在推薦時考慮到了時間、空間和地點流行度等因素，但是忽略了多屬性軌跡中的文本屬性對推薦的影響。

文獻(xiàn)[9]結(jié)合了用戶軌跡數(shù)據(jù)和社交平臺數(shù)據(jù)，將用戶的偏好形式化地表示為關(guān)鍵字集合，設(shè)計了一個關(guān)鍵字提取模塊對POI相關(guān)標(biāo)簽進(jìn)行分類，以便與查詢關(guān)鍵字進(jìn)行有效匹配。通過路徑重建算法構(gòu)建滿足符合用戶指定關(guān)鍵字需求的軌跡。借助Skyline概念，向用戶推薦在不同POI特征之間均不能被控制(dominate)的軌跡路線。文獻(xiàn)[5]提出一種基于短時間體驗式路線搜索方法SERS，該方法根據(jù)用戶給定的查詢位置、時間約束以及用戶指定的文本類別集合，找到一條地點非重復(fù)、包含類別最多、收益最大的訪問路線。上述工作雖然考慮到了多屬性軌跡中的文本屬性，但均沒有考慮用戶個性化的出行行為習(xí)慣。

與上述工作不同，本文無須用戶手動設(shè)定行為偏好，通過簡單地指定起點和終點位置，即可為用戶推薦個性化的出行路線。

1 預(yù)備知識

1.1 相關(guān)定義

用戶的興趣偏好蘊(yùn)含在用戶的活動即多屬性軌跡中。多屬性軌跡中的每一個位置點的語義都可體現(xiàn)用戶在該點進(jìn)行的活動，如就餐、鍛煉和購物等。這些活動以文本標(biāo)簽的形式與位置點關(guān)聯(lián)。定義1給出了多屬性軌跡的定義。

定義1多屬性軌跡。一條多屬性軌跡ti={pi,1,pi,2,…,pi,3},其中活動點pi,j=，代表用戶i在timj時刻和vj點進(jìn)行了活動，活動的文本標(biāo)記集合用sj表示。

表1列舉了6個用戶的多屬性軌跡，包括位置點、時間以及在位置點上進(jìn)行的活動(即文本集合)。用戶的行為與用戶在某一個位置點進(jìn)行的活動內(nèi)容有關(guān)，更與用戶連續(xù)進(jìn)行的活動相關(guān)。比如，健身愛好者在工作后喜歡去健身房健身。因此，將用戶在多屬性軌跡上的兩個連續(xù)位置定義為用戶行為。

表1 多屬性軌跡

定義2用戶行為。給定用戶軌跡集合,一個用戶行為bk表示用戶在時間(timi,timj)內(nèi)連續(xù)在(vi,vj)兩位置點進(jìn)行了活動si和sj，形式化地表示為：

bk=<(vi,vj),(timi,timj),si∪sj>

(1)

根據(jù)定義2，可以從表1中的6條軌跡中抽取10個用戶行為，具體信息如表2所示。為防止時間粒度過細(xì)造成的數(shù)據(jù)稀疏問題，將時間進(jìn)行了分段。例如，以24小時為例，每2個小時為1段，共12段。

表2 用戶行為

將用戶行為以有向圖的形式組織起來，圖中的點即帶有時間和文本的空間點，邊即一個行為。定義3給出了具體定義。

定義3行為圖。行為圖G是一個有向圖，G=，V是由所有用戶的軌跡中的所有活動點組成的集合，其中每一個活動點p∈V包含空間位置、時間和文本集合三個部分。E是由軌跡中連續(xù)兩個點組成的邊集合，即ei,j=，其中vi,vj∈V。由定義2可知，圖G中的每一條邊即用戶的一個行為b。圖G上的每條邊都被賦予一個權(quán)重，表示某用戶發(fā)生此行為的概率。因此，不同的用戶在圖G的同一條邊上具有不同的權(quán)值。

定義4是軌跡推薦問題的形式化定義。

定義4軌跡推薦。給定用戶的起點v0和終點vd，軌跡推薦方法會為用戶u返回一條軌跡t=(v0,v1,…，vd)使得概率p(t|u)的值最大，即：

p(t|u)=p(v0,v1,…,vd|u)=

p(v0,v1,…,vd,u)/p(u)

(2)

假設(shè)用戶的行為相互獨(dú)立，軌跡概率p(t|u)的值最大，即為p(u,b1)×p(u,b2)×…×p(u,bn)最大。設(shè)L=1/p(u,b1)×p(u,b2)×…×p(u,bn),則求解p(t|u)的值最大問題轉(zhuǎn)化為了求解L最小值問題，對L進(jìn)行取對數(shù)變換，計算式表示為:

(3)

根據(jù)式(3)可知，計算軌跡概率最大問題，可以轉(zhuǎn)換成尋找若干個用戶行為，使得用戶行為概率倒數(shù)之和最小問題。結(jié)合定義3中的行為圖，每一個行為發(fā)生的概率即行為邊的權(quán)重，則求解軌跡概率最大問題可轉(zhuǎn)變成基于圖的最短路徑問題。

1.2 研究框架

本文的研究框架大體可分為2部分，具體如圖1所示。

圖1 研究框架

首先，在對用戶軌跡數(shù)據(jù)進(jìn)行了異常點預(yù)處理后，利用多屬性軌跡構(gòu)建用戶行為圖和用戶行為概率矩陣。通過分析真實數(shù)據(jù)發(fā)現(xiàn)，用戶行為數(shù)據(jù)非常稀疏，存在大量未知的用戶行為概率值。為了解決稀疏問題，本文提出基于矩陣分解的用戶行為概率學(xué)習(xí)方法，對用戶行為概率進(jìn)行估計。

其次，使用貝葉斯方法對軌跡概率進(jìn)行計算，如式(2)所示。結(jié)合用戶給定的起點和終點，基于用戶行為概率采用雙向Dijkstra算法[12]——一種對傳統(tǒng)Dijkstra算法在時間效率進(jìn)行的改進(jìn)算法，軌跡推薦將返回使概率最大的軌跡作為參考。

2 基于矩陣分解的用戶行為概率學(xué)習(xí)

矩陣分解是協(xié)同過濾中一種有效并且常見的方法，旨在通過構(gòu)建用戶項目矩陣來預(yù)測用戶的偏好。本節(jié)首先構(gòu)建用戶行為頻數(shù)矩陣UB，然后利用矩陣分解方法對用戶的行為頻數(shù)進(jìn)行估計，進(jìn)而得到用戶行為概率。

2.1 用戶行為頻數(shù)估計

采用矩陣分解法對用戶行為頻數(shù)進(jìn)行填充。假設(shè)用戶和用戶的行為是受一定因素影響的，即pui、qbj分別代表影響用戶和用戶行為的潛在因素向量，如式(4)和式(5)所示，其中k為因素的個數(shù)。矩陣分解不探究這些因素具體是什么，而是通過這些因素得到受這些因素影響的用戶ui產(chǎn)生行為bj的頻數(shù)。

pui=(fui1,fui2,…,fuik)

(4)

qbj=(fbj1,fbj2,…,fbjk)

(5)

(6)

式中：S是已知頻數(shù)的用戶ui和行為bi的集合；UBi,j是用戶ui發(fā)生行為bi的頻數(shù)；因素向量pui和qbj的乘積代表估計值；常數(shù)η為正規(guī)化參數(shù)，防止發(fā)生過擬合。

2.2 計算用戶行為概率

用戶的行為概率描述了用戶的選擇執(zhí)行該行為的可能性，可通過下式計算：

(7)

式中：a為平滑參數(shù)。

通過式(7)，用戶行為頻數(shù)矩陣轉(zhuǎn)變?yōu)橛脩粜袨楦怕示仃嘝ro={pi,j}，即已獲得行為圖中的邊權(quán)值。給定用戶起點v0和終點vd，軌跡查詢推薦方法將利用雙向Dijkstra算法為用戶u返回概率最大的軌跡。

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

3.1 實驗設(shè)計

從Foursquare數(shù)據(jù)集的LA和NYC中，將用戶簽到時刻以升序排序得到每一個用戶的簽到軌跡,軌跡上每一個點均包含簽到時間、簽到位置、簽到POI的類別集合信息。從中隨機(jī)選取了2 000條軌跡，剔除簽到頻數(shù)低于30、簽到用戶數(shù)低于10的簽到冷點，并對其利用Geohash方法進(jìn)行了網(wǎng)格劃分。

本文所有的推薦模型和算法均用Java語言實現(xiàn)，運(yùn)行于2.7 GHz處理器、16 GB內(nèi)存的Windows 10計算機(jī)上。實驗選擇了基于馬爾可夫的推薦方法[15](簡稱為Markov)、基于多因素融合的推薦方法[14](簡稱為UBPMF)進(jìn)行對比驗證。

本文采用F-Measure方法，計算精確度P和召回率R的加權(quán)調(diào)和平均，具體計算如下：

(8)

(9)

(10)

式中:當(dāng)α取1時，F(xiàn)-Measure為F1-Measure。

3.2 結(jié)果分析

實驗評價可以分為兩部分：推薦結(jié)果準(zhǔn)確性評價和查詢效率評價。其中，由于查詢直接采用的是雙向Dijkstra算法，查詢效率方面不做特別的評價。本節(jié)將具體介紹推薦結(jié)果準(zhǔn)確性的評價。

(1) 用戶平均好友個數(shù)對推薦結(jié)果的影響。用戶平均好友個數(shù)不同時各方法推薦結(jié)果的變化如圖2所示。由于馬爾可夫方法并沒有考慮用戶的好友關(guān)系，所以本文僅評價了UBPMD和UBPMF。圖中橫軸代表用戶平均好友個數(shù)，縱軸為推薦評價標(biāo)準(zhǔn)F值?？梢钥闯觯琔BPMF方法得到的平均F值略低于UBPMD方法，但這兩種方法下平均F值隨好友個數(shù)的變化趨勢大體相同。當(dāng)用戶好友個數(shù)為0時，推薦的準(zhǔn)確度僅依靠用戶自身的歷史軌跡數(shù)據(jù)，平均F值低于0.40。用戶好友數(shù)量介于0至22時，隨著用戶數(shù)量的增加，平均F值處于波動狀態(tài)，總體呈現(xiàn)下降趨勢。這是由于當(dāng)用戶數(shù)量較少時，可能無法體現(xiàn)出該用戶的行為偏好，甚至?xí)τ脩羝卯a(chǎn)生消極影響。在用戶好友個數(shù)為23時，平均F值處于頂峰。用戶好友數(shù)量介于22～65時，隨著好友個數(shù)的增加，平均F值總體呈現(xiàn)上升趨勢。用戶好友數(shù)量大于65后，平均F值開始下降。通過上述實驗表明，過高和過低的好友數(shù)量會對推薦結(jié)果的準(zhǔn)確度產(chǎn)生一定的影響，用戶好友數(shù)量介于50～60時，推薦準(zhǔn)確度較高。

圖2 用戶好友個數(shù)與F值的關(guān)系

(2) 不同軌跡長度對推薦結(jié)果的影響。用戶軌跡長度不同時對各方法推薦結(jié)果的影響變化如圖3所示。圖中橫軸代表用戶軌跡長度，縱軸為推薦評價標(biāo)準(zhǔn)F值?？梢钥闯?，隨著軌跡長度的增加，推薦結(jié)果的平均F值呈現(xiàn)下降趨勢。軌跡長度過長，推薦結(jié)果的準(zhǔn)確度越低。當(dāng)軌跡長度介于4～12 km時，推薦結(jié)果的準(zhǔn)確度較高。結(jié)果表明，在進(jìn)行用戶行為偏好學(xué)習(xí)時，用戶軌跡不宜過長，這一點比較符合人們直觀認(rèn)知，軌跡過長說明用戶簽到次數(shù)過多或者經(jīng)歷的時間周期較長。例如，一周內(nèi)的軌跡與半月內(nèi)的軌跡相比，一周內(nèi)的軌跡更具有一定的規(guī)律性，軌跡過長無法準(zhǔn)確反映出用戶的行為習(xí)慣。

圖3 軌跡長度與F值的關(guān)系

(3) 不同數(shù)據(jù)集下各方法的推薦效果評價。在LA和NYC數(shù)據(jù)集上，分別評價和比較基于矩陣的用戶行為概率學(xué)習(xí)方法CFPTR、基于多因素的用戶行為概率學(xué)習(xí)方法MFPTR以及基于馬爾可夫模型的推薦方法MTR的推薦效果。

參數(shù)設(shè)定：基于矩陣分解的潛在因子的數(shù)量設(shè)定為4，正則化參數(shù)π設(shè)定為0.01，平滑參數(shù)a設(shè)定為0.01?；诙嘁蛩馗怕拭芏群瘮?shù)方法中，基于空間因素中的靈敏度參數(shù)α設(shè)定為0.1。

圖4展示了在LA和NYC數(shù)據(jù)集上根據(jù)三種方法得到的F-Measure值。以LA為例，基于矩陣分解的用戶行為學(xué)習(xí)的軌跡推薦方法和基于多因素概率密度函數(shù)的用戶行為概率學(xué)習(xí)的軌跡推薦方法在F值方面都優(yōu)于基于馬爾可夫的軌跡推薦算法。在這三種方法中，基于矩陣分解的用戶行為概率學(xué)習(xí)方法的F值最高為0.46，基于多因素概率密度估計的方法F值為0.41，基于馬爾可夫的方法為0.40。

圖4 軌跡推薦結(jié)果評價

結(jié)果表明，與基于馬爾可夫的軌跡推薦方法相比，用戶更喜歡具有最大行為概率的路線。實驗表明用戶在選擇路線或者出行方案時不僅考慮距離因素，而且還綜合考慮了許多因素，例如：時間、文本和社交關(guān)系等。盡管如此，基于矩陣分解的用戶行為學(xué)習(xí)的軌跡推薦方法取得了比基于多因素概率密度函數(shù)的用戶行為概率學(xué)習(xí)的軌跡推薦方法更好的結(jié)果，上述因素在軌跡推薦中是作為整體對用戶的行為產(chǎn)生影響的，這在路線推薦中起著非常重要的作用。

4 結(jié) 語

本文針對現(xiàn)有大多數(shù)軌跡推薦工作僅關(guān)注時空特征，無法用戶個性化行為習(xí)慣的問題，在多屬性軌跡上同時考慮了用戶前后聯(lián)系活動，通過矩陣分解自學(xué)習(xí)用戶行為習(xí)慣，并將用戶推薦個性化的軌跡路線轉(zhuǎn)換為在行為圖上尋找最短路徑的問題。經(jīng)過一系列實驗，基于用戶行為學(xué)習(xí)的矩陣分解的軌跡推薦方法展現(xiàn)了較好的效果。在未來的工作中，將致力于基于多源數(shù)據(jù)融合的軌跡推薦，可以使用多源數(shù)據(jù)來進(jìn)一步提高推薦質(zhì)量。