付 訊 薛麗惠 謝 衛(wèi)

（中國西南電子技術研究所 成都 610036）

1 引言

隨著傳感定位設備的廣泛使用，產(chǎn)生并積累了海量的時空軌跡數(shù)據(jù)，真實記錄了目標在現(xiàn)實世界的活動情況，在一定程度上能夠反應其活動規(guī)律及變化趨勢［1～5］。以目標為中心的歷史時空軌跡數(shù)據(jù)挖掘分析在商業(yè)智能、國家安全等領域有著迫切應用需求［6～9］，推動著時空數(shù)據(jù)挖掘成為近年來的研究熱點問題。目標經(jīng)典航道提取是時空數(shù)據(jù)挖掘的一個典型場景，它從航跡的整體相似性出發(fā)，對航跡進行相似性計算與聚類分析，挖掘目標頻繁使用的軌跡序列。

目前，國內(nèi)外基于歷史數(shù)據(jù)進行經(jīng)典航跡提取的研究主要從以下三大類進行：第一類、基于路網(wǎng)匹配［10～12］，這類算法首先將航跡與道路信息網(wǎng)進行匹配，統(tǒng)計路網(wǎng)中的道路熱度，基于熱度提取經(jīng)典航跡；第二類、基于序列規(guī)則［13～15］，提取航跡駐留點并與現(xiàn)實世界具體位置關聯(lián)，將航跡轉為地理位置的途徑序列，使用序列規(guī)則挖掘算法實現(xiàn)；第三類、基于軌跡聚類分析［16～20］，首先對航跡進行聚類分析，通過特定方法選擇類中某一條航跡作為經(jīng)典航跡。

上述方法在一定程度上實現(xiàn)經(jīng)典航跡提取，但在面向?？漳繕说慕?jīng)典航跡提取仍然存在以下問題：第一、?？漳繕瞬淮嬖陬愃脐懙啬繕说穆肪W(wǎng)信息；第二、相似性與駐留區(qū)域分析依賴經(jīng)驗值，可擴展性不高；第三、面向海量數(shù)據(jù)處理能力不足。對此，本文提出一種經(jīng)典航道提取算法，考慮數(shù)據(jù)的實際分布特征，將經(jīng)典航跡拓展為帶狀區(qū)域的經(jīng)典航道，使得挖掘生成的知識數(shù)據(jù)有一定的容錯性。算法基于MapReduce 編程，通過數(shù)據(jù)預處理、聚類分析、邊界提取等步驟完成經(jīng)典航道提取。

2 問題定義與描述

海量的時空航跡數(shù)據(jù)中蘊含了目標空間活動規(guī)律信息，其主要表現(xiàn)為目標在一段時間范圍內(nèi)或一定任務下，總以相同或者相似的航跡在出發(fā)地與目的地之間反復的出現(xiàn)。通過對這些航跡數(shù)據(jù)的挖掘分析，可輔助實現(xiàn)目標行為異常檢測、任務意圖分析、活動趨勢預測。但在現(xiàn)實的場景下，目標規(guī)律隱藏在海量的原始航跡中，很難直觀地發(fā)現(xiàn)與描述，因此需要設計實現(xiàn)經(jīng)典航跡數(shù)據(jù)的提取算法，輔助分析人員進行知識發(fā)現(xiàn)。

2.1 問題描述

航跡是目標在三維空間中一次運動所產(chǎn)生的空間位置按時間順序排列的點集合，位置點信息一般包括航跡編號、目標名稱、經(jīng)度、緯度、高度、速度、航向、位置時間等要素信息。本文研究對象為ADS-B獲取的目標航跡數(shù)據(jù)。

經(jīng)典航跡則用于描述目標在一段時間范圍內(nèi)或特定任務背景下經(jīng)常使用的航跡，它們在空間上位置相近、形狀相似；由于目標在三維空間活動時其航跡一般都分布在一定的空間范圍內(nèi)的帶狀區(qū)域，因此本文使用帶航道來描述艦機目標頻繁（規(guī)律）路徑。

