基于矩陣分解的個(gè)性化軌跡推薦方法

潘 曉 馬 昂 閆曉倩 吳 雷

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

0 引 言

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

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

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

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

1 預(yù)備知識(shí)

1.1 相關(guān)定義

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

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

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

表1 多屬性軌跡

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

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

(1)

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

表2 用戶行為

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

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

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

定義4軌跡推薦。給定用戶的起點(diǎn)v0和終點(diǎn)vd，軌跡推薦方法會(huì)為用戶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最小值問題，對(duì)L進(jìn)行取對(duì)數(shù)變換，計(jì)算式表示為:

(3)

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

1.2 研究框架

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

圖1 研究框架

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

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

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

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

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

采用矩陣分解法對(duì)用戶行為頻數(shù)進(jìn)行填充。假設(shè)用戶和用戶的行為是受一定因素影響的，即pui、qbj分別代表影響用戶和用戶行為的潛在因素向量，如式(4)和式(5)所示，其中k為因素的個(gè)數(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的乘積代表估計(jì)值；常數(shù)η為正規(guī)化參數(shù)，防止發(fā)生過擬合。

2.2 計(jì)算用戶行為概率

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

(7)

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

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

3 實(shí)驗(yàn)與結(jié)果分析

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

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

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

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

(8)

(9)

(10)

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

3.2 結(jié)果分析

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

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

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

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

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

(3) 不同數(shù)據(jù)集下各方法的推薦效果評(píng)價(jià)。在LA和NYC數(shù)據(jù)集上，分別評(píng)價(jià)和比較基于矩陣的用戶行為概率學(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，基于多因素概率密度估計(jì)的方法F值為0.41，基于馬爾可夫的方法為0.40。

圖4 軌跡推薦結(jié)果評(píng)價(jià)

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

4 結(jié) 語

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