時空軌跡序列模式挖掘方法綜述

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

（1.長安大學信息工程學院，西安 710064；2.陜西省道路交通智能檢測與裝備工程技術研究中心，西安 710064）

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

1.2 時空軌跡序列模式挖掘的應用

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

圖1 時空軌跡序列模式挖掘應用Fig.1 Applicationsof spatio-temporal trajectory sequence pattern mining

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

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

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

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

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

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

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

2.1 挖掘過程

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

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

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

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

2.2 研究現(xiàn)狀

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

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

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

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

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

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

雖然文獻［18-20］以軌跡點所處的網(wǎng)格離散化軌跡達到了簡化軌跡的目的，但是對于網(wǎng)格大小的劃分沒有明確標準，并且網(wǎng)格劃分過程中還存在軌跡點位于網(wǎng)格邊界上而無法判斷具體歸屬于哪個網(wǎng)格的問題，這些最終都容易導致軌跡模式丟失的情況。為了規(guī)避此問題，Wang等［21］提出了一種模糊空間劃分（Vague Space Partition，VSP）方法將研究區(qū)域劃分一組模糊網(wǎng)格單元，并通過基于距離的隸屬函數(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)具有嚴格時間約束的頻繁軌跡模式；Chen等［22］在此基礎上又提出了一種基于垂直投影距離的網(wǎng)格劃分方法——VGS（Vague Grid Sequence method based on vertical projection distance），根據(jù)垂直投影距離將每個網(wǎng)格劃分為顯式區(qū)域和模糊區(qū)域；然后將軌跡變換為模糊網(wǎng)格序列；最后提出VGS-PrefixSpan（Vague Grid Sequence method based on vertical projection distance-PrefixSpan）算法，在PrefixSpan算法的基礎上，通過記錄軌跡序列中項的位置來減少構(gòu)造投影數(shù)據(jù)庫的時間。

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

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

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

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

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

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

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

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

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

2.2.3 基于時空軌跡序列的語義模式挖掘。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)語

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