康 軍，黃 山，段宗濤，2，李宜修

（1.長(zhǎng)安大學(xué)信息工程學(xué)院，西安 710064；2.陜西省道路交通智能檢測(cè)與裝備工程技術(shù)研究中心，西安 710064）

0 引言

在全球定位、位置感知、移動(dòng)通信和遙感等技術(shù)高速發(fā)展的背景下，時(shí)空軌跡數(shù)據(jù)，如：車輛行駛軌跡、人群移動(dòng)軌跡、動(dòng)物遷徙軌跡等，開(kāi)始大量涌現(xiàn)。時(shí)空軌跡數(shù)據(jù)含位置、時(shí)間、速度等基本信息，其具有時(shí)空序列性、異頻采樣性、數(shù)據(jù)質(zhì)量差的特點(diǎn)［1］，是對(duì)移動(dòng)對(duì)象在時(shí)空環(huán)境下的個(gè)體移動(dòng)和行為歷史的真實(shí)寫照。它不僅蘊(yùn)含著群體對(duì)象泛在的移動(dòng)行為模式與規(guī)律，例如人群的出行活動(dòng)特征、車輛移動(dòng)軌跡特征，還能反映城市交通流演化的內(nèi)在規(guī)律。通過(guò)從海量的時(shí)空軌跡數(shù)據(jù)中發(fā)現(xiàn)這些模式規(guī)律，能夠?yàn)槌鞘幸?guī)劃、交通管理、交通指揮、服務(wù)推薦、位置預(yù)測(cè)等領(lǐng)域提供新的解決思路和建設(shè)性幫助，而這些過(guò)程通常需要通過(guò)對(duì)時(shí)空軌跡數(shù)據(jù)進(jìn)行序列模式挖掘來(lái)得以實(shí)現(xiàn)。

時(shí)空軌跡序列模式挖掘作為序列模式挖掘的一個(gè)重要研究分支，可以定義為從海量的、異構(gòu)的、含噪聲的移動(dòng)全球定位系統(tǒng)（Global Positioning System，GPS）軌跡序列中提取潛在的、頻繁出現(xiàn)的、具有價(jià)值的軌跡序列的過(guò)程。隨著數(shù)據(jù)采集和存儲(chǔ)等技術(shù)的飛速發(fā)展，時(shí)空軌跡數(shù)據(jù)呈指數(shù)級(jí)增長(zhǎng)，出現(xiàn)了“數(shù)據(jù)過(guò)剩，信息匱乏”的局面。在這樣的背景下，很多領(lǐng)域內(nèi)的學(xué)者，都致力于研究和開(kāi)發(fā)相關(guān)時(shí)空軌跡序列模式挖掘算法和應(yīng)用程序，揭示移動(dòng)軌跡數(shù)據(jù)中有價(jià)值的信息。然而在大數(shù)據(jù)的時(shí)代下，各種時(shí)空軌跡數(shù)據(jù)規(guī)模持續(xù)增長(zhǎng)，應(yīng)用需求日趨提升，現(xiàn)有的時(shí)空軌跡數(shù)據(jù)序列模式挖掘方法在對(duì)海量軌跡數(shù)據(jù)進(jìn)行處理時(shí)存在著諸多局限性，如挖掘效率低、適用范圍有限等。該領(lǐng)域亟待突破分布式挖掘算法、針對(duì)實(shí)時(shí)數(shù)據(jù)流的處理算法等關(guān)鍵技術(shù)。

本文將從時(shí)空軌跡序列模式挖掘的需求入手，從時(shí)空軌跡序列的數(shù)據(jù)特征及其應(yīng)用、時(shí)空軌跡序列模式的挖掘過(guò)程及研究現(xiàn)狀、時(shí)空軌跡序列模式挖掘的現(xiàn)有問(wèn)題及未來(lái)發(fā)展趨勢(shì)3個(gè)方面來(lái)闡述該領(lǐng)域的現(xiàn)狀和發(fā)展。在第一方面介紹時(shí)空序列數(shù)據(jù)的基本特點(diǎn)及其典型的應(yīng)用場(chǎng)景；在第二方面介紹時(shí)空軌跡序列模式的挖掘過(guò)程，并闡述近幾年該領(lǐng)域的研究情況；最后闡述現(xiàn)有時(shí)空軌跡序列模式挖掘方法存在的問(wèn)題，指出其未來(lái)的發(fā)展趨勢(shì)。

1 時(shí)空軌跡序列的數(shù)據(jù)特征及其應(yīng)用

1.1 數(shù)據(jù)特征

軌跡序列就是在時(shí)空環(huán)境下，通過(guò)對(duì)一個(gè)或多個(gè)移動(dòng)對(duì)象運(yùn)動(dòng)過(guò)程的采樣所獲得的數(shù)據(jù)信息，包括采樣點(diǎn)位置、時(shí)間、方向、速度等，這些采樣點(diǎn)數(shù)據(jù)信息根據(jù)采樣先后順序排列構(gòu)成的數(shù)據(jù)序列。時(shí)空軌跡數(shù)據(jù)可以通過(guò)帶定位功能的移動(dòng)智能設(shè)備、車載GPS設(shè)備、通信基站、社交媒體、地圖APP等不同方式來(lái)獲取，其來(lái)源多樣復(fù)雜。時(shí)空軌跡數(shù)據(jù)用于分析研究移動(dòng)對(duì)象隨著時(shí)間特性和空間特性的變化而產(chǎn)生的演化規(guī)律，是對(duì)移動(dòng)對(duì)象在時(shí)空環(huán)境下的歷史行為活動(dòng)的真實(shí)寫照。