經(jīng)典航道挖掘可形式化描述如下：一組待處理的原始航跡數(shù)據(jù)集T=｛t1，t2，……，tn｝，其中ti=｛p1，p2，……，pm｝（1 ≤i ≤n）表示集合中某一條航跡，航跡點pi=｛trkNum，name，lon，lat，height，speed，movdir，loctim｝（1 ≤i ≤m）。經(jīng)過航跡預處理生成的航跡段集合Segs=｛L1，L2，……，Lo｝，Li（1 ≤i ≤o）表示一條航跡段；4 航跡聚類結果RS=｛C1，C2，……，Cr｝，Ci（1 ≤i ≤r）表示由若干航跡段組成的類簇，滿足Ci∩Cj=Ф（i≠j）且C1∪C2∪……∪Cr=Segs。經(jīng)典航道生成就是對每一個類簇Ci進行處理，提取其邊界，使得類簇中大多數(shù)航跡位于航道內(nèi)部。

2.2 概念定義

下面給出目標經(jīng)典航道挖掘過程中的涉及到的部分名詞定義。

野值點：由于傳感器誤差原因，導致采集到的目標空間位置點，顯著偏離目標活動的正常值，從而形成航跡數(shù)據(jù)中的野值數(shù)據(jù)。圖1 給出了航跡中常見的野值點分布模式。

圖1 野值點示例

航跡柵格化：柵格在本文指通過使用二分法將地理空間劃分為若干大小相等的網(wǎng)格，網(wǎng)格內(nèi)每個經(jīng)緯度點都有相同的代號，每個劃分后的網(wǎng)格稱之為一個地理柵格。本文采用GeoHash 進行航跡柵格化，從而壓縮數(shù)據(jù)規(guī)模，提高處理效率，表1給出了不同編碼長度下的誤差信息，參考民用航道劃分的標準，本文采用5位GeoHash編碼。

表1 GeoHash精度

航跡相似性：是指兩條航跡在位置向形狀上的相近程度，假設track1 經(jīng)過航跡柵格編碼后的序列為｛str11，str12，……，str1m｝，track2 柵格編碼序列為｛str21，str22，……，str2n｝，track1 與track2 的公共子串為comSegs=｛strc1，strc2，……，strck｝，則航跡相似度計算公式（1），其中n，m分別為兩條航跡的長度。

駐留區(qū)域：指目標過航某一區(qū)域所用時間顯著超過其按照正常速度過航所用時間，這樣的區(qū)域稱之為駐留區(qū)，這些區(qū)域一般是目標的作業(yè)區(qū)域，具有豐富的業(yè)務含義，是目標行為分析時關注的重點。圖2給出了航跡駐留區(qū)域分布模式。

3 經(jīng)典航道提取

本文給出的航道提取算法包括數(shù)據(jù)預處理、航跡聚類、航道生成等步驟。

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

原始航跡中的野值點、駐留區(qū)域數(shù)據(jù)會導致航跡相似性計算結果存在偏差，影響航跡聚類與經(jīng)典航道結果的準確性。為提高航道提取的準確率，需要剔除野值點、分析駐留區(qū)，并基于駐留區(qū)域將原始航跡劃分為若干航跡段，基于劃分結果進行聚類分析及航道提取。下面給出預處理中兩個關鍵步驟的實現(xiàn)邏輯。

1）野值剔除

本文采用一種啟發(fā)式的航跡野值剔除算法，基本思想為：首先，基于背景知識獲取每類目標的最大速度；其次，遍歷每一航跡點，剔除屬性為非法值的航跡點，基于航跡點間距離與時間差計算當前點與后續(xù)三個點的距離、時間差，在此基礎上計算當前點到后續(xù)三個點的速度v1、v2、v3；再次，如果三個速度均為大于知識數(shù)據(jù)給定的值，則判定當前航跡點為異常點，進入下一步循環(huán)。圖3給出了異常值剔除的基本流程。

