移動行為感知計算技術研究綜述

鄧舟彥 韓楠 喬少杰 徐小玲 黃萍 熊熙

摘要：隨著智能計算、無線通信、傳感器等技術的快速發展，具有GPS定位功能的移動便攜設備日益普及和流行，這些設備會產生能夠反映設備的移動行為運動規律的大規模軌跡數據，可以為出行規劃、城市道路規劃、共享單車站點分布、出租車調度等提供有力支撐。本文從軌跡數據的采集、提取和移動行為感知分析等方面進行闡述，討論當前主流技術基本思想及工作原理，最后對未來的研究工作進行展望。

關鍵字：移動行為感知；GPS；軌跡數據；行為分析

中圖分類號：TP393.03 文獻標識碼：B 文章編號：1672-9129（2019）04-0001-06

Abstract：With the rapid development of the intelligent computing， wireless communication and sensors， mobile portable devices with GPS positioning function are becoming more and more popular. These devices will generate large-scale trajectory data which can reflect the movement behavior of devices， which can be used for trip planning， urban road planning， station planning of sharing bicycles and taxi dispatch. This study reviews the techniques of trajectory data collection， extraction and mobile behavior perception analysis， discusses the basic ideas and working principles of the state-of-the-art techniques， and finally presents the future research work.

Keywords：mobile behavior perception； GPS； trajectory data； behavior analysis

引言

近年來，隨著具有GPS定位功能的設備的普及，手機、平板、車載導航、共享單車等移動設備進入我們的生活并變得日益普及。據工業和信息化部統計，截至2018年5月，三家基礎電信公司的手機用戶總數接近15億。大城市的手機普及率接近100%。手機自帶的位置定位功能在服務于用戶定位時，通信運營商也積累了大量的位置軌跡數據。同時，手機導航作為汽車導航的普遍率很高。艾媒咨詢發布了“2017-2018中國移動地圖市場研究報告”。根據該機構的數據，截至2017年第四季度，中國的移動地圖用戶數量已達到7.07億。

比起基于移動通信數據等方法對用戶行為的預測，基于GPS和移動數據的定位軌跡因為其具有海量的規模、不易受天氣影響和能精準及時地反饋記錄的坐標等特點而具有較大的研究價值和應用前景。這些數據大大降低了數據采集成本，為行駛路徑規劃、交通流量預測、城市道路規劃、共享類交通工具調度等提供有效數據支撐。

1 問題描述

近年來，使用移動軌跡數據做數據挖掘和機器學習來感知移動行為得到許多研究人員的關注。運動物體軌跡預測方法主要分為基于道路網絡限制的軌跡預測和基于歐式空間的軌跡預測[1]。通過頻繁模式挖掘到的軌跡模式來對軌跡進行預測和根據當前移動對象前一段時間片的位置和速度預測當前時刻的軌跡位置都是基于歐式空間軌跡預測。但基于移動設備的軌跡數據往往只是單一地在道路網上運動，其位置和速度都會受到限制，而無法有效的通過基于歐式空間的方法進行預測。

大部分的研究都集中在具體分析運動物體的歷史軌跡，從而得到有價值的信息，針對基于歷史數據的位置預測的研究相對較少。運動物體的連續位置預測主要包括過去軌跡的重建以及當前和未來軌跡的預測。研究重點是挖掘軌跡頻繁模式找出典型運動路徑[2]。目前，移動行為感知研究主要關注兩個問題：一、提高交通設施運行效率的提高智能交通系統（ ITS），二、通過電信移動運營商的無線電通訊網絡（例如，GSM網絡，CDMA網絡或外部定位方法（例如GPS）獲得移動終端用戶的位置信息服務。

2 國內外研究現狀

越來越多的研究人員利用機器學習技術和數據挖掘來對移動對象行為感知研究。由此，產生了大量關于移動行為感知的研究成果。文獻[3]介紹了移動軌跡可視化技術對于智能交通、人員流動性評估和路徑規劃三個方面的作用。通過對軌跡空間和時間等屬性的可視化分析，在一個顯示圖上展現這些屬性之間的關系。可以為研究人員尋找數據之間的聯系和規律提供鋪墊。劉震等人[4]指出，基于移動通信技術對用戶軌跡預測，通過記錄手機通話時基站位置來確定用戶位置是不準確的，因信號、基站容量等客觀因素的影響，手機通信時選擇的并不一定是最近的基站，可以用過設定地區轉換的上限的方法來判斷用戶是否移動。Wiest等人0提出建立概率模型，對物體運動前一段時間運動的參數進行收集作為運動模型的聯合概率分布，通過對分布的計算來推斷未來運動軌跡。這種方法的優點在于不僅是對運動軌跡的預測，而且能反映對未來軌跡的整體分布，通過對統計的屬性評估可以對特定的目標進行預測。該預測結果還可以用方差來評估預測的準確性。

