孫 爽,陳 燕,樸在吉,張金松
1.大連海事大學(xué) 航運(yùn)經(jīng)濟(jì)與管理學(xué)院,遼寧 大連116026
2.大連外國語大學(xué) 軟件學(xué)院,遼寧 大連116044
在大數(shù)據(jù)的時(shí)代背景下,軌跡數(shù)據(jù)的多樣性愈發(fā)明顯,在包含時(shí)間、位置、位移、速度等基本信息的前提下又可包括根據(jù)實(shí)際情況的個(gè)性化信息。由于時(shí)空軌跡數(shù)據(jù)是真實(shí)存在的移動(dòng)對象的行為模式,在數(shù)據(jù)處理和計(jì)算過程中可以利用軌跡中含有的時(shí)空序列的特征,但同時(shí)由于傳感器、噪聲和其他因素的差異和影響,軌跡數(shù)據(jù)是永遠(yuǎn)不會完全精確的[1]。各個(gè)交通領(lǐng)域的軌跡數(shù)據(jù)大量存在,有著多方面的應(yīng)用。它包含不同交通個(gè)體泛在的共性的行為模式與移動(dòng)規(guī)律,例如城市車輛出行活動(dòng)特征、人群的移動(dòng)軌跡特征、港口船舶軌跡流的內(nèi)在規(guī)律?;谲壽E數(shù)據(jù)的時(shí)空模式挖掘是大數(shù)據(jù)研究的重要方向,例如路徑推薦、城市交通規(guī)劃、交通路況預(yù)測、安全情報(bào)分析等具體應(yīng)用,對于人類的生產(chǎn)生活有重要的意義。早在2004年新加坡就將出租車的軌跡數(shù)據(jù)應(yīng)用于實(shí)時(shí)的交通監(jiān)控的管理決策中,后續(xù)又用于路徑、交通流監(jiān)控、交通異常檢測等方面[2]。近年來,Zheng[3]針對軌跡數(shù)據(jù)挖掘進(jìn)行了一次全面的調(diào)查,提出了研究框架來深入探討軌跡數(shù)據(jù)時(shí)空模式挖掘的研究領(lǐng)域。Mao等[4]研究基于出租車運(yùn)行軌跡及其在城市通勤模式挖掘中的應(yīng)用,提出了一種從具有大量點(diǎn)位置的出租車軌跡數(shù)據(jù)集中發(fā)現(xiàn)家庭出行時(shí)空模式的新方法,從而了解城市結(jié)構(gòu)和隱含的家庭通勤行為的空間分布和時(shí)間趨勢。Zhang等[5]提出了一種軌跡模式識別方法,采用狀態(tài)轉(zhuǎn)移模型預(yù)測實(shí)時(shí)位置的更新,基于聚類方法識別出人類的日常位置和重要位置,展示了處理位置信息促進(jìn)應(yīng)急管理的潛力。Enami等[6]提出利用大量軌跡數(shù)據(jù)的挖掘與預(yù)測算法,挖掘出時(shí)空軌跡頻繁模式來預(yù)測用戶未來移動(dòng)的方法,掌握移動(dòng)在時(shí)空中的行為。由此可以看出,對于軌跡數(shù)據(jù)進(jìn)行時(shí)空模式挖掘并進(jìn)行管理決策可以從多個(gè)方面為人類提供便利,但是大多數(shù)時(shí)空軌跡模式挖掘?qū)A寇壽E數(shù)據(jù)的挖掘方法、效率和挖掘的范圍都存在著一定的局限性,在軌跡數(shù)據(jù)驅(qū)動(dòng)的時(shí)空模式挖掘與管理決策需求下,本文基于文獻(xiàn)[3]中的框架對基于軌跡數(shù)據(jù)的時(shí)空模式挖掘與管理決策方法進(jìn)行了研究,基于底層軌跡預(yù)處理到軌跡索引與檢索、軌跡模式挖掘,添加了基于軌跡的智能交通管理,位置預(yù)測和服務(wù)推薦模塊都是當(dāng)前研究的熱點(diǎn)。在軌跡數(shù)據(jù)的不同時(shí)空模式挖掘的基礎(chǔ)上發(fā)現(xiàn)對行業(yè)決策有價(jià)值的信息,將人從決策中解放出來,使得決策的主體更趨于多元化,助力決策者做出精準(zhǔn)客觀的決策,在競爭中獲得優(yōu)勢。
本文將從時(shí)空軌跡模式挖掘的需求入手,從時(shí)空軌跡數(shù)據(jù)的預(yù)處理與相似性度量、時(shí)空軌跡模式的挖掘過程及研究現(xiàn)狀、基于時(shí)空軌跡挖掘的管理決策方法及未來發(fā)展趨勢三方面來闡述該領(lǐng)域的現(xiàn)狀和發(fā)展。第一方面,針對數(shù)據(jù)的預(yù)處理進(jìn)行介紹,包括數(shù)據(jù)清洗中的異常點(diǎn)和異常軌跡檢測,以及軌跡壓縮和軌跡分段,接著介紹了軌跡的相似性度量;第二方面,介紹時(shí)空軌跡的模式挖掘,并闡述近幾年該領(lǐng)域的研究情況和存在的問題;最后,闡述現(xiàn)有基于軌跡數(shù)據(jù)的管理決策方法和未來會面臨的挑戰(zhàn)以及發(fā)展趨勢。
時(shí)空軌跡是移動(dòng)對象在空間中隨著時(shí)間變化而形成的,符合大數(shù)據(jù)傳統(tǒng)的3V基本特征[7]。時(shí)空軌跡除包含本身時(shí)間、位置、速度、加速度等內(nèi)在特征外,還可以被賦予語義特征。綜合軌跡位置相關(guān)的天氣數(shù)據(jù)、地形數(shù)據(jù)以及具體應(yīng)用領(lǐng)域的其他信息數(shù)據(jù)即可以得到該軌跡的語義信息,例如軌跡停留段和移動(dòng)段等。時(shí)空軌跡數(shù)據(jù)的原始數(shù)據(jù)有著漂移、中斷與冗余等問題,因此在進(jìn)行研究之前需要進(jìn)行數(shù)據(jù)的預(yù)處理,這是保證研究有效且能夠應(yīng)用于不同領(lǐng)域的必要步驟。
實(shí)際中大部分軌跡數(shù)據(jù)存在著所謂的臟數(shù)據(jù),需要對其進(jìn)行數(shù)據(jù)清洗,這是所有預(yù)處理流程中的共性操作。在原始數(shù)據(jù)中,一些誤差是可以接受的,像通信網(wǎng)絡(luò)中少量位置信號丟失,這樣的誤差可以通過添加保持器等方法修正;另一方面,有些誤差是不可以接受的,需要進(jìn)行剔除,比如嚴(yán)重偏離了軌跡的數(shù)據(jù)和大量重復(fù)的數(shù)據(jù)等。
1.1.1異常點(diǎn)檢測
1980年,Hawkins對異常點(diǎn)做出了定義[8],傳統(tǒng)的異常點(diǎn)檢測算法主要基于四類:統(tǒng)計(jì)、分類、密度和距離[9]。但是在軌跡的異常點(diǎn)檢測中,由于大多數(shù)軌跡數(shù)據(jù)都是基于時(shí)間和空間的位置序列,軌跡中的相鄰點(diǎn)互相有著上下文關(guān)系,這是傳統(tǒng)的異常點(diǎn)檢測方法所忽視的問題。改進(jìn)的傳統(tǒng)異常點(diǎn)檢測算法大部分是根據(jù)特定的軌跡數(shù)據(jù)人工設(shè)置相應(yīng)的參數(shù)和規(guī)則來完成檢測[10-12],存在的主要問題包括:
(1)參數(shù)設(shè)置過程需要大量的人工分析和繁瑣的測試調(diào)整;
(2)參數(shù)閾值難以設(shè)定,方法容易出現(xiàn)漏檢和錯(cuò)檢的情況;
(3)適用于限定類型的軌跡數(shù)據(jù),擴(kuò)展性不強(qiáng);
(4)不能自動(dòng)學(xué)習(xí)異常點(diǎn)存在的差異。
目前,與傳統(tǒng)方法不同的是深度學(xué)習(xí)方法在異常檢測中發(fā)揮了巨大的潛力,可以直接從軌跡大數(shù)據(jù)中自動(dòng)學(xué)習(xí)位置、時(shí)序等特征。Fernando等[13]提出了一個(gè)新的以注意力機(jī)制為基礎(chǔ)的框架來模擬行人流量的監(jiān)控設(shè)置,從而預(yù)測出感興趣行人的未來位置,可以應(yīng)用于具有大量鄰居的真實(shí)場景,將預(yù)測路徑和位置與行人的真實(shí)路徑進(jìn)行對比,來檢測軌跡的異常行為。文獻(xiàn)[14]在長短時(shí)記憶網(wǎng)絡(luò)優(yōu)異的特征學(xué)習(xí)能力的基礎(chǔ)上,提出一種雙向長短時(shí)記憶網(wǎng)絡(luò)(Bi-directional Long Short-Term Memory,Bi-LSTM),對于正常點(diǎn)與其臨近的異常點(diǎn)在運(yùn)動(dòng)特征上的差異能夠自動(dòng)進(jìn)行學(xué)習(xí),檢測的性能顯著優(yōu)于恒定速度閾值法和經(jīng)典機(jī)器學(xué)習(xí)分類法。
1.1.2異常軌跡檢測
軌跡模式挖掘中的異常軌跡檢測技術(shù)為后續(xù)全部挖掘過程提供精準(zhǔn)的數(shù)據(jù)基礎(chǔ),在智能交通與位置推薦等服務(wù)中有廣泛的應(yīng)用。目前的研究主要集中在軌跡空間特征上,不同的研究者針對異常檢測方式有不同的分類規(guī)范,針對不同研究角度和文獻(xiàn)分析,將主流的軌跡異常檢測技術(shù)總結(jié)劃分為以下四類[15-17],如圖1所示。
圖1 時(shí)空軌跡數(shù)據(jù)的異常檢測技術(shù)分類Fig.1 Classification of anomaly detection techniques for spatiotemporal trajectory data
(1)基于統(tǒng)計(jì)分析的異常檢測
統(tǒng)計(jì)分析是異常檢測最早使用的方法,利用某個(gè)統(tǒng)計(jì)分布來對數(shù)據(jù)進(jìn)行建模,正常軌跡分布在高概率區(qū)域,而異常軌跡則分布在概率較低區(qū)域。參數(shù)化統(tǒng)計(jì)分析方法可以快速無監(jiān)督地檢測異常,但是需要對參數(shù)的配置和優(yōu)化狀況進(jìn)行估計(jì);非參數(shù)化統(tǒng)計(jì)方法則不用對數(shù)據(jù)底層分布做假設(shè)。Laxhammar等[18]提出了用于在線學(xué)習(xí)和軌跡異常檢測算法SHNN-CAD,使用統(tǒng)計(jì)學(xué)方法對閾值進(jìn)行矯正來區(qū)分正常與異常軌跡,應(yīng)用一致性方差檢測器來計(jì)算軌跡的統(tǒng)計(jì)置信值。李楠等[19]使用多元回歸模型擬合位置信息特征,得到多維特征表達(dá)式,計(jì)算測試軌跡到多維特征表達(dá)式的距離是否在所確定置信區(qū)間范圍內(nèi),基于統(tǒng)計(jì)學(xué)方法完成對航空器異常軌跡檢測。
(2)基于機(jī)器學(xué)習(xí)的異常檢測
訓(xùn)練與測試兩個(gè)階段是機(jī)器學(xué)習(xí)中基于分類的軌跡異常檢測技術(shù)的核心,包括構(gòu)建分類器和根據(jù)分類器將測試軌跡實(shí)例劃分為正常與異常兩類對象。文獻(xiàn)[20]針對移動(dòng)對象的異常檢測問題提出了ROAM框架,是第一個(gè)在基于離散單元的特征空間中表示軌跡的算法,基于規(guī)則的分類器可以學(xué)習(xí)特定于任何場景的規(guī)則來檢測異常軌跡,但是基于分類的異常檢測方法需要訓(xùn)練的過程。Piciarelli等[21]引入了機(jī)器學(xué)習(xí)中的支持向量機(jī)來檢測軌跡異常,將多特征的軌跡集進(jìn)行聚類分析,對新到軌跡與聚類模型進(jìn)行比較以檢驗(yàn)其是否存在異常。Yin等[22]集成了卷積神經(jīng)網(wǎng)絡(luò)和遞歸自動(dòng)編碼器來進(jìn)行異常檢測,通過兩級滑動(dòng)窗口進(jìn)行低層次的時(shí)間特征提取,對全連通網(wǎng)絡(luò)進(jìn)行分類,提高時(shí)間序列的分類性能和異常檢測效果。
(3)基于距離的異常檢測
基于距離來進(jìn)行軌跡異常檢測的概念是由Knorr等[23]首次提出,用一些軌跡中包含的位置、方向和速度組成的代表性特征來表示軌跡,之后對這些特征的相似性進(jìn)行計(jì)算來檢測異常軌跡。隨著軌跡劃分的提出,針對劃分后的子軌跡中存在的異常檢測,Lee等[24]提出了一種基于分割檢測框架的TRAOD算法,通過粗粒度、細(xì)粒度二級細(xì)分策略將軌跡劃分成線段集,將異常的局部特征所占比例作為判斷標(biāo)準(zhǔn),但該算法不適用于軌跡流的在線異常檢測。Yu等[25]針對軌跡流中異常移動(dòng)對象提出了兩種軌跡近鄰的概念和兩種異常定義,提出一種可擴(kuò)展到大數(shù)據(jù)軌跡流的優(yōu)化MEX策略來檢測新的異常點(diǎn)。
(4)基于網(wǎng)格劃分的異常檢測
軌跡異常研究中,基于網(wǎng)格劃分的軌跡異常檢測技術(shù)被大量工作采用,針對城市路網(wǎng)進(jìn)行劃分,均分成等大小的網(wǎng)格單元后對異常的網(wǎng)格單元序列進(jìn)行檢測。Zhang等[26]基于異常數(shù)據(jù)特征的異常檢測初衷建立了一種基于隔離的異常軌跡檢測方法(isolation-Based Anomalous Trajectory detection method,iBAT),劃分網(wǎng)格后將每條軌跡的軌跡點(diǎn)序列轉(zhuǎn)化成網(wǎng)格序列,得到多個(gè)相同起點(diǎn)和終點(diǎn)的軌跡簇,最后通過隔離機(jī)制檢測出異常軌跡。Wang等[27]提出基于密度的空間聚類(Density-Based Spatial Clustering of Applications with Noise,DBSCAN)方法,采用兩層方法來對船舶航線的異?;顒?dòng)進(jìn)行識別,并利用標(biāo)記數(shù)據(jù)對Hadoop中的學(xué)習(xí)算法進(jìn)行訓(xùn)練。
四種異常軌跡檢測方法的特點(diǎn)總結(jié)如表1所示。
表1 異常軌跡檢測方法比較Table 1 Comparison of anomaly detection methods for trajectory data
軌跡分段是在長時(shí)段軌跡中利用設(shè)定的時(shí)間段或選取一些變化較大的特征點(diǎn)等,進(jìn)行合理切分與標(biāo)注。分段后的軌跡在后續(xù)軌跡挖掘計(jì)算過程中的復(fù)雜度得到了降低,同時(shí)還能夠提供比分段之前更加豐富的規(guī)律和知識,提高存儲的有效性。軌跡分段的三種基本策略包括基于時(shí)間閾值的軌跡分段,劃分基于設(shè)定的時(shí)間段或時(shí)間間隔;基于幾何拓?fù)涞能壽E分段,劃分基于軌跡的特征點(diǎn),如壓縮后保留的點(diǎn)、方向角變化大的點(diǎn)等;基于語義的軌跡分段,劃分基于軌跡的上下文,如停留點(diǎn)、出行模式等[28]。文獻(xiàn)[29]基于軌跡數(shù)據(jù)和道路信息的復(fù)雜性,提出了一種基于概率邏輯的數(shù)據(jù)分割方法(Probabilistic Logic Based Data Segmentation Method,PLDSM),有助于快速查找所有物流運(yùn)輸中的業(yè)務(wù)點(diǎn)。文獻(xiàn)[30]在現(xiàn)有分段方法基礎(chǔ)上,提出了一種無監(jiān)督軌跡分段方法,構(gòu)造了衡量特征距離的損失函數(shù),設(shè)計(jì)元啟發(fā)算法調(diào)整部分參數(shù)權(quán)重來影響構(gòu)建過程,在沒有先驗(yàn)知識前提下實(shí)現(xiàn)軌跡分段。
時(shí)空軌跡中存在的移動(dòng)對象的軌跡點(diǎn)通常采用秒級記錄,每一個(gè)點(diǎn)在軌跡挖掘過程中的重要程度并不相同,大量的軌跡點(diǎn)數(shù)據(jù)加重?cái)?shù)據(jù)庫存儲和工作負(fù)荷,而大部分軌跡數(shù)據(jù)挖掘工作不需要全部位置定位,因此可對軌跡進(jìn)行壓縮來實(shí)現(xiàn)更為簡潔的軌跡表示。在進(jìn)行軌跡壓縮時(shí),通常利用壓縮算法將軌跡簡化,用距離表示壓縮誤差。根據(jù)應(yīng)用場景的不同,軌跡壓縮分為離線壓縮和在線壓縮。離線壓縮主要是從全局的視角,對歷史軌跡數(shù)據(jù)或者靜態(tài)軌跡數(shù)據(jù)中最具代表性的軌跡點(diǎn)進(jìn)行保留,如經(jīng)典Douglas-Peucker算法;在線壓縮主要是從局部的視角,對軌跡中累計(jì)誤差最大的點(diǎn)進(jìn)行保留,因此離線壓縮不適用于所有場景。目前主流的在線壓縮算法有Sliding Window、SQUISH(Spatial Quality Simplification Heuristic)、SPM(Scan-Pick-Move)、TD-TR(Top-Down Time Ratio)等[31-32],作者在文獻(xiàn)[32]中基于Sliding Window和SPM算法進(jìn)行了改進(jìn)和對比,基于的思想是經(jīng)典Sliding Window的逐步壓縮,如圖2所示。
圖2 經(jīng)典滑動(dòng)窗口壓縮算法過程Fig.2 Process of classical sliding window compression algorithm
基于某港口300多條活動(dòng)較為頻繁的船舶連續(xù)1個(gè)月的AIS軌跡運(yùn)行數(shù)據(jù)集,共有1 402 015個(gè)軌跡點(diǎn),為評價(jià)壓縮效果,采用最通用的性能評價(jià)方法,壓縮時(shí)間T、壓縮率R和壓縮誤差E,得到的對比結(jié)果如圖3所示。
圖3 壓縮性能對比Fig.3 Comparison of compression performance
通過比較可以發(fā)現(xiàn),隨著閾值的增大,改進(jìn)算法不僅獲得了更好的壓縮精度,而且在壓縮時(shí)間上比其他算法具有更大的優(yōu)勢,繼承了SPM算法良好的壓縮時(shí)間,軌跡的在線壓縮需要對數(shù)據(jù)進(jìn)行在線分析和處理,因此壓縮時(shí)間越短,算法效果越好,壓縮比的降低使得數(shù)據(jù)存儲成為能夠準(zhǔn)確反映軌跡的特征點(diǎn)。
軌跡處于多維空間中,也是一種特殊的時(shí)序類型,且軌跡中的位置屬于二維數(shù)據(jù),因此針對于時(shí)序數(shù)據(jù)適用的相似性準(zhǔn)則函數(shù),也可以適用于針對軌跡數(shù)據(jù)的相似性度量,例如歐氏距離、DTW(Dynamic Time Warping)、LCSS(Longest Common Subsequence)、CPD(Closest-Pair Distance)、SPD(Sum-of-Pairs Distance)、EDR(Edit Distance on Real sequence)等。
(1)CPD
CPD需要找出兩條軌跡之間距離最小的兩個(gè)點(diǎn)之間的距離,計(jì)算如下:
其中,Dist(loc,loc′)是歐氏距離,這種方法比較容易受到兩條軌跡在某點(diǎn)相交但整體差異較大等局部極端情況的影響。
(2)SPD
SPD針對的是具有相同長度的兩條軌跡,它計(jì)算兩條軌跡中對應(yīng)序號位置點(diǎn)的距離總和,并以該總和距離作為兩條軌跡之間距離的度量,計(jì)算如下:
(3)DTW
DTW針對的是長度不同的兩條軌跡,這樣就存在計(jì)算過程中允許根據(jù)需要將某些位置點(diǎn)重復(fù)使用的情況,基于這種情況可以對齊兩條軌跡之間的所有位置點(diǎn),計(jì)算如下:
其中,|Ta|和|Tb|分別表示軌跡Ta和Tb中的位置點(diǎn)數(shù)目,loc1和loc1′分別表示軌跡Ta和Tb的第一個(gè)位置點(diǎn),Rt(Ta)和Rt(Tb)分別表示在軌跡Ta和Tb中去除第一個(gè)位置點(diǎn)后剩余的軌跡。
(4)LCSS
LCSS的目標(biāo)是減少軌跡中噪聲點(diǎn)對軌跡距離度量的影響,它允許在軌跡距離度量時(shí)忽略掉某些噪聲點(diǎn),找到所有序列中的最長公共子序列,計(jì)算公式如下:
其中,δ和ε分別表示兩個(gè)位置點(diǎn)在x坐標(biāo)和y坐標(biāo)上的相似性閾值。LCSS越大,表明兩條軌跡越相似,相應(yīng)地,基于LCSS方法的兩條軌跡之間的距離可以計(jì)算如下:
(5)EDR
EDR與LCSS類似,忽略掉某些噪聲點(diǎn)的影響,也能解決LCSS對具有相同公共子序列的軌跡無法區(qū)分的情況,計(jì)算公式如下:
軌跡之間的距離度量可以用于軌跡聚類、移動(dòng)對象分析等多個(gè)領(lǐng)域,根據(jù)具體應(yīng)用場景不同選擇最佳距離計(jì)算方法至關(guān)重要。
從軌跡數(shù)據(jù)中挖掘移動(dòng)目標(biāo)的時(shí)空模式,對于理解人群流動(dòng)、動(dòng)物遷徙、智能交通、生態(tài)環(huán)境和城市規(guī)劃中的諸多問題具有重要價(jià)值。一般可根據(jù)軌跡的空間和時(shí)間特性將軌跡模式分為聚集模式、伴隨模式、異常模式、頻繁模式,四種時(shí)空模式挖掘的特點(diǎn)總結(jié)如表2所示。
表2 時(shí)空模式挖掘Table 2 Spatiotemporal pattern mining
在一個(gè)時(shí)空序列中頻繁重復(fù)的路徑[33]被稱為時(shí)空軌跡頻繁模式。時(shí)空軌跡的頻繁模式挖掘可以對應(yīng)于序列的頻繁模式挖掘,但無法簡單地采用傳統(tǒng)序列挖掘方法解決時(shí)空軌跡頻繁模式挖掘問題。
2007年,Giannotti等[34]針對簡單地采用傳統(tǒng)序列挖掘方法無法完全適用的問題,建立了一種序列模式挖掘范式的擴(kuò)展,提出了T模式來提取軌跡數(shù)據(jù)中位置、時(shí)間和語義維度等信息。鄧佳等[35]依托T模式,提出DPTUpdate算法,設(shè)計(jì)蘊(yùn)涵時(shí)空信息的快捷數(shù)據(jù)結(jié)構(gòu),存儲和查詢移動(dòng)物體的T-模式,并提出Prediction算法計(jì)算最佳匹配度,與已有方法相比,其預(yù)測效果有顯著提升,但是只能提取最精細(xì)時(shí)間粒度的模式,忽略了在較粗時(shí)間粒度下可用的潛在模式。因此,Karli等[36]提出了兩種技術(shù),使其應(yīng)用在不同的時(shí)間粒度。譚軍等[37-38]針對數(shù)據(jù)流的頻繁模式挖掘提出一種單遍掃描頻繁模式樹結(jié)構(gòu)FPS-tree,這種結(jié)構(gòu)是在傳統(tǒng)FP-tree[39]基礎(chǔ)上進(jìn)行的改進(jìn)算法,只需要對數(shù)據(jù)流進(jìn)行單遍的掃描就能獲取全部信息,為了滿足滑動(dòng)窗口特征提出了“尾結(jié)點(diǎn)”概念用來保存窗格信息,不用考慮數(shù)據(jù)的分布和項(xiàng)目的順序,具有良好的壓縮性能。2018年,Xia等[40]利用MapReduce發(fā)現(xiàn)隱含的時(shí)空頻繁模式,提出了一種改進(jìn)PFP[41]并行頻繁模式增長(MR-PFP)算法,在Hadoop平臺上利用大規(guī)模出租車軌跡和大量小文件處理策略分析出租車運(yùn)營的時(shí)空特性。頻繁模式挖掘算法比較如表3所示。
表3 頻繁模式挖掘算法比較Table 3 Comparison of frequent pattern mining algorithms
通過挖掘時(shí)空軌跡數(shù)據(jù)中做相似運(yùn)動(dòng)的移動(dòng)群體,可以幫助路線相似的上班族分享停車位,科學(xué)家們通過對伴隨模式的挖掘來對物種遷移進(jìn)行研究。同時(shí),伴隨模式能被應(yīng)用于資源分配、安全管理、傳染病控制等諸多方面。
目前,已有主流的關(guān)于伴隨模式的研究包括以下四種方法[42]:Flock方法,考慮持續(xù)時(shí)間和圓形地理空間內(nèi)的群體時(shí)空約束條件;Convoy方法,定義一種時(shí)空間約束擴(kuò)展Flock;Swarm方法,放寬時(shí)間約束條件擴(kuò)展為不一定連續(xù);Platoon方法,滿足時(shí)間總和、閾值細(xì)化得到局部和全局時(shí)間連續(xù)模式,這些方法主要針對的都是靜態(tài)軌跡流數(shù)據(jù)。李勇男[43]對反恐情報(bào)中的時(shí)空軌跡數(shù)據(jù)進(jìn)行研究,通過對其伴隨模式挖掘,能夠發(fā)現(xiàn)重點(diǎn)人群在特定時(shí)間內(nèi)的移動(dòng)規(guī)律。根據(jù)反恐?jǐn)?shù)據(jù)的特殊性對傳統(tǒng)挖掘方式進(jìn)行改進(jìn),進(jìn)一步提供更深層次的情報(bào)。2017年,朱美玲等[44]基于傳統(tǒng)伴隨模式挖掘,提出Traveling Companion伴隨模式,基于Spark設(shè)計(jì)伴隨發(fā)現(xiàn)算法重新定義了Platoon伴隨模式,同時(shí)提出了點(diǎn)伴隨的概念,降低了計(jì)算復(fù)雜度。2020年,王齊童等[45]針對數(shù)據(jù)量大且空間離散的數(shù)據(jù)設(shè)計(jì)了基于單位步長滑動(dòng)窗口的寬度優(yōu)先搜索算法,同時(shí)設(shè)計(jì)兩層剪枝算法來解決中間結(jié)果過多的問題,提高軌跡挖掘效率。
時(shí)空軌跡數(shù)據(jù)中嚴(yán)重偏離正常模式的行為被稱為時(shí)空軌跡異常模式,挖掘隱藏在時(shí)空數(shù)據(jù)中的異常模式,是軌跡挖掘中不可或缺的一部分,可以在多方面提供良好的決策支持。
2006年,Wu等[46]針對現(xiàn)有的軌跡異常檢測方法側(cè)重于探索軌跡的密度、形狀或特征,即地理空間中的軌跡特征,受自然語言處理中單詞或句子的表示方法的啟發(fā),提出了一種新的基于軌跡表示模型ADTR的軌跡數(shù)據(jù)異常檢測方法。2016年,針對船舶在海洋空間自由移動(dòng)產(chǎn)生的軌跡數(shù)據(jù)增加了海上交通分析和異常行為檢測難度的問題,Lei[47]提出一種有效的自動(dòng)挖掘軌道數(shù)據(jù)和探測異常的方法,利用一個(gè)指標(biāo)對可疑行為進(jìn)行評估,并根據(jù)定義的外圍特征對軌跡行為進(jìn)行評分。實(shí)驗(yàn)結(jié)果表明,所提出的MT-MAD框架能夠有效地檢測海上軌跡中的異常。2018年,Ka?u?ny等[48]描述了一個(gè)行為認(rèn)證系統(tǒng)的實(shí)現(xiàn),該系統(tǒng)處理移動(dòng)設(shè)備以CDR日志形式生成的稀疏地理數(shù)據(jù)。利用基于軌跡的停留提取模型建立用戶移動(dòng)模式,在此基礎(chǔ)上異常檢測模型從地理、時(shí)間和序列三個(gè)維度來度量人類行為的可重復(fù)性。目標(biāo)是測量人類移動(dòng)的地理方面在多大程度上可用于行為生物特征識別系統(tǒng)。
時(shí)空軌跡聚集模式是指一組移動(dòng)對象在一定時(shí)間內(nèi)在特定區(qū)域集聚形成的行為模式,聚集模式挖掘有助于感知、監(jiān)測和預(yù)測日常生活中的非平凡群體事件。
2013年,Zheng等[49]提出了一種適用于大批量電動(dòng)汽車的聚集充電模式。采用遺傳算法獲取聚集模式的隨機(jī)特征參數(shù),并在此基礎(chǔ)上提出了一種基于聚集模式的充電策略,以降低電動(dòng)汽車充電引起的功率波動(dòng)水平。此外,提出了一種可更新的優(yōu)化方法來跟蹤電動(dòng)汽車充電特性的變化。Zheng等[50]提出了Gathering模式,使用線性插值法在挖掘聚集模式中數(shù)據(jù)缺失方面進(jìn)行了改進(jìn)。為了提高挖掘的準(zhǔn)確性和效率,Zhang等[51]提出了一種運(yùn)動(dòng)對象采集模式檢索方法,通過搜索滿足時(shí)空約束的最大完備圖來挖掘聚集模式,從而預(yù)測交通系統(tǒng)中的異常。2020年,He等[52]構(gòu)建MongoDB集群存儲海量軌跡數(shù)據(jù),提出一種基于彈性分布式數(shù)據(jù)集RDDGathering和R-tree索引的并行挖掘算法來發(fā)現(xiàn)海量軌跡數(shù)據(jù)中的聚集模式,解決傳統(tǒng)算法不能有效地分析大規(guī)模軌跡數(shù)據(jù)的問題。
軌跡數(shù)據(jù)獲取技術(shù)的日益普及使得軌跡中豐富的時(shí)間、空間特征和運(yùn)動(dòng)知識被發(fā)現(xiàn),對交通軌跡數(shù)據(jù)的分析在智能交通管理的很多領(lǐng)域取得了相對成熟的管理決策應(yīng)用方向,促進(jìn)了新的應(yīng)用和服務(wù),主要有道路交通區(qū)域劃分、道路交通流量預(yù)測、道路交通擁堵因素挖掘、道路交通流分布模式挖掘、城市道路綜合智能交通系統(tǒng)等。
交通區(qū)域劃分的概念最早由Walinchus提出,用以改善城市交通控制[53]?;谲壽E數(shù)據(jù)的交通子區(qū)域劃分不是直接以交通區(qū)域的地理位置或道路特征作為依據(jù)進(jìn)行劃分[54],而是通過對具有時(shí)空屬性的數(shù)據(jù)進(jìn)行挖掘分析來劃分交通網(wǎng)絡(luò),例如交通車輛的軌跡挖掘。Andrienko等[55]基于軌跡數(shù)據(jù)特征提取方法控制數(shù)據(jù)抽象的總體級別進(jìn)行空間劃分,將軌跡運(yùn)動(dòng)轉(zhuǎn)化為劃分后的類簇之間的運(yùn)動(dòng),并基于聚類中心生成泰森多邊形,實(shí)現(xiàn)交通區(qū)域劃分?;跀?shù)據(jù)挖掘的交通子區(qū)域劃分往往分析歷史軌跡數(shù)據(jù)對當(dāng)前時(shí)段的交通區(qū)域進(jìn)行劃分,然而合理的交通子區(qū)域需在處理復(fù)雜、時(shí)變的交通網(wǎng)絡(luò)條件時(shí)適應(yīng)路網(wǎng)變化,不同時(shí)段如早晚高峰應(yīng)具有特定的交通子區(qū)域劃分方案,來緩解城市交通擁塞問題。為有效劃分交通子區(qū)域,文獻(xiàn)[56]認(rèn)為直接進(jìn)行交通分區(qū)劃分對于交通擁堵的緩解是不充分的,為此設(shè)計(jì)了一種基于多維數(shù)據(jù)點(diǎn)的潛在密集時(shí)間間隔提取算法,將每個(gè)密集時(shí)間間隔的整個(gè)交通網(wǎng)絡(luò)劃分為一組子區(qū)域,進(jìn)而完成整個(gè)交通網(wǎng)絡(luò)的交通子區(qū)域劃分。文獻(xiàn)[57]提出了一種稱為RoadRank的算法來計(jì)算每個(gè)路段的交通量的全局影響分?jǐn)?shù),并根據(jù)它們的總體影響進(jìn)行排序,之后提出了一種基于路網(wǎng)劃分的擴(kuò)展分布式道路等級,實(shí)現(xiàn)道路交通流分布模式挖掘。
基于軌跡挖掘?qū)σ苿?dòng)對象未來的位置和移動(dòng)趨勢進(jìn)行預(yù)測,能夠發(fā)現(xiàn)描述移動(dòng)對象行為有趣而有價(jià)值的知識模式,有效拓展基于位置服務(wù)的應(yīng)用范圍。移動(dòng)對象的位置預(yù)測與推薦服務(wù)對于位置社交網(wǎng)絡(luò)服務(wù)、環(huán)境監(jiān)測、推送服務(wù)、智慧城市建設(shè)等方面具有十分重要的應(yīng)用價(jià)值和學(xué)術(shù)價(jià)值[58-63]。
目前基于軌跡數(shù)據(jù)的位置預(yù)測模型構(gòu)建主要可以分為三類:第一類是關(guān)聯(lián)規(guī)則方法,通過對頻繁項(xiàng)進(jìn)行挖掘構(gòu)造關(guān)聯(lián)規(guī)則,之后進(jìn)行序列匹配來實(shí)現(xiàn)位置預(yù)測。文獻(xiàn)[64]設(shè)計(jì)了一種高效的Traj-PrefixSpan算法和頻繁軌跡匹配算法來改進(jìn)頻繁軌跡模型,對軌跡位置數(shù)據(jù)進(jìn)行挖掘,發(fā)現(xiàn)頻繁軌跡和運(yùn)動(dòng)特征,有效地預(yù)測運(yùn)動(dòng)目標(biāo)的未知位置。第二類是使用馬爾可夫模型,構(gòu)建軌跡轉(zhuǎn)移矩陣,計(jì)算歷史軌跡中一個(gè)位置轉(zhuǎn)移到其他位置的概率,從而進(jìn)行軌跡預(yù)測。文獻(xiàn)[65]提出了一種基于隱馬爾可夫模型的軌跡預(yù)測方法HMTP以及自適應(yīng)參數(shù)選擇算法,代替軌跡模式的切片,預(yù)測運(yùn)動(dòng)目標(biāo)的連續(xù)軌跡。文獻(xiàn)[66]改進(jìn)了低階馬爾可夫預(yù)測精度差的問題,提出一種結(jié)合馬爾可夫模型與軌跡相似度的位置預(yù)測算法,預(yù)測精度得到了顯著的提高。第三類是使用神經(jīng)網(wǎng)絡(luò)方法,通過模型訓(xùn)練和學(xué)習(xí)實(shí)現(xiàn)移動(dòng)位置預(yù)測。文獻(xiàn)[67]基于地理信息訪問地點(diǎn)語義編碼,結(jié)合長短時(shí)記憶網(wǎng)絡(luò)和RNN訓(xùn)練和預(yù)測出租車下一個(gè)下車點(diǎn)坐標(biāo)。除了使用RNN模型,文獻(xiàn)[68]將車輛軌跡建模為二維圖像,提出了多范圍卷積神經(jīng)網(wǎng)絡(luò)框架對多尺度的軌跡建模,根據(jù)交通流的局部空間上下文自動(dòng)選擇局部區(qū)域的最優(yōu)范圍,實(shí)現(xiàn)軌跡位置預(yù)測,更加精準(zhǔn)地對移動(dòng)軌跡的局部空間模式進(jìn)行建模。
移動(dòng)網(wǎng)絡(luò)迅猛發(fā)展背景下,移動(dòng)用戶、用戶的位置和軌跡之間存在著密切的聯(lián)系,基于豐富的軌跡數(shù)據(jù)和序列偏好能夠生成精準(zhǔn)的服務(wù)推薦結(jié)果。在GPS廣泛被接受普及的過程中,基于GPS數(shù)據(jù)的各種服務(wù)應(yīng)用就大量地衍生出來,其中移動(dòng)推薦[69]逐漸成為了研究人員的熱門話題,特別是Zheng等在文獻(xiàn)[70]中介紹了GeoLife社交網(wǎng)絡(luò)服務(wù),基于用戶軌跡挖掘用戶與位置之間的相關(guān)性,生成旅游推薦和個(gè)性化的朋友推薦等服務(wù),推動(dòng)了移動(dòng)對象服務(wù)推薦的研究進(jìn)程。隨著具有豐富語義信息和時(shí)序信息的軌跡數(shù)據(jù)大量涌現(xiàn),產(chǎn)生了明顯不同于傳統(tǒng)的移動(dòng)推薦的挖掘方法,不同的位置節(jié)點(diǎn)和節(jié)點(diǎn)順序都具有不同的語義和影響。因此對軌跡數(shù)據(jù)進(jìn)行更為深度的信息挖掘是針對服務(wù)推薦中不同節(jié)點(diǎn)和節(jié)點(diǎn)順序等問題的核心思想,獲取移動(dòng)對象的時(shí)空語義特征,分析不同強(qiáng)度的關(guān)聯(lián)性,綜合考慮各種時(shí)序特征生成個(gè)性化推薦結(jié)果[71]。在基于軌跡數(shù)據(jù)的移動(dòng)推薦過程中,針對軌跡的時(shí)空上下文[72-73]和序列上下文[74]信息的發(fā)現(xiàn),能夠更有效地在服務(wù)推薦中提供知識發(fā)現(xiàn)。在這兩種上下文信息中,時(shí)空屬性,包括時(shí)間變化、時(shí)空序列等,得到了充分的體現(xiàn)和應(yīng)用。其中,時(shí)空上下文既包括時(shí)間上下文中的時(shí)間屬性,還包括空間上下文的空間屬性,結(jié)合序列上下文信息,能夠基于軌跡數(shù)據(jù)對用戶行為在時(shí)空域上的連續(xù)性進(jìn)行精準(zhǔn)的刻畫,對移動(dòng)對象的真實(shí)活動(dòng)和行為規(guī)律的發(fā)現(xiàn)起到了更為深入的輔助作用?;谲壽E數(shù)據(jù)的管理決策方法的分析和比較如表4所示。
表4 基于軌跡數(shù)據(jù)的管理決策方法Table 4 Management decision methods based on trajectory data
軌跡數(shù)據(jù)模式挖掘在互聯(lián)網(wǎng)發(fā)展進(jìn)步的背景下已經(jīng)得到許多專家學(xué)者的廣泛研究,并且開發(fā)出許多軌跡數(shù)據(jù)模式挖掘的方法。本文將軌跡數(shù)據(jù)清洗、壓縮、分段、相似性度量這四方面作為軌跡模式挖掘的基礎(chǔ)建設(shè),歸納總結(jié)了近年來軌跡數(shù)據(jù)預(yù)處理的主要技術(shù)和算法,重點(diǎn)闡述了異常點(diǎn)和異常軌跡的檢測方法,之后分析了軌跡模式挖掘中的聚集、伴隨、異常、頻繁四種模式的研究進(jìn)展,并延伸了軌跡模式挖掘在智能交通管理、位置預(yù)測和服務(wù)推薦領(lǐng)域中的管理決策方法。但是現(xiàn)有的研究表明,軌跡數(shù)據(jù)的時(shí)空模式挖掘技術(shù)與管理決策方法仍然存在諸多局限性:
(1)大數(shù)據(jù)時(shí)代下,沒有形成一個(gè)完整的、適應(yīng)性強(qiáng)的理論框架和決策模型。
(2)多維時(shí)空粒度下挖掘時(shí)空軌跡模式的方式研究較少,單時(shí)空得到的結(jié)論往往不能夠充分體現(xiàn)與反映移動(dòng)對象的活動(dòng)規(guī)律及模式。
(3)處理海量的時(shí)空軌跡數(shù)據(jù)時(shí),效率低下且算法各方面性能遭遇瓶頸,難以滿足大量時(shí)空軌跡數(shù)據(jù)的挖掘需求。
(4)對數(shù)據(jù)流的實(shí)時(shí)更新進(jìn)行序列模式挖掘的技術(shù)方法不夠成熟。
針對上述四個(gè)問題,本文給出了對應(yīng)的解決思路,以及未來應(yīng)更多地聚焦于為以下幾方面的研究提供思路與方法:
(1)建立基于軌跡數(shù)據(jù)的決策支持系統(tǒng)。利用大數(shù)據(jù)技術(shù)作為系統(tǒng)基礎(chǔ)支撐,將規(guī)模巨大的數(shù)據(jù)集分散到不同服務(wù)器,并且使得系統(tǒng)能夠自學(xué)習(xí)、自計(jì)算。
(2)研究基于多源數(shù)據(jù)、多維時(shí)空的軌跡模式挖掘方法。融合其他領(lǐng)域數(shù)據(jù)來擴(kuò)大軌跡數(shù)據(jù)挖掘的應(yīng)用范圍,研究軌跡數(shù)據(jù)背后的語義信息以及多維時(shí)空的軌跡模式挖掘,將移動(dòng)對象的軌跡所對應(yīng)的時(shí)空信息進(jìn)行層次劃分,融合社交網(wǎng)絡(luò)數(shù)據(jù)等多源數(shù)據(jù)。
(3)建立基于分布式、增量式的軌跡模式挖掘模型。為了規(guī)避由數(shù)據(jù)庫原始數(shù)據(jù)的改變導(dǎo)致的重新挖掘的時(shí)空消耗,適應(yīng)海量軌跡數(shù)據(jù)的挖掘需求,只針對發(fā)生變化的數(shù)據(jù)進(jìn)行部分挖掘,節(jié)省大量計(jì)算開銷并提高適應(yīng)性,以適應(yīng)海量軌跡挖掘需求。
(4)設(shè)計(jì)并行的單遍數(shù)據(jù)集掃描算法。借助目前的一些流式處理框架和并行計(jì)算技術(shù),可以作為軌跡數(shù)據(jù)流實(shí)時(shí)挖掘的基礎(chǔ)。