圖3 野值剔除算法

2）駐留區(qū)域檢測與航跡分段

航跡中的駐留區(qū)域一般分為兩種：單點停留與某區(qū)域內(nèi)反復活動，對于海空艦機目標而言更常見的駐留區(qū)域則是后一種情況，在實際的運動過程中具體表現(xiàn)為在一定的區(qū)域內(nèi)通過跑馬環(huán)線或者八字環(huán)線往復運動。它有一個顯著特征，在駐留區(qū)域每一個點附近都會反復多次經(jīng)過。針對這種情況本文使用一種基于距離的駐留區(qū)檢測方法，算法步驟描述如下：

步驟一：獲取野值剔除后的目標航跡Trajectory并按照位置時間進行升序排列，對航跡中的每一個點采用GeoHash 5 進行編碼處理，生成序列geoHashs。

步驟二：按序獲取geoHashs 的值，對當前值i，如果i后連續(xù)k 個點均落在hashcodei中，第i+k+1 個點落在另一個柵格中，則將這n 個點的柵格信息簡化記錄為，下一次處理從i+k+1開始，從而生成序列dataLst。

步驟三：篩選出datalst 中hashcode 出現(xiàn)頻度大于2 的柵格，合并相同編碼的柵格，記錄其出現(xiàn)頻度，重新計算進入柵格時間與離開柵格時間，其中tin=min（tin1，tin2）、tout=max（tout1，tout2），生成新的數(shù)據(jù)結構放入候選停留柵格stayLst中，并按照出現(xiàn)頻度對stayLst進行降序排列。

步驟四：分隔目標的原始航跡，遍歷原始航跡中的點，如果當前點位置時間落在stayLst中的某個元組的時間區(qū)間，則將其從改點分隔，為前序點集合分配一個航跡段標識，知道Trajectory 中所有航跡點都被處理。

3.2 航跡聚類

航跡聚類是航道提取的一個重要步驟，它從空間相似性出發(fā)，將形狀相似、空間相近的航跡聚成一類。本文基于一種層次聚類算我完成航跡聚類分析。算法實現(xiàn)思路如下：

步驟一：將預處理后的航跡數(shù)據(jù)使用GeoHash編碼算法（編碼長度為5）進行柵格化處理，將航跡點序列轉化為GeoHash 串，降低數(shù)據(jù)維度、提升處理效率。

步驟二：基于最大公共子串思路，采用公式1計算兩兩航跡段之間的相似度，生成各類簇中航跡段的相似度矩陣。

步驟三：引入最小相似度閾值minScore，基于相似度矩陣求解各個航跡段的鄰域組合。

步驟四：對鄰域進行迭代合并，直至類簇不再發(fā)生變化且每個航跡段都被唯一劃分值一個類簇中，其中合并原則為：如果兩個類簇包含相同的航跡段則將其合并為一個類簇。

3.3 航道生成

目標航跡完成聚類分析后形成若干航跡簇，同一類簇中的各個航跡段在形狀與空間上具有相似性，類簇的邊界可大致描述目標在該區(qū)域的活動時所采用的的航道信息。因此可將目標航道提取轉換為求解平面離散點集合的輪廓問題，對此，本文提出一種自適應半徑的基于Delaunay 三角刨分算法的目標航道提取算法。算法步驟描述如下：

步驟一：本算法首先獲取類簇中所有的航跡點，采用GeoHash 6 對航跡點進行稀疏化處理，即落在同一個柵格中的多個航跡點均使用該柵格的中心點去表征，記稀疏化后的點集為S。

步驟二：遍歷S 中各個航跡點，求解每個航跡點離其最近航跡點的距離distance，選擇其中最大值記錄為步驟四邊界判斷的閾值radius。

步驟三：對集合S 中的點按照經(jīng)度、緯度進行升序排列，采用Delaunay 三角刨分算法構造S 的三角刨分網(wǎng)格M。