表1匯總了不同方式下獲取到的幾種典型的時(shí)空軌跡序列數(shù)據(jù)。從表1可以看出，時(shí)空軌跡序列數(shù)據(jù)具有“3V”特性——量大（Volume）、實(shí)時(shí)（Velocity）、多樣（Variety）。此外，移動(dòng)對(duì)象的時(shí)空軌跡數(shù)據(jù)還具備以下特點(diǎn)：

表1 代表性時(shí)空軌跡序列數(shù)據(jù)Tab.1 Representative spatio-temporal trajectory sequence data

1）時(shí)空序列性。軌跡序列是一系列具有位置、時(shí)間信息的采樣點(diǎn)序列，體現(xiàn)了移動(dòng)對(duì)象的時(shí)空動(dòng)態(tài)性。軌跡序列的最基本特性就是時(shí)空序列性。

2）異頻采樣性。不同的移動(dòng)對(duì)象其運(yùn)動(dòng)軌跡的采樣間隔也呈現(xiàn)出顯著的差異。像車輛軌跡、用戶移動(dòng)軌跡、動(dòng)物遷徙軌跡，其更新頻率一般為秒/分鐘級(jí)；而諸如氣溫、氣流、降水的氣象數(shù)據(jù)其更新頻率為由分鐘、小時(shí)到天不等。不同軌跡序列的差異采樣極大影響了軌跡序列模式挖掘的過(guò)程。

3）數(shù)據(jù)質(zhì)量差。移動(dòng)對(duì)象的時(shí)空運(yùn)動(dòng)軌跡是連續(xù)的，軌跡序列則是時(shí)空運(yùn)動(dòng)軌跡的離散化表示形式，但是會(huì)受到GPS設(shè)備采樣精度的影響，當(dāng)某對(duì)象運(yùn)動(dòng)到拐角或突然停止運(yùn)動(dòng)時(shí)，GPS設(shè)備采集到的軌跡點(diǎn)會(huì)出現(xiàn)位置不確定、位置偏離等問(wèn)題，這就給時(shí)空軌跡序列模式挖掘的過(guò)程增加了困難。

綜上所述，時(shí)空軌跡序列數(shù)據(jù)廣泛存在于生活的諸多領(lǐng)域且蘊(yùn)藏著大量的可用信息，但其數(shù)據(jù)特性給時(shí)空軌跡序列模式挖掘帶來(lái)極大的挑戰(zhàn)。

1.2 時(shí)空軌跡序列模式挖掘的應(yīng)用

時(shí)空軌跡序列數(shù)據(jù)蘊(yùn)含著豐富的運(yùn)動(dòng)信息，通過(guò)對(duì)其進(jìn)行序列模式挖掘分析，可從中揭示出有價(jià)值的模式信息來(lái)服務(wù)于社會(huì)。城市規(guī)劃［2-4］、交通管理［5-7］、出行服務(wù)推薦［8-9］、旅游推薦［10-12］、位置預(yù)測(cè)［13-14］和異常軌跡行為檢測(cè)［15-16］等領(lǐng)域已經(jīng)有諸多應(yīng)用，如圖1所示，并深入影響了人們的生活方式。

圖1 時(shí)空軌跡序列模式挖掘應(yīng)用Fig.1 Applicationsof spatio-temporal trajectory sequence pattern mining

1）城市規(guī)劃。群體移動(dòng)對(duì)象的運(yùn)動(dòng)軌跡蘊(yùn)含著其在城市時(shí)空環(huán)境下的行為活動(dòng)模式與規(guī)律，通過(guò)挖掘這種行為模式規(guī)律，有利于揭示城市內(nèi)部的交通流演變規(guī)律、城市不同區(qū)域的社會(huì)功能和熱度特征以及不同移動(dòng)對(duì)象與城市空間的占用關(guān)系，這些信息的發(fā)現(xiàn)能夠?yàn)槌鞘泄部臻g布局、土地利用、基礎(chǔ)設(shè)施建設(shè)等規(guī)劃提供輔助決策，使得城市規(guī)劃更符合城市的地理環(huán)境、人文條件和經(jīng)濟(jì)發(fā)展?fàn)顩r。

2）交通管理。人群和各種車輛是城市交通中最主要的活動(dòng)對(duì)象，其移動(dòng)軌跡數(shù)據(jù)中記錄了人們?nèi)粘３鲂械念l繁歷史路線，這些頻繁軌跡模式的發(fā)現(xiàn)能夠深入了解城市交通流的變化特點(diǎn)，還有助于發(fā)現(xiàn)人群和交通車輛活動(dòng)范圍的交集區(qū)域。這為緩解交通擁堵?tīng)顩r提供了機(jī)會(huì)，使交通管理人員更加合理地設(shè)置交通標(biāo)志、道路交通標(biāo)線及十字路口的紅綠燈等候時(shí)間，為司機(jī)和行人提供更好的交通出行環(huán)境。

3）出行服務(wù)推薦。出租車是人們戶外出行的重要交通工具，而很多時(shí)候人們都面臨著打不到車或者候車時(shí)間較長(zhǎng)的情況。通過(guò)對(duì)海量的出租車軌跡數(shù)據(jù)進(jìn)行分析，挖掘出出租車司機(jī)的經(jīng)驗(yàn)行駛軌跡，發(fā)現(xiàn)出租車的頻繁活動(dòng)區(qū)域，這些信息能夠用于幫助乘客推薦周圍有效的打車地點(diǎn)，從而有效減少乘客的打車等候時(shí)間，提高打車效率。

