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

潘 曉 馬 昂 閆曉倩 吳 雷

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

0 引 言

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

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

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

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

1 預備知識

1.1 相關定義

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

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

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

表1 多屬性軌跡

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

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

(1)

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

表2 用戶行為

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

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

定義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)

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

(3)

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

1.2 研究框架

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

圖1 研究框架

首先，在對用戶軌跡數據進行了異常點預處理后，利用多屬性軌跡構建用戶行為圖和用戶行為概率矩陣。通過分析真實數據發現，用戶行為數據非常稀疏，存在大量未知的用戶行為概率值。為了解決稀疏問題，本文提出基于矩陣分解的用戶行為概率學習方法，對用戶行為概率進行估計。

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

2 基于矩陣分解的用戶行為概率學習

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

2.1 用戶行為頻數估計

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

pui=(fui1,fui2,…,fuik)

(4)

qbj=(fbj1,fbj2,…,fbjk)

(5)

(6)

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

2.2 計算用戶行為概率

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

(7)

式中：a為平滑參數。

通過式(7)，用戶行為頻數矩陣轉變為用戶行為概率矩陣Pro={pi,j}，即已獲得行為圖中的邊權值。給定用戶起點v0和終點vd，軌跡查詢推薦方法將利用雙向Dijkstra算法為用戶u返回概率最大的軌跡。

3 實驗與結果分析

3.1 實驗設計

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

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

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

(8)

(9)

(10)

式中:當α取1時，F-Measure為F1-Measure。

3.2 結果分析

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

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

圖2 用戶好友個數與F值的關系

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

圖3 軌跡長度與F值的關系

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

參數設定：基于矩陣分解的潛在因子的數量設定為4，正則化參數π設定為0.01，平滑參數a設定為0.01。基于多因素概率密度函數方法中，基于空間因素中的靈敏度參數α設定為0.1。

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

圖4 軌跡推薦結果評價

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

4 結 語

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