步驟四：識別M 中的外部邊與外部三角形，并將邊長大于radius 的外部邊edge 放入隊列Q，其中外部邊指僅在一個三角形中存在的邊，外部三角形指包含外部邊的三角形，采用如下方式迭代刪除Q中所有的外部邊：從Q 中取出一條外部邊edge，找到edge 所在的外部三角形T，將edge 從Q 與T 中刪除，將T 從M 中刪除，此時T 中其它兩條邊edge1、edge2均變成外部邊，將其中邊長大于radius的邊放入Q中。

步驟五：識別經(jīng)步驟四處理后的M中所有的外部邊，生成外部邊列表edgeLst，作為目標的活動航道的邊界信息輸出。

通過上述處理步驟，算法可依據(jù)數(shù)據(jù)集分布特征，求解出一個合適的邊界判斷閾值radius，然后基于Delaunay算法完成目標航道邊界提取。

3.4 算法并行化設計

經(jīng)典航道挖掘是從海量的歷史數(shù)據(jù)集中進行，以2020年1至3月為例，某ADS-B系統(tǒng)接收到的航跡數(shù)據(jù)近4 億條航跡點，傳統(tǒng)單機系統(tǒng)很難在短時間內(nèi)處理完如此規(guī)模的數(shù)據(jù)。因此本文設計的算法基于MapReduce 編程模型在大數(shù)據(jù)計算平臺上實現(xiàn)，圖4給出了算法各個關鍵階段的數(shù)據(jù)分治策略。

圖4 并行化流程

其中，在預處理與聚類分析時的柵格化階段由于處理對象是以單條航跡進行的，故以航跡編號作為分組條件；相似度計算與聚類分析是以目標為單位進行的，因此以名稱進行數(shù)據(jù)分組；航道提取階段則以類簇ID為分組條件。

4 實驗評估

本文所提出的目標航道提取方法在阿里云MaxCompute V3.0大數(shù)據(jù)計算平臺上采用Map-Reduce 編程模型實現(xiàn)并驗證。實驗數(shù)據(jù)集為2020年1至3月某ADS-B 系統(tǒng)獲取的近4億條民航航跡數(shù)據(jù)。圖5 給出了算法中各主要環(huán)節(jié)中部分目標的實驗效果圖。

圖6 中（a）圖給出了野值檢測的效果，在算法實現(xiàn)過程中根據(jù)不同目標引入不同的速度閾值，從實驗結果可以看出，本文算法能夠有檢測出航跡中的野值數(shù)據(jù)。（b）圖給出了駐留區(qū)域檢測與航跡分段效果，可發(fā)現(xiàn)本文采用的基于距離與時間閾值的駐留區(qū)算法能夠有效檢測出原始航跡中的駐留區(qū)域。（c）圖與（d）圖給出了目標不同的航跡類簇及基于類簇生成的航道信息，根據(jù)試驗結果可以看出，本文提出的目標聚類與航道邊界提取算法能夠較好地區(qū)分目標的航跡空間特征，形成不同的航跡簇，并且能夠從航跡簇中有效提取出目標航道的邊界信息，從而印證了本文提出算法的有效性。

5 結語

本文針對海量時空航跡數(shù)據(jù)分析處理需求，設計并實現(xiàn)了一種目標經(jīng)典航道挖掘算法，通過數(shù)據(jù)去噪、駐留區(qū)域檢測、航跡分段、相似性計算。實驗結果表明，本文提出的算法能夠有效提取目標的航道特征，在一定程度上解決基于數(shù)據(jù)驅動的知識發(fā)現(xiàn)問題。由于本文僅從航跡數(shù)據(jù)的空間分布特征出發(fā)，未引入業(yè)務場景語義，因此在后續(xù)工作中可考慮多元數(shù)據(jù)關聯(lián)，引入目標行為意圖，分析目標在不同行為意圖下的航跡特征。其次可在本文的基礎上，開展實偵條件下的基于經(jīng)典航道的目標異常行為檢測與動向預測等研究工作。