4）旅游服務(wù)推薦。隨著在線旅游業(yè)的快速發(fā)展，旅游推薦也成為其熱點(diǎn)服務(wù)。海量的用戶移動(dòng)軌跡數(shù)據(jù)反映了他們的歷史活動(dòng)路線。從大量用戶的歷史軌跡數(shù)據(jù)中發(fā)現(xiàn)他們的頻繁移動(dòng)模式，可以揭示出用戶旅游出行的頻繁熱點(diǎn)區(qū)域，其代表了大多數(shù)用戶對(duì)旅游地標(biāo)和路線的偏好，這些信息能夠?yàn)槟切](méi)有明確出行目的的旅客提供參考意見(jiàn)，為其進(jìn)行個(gè)性化的推薦服務(wù)。

5）位置預(yù)測(cè)。移動(dòng)對(duì)象的歷史軌跡數(shù)據(jù)包含了豐富的運(yùn)動(dòng)信息，通過(guò)挖掘出移動(dòng)對(duì)象的歷史頻繁軌跡模式可以找出其行為潛在的時(shí)空規(guī)律性及其行為偏好，再與移動(dòng)對(duì)象當(dāng)前的運(yùn)動(dòng)狀況相結(jié)合，來(lái)分析確定對(duì)象在未來(lái)某個(gè)時(shí)刻或時(shí)間段的運(yùn)動(dòng)趨勢(shì)，這樣做可以有助于趨利避害、合理分配道路資源等。

6）異常軌跡行為檢測(cè)。一個(gè)異常軌跡是在一個(gè)距離度量，例如形狀和旅行時(shí)間上與語(yǔ)料庫(kù)中其他的軌跡有明顯不同的一個(gè)軌跡，或者是軌跡的一部分。這種離群軌跡可能是駕駛司機(jī)的惡意繞道或意外的道路變化（由于交通事故或施工）。通過(guò)頻繁軌跡模式挖掘方法，能夠從軌跡數(shù)據(jù)集中檢測(cè)出軌跡的異常段：如果某一軌跡（或子軌跡）不頻繁，則它可能是一個(gè)異常軌跡。這種異常軌跡的發(fā)現(xiàn)有利于及時(shí)發(fā)現(xiàn)隱患并輔助決策以確保社會(huì)公共環(huán)境的人身和財(cái)產(chǎn)安全。時(shí)空軌跡序列模式挖掘的應(yīng)用并不僅僅局限于上述幾個(gè)領(lǐng)域，隨著位置感知和定位技術(shù)的不斷發(fā)展，人們對(duì)于軌跡模式挖掘的需求越來(lái)越多，應(yīng)用領(lǐng)域也在不斷擴(kuò)大。

2 時(shí)空軌跡序列模式的挖掘過(guò)程及研究現(xiàn)狀

2.1 挖掘過(guò)程

時(shí)空軌跡序列模式挖掘旨在從時(shí)空軌跡數(shù)據(jù)集中找出頻繁出現(xiàn)的序列模式，如普遍性規(guī)律或公共性頻繁路徑等，而從軌跡數(shù)據(jù)中挖掘頻繁的序列模式是一個(gè)多步驟相互鏈接、反復(fù)交互過(guò)程，如圖2所示，指從收集原始軌跡點(diǎn)序列到提供可理解的軌跡模式的所有處理步驟，包括：

1）軌跡預(yù)處理：軌跡數(shù)據(jù)清洗，軌跡分割，軌跡壓縮。

2）軌跡模式挖掘：從軌跡數(shù)據(jù)中發(fā)現(xiàn)頻繁序列模式，挖掘時(shí)空數(shù)據(jù)中隱藏的信息，例如：位置模式（頻繁軌跡、熱點(diǎn)區(qū)域）、活動(dòng)周期模式、語(yǔ)義行為模式。

最重要的預(yù)處理步驟是軌跡分割和軌跡壓縮，因?yàn)轭l繁軌跡模式不僅可能出現(xiàn)在整個(gè)軌跡之間，還可能出現(xiàn)在子軌跡之間［17］。通常采集得到的軌跡數(shù)據(jù)都是以天為單位的、按周期性間隔采樣的連續(xù)點(diǎn)序列，其過(guò)于冗長(zhǎng)無(wú)法直接用于挖掘分析，所以有必要基于特定標(biāo)準(zhǔn)（如時(shí)隙等）將原始軌跡分割為若干短的子軌跡。另一方面，由于移動(dòng)軌跡在空間上的連續(xù)性分布，需要對(duì)其覆蓋的空間區(qū)域進(jìn)行離散化處理，如網(wǎng)格劃分、聚類等，以實(shí)現(xiàn)軌跡壓縮。經(jīng)過(guò)軌跡分割和空區(qū)間域離散化處理可以將原始的細(xì)粒度軌跡點(diǎn)序列轉(zhuǎn)換為諸如網(wǎng)格、區(qū)域或其他形式的粗粒度符號(hào)序列，從而基于序列模式挖掘算法來(lái)發(fā)現(xiàn)頻繁序列模式。

2.2 研究現(xiàn)狀

