基于數據挖掘的移動用戶出行軌跡預測

劉麗嫻 樊學寶

【摘? 要】為了解決移動用戶出行軌跡預測的問題，首先利用用戶出行軌跡數據進行語義化建模，然后根據語義位置和訪問概率對用戶群進行分類，再次，利用關聯規則挖掘不同群體的頻繁模式，最后，結合實時出行數據動態更新貝葉斯網絡實現移動用戶出行軌跡的實時預測。經過實驗表明，該算法能夠在一定程度上反映用戶出行的目的和偏好，并具有很好的擴展性。

【關鍵詞】語義化建模;關聯規則;貝葉斯網絡;軌跡預測

中圖分類號：TN915.0

文獻標志碼：A? ? ? ? 文章編號：1006-1010（2019）05-0092-05

1? ?引言

移動用戶行為具有很強的時空規律性，用戶群體間的移動行為具有很高的相似性[1]。基于地理位置的服務與推薦已經成為當前的研究的熱點，如：喬巖磊等人[2]利用高斯混合模型擬合連續時間下地點之間的轉移概率推測用戶的位置，但沒有對不同群體用戶的語義位置特點進行區別性對待，不能有效反應不同群體用戶的出行特征。廖文芳[3]根據移動用戶的出行位置信息進行社交平臺的設計，但并沒有考慮到利用用戶在不同位置的逗留時長來反映用戶在特定位置的停留偏好。姚迪等人[4]將用戶時空軌跡數據轉換成特定的語義信息，以此推測用戶的偏好和需求，但沒有區分不同群體用戶的停留時長和偏好。邱運芬等人[5]提出一種語義和概率的人群分類方法，根據語義位置分配情況獲取用戶對語義空間的訪問向量，采用聚類的方法對用戶進行人群的劃分，結果表明，同類用戶在語義位置空間的訪問概率向量相似。研究者[3-8]從不同的角度研究地理位置的服務和推薦，包括用戶的位置推測、用戶出行群體特點，但并沒有綜合采用不同語義位置的停留偏好和停留時長來反映不同群體的出行偏好，同時，研究者并沒有根據個體用戶的實時出行軌跡來預測個體的未來軌跡。

因此，本文在借鑒相關研究的基礎上，針對傳統用戶預測沒有考慮到用戶群體分類的問題，提出一種基于移動軌跡的用戶位置預測方法：在用戶軌跡語義化的基礎上，結合語義位置的概率向量采用聚類的方法對人群進行劃分;在此基礎上，采用關聯規則挖掘不同群體的頻繁模式;最后，結合實時出行數據動態更新貝葉斯網絡實現移動用戶出行軌跡的實時預測。

2? ?出行軌跡的相關研究

2.1? 移動用戶出行的時空序列模型

移動用戶出行的時空序列模型，是基于移動用戶的時空數據進行數據挖掘的模型，通過對用戶移動周期規律和相關參數的估計，能夠獲得移動用戶在不同時間下位置概率分布的信息[6-7]，以此挖掘用戶的行為模式與時間的關系。

假設移動用戶的出行時空序列為：Tri={（L1， t1）， （L2， t2）， …， （Li， ti）， …， （Ln， tn）}，其中，（Li， ti）表示用戶在某個時間內出現在基站位置，那么，用戶在不同時間的位置概率分布可表示為：

公式（1）表示，在特定的時間段內，用戶在不同位置下的分布概率，相比于位置數據，移動用戶出行的時空序列模型更能體現用戶的出行偏好以及出行規律。

2.2? 移動用戶語義位置模型

在獲取移動用戶出行的時空序列后，能夠根據用戶在某一個位置的逗留時間，獲取用戶停留點。但是僅僅以地理軌跡的停留點來分析用戶的出行規律似乎意義不大，因此，不少學者采用語義軌跡來反映用戶的活動行為模式，通過語義位置對地理位置進行功能性的描述，推測用戶在不同時間的不同行為特征以及其周邊的環境信息，這些信息能夠有效表征用戶的語義位置。移動用戶停留點的語義位置軌跡可用圖1表示：

2.3? 移動模式挖掘模型

移動用戶的行為具有群體的特征，移動用戶出行的頻繁模式，在一定程度上反映了移動用戶出行行為具有一定的相似性[8]。在獲取移動用戶一段時間的語義位置軌跡的基礎上，通過關聯規則的相關算法就能挖掘用戶在一段時間的出行規律。某一個用戶在一段時間的語義位置軌跡如表1、表2所示。

從表1、表2可知，<家，公司，餐館，公園>是一種用戶的語義位置軌跡模式，可以預測到用戶在一周內去家、公司、餐館、公園的頻率為1/7，也就是一周中用戶有一天會先去公司、然后去餐館、公園。

2.4? 軌跡預測模型

移動用戶的出行位置是不斷變換的，如果將用戶在移動過程中經過的語義位置軌跡視為一個個的狀態，那么可以通過狀態更新的方式對用戶的位置進行預測。語義位置軌跡是從地理位置提取高層的信息，使用語義位置軌跡能夠更好預測用戶的軌跡。而相似用戶的語義位置軌跡，更能夠解決位置預測中“新地點”的問題，當一個用戶達到一個新的地點，無法通過自己的歷史軌跡數據進行預測時，此時可以使用與之相似的用戶軌跡數據進行預測。

3? ?基于動態貝葉斯網絡動態更新的用戶出行軌跡

本文提出一種基于動態貝葉斯網絡的用戶出行軌跡預測方法，其步驟如下：