彭曲[5]等人基于馬爾科夫鏈進行軌跡預測，運用轉移概率矩陣評估狀態評估直接轉換的可能性，對處于交叉路口的軌道的選擇進行預測，但因為實際交通狀況具有不確定性，在交叉路口的選擇需遵守一定的規則等因素，故預測結果準確率存在瓶頸。Song等人[6]做了對人類移動軌跡預測的研究，利用DBSCAN算法在人群中找到的聚類來構建軌跡，基于Lempel-Ziv壓縮算法算出移動序列的熵值，定量地給出了人類動態運動軌跡具有70%-93%的可預測性，文中結論指出人類的運動規律獨立于軌跡路徑。Qiao等人[7]基于隱馬爾科夫模型，設計實現了自適應調整軌跡預測算法，可以根據軌跡數據預測算出最佳路線，但隨著數據量的增加，該算法會出現運行時間成本過高的問題。喬少杰等人[8]提出基于隱馬爾科夫模型的自適應軌跡預測模型，對移動對象軌跡數據基于密度聚類分區和高效分段處理，根據軌跡數據選擇參數組合，解決了隱馬爾科夫模型中狀態間斷、中斷等問題。Shi等人[9]基于馬爾科夫模型，根據移動軌跡所在的路段預測其在短期內將到達的路段。

3 軌跡特征提取

隨著智能設備與車載雷達的普及，GPS數據庫與顯示結合，讓我們能享受更加便利的生活，在這當中軌跡數據發揮了重要的作用。但是，隨著數據量的爆發式增長，現有存儲和計算能力的限制和冗余數據的存在，在海量數據中提取能夠精確反映軌跡信息的點就顯得尤為重要，而軌跡特征就是具有獨特價值的點。以下是對于軌跡特征提取的具體因素。

（1）對軌跡點數據的獲取進程，因GPS數據采集設施的定位精度等限制，導航中會出現軌跡偏差，故需要提取軌跡特征，來提高在軌跡模型系統匹配的準確率[10]。

（2）采集到的數據具有許多不確定性，如數據來源存在的不確定性、位置的不確定性、運動行為的不確定性等諸多不確定性因素[11]，使得原始軌跡數據中將存在一定的噪聲點，導致大軌跡數據查詢、挖掘、預測不精確。因此，在大數據挖掘之前從原始軌跡中提取特征是非常重要的。

（3）可以通過移動軌跡數據來體現交通狀態信息，并且可基于軌跡特征提取來評估交通流量。另外，我們可以通過對軌跡數據進行聚類分析從而找到功能區域的缺陷，重新規劃城市社區周邊配套設施布局提升的設施資源利用率。

3.1 數據預處理

軌跡原始數據往往包含誤差，所以需要對數據進行特征提取，可以通過數據去噪、分段、壓縮、地圖匹配等一系列的操作來對數據特征進行采集[12]。喬少杰等人[13]提出了一種基于GeoHash空間編碼[14]的軌跡特征提取方法，對軌跡數據進行GeoHash編碼，生成GeoHashTree，將拐角大于閾值的拐點作為特征點。

3.1.1 數據去噪

去噪是通過對軌跡數據進行預處理，通過如獲取聚類處理結果等方法對軌跡數據中的異常軌跡數據和冗余數據進行過濾，從而排除本身數據問題所帶來的干擾。一般來說，去噪一般可以通過基于中值或均值濾波、Kalman 濾波和基于粒子濾波[15]。

3.1.2 數據分段

分段是指對軌跡進行分段的操作，對原有軌跡進行分段，可以極大提高挖掘效率。軌跡分段可以分為三種分類型：

（1）利用時間間隔分段，表示對長時段軌跡進行合理劃分和標注。

（2）基于軌跡形狀分段，歷史軌跡在變化時與上一軌跡點方向角度的變化大小決定了是否要分段，一旦角度超過了某一零界點，則分段。

（3）基于軌跡實際意義分段，軌跡如果是存在實際停留點，則可作為分段結點。軌跡如果基于出行模式，若軌跡來源用戶交通工具發生改變，則分段。因此，應該考慮軌跡所存在的具體物理意義。

3.1.3 數據壓縮