近年來(lái)，不少專家學(xué)者致力于時(shí)空軌跡序列模式挖掘方法的研究，主要包括三類，即基于時(shí)空軌跡序列的位置模式挖掘、基于時(shí)空軌跡序列的周期模式挖掘和基于時(shí)空軌跡序列的語(yǔ)義模式挖掘，如圖3所示。

圖3 時(shí)空軌跡序列模式挖掘的方法分類Fig.3 Method classification of spatio-temporal trajectory sequence pattern mining

2.2.1 基于時(shí)空軌跡序列的位置模式挖掘

基于時(shí)空軌跡序列的位置模式挖掘是從時(shí)空軌跡數(shù)據(jù)集中發(fā)現(xiàn)頻繁的含位置信息的序列模式，如網(wǎng)格序列、地理區(qū)域序列、路段序列，故基于時(shí)空軌跡序列的位置模式挖掘又可分為基于網(wǎng)格劃分的位置模式挖掘、基于聚類劃分的位置模式挖掘、基于路網(wǎng)匹配的位置模式挖掘。

1）基于網(wǎng)格劃分的位置模式挖掘是將軌跡數(shù)據(jù)覆蓋的區(qū)域劃分為若干個(gè)規(guī)則的網(wǎng)格，以軌跡點(diǎn)所處網(wǎng)格標(biāo)識(shí)軌跡，將冗長(zhǎng)的軌跡點(diǎn)序列轉(zhuǎn)化成簡(jiǎn)潔的網(wǎng)格序列，再基于改進(jìn)的頻繁模式挖掘算法來(lái)發(fā)現(xiàn)反復(fù)出現(xiàn)的網(wǎng)格序列。

Zhang等［18］提出了一種基于時(shí)間、經(jīng)度、緯度三重因素的軌跡定界符將連續(xù)軌跡劃分為不同子軌跡，再對(duì)目標(biāo)區(qū)域進(jìn)行網(wǎng)格劃分，把子軌跡轉(zhuǎn)換為網(wǎng)格序列，通過(guò)Apriori算法來(lái)挖掘頻繁軌跡；Yu［19］首先基于網(wǎng)格劃分將原始軌跡點(diǎn)分配到不同網(wǎng)格中，在此基礎(chǔ)上將網(wǎng)格建模為節(jié)點(diǎn)，將相鄰網(wǎng)格間的交通流建模為具有權(quán)值的邊，構(gòu)建一個(gè)加權(quán)有向圖。然后用一種擴(kuò)展標(biāo)簽傳播算法來(lái)識(shí)別相鄰時(shí)隙內(nèi)有向圖中的移動(dòng)路徑，將每條路徑當(dāng)作一條transaction使用Apriori算法來(lái)挖掘一天內(nèi)不同時(shí)段的頻繁移動(dòng)路徑；Enami等［20］在對(duì)時(shí)空軌跡等時(shí)隙劃分的基礎(chǔ)上，將經(jīng)緯度覆蓋的地理區(qū)域劃分成若干網(wǎng)格，將時(shí)空軌跡轉(zhuǎn)換成具有時(shí)間間隔約束的網(wǎng)格序列，最后分別基于改進(jìn)的Prefixspan和BIDE（BI-Directional Extension paradigm）算法來(lái)挖掘頻繁時(shí)空軌跡，并將結(jié)果用于預(yù)測(cè)未來(lái)的移動(dòng)性。

雖然文獻(xiàn)［18-20］以軌跡點(diǎn)所處的網(wǎng)格離散化軌跡達(dá)到了簡(jiǎn)化軌跡的目的，但是對(duì)于網(wǎng)格大小的劃分沒(méi)有明確標(biāo)準(zhǔn)，并且網(wǎng)格劃分過(guò)程中還存在軌跡點(diǎn)位于網(wǎng)格邊界上而無(wú)法判斷具體歸屬于哪個(gè)網(wǎng)格的問(wèn)題，這些最終都容易導(dǎo)致軌跡模式丟失的情況。為了規(guī)避此問(wèn)題，Wang等［21］提出了一種模糊空間劃分（Vague Space Partition，VSP）方法將研究區(qū)域劃分一組模糊網(wǎng)格單元，并通過(guò)基于距離的隸屬函數(shù)把原始軌跡位置轉(zhuǎn)換為相鄰的模糊網(wǎng)格序列，再提出兩種挖掘算法，即VTPM-PrefixSpan（Vague space partition Trajectory Pattern Mining-PrefixSpan）算 法 和VTPM-GSP（Vague space partition Trajectory Pattern Mining-Generalized Sequential Patterns）算法，以發(fā)現(xiàn)具有嚴(yán)格時(shí)間約束的頻繁軌跡模式；Chen等［22］在此基礎(chǔ)上又提出了一種基于垂直投影距離的網(wǎng)格劃分方法——VGS（Vague Grid Sequence method based on vertical projection distance），根據(jù)垂直投影距離將每個(gè)網(wǎng)格劃分為顯式區(qū)域和模糊區(qū)域；然后將軌跡變換為模糊網(wǎng)格序列；最后提出VGS-PrefixSpan（Vague Grid Sequence method based on vertical projection distance-PrefixSpan）算法，在PrefixSpan算法的基礎(chǔ)上，通過(guò)記錄軌跡序列中項(xiàng)的位置來(lái)減少構(gòu)造投影數(shù)據(jù)庫(kù)的時(shí)間。