（1）提取移動用戶的歷史位置并對進行語義位置的挖掘;

（2）采用Apriori算法挖掘語義頻繁模式;

（3）基于用戶的語義頻繁模式和語義位置概率進行用戶分群;

（4）利用群體初始語義位置偏好生成初始的貝葉斯網絡;

（5）利用個體用戶的實時語義位置動態更新貝葉斯網絡，實現個體的軌跡預測。

3.1? 移動用戶的語義位置軌跡挖掘

如表3所示，本文通過提取某個城市3G/4G的10萬用戶的出行數據，提取的字段包括：用戶ID、小區編號、發生業務的時間戳。

語義位置是對地理環境的定性描述，在獲取用戶的小區編號的基礎上，采用反向的地理編碼服務（百度等提供的編碼接口）將基站位置轉化為地址信息，再利用POI數據庫獲取當前基站的語義位置。語義位置示例如表4所示：

3.2? 移動用戶語義頻繁模式挖掘

在挖掘用戶語義位置的基礎上，需要從大量的語義位置數據庫中找到滿足給定一定條件（滿足最小支持度和最小置信度）的用戶出行頻繁模式。其步驟為：

（1）找出所有的頻繁項目集;

（2）給定最小的支持度和置信度，找出滿足特定規則的頻繁項集。

本文考慮到移動用戶出行數據的特點，采用Apriori算法提取用戶的語義標簽數據集。其結果如表5所示：

3.3? 基于語義位置和概率的用戶分群

相似用戶的語義位置軌跡能夠更好預測用戶的出行軌跡，因此，在獲取每一個用戶的語義頻繁模式的基礎上，結合用戶在每一個語義位置上出現的概率進行分群。假設語義位置集為{l1， l2， l3， …， ln}，某一個用戶在每一個語義位置上出現的概率向量為{p1， p2， p3， …， pn}，且p1+p2+p3+…+pn=1。通過采用k-means算法對全體用戶的概率向量進行聚類，得到基于語義位置和概率的用戶分群結果。

3.4? 采用貝葉斯網絡動態預測用戶出行軌跡

貝葉斯網絡是基于概率推理的圖形化網絡[9]，在獲取群體的移動用戶歷史出行數據基礎上，網絡就會推斷同一群體移動用戶出行偏好，當實時輸入移動用戶的實時位置時，貝葉斯網絡的概率就會動態調整。某用戶群體初始語義位置偏好的貝葉斯網絡如圖2所示：

當移動用戶產生新的移動軌跡時，貝葉斯網絡的概率會自動更新，運營商會根據當前用戶的移動軌跡和逗留時長（如果逗留時長超過設定的閾值，則把將貝葉斯網絡的概率實施動態更新;否則不作更新）進行實時的動態更新，預測移動用戶去往某一個語義位置的概率。

從實驗數據得到，用戶在語義位置的平均逗留時長閾值為53分鐘，也就是說，用戶在某一個語義位置的逗留時長超過53分鐘時，初始語義位置偏好的貝葉斯網絡節點將被激活實現用戶實時語義位置的預測。其實驗結果與用戶真實的逗留偏好比較吻合，隨著用戶實時軌跡數據的增加，運營商對移動用戶的出行軌跡預測將會更加的準確，運營商可以為不同的用戶提供更加個性化的地理位置服務，提高位置服務提供商的效率和利潤。

4? ?結束語

本文提出一種融合語義位置數據的位置預測，結合了用戶的出行行為和周邊的環境位置來表征用戶的語義位置;利用用戶語義位置的相似性實現用戶的分群，利用分群的出行數據構造貝葉斯網絡;最后利用移動用戶的實時出行語義位置動態更新貝葉斯網絡并實現移動用戶出行軌跡的預測。相比傳統的地理位置的預測，本文提出的語義軌跡更能反映用戶的活動行為模式，能夠更好推測用戶在不同時間的各種行為模式，更有效表征用戶的行為。

參考文獻：

[1] 崔家祥. 基于移動通信數據的用戶移動行為分析與位置預測[D]. 北京： 北京郵電大學， 2018.

[2] 喬巖磊，杜永萍，趙東玥. 基于高斯分析的馬爾可夫位置預測方法[J]. 計算機技術與發展， 2018，28（1）： 41-44.

[3] 廖文芳. 基于位置的移動社交網絡平臺的設計[J]. 山東工業技術， 2018（11）： 139.

[4] 姚迪，張超，黃建輝，等. 時空數據語義理解：技術與應用[J]. 軟件學報， 2018，29（7）： 196-223.

[5] 邱運芬，張暉，李波，等. 一種基于語義位置和概率的人群分類方法[J]. 數據采集與處理， 2018，149（3）： 154-162.

[6] 連德富，張富錚，王英子，等. 移動數據挖掘[M]. 北京： 機械工業出版社， 2017.

[7] 錢琨. 基于蜂窩信令數據的移動軌跡清洗和預測方法研究與實現[D]. 成都： 西南交通大學， 2016.

[8] 陳少權. 基于改進LCSS的移動用戶軌跡相似性查詢算法研究[J]. 移動通信， 2017，41（6）： 77-82.

[9] 張小可，沈文明，杜翠鳳. 貝葉斯網絡在用戶畫像構建中的研究[J]. 移動通信， 2016，40（22）： 22-26.

[10] 付莉莉. 融合語義信息的位置預測技術研究[D]. 北京： 北京郵電大學， 2013.