對于基于時間的軌跡記錄可以采用以秒為計時單元，但由于計算能力、存儲容量等因素的限制，導致軌跡數據挖掘一般無法采用太過精細的位置數據，需要軌跡壓縮來處理數據[16]。軌跡壓縮可以分為離線壓縮方法和在線壓縮方法。對于離線壓縮的方法以軌跡起始點和終點進行連線，如下圖1（a）的P1和P2點連線，找到剩余點到連線的垂直歐氏距離最長的點作為圖1（a）中的P5點，選擇P5作為壓縮點，P1與P5、P10與P5分別連線，在P1-P10之間的點分別尋找所在范圍的歐氏距離最大的點，如果尋找到的點歐式距離達到閾值或以下則停止尋找。

在線壓縮的的方法可以用下圖2表示，P1，P10分別作為軌跡的起終點，從P3開始計算與P1垂直的歐幾里得距離，然后以此計算P4、P5、P6，如果計算P6的距離時發現大于閾值，就將P6，P10作為新的起終點，從P8開始依次計算歐幾里得距離，依次進行下去，直至計算到P10的值也沒有大于閾值時停止壓縮。

J Hershberger等人[17]利用著名的離線壓縮算法Douglas-Peucker算法實現軌跡點批處理模式，但在實際的應用環境時，卻很難批處理軌跡數據的壓縮，當數據量過大時，容易造成失真。在理想環境下的路徑而言，Douglas-Peucker算法是實用的，但因偏差是以垂直歐式距離為準的，當數據軌跡中存在折返路徑，會造成拐角處很容易被壓縮掉，使得壓縮后的軌跡無法正確的反映出軌跡的方向。

3.1.4 地圖匹配

軌跡地圖匹配時結合數據軌跡與數字地圖，將單純的GPS點的原始軌跡數據匹配在地圖數據上能夠更加直觀的反映數據軌跡。軌跡數據因為存在噪聲、信號丟失和數據精度不高等不足，通過將軌跡數據航跡與數字地圖上矢量路徑匹配，找到當前所行駛的路徑，將每一個軌跡數據點映射在地圖上的空間位置，可一定程度上彌補誤差[18]。

4 移動行為感知

4.1 用戶行為挖掘與分析

隨著手機等具有GPS功能的智能設備的普及，從收集的用戶軌跡數據中可以提取到用戶的相關信息，包括用戶個人活動規律喜好等。位置服務可以給用戶提供更加個性化、更便捷的生活方式，提高生活水平。

袁書寒等人錯誤！未找到引用源。通過對用戶軌跡進行分析，可以得到用戶在物理坐標位置下的行為方式，基于分析在各種領域范圍內用戶地理坐標的聚類，計算用戶行為軌跡上的相似性。Jure等人[19]利用MSN用戶的信息驗證了數學領域的“六度空間猜想”，該猜想表明了兩個陌生人間可以通過不超過6個人組成的關系網連接在一起。說明各個體之間的關系網絡看似毫無聯系，實際上可以通過幾個中間網絡關系連接在一起。

Song等人[20]對人類軌跡做了預測的研究，研究表明人類行為具有70%-90%的可預測性。對于人類行為的預測對城市交通管理和對用戶的個人服務推薦具有重要作用。鄭宇等人[21]通過對軌跡數據建模，將相似的位置點聚類形成層次樹，計算各個地區之間的興趣度。可以通過軌跡位置算出的興趣度較大的地區推薦給用戶，從而提高用戶體驗。

4.2 行為預測

用戶使用基于定位服務的軟件或者應用時，網絡中會留下用戶瀏覽痕跡，用戶下次使用軟件時，可以基于用戶當前位置和歷史瀏覽數據為用戶推薦相關信息，給用戶提供更加個性化的推薦。Pentland等人[22]指出人的行為可以被精準得描述為一組由馬爾科夫鏈排列在一起的動態模型（如：Kalman lters）。高衛華等人[23]以馬爾科夫模型和有向圖為基礎，采用MD（Al1.KthMarkov—and-Digraph）模型進行預測，準確度和馬爾科夫模型持平，但是其復雜度低于馬爾科夫模型，并且提出了一種算法—NDLACO算法，該算法是對蟻群算法的改進，根據算法在軌跡尋找過程中釋放的”信息素”等信息，能夠利用螞蟻算法正反饋快速發現較優解、并發性強等特點，并且可以避免算法容易出現停滯、收斂速度慢的特點。

Tseng等人[24]提出了一種型的數據挖掘方法，即SMAP-Mine，該算法能夠發現移動用戶和請求服務相關的順序移動模式。在對用戶行為預測中，Tseng等人使用了基于N-gram模型的SMAR-N-gram算法實現預測功能。George等人[25]使用運動循環、運動軌跡模型以及馬爾科夫鏈模型的預測移動和軌跡的方案，提出了MC/MT模型用于規律性的運動， MC/MT模型預測算法避免了在隨機模型中的復雜計算，降低了處理預測算法所需的計算能力，同時使用馬爾科夫模型處理隨機運動。并且George等人提出對MC/MT模型和馬爾科夫模型進行比較，希望尋找其與隨機因子的作用”交叉”點來研究兩種模型各自的特點。