2）基于聚類劃分的位置模式挖掘即把目標(biāo)研究區(qū)域聚類為若干不相重疊的區(qū)域，如熱點(diǎn)區(qū)域［23］、停留點(diǎn)區(qū)域［24］，以區(qū)域序列來(lái)表示軌跡，再通過(guò)序列模式挖掘從中挖掘頻繁軌跡模式。文獻(xiàn)［25］先將原始軌跡數(shù)據(jù)所處跨度區(qū)域劃分為若干子區(qū)域，通過(guò)K-means算法將所有子區(qū)域聚類為多個(gè)簇群，并根據(jù)各簇所含軌跡數(shù)以降序排列來(lái)提取熱點(diǎn)簇群，最后從這些熱點(diǎn)簇群中挖掘頻繁軌跡模式；文獻(xiàn)［26］中提出一種基于時(shí)空熱點(diǎn)區(qū)域的移動(dòng)模式挖掘算法FMTPM（Frequent Moving Trajectory Pattern Mining），通過(guò)動(dòng)態(tài)聚類方式提取移動(dòng)軌跡密集時(shí)間區(qū)間，在不同時(shí)間區(qū)間對(duì)軌跡點(diǎn)進(jìn)行聚類劃分以識(shí)別時(shí)空熱點(diǎn)區(qū)域，實(shí)現(xiàn)移動(dòng)軌跡序列向時(shí)空熱點(diǎn)區(qū)域序列的轉(zhuǎn)換；文獻(xiàn)［27］中提出一種基于3D網(wǎng)格的時(shí)空頻繁軌跡挖掘方法，識(shí)別出軌跡數(shù)據(jù)覆蓋范圍內(nèi)的停留區(qū)域，用密度聚類算法將軌跡數(shù)據(jù)轉(zhuǎn)化為停留區(qū)域序列并將其映射到水平坐標(biāo)為經(jīng)緯度空間信息、垂直坐標(biāo)為單一粒度時(shí)間信息的3D網(wǎng)格中，以挖掘頻繁軌跡模式；文獻(xiàn)［28］中提出基于從社交網(wǎng)站提取的用戶軌跡數(shù)據(jù)利用Apriori-like算法發(fā)現(xiàn)頻繁軌跡模式的方法，主要是通過(guò)DBSCAN（Density-Based Spatial Clustering of Applications with Noise）算法識(shí)別出用戶日?；顒?dòng)區(qū)域中的頻繁訪問(wèn)區(qū)域，將原始數(shù)據(jù)轉(zhuǎn)換為時(shí)序排列的頻繁區(qū)域序列來(lái)實(shí)現(xiàn)的。

雖然文獻(xiàn)［25-28］通過(guò)不同的聚類方式來(lái)簡(jiǎn)化原始軌跡序列的表達(dá)形式，縮減軌跡序列的長(zhǎng)度，以降低挖掘過(guò)程的復(fù)雜度；但是聚類算法也存在時(shí)間復(fù)雜度較高的問(wèn)題，同時(shí)對(duì)于各聚類簇內(nèi)部的序列模式并不能很好地挖掘。

3）基于路網(wǎng)匹配的位置模式挖掘是通過(guò)假設(shè)研究對(duì)象被限制在目標(biāo)區(qū)域的相關(guān)道路網(wǎng)絡(luò)上移動(dòng)，通過(guò)路網(wǎng)匹配算法將軌跡點(diǎn)映射到路網(wǎng)中，使其轉(zhuǎn)化為具有路網(wǎng)含義的路段序列，以便于進(jìn)行頻繁軌跡模式挖掘。

文獻(xiàn)［29-31］通過(guò)提取道路網(wǎng)絡(luò)中的關(guān)鍵位置、特征點(diǎn)以表示原始軌跡。王亮等［29］在移動(dòng)過(guò)程模式發(fā)現(xiàn)中，提出了基于移動(dòng)軌跡的路網(wǎng)拓?fù)潢P(guān)系模型構(gòu)建方法，通過(guò)路網(wǎng)關(guān)鍵位置點(diǎn)的探測(cè)抽取拓?fù)潢P(guān)系模型，最后基于空間劃分集合與路網(wǎng)拓?fù)淠Ｐ蛯?duì)原始移動(dòng)軌跡數(shù)據(jù)進(jìn)行序列數(shù)據(jù)轉(zhuǎn)換與頻繁模式挖掘。Wang等［30］研究了道路網(wǎng)絡(luò)中的個(gè)人軌跡頻繁模式挖掘，利用拐角檢測(cè)技術(shù)來(lái)識(shí)別嵌入在個(gè)人GPS軌跡中的物理道路拓?fù)湫畔?，從GPS軌跡中提取特征點(diǎn)，將軌跡變換為道路網(wǎng)絡(luò)中有序的拐角序列，來(lái)挖掘頻繁軌跡。Bermingham等［31］提 出 了 一 種DC-SPAN（Distinct Contiguous Sequential PAtterNs）算法從車輛軌跡中來(lái)挖掘軌跡模式，通過(guò)假設(shè)車輛被限制在研究區(qū)域的相關(guān)道路網(wǎng)絡(luò)上行駛，使用地圖匹配將軌跡映射到路網(wǎng)中，將原始軌跡轉(zhuǎn)換為道路節(jié)點(diǎn)訪問(wèn)序列，以挖掘連續(xù)軌跡模式。

2.2.2 基于時(shí)空軌跡序列的周期模式挖掘

