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

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

關(guān)鍵字：移動行為感知；GPS；軌跡數(shù)據(jù)；行為分析

中圖分類號：TP393.03 文獻(xiàn)標(biāo)識碼：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定位功能的設(shè)備的普及，手機(jī)、平板、車載導(dǎo)航、共享單車等移動設(shè)備進(jìn)入我們的生活并變得日益普及。據(jù)工業(yè)和信息化部統(tǒng)計，截至2018年5月，三家基礎(chǔ)電信公司的手機(jī)用戶總數(shù)接近15億。大城市的手機(jī)普及率接近100%。手機(jī)自帶的位置定位功能在服務(wù)于用戶定位時，通信運(yùn)營商也積累了大量的位置軌跡數(shù)據(jù)。同時，手機(jī)導(dǎo)航作為汽車導(dǎo)航的普遍率很高。艾媒咨詢發(fā)布了“2017-2018中國移動地圖市場研究報告”。根據(jù)該機(jī)構(gòu)的數(shù)據(jù)，截至2017年第四季度，中國的移動地圖用戶數(shù)量已達(dá)到7.07億。

比起基于移動通信數(shù)據(jù)等方法對用戶行為的預(yù)測，基于GPS和移動數(shù)據(jù)的定位軌跡因?yàn)槠渚哂泻Ａ康囊?guī)模、不易受天氣影響和能精準(zhǔn)及時地反饋記錄的坐標(biāo)等特點(diǎn)而具有較大的研究價值和應(yīng)用前景。這些數(shù)據(jù)大大降低了數(shù)據(jù)采集成本，為行駛路徑規(guī)劃、交通流量預(yù)測、城市道路規(guī)劃、共享類交通工具調(diào)度等提供有效數(shù)據(jù)支撐。

1 問題描述

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

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

2 國內(nèi)外研究現(xiàn)狀

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

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

3 軌跡特征提取

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

（1）對軌跡點(diǎn)數(shù)據(jù)的獲取進(jìn)程，因GPS數(shù)據(jù)采集設(shè)施的定位精度等限制，導(dǎo)航中會出現(xiàn)軌跡偏差，故需要提取軌跡特征，來提高在軌跡模型系統(tǒng)匹配的準(zhǔn)確率[10]。

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

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

3.1 數(shù)據(jù)預(yù)處理

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

3.1.1 數(shù)據(jù)去噪

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

3.1.2 數(shù)據(jù)分段

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

（1）利用時間間隔分段，表示對長時段軌跡進(jìn)行合理劃分和標(biāo)注。

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

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

3.1.3 數(shù)據(jù)壓縮

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

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

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

3.1.4 地圖匹配

軌跡地圖匹配時結(jié)合數(shù)據(jù)軌跡與數(shù)字地圖，將單純的GPS點(diǎn)的原始軌跡數(shù)據(jù)匹配在地圖數(shù)據(jù)上能夠更加直觀的反映數(shù)據(jù)軌跡。軌跡數(shù)據(jù)因?yàn)榇嬖谠肼?、信號丟失和數(shù)據(jù)精度不高等不足，通過將軌跡數(shù)據(jù)航跡與數(shù)字地圖上矢量路徑匹配，找到當(dāng)前所行駛的路徑，將每一個軌跡數(shù)據(jù)點(diǎn)映射在地圖上的空間位置，可一定程度上彌補(bǔ)誤差[18]。

4 移動行為感知

4.1 用戶行為挖掘與分析

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

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

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

4.2 行為預(yù)測

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

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

4.3 智能交通技術(shù)

智能交通研究的一個重要的話題是對行駛過程中的車輛進(jìn)行路徑誘導(dǎo)，為駕駛員提供最優(yōu)路徑。Balan等人[26]通過對出租車軌跡的分析，可以提前預(yù)測兩地之間所需要花費(fèi)的時間。但由于交通環(huán)境存在諸多不確定性，所以最短路徑花費(fèi)的時間不一定最短。貪心算法可尋找道路兩點(diǎn)之間最短路線[27]，但往往在實(shí)際條件下，因?yàn)榈缆方煌顩r、駕駛成本、道路等級等原因，貪心算法得到的路徑對于駕駛者來說并不是最優(yōu)路徑。

Gonzalez等人[28]提出了基于道路信息尋找最優(yōu)路徑的方法，道路因?yàn)榈燃壊町悾缆返燃壴礁?，可達(dá)到的速度越快，不同等級的道路之間又可以劃分為各自的封閉環(huán)路。此外，由于路線中有些道路雖然等級較高，但通行的車輛卻不多，因此，Gonzalez對道路等級評定制定了一些相關(guān)標(biāo)準(zhǔn)，即道路等級同時取決于道路靜態(tài)等級和道路動態(tài)特征。

文獻(xiàn)[29]中的算法在路段較長的環(huán)境中能夠較好地發(fā)揮作用，但對路段較短、起始段和終點(diǎn)端處于同一個道路封閉區(qū)域時，跳轉(zhuǎn)至更高一級路網(wǎng)會浪費(fèi)更多的時間。鄭宇等人[28]基于出租車駕駛員的經(jīng)驗(yàn)的記錄數(shù)據(jù)，鄭宇等人認(rèn)為在同一城市內(nèi)，出租車駕駛員經(jīng)驗(yàn)普遍較高，所以可以通過采集出租車軌跡數(shù)據(jù)作為兩點(diǎn)之間最優(yōu)路徑。

5 結(jié)語

基于移動用戶行為軌跡的收集，產(chǎn)生了海量的數(shù)據(jù)可供研究分析。但隨著對著世界各地區(qū)對自身隱私關(guān)注度的不斷提高，避免隱私泄露成為了研究者獲取數(shù)據(jù)來源的阻力[29]。研究人員如Ratti等人[30]運(yùn)用收集手機(jī)時空行為數(shù)據(jù)產(chǎn)生的數(shù)據(jù)群來研究城市結(jié)構(gòu)的變化規(guī)律，避免了與個人信息的關(guān)聯(lián)。對于科學(xué)研究與個人隱私?jīng)_突問題具有指導(dǎo)價值[31]。

目前，智能交通的運(yùn)用主要研究方向在駕駛路徑誘導(dǎo)、交通狀況判斷等傳統(tǒng)問題上。隨著物聯(lián)網(wǎng)技術(shù)的興起和基于社交網(wǎng)絡(luò)服務(wù)的發(fā)展，研究的內(nèi)容將更有實(shí)用性，特別是基于商業(yè)活動的個性化推薦和基于共享設(shè)備管理等問題的出現(xiàn)給相關(guān)研究注入了新的活力。

參考文獻(xiàn)：

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

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

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

[4] 劉震， 付俊輝， 趙楠. 基于移動通信數(shù)據(jù)的用戶移動軌跡預(yù)測方法[J]. 計算機(jī)應(yīng)用與軟件， 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] 喬少杰， 李天瑞， 韓楠， 等. 大數(shù)據(jù)環(huán)境下移動對象自適應(yīng)軌跡預(yù)測模型[J]. 軟件學(xué)報， 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.