4.3 智能交通技術

智能交通研究的一個重要的話題是對行駛過程中的車輛進行路徑誘導，為駕駛員提供最優路徑。Balan等人[26]通過對出租車軌跡的分析，可以提前預測兩地之間所需要花費的時間。但由于交通環境存在諸多不確定性，所以最短路徑花費的時間不一定最短。貪心算法可尋找道路兩點之間最短路線[27]，但往往在實際條件下，因為道路交通狀況、駕駛成本、道路等級等原因，貪心算法得到的路徑對于駕駛者來說并不是最優路徑。

Gonzalez等人[28]提出了基于道路信息尋找最優路徑的方法，道路因為等級差異，道路等級越高，可達到的速度越快，不同等級的道路之間又可以劃分為各自的封閉環路。此外，由于路線中有些道路雖然等級較高，但通行的車輛卻不多，因此，Gonzalez對道路等級評定制定了一些相關標準，即道路等級同時取決于道路靜態等級和道路動態特征。

文獻[29]中的算法在路段較長的環境中能夠較好地發揮作用，但對路段較短、起始段和終點端處于同一個道路封閉區域時，跳轉至更高一級路網會浪費更多的時間。鄭宇等人[28]基于出租車駕駛員的經驗的記錄數據，鄭宇等人認為在同一城市內，出租車駕駛員經驗普遍較高，所以可以通過采集出租車軌跡數據作為兩點之間最優路徑。

5 結語

基于移動用戶行為軌跡的收集，產生了海量的數據可供研究分析。但隨著對著世界各地區對自身隱私關注度的不斷提高，避免隱私泄露成為了研究者獲取數據來源的阻力[29]。研究人員如Ratti等人[30]運用收集手機時空行為數據產生的數據群來研究城市結構的變化規律，避免了與個人信息的關聯。對于科學研究與個人隱私沖突問題具有指導價值[31]。

目前，智能交通的運用主要研究方向在駕駛路徑誘導、交通狀況判斷等傳統問題上。隨著物聯網技術的興起和基于社交網絡服務的發展，研究的內容將更有實用性，特別是基于商業活動的個性化推薦和基于共享設備管理等問題的出現給相關研究注入了新的活力。

參考文獻：

[1] 彭曲， 丁治明， 郭黎敏. 基于馬爾可夫鏈的軌跡預測[J]. 計算機科學， 2010， 37（8）： 189-193.

[2] 喬少杰， 韓楠， 李天瑞， 等. 基于前綴投影技術的大規模軌跡預測模型[J]. 軟件學報， 2017， 28（11）： 3043- 3057.

[3] 蒲劍蘇， 屈華民， 倪明選. 移動軌跡數據的可視化[J]. 計算機輔助設計與圖形學學報， 2012， 24（10）：1273- 1282.

[4] 劉震， 付俊輝， 趙楠. 基于移動通信數據的用戶移動軌跡預測方法[J]. 計算機應用與軟件， 2013， 30（2）：10-13.

[5] Wiest J， H?ffken M， Kre?el U， et al. Probabilistic trajectory prediction with gaussian mixture models[C]//Proceedings of Intelligent Vehicles Symposium （IV）， 2012 IEEE. IEEE， 2012： 141-146.

[6] Song C， Qu Z， Blumm N， et al. Limits of Predictability in Human Mobility[C]//Proceedings of American Association for the Advancement of Science， 2010： 1018-1021.

[7] Qiao SJ， Shen D， Wang X， et al. A Self-Adaptive Parameter Selection Trajectory Prediction Approach via Hidden Markov Models[J]. IEEE Transactions on Intelligent Transportation Systems， 2015， 16（1）： 284-296.

[8] 喬少杰， 李天瑞， 韓楠， 等. 大數據環境下移動對象自適應軌跡預測模型[J]. 軟件學報， 2015， 26（11）： 2869-2883.

[9] Shi C， Yan Z， Wang Y， et al. A Genetic Algorithm for Detecting Communities in Large-scale Complex Networks[J]. Advances in Complex Systems， 2010， 13（01）： 3-17.

[10] Xiang L， Jiangshui Z， Jian M， et al. Feature Extraction Algorithm in Consideration of the Trend Changing of Track[J]. Journal of Computer-Aided Design & Computer Graphics， 2016， 28（8）： 1341-1349.