基于時(shí)空軌跡序列的位置模式挖掘更多側(cè)重于發(fā)現(xiàn)移動(dòng)對(duì)象頻繁經(jīng)過(guò)的軌跡路線，然而移動(dòng)對(duì)象的行為在很多時(shí)候還呈現(xiàn)出一定的周期性規(guī)律，即移動(dòng)對(duì)象總是會(huì)在特定時(shí)間間隔內(nèi)或多或少遵循相同的運(yùn)動(dòng)軌跡，例如：鳥(niǎo)類定期的遷徙行為，人們每天按固定的路線上下班，商業(yè)客機(jī)按固定的時(shí)間表從一個(gè)地方到另一個(gè)地方等。對(duì)于這種周期性軌跡模式的發(fā)現(xiàn)同樣很有研究?jī)r(jià)值，可用于壓縮運(yùn)動(dòng)數(shù)據(jù)，預(yù)測(cè)對(duì)象未來(lái)的運(yùn)動(dòng)趨勢(shì)。

文獻(xiàn)［32］中提出了一種基于Traclus的融合軌跡點(diǎn)方向、速度、時(shí)間等時(shí)空語(yǔ)義信息的層次軌跡聚類方法用于時(shí)空周期性模式挖掘，克服了傳統(tǒng)周期模式挖掘方法其忽略了序列和固有層次結(jié)構(gòu)的缺陷，但是未能考慮軌跡點(diǎn)的語(yǔ)義背景信息，同時(shí)也無(wú)法處理不規(guī)則軌跡；文獻(xiàn)［33］針對(duì)［32］算法的缺陷，在從不規(guī)則采樣的時(shí)空軌跡中檢測(cè)參考點(diǎn)時(shí)，綜合考慮所有空間性、時(shí)間性、語(yǔ)義和層次結(jié)構(gòu)，提出一種分層語(yǔ)義周期性模式挖掘方法，以找到分層周期性模式。

Yang等［34］提出一種兩階段方法：階段一，使用運(yùn)動(dòng)參數(shù)對(duì)周期性行為建模；階段二，基于循環(huán)周期模式特點(diǎn)，提出了軌跡距離矩陣搜索算法TDMS（Trajectory Distance Matrix Search）用于識(shí)別周期性軌跡和提取周期軌跡。利用Delaunay三角剖分和逆向地理編碼方法，從收集的周期軌跡中提取運(yùn)動(dòng)位置信息。Shi等［35］提出了一種GPMine（Group Periodic moving pattern Mining）算法用于挖掘群體對(duì)象的周期性運(yùn)動(dòng)模式。文獻(xiàn)［36-37］則研究了周期模式挖掘中面臨不確定性時(shí)空數(shù)據(jù)采樣頻率及數(shù)據(jù)稀疏性的問(wèn)題。

上述的周期模式挖掘方法大都只專注于發(fā)現(xiàn)特定時(shí)空范圍內(nèi)具有不同周期長(zhǎng)度的模式，與固定時(shí)空粒度的周期模式相比，不同時(shí)空粒度下的周期模式則具有更大的實(shí)用價(jià)值，這樣的模式可以更準(zhǔn)確地描述個(gè)人行為。文獻(xiàn)［38］引入多粒度模型來(lái)描述對(duì)象活動(dòng)的時(shí)空信息，并通過(guò)空間優(yōu)先和時(shí)間優(yōu)先的多粒度活動(dòng)發(fā)現(xiàn)算法，來(lái)識(shí)別出不同的粒度下對(duì)象的活動(dòng)行為，最后提出一種多粒度周期性活動(dòng)發(fā)現(xiàn)算法MPAD（Multi-granularity Periodic Activity Discovery）來(lái)挖掘物體活動(dòng)的周期性模式。文獻(xiàn)［39］中提出了一個(gè)發(fā)現(xiàn)具有不同時(shí)空粒度下周期模式的框架：首先通過(guò)軌跡抽象將軌跡點(diǎn)序列轉(zhuǎn)換為具有位置信息的時(shí)間序列；然后，根據(jù)時(shí)空信息定義了一個(gè)多粒度行為模型；最后，提出了SBPM（Single Behavior Period Mining）和MBPM（Muti-Behavior Period Mining）算法，SBPM可以在不知道周期長(zhǎng)度的情況下發(fā)現(xiàn)單個(gè)行為周期模式，MBPM可以從單個(gè)行為模式中識(shí)別多個(gè)行為的周期模式。

2.2.3 基于時(shí)空軌跡序列的語(yǔ)義模式挖掘。

從時(shí)空軌跡序列中挖掘的位置模式和周期性模式往往只能反映移動(dòng)對(duì)象頻繁經(jīng)過(guò)的位置信息或在某些特定時(shí)間內(nèi)反復(fù)遵循的路線，卻無(wú)法捕獲軌跡的語(yǔ)義信息。然而軌跡數(shù)據(jù)所蘊(yùn)含的豐富語(yǔ)義信息，如其所在的場(chǎng)景地理知識(shí)、在某處的行為模式與狀態(tài)等，能更好地反映與體現(xiàn)真實(shí)環(huán)境，通過(guò)從時(shí)空軌跡數(shù)據(jù)集中挖掘出的語(yǔ)義軌跡模式更具有實(shí)際應(yīng)用性。Chen等［40］中定義了一種語(yǔ)義軌跡模式，即具有空間、時(shí)間和語(yǔ)義屬性的移動(dòng)模式。通過(guò)從原始軌跡數(shù)據(jù)中提取出這三種屬性，將其轉(zhuǎn)換為語(yǔ)義軌跡序列，再基于PrefixSpan算法來(lái)發(fā)現(xiàn)語(yǔ)義模式，以預(yù)測(cè)用戶的移動(dòng)行為。Comito等［41］通過(guò)基于密度的聚類算法將GPS軌跡點(diǎn)聚類到具有實(shí)際語(yǔ)義的位置區(qū)域中，實(shí)現(xiàn)軌跡序列到語(yǔ)義位置區(qū)域序列的轉(zhuǎn)換，再運(yùn)用改進(jìn)的PrefixSpan算法來(lái)挖掘轉(zhuǎn)換后具有時(shí)間間隔約束的序列，使其只獲得最大頻繁模式，并將所得結(jié)論用于分析人們的移動(dòng)行為。

文獻(xiàn)［42］中提出了一種基于停留時(shí)間的語(yǔ)義行為模式挖掘方法。先將原始軌跡轉(zhuǎn)化為停留點(diǎn)區(qū)域序列并賦予其實(shí)際的區(qū)域背景信息，構(gòu)建停留語(yǔ)義行為集，再結(jié)合PrefixSpan算法挖掘頻繁語(yǔ)義行為模式，通過(guò)定義語(yǔ)義行為模式之間的相似性度量方法以找出具有相似行為模式的群體移動(dòng)對(duì)象；文獻(xiàn)［43］中提出了SMOPAT（Semantic MObility PATterns）算法來(lái)從私家車軌跡數(shù)據(jù)中挖掘時(shí)空語(yǔ)義移動(dòng)模式，以理解司機(jī)的行為目的；文獻(xiàn)［44］中提出了一種基于語(yǔ)義軌跡模式挖掘的路線推薦系統(tǒng)，該系統(tǒng)通過(guò)從帶有地理標(biāo)簽的照片中提取軌跡，用所需的語(yǔ)義去擴(kuò)展軌跡來(lái)構(gòu)建語(yǔ)義軌跡集并挖掘語(yǔ)義軌跡模式，這些語(yǔ)義軌跡模式將連同用戶的各種需求來(lái)生成一組滿足用戶指定約束和目標(biāo)的語(yǔ)義軌跡路線；文獻(xiàn)［45］中使用豐富的上下文語(yǔ)義注釋擴(kuò)展了從社交媒體獲取的用戶時(shí)空軌跡數(shù)據(jù)，并提出一種語(yǔ)義軌跡模式挖掘算法來(lái)挖掘基本和多維語(yǔ)義軌跡模式以深入理解用戶的移動(dòng)行為模式。

3 時(shí)空軌跡序列模式挖掘的現(xiàn)有問(wèn)題及發(fā)展趨勢(shì)

關(guān)于移動(dòng)對(duì)象的時(shí)空軌跡序列模式挖掘已經(jīng)得到許多專家學(xué)者的廣泛研究，并且開(kāi)發(fā)出許多時(shí)空軌跡序列模式挖掘的方法，然而大部分算法只是從理論上進(jìn)行分析，沒(méi)有投入到實(shí)際應(yīng)用中，適用性也差?，F(xiàn)有的時(shí)空軌跡序列模式挖掘技術(shù)仍然存在諸多局限性，具體包括以下幾個(gè)方面：

1）對(duì)于移動(dòng)時(shí)空軌跡序列模式挖掘的研究沒(méi)有形成一個(gè)完整的、適應(yīng)性強(qiáng)的理論框架和模型，同時(shí)缺乏必要的相關(guān)模式定義、分類方法以及處理流程規(guī)范，沒(méi)有一個(gè)統(tǒng)一的開(kāi)發(fā)平臺(tái)。

2）在實(shí)際的挖掘過(guò)程中，大多數(shù)算法仍然沿用著在單一時(shí)空粒度下挖掘頻繁軌跡模式的方式，這樣得到的結(jié)論往往不能夠充分體現(xiàn)與反映移動(dòng)對(duì)象的活動(dòng)規(guī)律及模式。因此，今后更多的研究工作應(yīng)基于多維時(shí)空粒度來(lái)挖掘時(shí)空頻繁軌跡模式中蘊(yùn)含的群體活動(dòng)規(guī)律語(yǔ)義信息。

3）信息時(shí)代下時(shí)空軌跡數(shù)據(jù)無(wú)時(shí)無(wú)刻不在增加，而現(xiàn)有的研究方法僅僅只是基于移動(dòng)對(duì)象的歷史軌跡數(shù)據(jù)來(lái)進(jìn)行模式挖掘，一旦軌跡數(shù)據(jù)集發(fā)生改變，整個(gè)挖掘過(guò)程將要重新開(kāi)始，這樣會(huì)造成巨大的計(jì)算開(kāi)銷。

4）大數(shù)據(jù)時(shí)代下，時(shí)空軌跡數(shù)據(jù)日益激增，現(xiàn)有的軌跡模式挖掘算法大多都是基于單機(jī)環(huán)境的，在處理海量的時(shí)空軌跡數(shù)據(jù)時(shí)，效率低下且算法各方面性能遭遇瓶頸，難以滿足大量時(shí)空軌跡數(shù)據(jù)的挖掘需求。

5）由于GPS設(shè)備的采樣頻率基本都是秒級(jí)的，因此獲取的時(shí)空軌跡數(shù)據(jù)具有實(shí)時(shí)更新的特性，從而使其呈現(xiàn)出數(shù)據(jù)流式的結(jié)構(gòu)?，F(xiàn)有的對(duì)于實(shí)時(shí)更新的軌跡數(shù)據(jù)流進(jìn)行序列模式挖掘的技術(shù)方法還不夠成熟，基于時(shí)空軌跡數(shù)據(jù)流的序列模式挖掘方法還有待深入研究。

綜上所述，時(shí)空軌跡序列模式挖掘的研究工作今后應(yīng)更多地聚焦于以下幾個(gè)發(fā)面：

1）基于多維時(shí)空粒度的軌跡序列模式挖掘方法。由于時(shí)空信息是移動(dòng)對(duì)象行為活動(dòng)的兩個(gè)最基本屬性，該方法通過(guò)將移動(dòng)對(duì)象的軌跡所對(duì)應(yīng)的時(shí)空信息進(jìn)行層次劃分，形成多維的時(shí)空粒度，再挖掘出移動(dòng)對(duì)象在所有時(shí)空粒度下的頻繁位置模式，從而得到移動(dòng)對(duì)象的活動(dòng)規(guī)律，為位置感知和個(gè)性化位置等服務(wù)提供相應(yīng)的技術(shù)支持。

2）基于增量式的時(shí)空軌跡序列模式挖掘方法。該類方法是專門用于規(guī)避一旦數(shù)據(jù)庫(kù)原始數(shù)據(jù)發(fā)生改變，對(duì)改變后的整個(gè)數(shù)據(jù)集重新挖掘而造成的時(shí)空消耗，其只需要通過(guò)對(duì)變化部分的數(shù)據(jù)挖掘，并在原有所得軌跡序列模式的基礎(chǔ)上進(jìn)行更新就能夠挖掘得到每次數(shù)據(jù)集改變后的軌跡序列模式，從而節(jié)省大量計(jì)算開(kāi)銷，更具靈活性和適應(yīng)性。

3）基于分布式的時(shí)空軌跡序列模式挖掘方法。這類方法旨在通過(guò)將規(guī)模巨大的軌跡數(shù)據(jù)集分散在不同的服務(wù)器上存儲(chǔ)，然后每臺(tái)機(jī)器對(duì)分布在本機(jī)上的數(shù)據(jù)進(jìn)行挖掘，最后將所有機(jī)器的挖掘結(jié)果匯總整合，具體可以借助于并行編程模型如Spark、MapReduce等來(lái)實(shí)現(xiàn)，以適應(yīng)對(duì)于海量軌跡數(shù)據(jù)的挖掘需求。由于整體的工作量是不可預(yù)測(cè)的，因此如何在服務(wù)器之間均勻地分配任務(wù)是非常棘手的。同時(shí)，并行挖掘需要各個(gè)機(jī)器之間的信息交互，通信IO就無(wú)可避免。這些問(wèn)題都將是分布式的軌跡序列模式挖掘方法即將面臨的難題。

4）基于實(shí)時(shí)軌跡數(shù)據(jù)流的模式挖掘方法。軌跡數(shù)據(jù)流是指那些數(shù)據(jù)量非常巨大的，無(wú)法全部存放在存儲(chǔ)介質(zhì)上進(jìn)行分析和計(jì)算的數(shù)據(jù)。其特點(diǎn)是數(shù)據(jù)持續(xù)到達(dá)，且速度快、多變化、規(guī)模宏大；基于實(shí)時(shí)軌跡數(shù)據(jù)流的模式挖掘方法其核心是設(shè)計(jì)高效的單遍數(shù)據(jù)集掃描算法，在一個(gè)遠(yuǎn)小于數(shù)據(jù)規(guī)模的內(nèi)存空間里不斷更新一個(gè)代表數(shù)據(jù)集的結(jié)構(gòu)，使得在任何時(shí)候都能根據(jù)這個(gè)結(jié)構(gòu)迅速挖掘出軌跡序列模式。目前已經(jīng)有了一些流式處理框架如Spark Streaming、Flink、Storm等，所以可以以這些框架為基礎(chǔ)來(lái)設(shè)計(jì)基于軌跡數(shù)據(jù)流的挖掘方法。

4 結(jié)語(yǔ)

時(shí)空軌跡序列模式挖掘是在全球定位技術(shù)與位置感知技術(shù)快速進(jìn)步的背景下催生出的熱門研究領(lǐng)域之一，已經(jīng)成為分析移動(dòng)對(duì)象行為模式規(guī)律的重要手段。為此，各領(lǐng)域業(yè)界人士開(kāi)展廣泛的研究，相繼提出針對(duì)移動(dòng)對(duì)象時(shí)空軌跡的序列模式挖掘方法，主要包括從時(shí)空軌跡數(shù)據(jù)中挖掘位置模式、周期模式和語(yǔ)義模式三類方法，并在城市規(guī)劃、交通管理、服務(wù)推薦等領(lǐng)域取得諸多應(yīng)用。但是隨著GPS采集技術(shù)、位置感知技術(shù)等的不斷完善，時(shí)空軌跡數(shù)據(jù)規(guī)模呈現(xiàn)出爆炸式增長(zhǎng)，現(xiàn)有的技術(shù)方法在算法效率、適應(yīng)性等方面已經(jīng)無(wú)法滿足實(shí)際的應(yīng)用需求。未來(lái)，該領(lǐng)域的研究工作重點(diǎn)可能主要在以下方面：1）基于多維時(shí)空粒度的時(shí)空軌跡序列模式挖掘；2）基于增量式的時(shí)空軌跡序列模式挖掘；3）基于分布式的時(shí)空軌跡序列模式挖掘；4）基于時(shí)空軌跡數(shù)據(jù)流的序列模式挖掘。