時(shí)空軌跡多維特征融合的行為規(guī)律挖掘算法

姜喬文，劉瑜，*，譚大寧，孫順，董凱，2

1．海軍航空大學(xué) 信息融合研究所，煙臺(tái) 264000

2．中國(guó)電子科學(xué)研究院，北京 100041

隨著雷達(dá)、衛(wèi)星和無(wú)線傳感器網(wǎng)絡(luò)等目標(biāo)定位技術(shù)的迅猛發(fā)展，已經(jīng)基本形成了覆蓋天基、空基、岸基、海上和水下等多層次的傳感器預(yù)警監(jiān)測(cè)體系［1-2］，各種被監(jiān)視目標(biāo)的行為得到了準(zhǔn)確的檢測(cè)、跟蹤和關(guān)聯(lián)，最終以時(shí)空軌跡的形式記錄下來(lái)。海量的時(shí)空軌跡數(shù)據(jù)在預(yù)警監(jiān)視系統(tǒng)中不斷地生成和積累，其中蘊(yùn)含著大量規(guī)律性的信息和知識(shí)。當(dāng)前目標(biāo)監(jiān)視數(shù)據(jù)庫(kù)已經(jīng)初具規(guī)模，但是由于各型傳感器的探測(cè)感知能力有限，在實(shí)際監(jiān)視過(guò)程中獲得的時(shí)空軌跡往往存在采樣率不穩(wěn)定、數(shù)據(jù)多源異質(zhì)等問(wèn)題，這對(duì)于多源探測(cè)數(shù)據(jù)的融合處理帶來(lái)了巨大的挑戰(zhàn)［3］。因此，基于時(shí)空軌跡數(shù)據(jù)多維特征挖掘目標(biāo)行為規(guī)律，分析和預(yù)測(cè)目標(biāo)行為意圖，對(duì)于提升信息質(zhì)量、輔助指揮決策、實(shí)現(xiàn)智能化態(tài)勢(shì)感知具有重要意義。

在時(shí)空軌跡數(shù)據(jù)挖掘領(lǐng)域，通過(guò)對(duì)目標(biāo)海量的歷史軌跡數(shù)據(jù)進(jìn)行相似性度量和聚類分析，可以發(fā)現(xiàn)目標(biāo)在運(yùn)動(dòng)過(guò)程中呈現(xiàn)出的相似性行為模式。近年來(lái)，國(guó)內(nèi)外大量專家學(xué)者在軌跡相似性度量［4-8］和軌跡聚類［9-14］方面進(jìn)行了大量有價(jià)值的研究。周星星等［15］對(duì)經(jīng)典的時(shí)空軌跡相似性度量方法進(jìn)行了總結(jié)和分類，分析了各自優(yōu)缺點(diǎn)和應(yīng)用場(chǎng)景。Liao［16］總結(jié)了時(shí)間序列聚類的概念、距離度量、聚類算法、評(píng)價(jià)方法以及應(yīng)用領(lǐng)域。Zheng［17］系統(tǒng)地綜述了現(xiàn)有的軌跡數(shù)據(jù)挖掘技術(shù)，構(gòu)建了從軌跡數(shù)據(jù)預(yù)處理到軌跡相似性度量再到軌跡聚類的目標(biāo)行為模式挖掘框架，并提供了一些公開(kāi)的軌跡數(shù)據(jù)集。雖然目前時(shí)空軌跡行為規(guī)律挖掘方法的研究已經(jīng)取得了很大進(jìn)展，但是現(xiàn)有研究大部分僅考慮軌跡的空間位置信息，忽略了時(shí)間、航向和速度等多維信息，因而難以區(qū)分空間位置相似但運(yùn)動(dòng)速度和方向不同的行為。Pan 等［18］利用軌跡的位置、航向和速度信息提出了基于多維軌跡特征的行為規(guī)律挖掘算法，但是該算法通過(guò)權(quán)重系數(shù)融合量綱不同的特征信息，存在參數(shù)設(shè)置困難、穩(wěn)定性不強(qiáng)等缺點(diǎn)；除此之外，該算法容易受到軌跡行為分布密度的影響，易造成虛警和漏警。

針對(duì)現(xiàn)有軌跡行為規(guī)律挖掘方法的局限性，本文提出了一種時(shí)空軌跡多維特征融合的行為規(guī)律挖掘算法，通過(guò)軌跡的時(shí)間和空間信息進(jìn)行多維特征融合相似性度量，基于k最近鄰距離和決策圖進(jìn)行軌跡聚類，實(shí)現(xiàn)未知場(chǎng)景下對(duì)目標(biāo)行為規(guī)律的無(wú)監(jiān)督挖掘。

1 時(shí)空軌跡

時(shí)空軌跡數(shù)據(jù)是由若干個(gè)目標(biāo)數(shù)據(jù)點(diǎn)按時(shí)間順序組成的序列。假設(shè)預(yù)警監(jiān)視系統(tǒng)中積累的所有目標(biāo)時(shí)空軌跡數(shù)據(jù)為

式中：TR 表示時(shí)空軌跡數(shù)據(jù)集；i為航跡編號(hào)；n為航跡總條數(shù)；tri表示數(shù)據(jù)集中的第i條時(shí)空軌跡，即

其中：pi，k表示第i條時(shí)空軌跡中的第k個(gè)目標(biāo)信息數(shù)據(jù)點(diǎn)；m表示時(shí)空軌跡tri中信息點(diǎn)總數(shù)。由于各種傳感器的采樣率存在差異，加上偶爾的探測(cè)數(shù)據(jù)缺失，因此在不同的時(shí)空軌跡中，即使是運(yùn)動(dòng)模式相似的軌跡，信息點(diǎn)總數(shù)通常也并不相同。

pi，k是一個(gè)含有多維信息的目標(biāo)數(shù)據(jù)點(diǎn)，其中至少包含探測(cè)時(shí)刻ti，k和目標(biāo)位置li，k這2個(gè)重要信息，ti，k＜ti，k+1，li，k為二維平面上或三維空間中的一個(gè)點(diǎn)。除此之外，根據(jù)傳感器的探測(cè)感知能力差異，其中還可能包含在該時(shí)刻目標(biāo)的航向θi，k、速度vi，k、加速度ai，k等特征，可以將其表達(dá)為一個(gè)多維向量［18］：

對(duì)于僅含有ti，k和li，k信息的時(shí)空軌跡，既 可以把它理解為帶有時(shí)間標(biāo)記的空間序列，也可以理解為帶有空間標(biāo)記的時(shí)間序列［19］。Hung 等［20］將時(shí)空軌跡視為一種時(shí)空棱柱結(jié)構(gòu)，例如一個(gè)在二維平面上運(yùn)動(dòng)的目標(biāo)，X軸和Y軸構(gòu)成的平面為其位置空間，li，k中的位置信息為(xi，k，yi，k)，T軸表示其時(shí)間信息，那么它的時(shí)空軌跡tri在XY平面上的投影即為位置信息點(diǎn)li，k構(gòu)成的軌跡曲線，如圖1 所示。

圖1 時(shí)空軌跡示意圖Fig.1 Schematic diagram of space-time trajectory

2 時(shí)空Hausdorff 距離

2.1 時(shí)空軌跡相似性度量

在時(shí)空軌跡數(shù)據(jù)挖掘中，相似性度量是一個(gè)非常關(guān)鍵的過(guò)程，決定著后續(xù)軌跡聚類結(jié)果的好壞。軌跡間的相似性度量方法是通過(guò)衡量不同軌跡在空間上的遠(yuǎn)近程度來(lái)判斷是否相似，由于目標(biāo)行為規(guī)律挖掘的應(yīng)用場(chǎng)景和目的需求的不同，相似性度量算法對(duì)于軌跡間的匹配度有著不同的解釋。目前應(yīng)用廣泛的方法主要有基于歐式距離 （Euclidean Distance， ED）的相似性度量［4］、編輯距離［5］（Edit Distance on Real sequence， EDR）、豪斯多夫距離［6］（Hausdorff Distance，HD）、最長(zhǎng)公共子序列［7］（Longest Common Sub-Sequence， LCSS）、動(dòng)態(tài)時(shí)間歸整［8］（Dynamic Time Warping， DTW）等以及其改進(jìn)算法。Agrawal 和Swami［21］運(yùn)用歐氏距離來(lái)計(jì)算軌跡對(duì)應(yīng)點(diǎn)的相似程度，其優(yōu)點(diǎn)在于計(jì)算簡(jiǎn)單，復(fù)雜度只有O（n），但要求軌跡的采樣率和點(diǎn)數(shù)量一致，在實(shí)際應(yīng)用中幾乎無(wú)法滿足條件。魏龍翔等［22］結(jié)合Hausdorff 距離和LCSS 同時(shí)利用軌跡的位置信息和方向信息進(jìn)行相似性度量。Li等［23］針對(duì)DTW 算法在距離度量使存在過(guò)度拉伸和壓縮的問(wèn)題，通過(guò)引入懲罰函數(shù)提出了一種自適應(yīng)約束DTW 算法，可以自適應(yīng)的調(diào)整時(shí)空軌跡間的對(duì)應(yīng)關(guān)系。Lee 等［24］改進(jìn)了歐氏距離的相似性度量方法，提出了水平、垂直以及角距離等多個(gè)維度融合的Hausdorff 距離度量算法。

不同于勻速直線運(yùn)動(dòng)、加速直線運(yùn)動(dòng)、轉(zhuǎn)向等簡(jiǎn)單的、可以模型化的目標(biāo)局部行為模式，本文的行為規(guī)律是指目標(biāo)根據(jù)其本身特性和運(yùn)動(dòng)目的在某一時(shí)段、某一區(qū)域呈現(xiàn)出的全局運(yùn)動(dòng)特點(diǎn)。例如在空管交通中，軍用飛行器和民用飛機(jī)由于性質(zhì)和運(yùn)動(dòng)目的不同，在同一區(qū)域的全局運(yùn)動(dòng)軌跡和運(yùn)動(dòng)方式呈現(xiàn)出不同的模式，這就需要綜合利用時(shí)空軌跡的多維特征來(lái)進(jìn)行相似性度量。然而目前大部分度量算法僅考慮軌跡的空間位置信息，忽略了時(shí)間、航向和速度等多維信息，導(dǎo)致后續(xù)的聚類算法無(wú)法挖掘出空間位置相似但運(yùn)動(dòng)速度和方向不同的行為，于是本節(jié)提出了時(shí)空Hausdorff 距離來(lái)解決這一問(wèn)題。

2.2 多維特征融合的相似性度量

Hausdorff 距離是描述2 個(gè)集合之間相似性的度量方法，可以用來(lái)度量軌跡間的相似性。優(yōu)點(diǎn)在于不要求軌跡的采樣率和點(diǎn)數(shù)量一致，可以度量整條軌跡的全局特征，當(dāng)軌跡不完整時(shí)依然可以很好地進(jìn)行相似性度量，具有較強(qiáng)的魯棒性［25］。對(duì)于時(shí)空軌跡tri和trj，Hausdorff 距離 的意義為tri中的位置信息點(diǎn)到trj中的位置信息點(diǎn)的最近距離中的最大值，定義tri到trj的定向Hausdorff 距離為

式中：{dist(li，k，lj，k)}表示2點(diǎn)之間的歐氏距離。以二維空間為例，

軌跡tri和trj的定向Hausdorff 距離h(tri，trj)如圖2 所示。

圖2 定向Hausdorff 距離示意圖Fig.2 Schematic diagram of Hausdorff distance

通常情況下，采用雙向Hausdorff 距離來(lái)定義相似度：

針對(duì)Hausdorff 距離只能度量軌跡位置特征而忽略速度、航向特征的問(wèn)題，Pan 等提出了多因素Hausdorff距離［18］（Multi-Factor Hausdorff Distance，MFHD），同時(shí)考慮了軌跡的位置、速度以及航向信息，用多因素距離mfdist(pi，k，pj，k)代替歐氏距離來(lái)度量軌跡的多維特征相似度。

式中：wd、wv、wθ分別為位置、速度和航向信息的權(quán)重因子，權(quán)重因子的選擇取決于應(yīng)用場(chǎng)景，滿足條件

然而，由于距離、速度和航向是量綱完全不同的信息，因此MFHD 很難確定一組行之有效的參數(shù)，存在一定的局限性。

事實(shí)上，目標(biāo)在運(yùn)動(dòng)過(guò)程中的位置信息是目標(biāo)的速度、航向等特征在時(shí)間上積累的結(jié)果，僅利用時(shí)間和位置信息即可很好地反映出目標(biāo)在速度、航向等多維特征上的差異。因此考慮引入時(shí)空軌跡中的時(shí)間信息，通過(guò)構(gòu)造時(shí)間滑窗，定義時(shí)空Hausdorff 距離（Spatio-Temporal Hausdorff Distance， STHD），由局部到整體逐步對(duì)時(shí)空軌跡進(jìn)行相似性度量，利用時(shí)間積累后所有滑窗中最大的Hausdorff 距離來(lái)度量多維特征差異。時(shí)空Hausdorff 距離主要通過(guò)以下3 個(gè)步驟來(lái)構(gòu)造：

步驟1確定時(shí)間滑窗長(zhǎng)度τ。τ由參數(shù)ξ決定，ξ表示期望每個(gè)時(shí)間窗中信息數(shù)據(jù)點(diǎn)的個(gè)數(shù)。定義時(shí)間滑窗長(zhǎng)度

步驟2根據(jù)滑動(dòng)窗口長(zhǎng)度τ對(duì)軌跡進(jìn)行分段。若最后一段軌跡的時(shí)間不足一個(gè)滑窗長(zhǎng)度τ，依然按照一個(gè)滑窗長(zhǎng)度τ分段。分段后的時(shí)空軌跡tri和trj表示為

式中：tri，k和trj，k分別表示時(shí)空軌跡tri和trj中第k個(gè)時(shí)間窗中的軌跡段；M和N分別表示時(shí)空軌跡tri和trj中軌跡段的總數(shù)。

按時(shí)間順序計(jì)算時(shí)空軌跡中2 個(gè)對(duì)應(yīng)時(shí)間窗口中軌跡段的雙向Hausdorff 距離H(tri，k，trj，k)，直到其中一個(gè)軌跡的時(shí)間滑窗終止。

步驟3計(jì)算時(shí)空軌跡tri和trj之間的時(shí)空Hausdorff 距離

這樣就可以僅通過(guò)一個(gè)距離實(shí)現(xiàn)時(shí)空軌跡位置、航向以及速度等多維特征融合的相似性度量，同時(shí)也解決了多源時(shí)空軌跡數(shù)據(jù)采樣率不穩(wěn)定、數(shù)據(jù)多源異質(zhì)等問(wèn)題。

通過(guò)圖3 中可以直觀地看出，由于時(shí)間信息的引入，相比于Hausdorff 距離，對(duì)于位置相近而航向和速度不同的軌跡具有很好地區(qū)分度。

圖3 時(shí)空Hausdorff 距離示意圖Fig.3 Schematic diagram of STHD

3 多維特征融合的時(shí)空軌跡聚類

3.1 軌跡聚類

軌跡聚類是指通過(guò)最大化或最小化類內(nèi)的相似性原則把軌跡數(shù)據(jù)集合分組為多個(gè)類或簇，同時(shí)用顯式或隱式方法描述不同類或簇的過(guò)程，是軌跡數(shù)據(jù)挖掘的重要手段，對(duì)于揭示運(yùn)動(dòng)目標(biāo)行為模式、偵查預(yù)警監(jiān)視以及區(qū)域態(tài)勢(shì)感知具有重要意義。目前軌跡聚類采用的主流算法包括K-means［9］、K-Medoids［10］、基于密度的帶噪聲的聚類方法［11］（Density-Based Spatial Clustering of Applications with Noise， DBSCAN）、密度峰值聚類［12］（Density Peaks Clustering， DPC） 、譜 聚 類［13］（Spectral Clustering）等 以 及其改進(jìn)算法。K-means 和K-medoids 算法簡(jiǎn)單易于實(shí)現(xiàn)，但是需要提前設(shè)置聚類參數(shù)，且迭代運(yùn)算耗時(shí)過(guò)長(zhǎng)。Wen 等［25］采用非參數(shù)統(tǒng)計(jì)方法核密度估計(jì)（Kernal Density Estimation， KDE），通過(guò)選取合適的核函數(shù)和滑動(dòng)窗口自適應(yīng)地解決軌跡聚類中存在的未知情況，但是選取核函數(shù)往往需要借鑒經(jīng)驗(yàn)和專家系統(tǒng)。李旭東和成烽［26］基于密度峰值聚類，將密度峰值聚類中心作為經(jīng)典軌跡，使挖掘出軌跡行為真實(shí)自然，但是該方法中截?cái)嗑嚯x的選擇較為困難。Pan等［18］基于密度聚類的思想，利用MFHD 作為軌跡間的多維度相似性度量，提出了一種多維航跡聚類算法MTCA，但是該算法需要設(shè)置鄰域半徑ε和最小近鄰航跡數(shù)量MinTRs，對(duì)于密度分布均勻的軌跡數(shù)據(jù)具有良好的效果，但是在目標(biāo)行為模式分布不均勻的復(fù)雜數(shù)據(jù)集中存在虛警和漏警的問(wèn)題。

3.2 時(shí)空軌跡k 最近鄰決策聚類

密度峰值聚類［12］是近幾年比較熱門(mén)的聚類算法，該算法能夠通過(guò)快速地搜索和發(fā)現(xiàn)密度峰值從而自動(dòng)地發(fā)現(xiàn)簇中心，實(shí)現(xiàn)任意形狀數(shù)據(jù)的高效聚類，在軌跡數(shù)據(jù)挖掘中得到了應(yīng)用，但算法中截?cái)嗑嚯x的設(shè)定比較困難，并不能很好地適用于不同場(chǎng)景中。針對(duì)這一問(wèn)題，我利用k最近鄰思想，與密度峰值聚類中的決策圖相結(jié)合，通過(guò)正整數(shù)參數(shù)k確定k最近鄰距離，避免了截?cái)嗑嚯x參數(shù)的設(shè)定，同時(shí)采用時(shí)空Hausdorff 距離作為相似性度量，提出了多維特征融合的時(shí)空軌跡聚類算法（Spatio-Temporal Trajectory Clustering Algorithm， STTCA）。

首先介紹STTCA 的相關(guān)定義：

定義1在時(shí)空軌跡數(shù)據(jù)庫(kù)TR 中，對(duì)于某一條時(shí)空軌跡tri，與之時(shí)空Hausdorff 距離第k近的時(shí)空軌跡定義為tri的k最近鄰時(shí)空軌跡（k-Nearest Spatio-Temporal Trajectory），記 為NSTT(tri，k)。

定義2時(shí)空軌跡tri與它的k最近鄰時(shí)空軌跡的時(shí)空Hausdorff 距離定義為k最近時(shí)空Hausdorff 距離（k-Nearest Spatio-Temporal Hausdorff distance），記為

定義3定義最小k最近鄰時(shí)空軌跡Hausdorff 距離

即在k最近時(shí)空Hausdorff 距離小于tri的所有時(shí)空軌跡中，與tri時(shí)空Hausdorff 距離最小的距離。特殊地，對(duì)于k最近時(shí)空Hausdorff 距離最小的那條時(shí)空軌跡，設(shè)置δ=max(STHD(tri，trj))。因此，只有那些k最近時(shí)空Hausdorff 距離小的軌跡，其最小k最近鄰時(shí)空軌跡Hausdorff 距離才會(huì)遠(yuǎn)超正常值。

定義4以k最近時(shí)空Hausdorff 距離λi為橫軸，最小k最近鄰時(shí)空軌跡Hausdorff 距離δi為縱軸繪制出的散點(diǎn)圖稱為決策圖。

定義5將最小k最近鄰時(shí)空軌跡Hausdorff距離δi與k最近時(shí)空Hausdorff 距離λi的比值定義為決策值

式中：γi是進(jìn)行聚類中心決策的重要參數(shù)。

定義6對(duì)于λi很大，即位于決策圖靠右側(cè)的軌跡，通過(guò)閾值THabnormal過(guò)濾，超過(guò)閾值的軌跡定義為異常軌跡。

定義7對(duì)于γi很大的軌跡，通過(guò)閾值THcenter決策，超過(guò)閾值的軌跡定義為中心軌跡。

定義8聚類完成后，對(duì)于某一時(shí)空軌跡tri，若它本身屬于某一簇，但在其k最近時(shí)空Hausdorff 距離范圍內(nèi)存在屬于其他簇的軌跡，那么定義其為可疑軌跡，屬于異常軌跡的一種。

STTCA 算法流程如圖4 所示，主要分為5 個(gè)步驟：

圖4 STTCA 算法流程圖Fig.4 Flow chart of STTCA algorithm

步驟1（軌跡相似性度量）計(jì)算時(shí)空軌跡數(shù)據(jù)庫(kù)TR 中所有軌跡之間時(shí)空Hausdorff 距離，得到時(shí)空軌跡相似度矩陣。

步驟2（異常軌跡剔除）對(duì)時(shí)空軌跡數(shù)據(jù)庫(kù)TR 中所有軌跡tri計(jì)算k最近時(shí)空Hausdorff 距離λi和與最小k最近鄰時(shí)空軌跡Hausdorff 距離δi，以λi為橫軸，δi為縱軸繪制出決策圖，通過(guò)觀察決策圖中特征點(diǎn)的分布，在特征點(diǎn)密度很小的位置設(shè)定閾值THabnormal，λi大于該閾值的軌跡判定為異常軌跡，進(jìn)行剔除。

步驟3（確定中心軌跡）計(jì)算決策值γi并按照降序排列，觀察中心軌跡過(guò)渡到非中心軌跡的跳躍點(diǎn)，設(shè)定閾值THcenter，決策值大于閾值可判定為中心軌跡，從而確定軌跡簇個(gè)數(shù)。

步驟4（軌跡聚類）將剔除異常軌跡后剩余的軌跡進(jìn)行分配。分配時(shí)，按照k最近鄰時(shí)空軌跡Hausdorff 距離λi從小到大的順序進(jìn)行，將每條軌跡分配到k最近時(shí)空Hausdorff 距離比它小的軌跡中且與它時(shí)空Hausdorff 距離最近的軌跡所在的簇。

步驟5（可疑軌跡檢測(cè)）對(duì)分配后的結(jié)果進(jìn)行可疑軌跡檢測(cè)，完成最終的目標(biāo)行為規(guī)律挖掘。

4 仿真數(shù)據(jù)實(shí)驗(yàn)分析

本實(shí)驗(yàn)采用一個(gè)仿真的時(shí)空軌跡數(shù)據(jù)集模擬某預(yù)警監(jiān)視區(qū)域中未知飛行器的飛行行為，利用本文所提算法和其他對(duì)比算法進(jìn)行目標(biāo)行為規(guī)律挖掘，并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行對(duì)比分析。

4.1 仿真軌跡數(shù)據(jù)集

本實(shí)驗(yàn)使用Piciarelli 等［27］公開(kāi)發(fā)表 的目標(biāo)航跡生成程序，該程序可以產(chǎn)生成簇的規(guī)律性軌跡以及隨機(jī)的異常航跡，可設(shè)置軌跡簇密度分布參數(shù)，軌跡簇的個(gè)數(shù)，每一簇的軌跡條數(shù)，每條軌跡的信息數(shù)據(jù)點(diǎn)數(shù)，異常軌跡數(shù)等參數(shù)。用該程序產(chǎn)生二維空間中的目標(biāo)軌跡數(shù)據(jù)，人為添加信息數(shù)據(jù)點(diǎn)中目標(biāo)的時(shí)間、速度以及航向信息。本數(shù)據(jù)集共有1 500 條時(shí)空軌跡，每條時(shí)空軌跡包含20～60 個(gè)不等的信息數(shù)據(jù)點(diǎn)。在預(yù)警監(jiān)視區(qū)域中總共設(shè)置了目標(biāo)的10 種行為模式，即有10 個(gè)時(shí)空軌跡簇。

數(shù)據(jù)集的主要分布情況為主要為：在位置1附近生成4 簇軌跡，軌跡密度分布參數(shù)為0.5，每個(gè)軌跡簇有200 條軌跡，包括一簇標(biāo)準(zhǔn)行為、一簇2 倍速行為、一簇3 倍速行為和一簇反航向行為，用來(lái)驗(yàn)證算法對(duì)軌跡多維特征信息的挖掘能力；在位置2 附近生成2 簇軌跡，一簇為標(biāo)準(zhǔn)行為，密度分布參數(shù)為0.5，軌跡數(shù)量為200 條，另一簇為2 倍速行為，密度分布參數(shù)為0.6，軌跡數(shù)量為50 條，為了驗(yàn)證算法在高密度行為中挖掘低密度行為的能力；在位置3 附近生成2 簇軌跡，一簇為標(biāo)準(zhǔn)行為，密度分布參數(shù)為0.5，軌跡數(shù)量為100 條，另一簇為反航向行為，密度分布參數(shù)為0.6，軌跡數(shù)量為30 條，為了驗(yàn)證算法在高密度行為中挖掘更低密度行為的能力；在位置4 附近生成1 簇軌跡，密度分布參數(shù)為0.7，軌跡數(shù)量為100 條，為了檢驗(yàn)算法對(duì)軌跡行為密度分布的魯棒性；在位置5 附近生成1 簇軌跡，密度分布參數(shù)為0.7，軌跡數(shù)量為20 條，為了檢驗(yàn)算法挖掘潛在行為的能力；同時(shí)還包括200 條隨機(jī)生成的無(wú)規(guī)律異常軌跡，整個(gè)數(shù)據(jù)集如圖5 所示。

圖5 仿真軌跡數(shù)據(jù)集示意圖Fig.5 Plot of all trajectories in dataset

4.2 算法復(fù)雜度

在STHD 算法中，對(duì)于度量含有n個(gè)信息數(shù)據(jù)點(diǎn)、N個(gè)軌跡段和含有m個(gè)信息數(shù)據(jù)點(diǎn)、M個(gè)軌跡段的2 條時(shí)空軌跡，本文算法復(fù)雜度為而MFHD 算 法 的 復(fù)雜度為O(mn)，優(yōu)于MFHD 算法。特殊地，當(dāng)時(shí)間窗足夠小時(shí)，STHD 近似于歐式距離度量，復(fù)雜度為O(n)，此時(shí)算法復(fù)雜度最小，對(duì)于速度和航向的度量效果最佳，但對(duì)軌跡整體的位置和形狀度量效果最差；當(dāng)時(shí)間窗足夠大時(shí)，STHD 相當(dāng)傳統(tǒng)的Hausdorff 距離，復(fù)雜度為O(mn)，此時(shí)算法復(fù)雜度最大，對(duì)軌跡整體的位置和形狀度量效果最佳，但無(wú)法度量軌跡的速度和航向信息。

在STTCA 算法中，對(duì)于含有n條時(shí)空軌跡的數(shù)據(jù)集，本文算法的復(fù)雜度為O(n2)，與MTCA 相當(dāng)。

4.3 STTCA 算法實(shí)驗(yàn)結(jié)果

利用本文所提算法對(duì)仿真飛行器軌跡進(jìn)行行為規(guī)律挖掘。采用時(shí)空Hausdorff 距離作為相似性度量，對(duì)于參數(shù)ξ的選擇，考慮到STHD 的度量效果和算法復(fù)雜度，相似度計(jì)算消耗的時(shí)間隨著ξ減小而減小，因此應(yīng)當(dāng)選擇一個(gè)較小的值，但同時(shí)為了保證算法對(duì)軌跡整體的位置和形狀度量效果，ξ又不宜過(guò)小，綜合考量，設(shè)置ξ= 5 進(jìn)行實(shí)驗(yàn)。采用STTCA 算法進(jìn)行軌跡聚類，對(duì)于參數(shù)k的選擇，考慮到算法復(fù)雜度，k越大，算法搜索近鄰軌跡所消耗的時(shí)間越長(zhǎng)，且參數(shù)k有一個(gè)重要意義：軌跡成簇和異常行為的分界點(diǎn)，即在某一位置聚集的軌跡數(shù)量超過(guò)k時(shí)就可以從海量軌跡數(shù)據(jù)中挖掘出該行為，聚集的軌跡數(shù)量未超過(guò)k時(shí)就不認(rèn)為其為一種頻繁出現(xiàn)行為，判定為無(wú)規(guī)律行為。因此為了挖掘出目標(biāo)更多的行為規(guī)律，k的設(shè)定一般不宜過(guò)大。對(duì)于本節(jié)使用的仿真數(shù)據(jù)集，存在一簇包含20 條時(shí)空軌跡的行為規(guī)律和一簇包含30 條時(shí)空軌跡的行為規(guī)律，因此為了挖掘出這種低密度的行為，k的設(shè)置應(yīng)當(dāng)不超過(guò)20。分別設(shè)置k= 5， 15， 25， 35 進(jìn)行實(shí)驗(yàn)，得到4 個(gè)λ-δ決策圖如圖6 所示?？梢园l(fā)現(xiàn)，當(dāng)k= 5，15 時(shí)，都可以較好地挖掘出10 種行為規(guī)律的中心軌跡；而當(dāng)k= 25 時(shí)僅可以發(fā)現(xiàn)9 種行為；當(dāng)k= 35 時(shí)更是只能發(fā)現(xiàn)8 種行為。因此在后續(xù)的實(shí)驗(yàn)中，設(shè)置k最近鄰參數(shù)k= 5。通過(guò)觀察λ-δ決策圖設(shè)置閾值THabnormal= 0.6，剔除異常軌跡。通過(guò)觀察決策值降序圖，如圖7 所示，取決策閾值THcenter= 5，圖中紫色虛線所示，提取出10 條中心軌跡。

圖6 λ-δ 決策圖Fig.6 λ-δ decision graph

圖7 決策值示意圖Fig.7 Plot of decision value

經(jīng)過(guò)聚類和可疑軌跡判定，最終挖掘出飛行器運(yùn)動(dòng)的10 種行為規(guī)律，紅色點(diǎn)代表目標(biāo)軌跡起點(diǎn)，黑色點(diǎn)代表終點(diǎn)，相鄰軌跡點(diǎn)間隔的長(zhǎng)短表示目標(biāo)的速度大小，如圖8 所示。直接觀察圖5，很難發(fā)現(xiàn)目標(biāo)軌跡的10 種行為規(guī)律，但是通過(guò)聚類結(jié)果圖8，可以清晰直觀地感知目標(biāo)的10 種行為規(guī)律。

圖8 挖掘出的10 種行為規(guī)律的中心軌跡Fig.8 Plot of central trajectories of excavated 10 behavior rules

為了證明本文算法的優(yōu)越性，采用輪廓系數(shù)（Silhouette Coefficient）、精確度（Accuracy）和算法運(yùn)行時(shí)間對(duì)算法進(jìn)行評(píng)估，與軌跡相似性度量方法Hausdorff、MFHD 以及軌跡聚類算法MTCA、K-medoids、DPC 進(jìn)行對(duì)比，采用不同參數(shù)進(jìn)行多次重復(fù)實(shí)驗(yàn)，以多次試驗(yàn)結(jié)果的最優(yōu)值作為最終結(jié)果，如表1 所示。

輪廓系數(shù)可以反映聚類出的簇的緊湊程度，輪廓系數(shù)越大表示同一簇中的目標(biāo)行為越相近，不同簇中的目標(biāo)行為越不相近，是一種內(nèi)在的評(píng)估方法；精確率是指在同一個(gè)聚類結(jié)果簇中，與仿真數(shù)據(jù)集中基準(zhǔn)確定的軌跡簇一致的軌跡占該聚類結(jié)果簇中所有軌跡的比例，是一種外在的評(píng)估方法。通過(guò)表1 可以看出本文算法與MTCA、K-medoids、DPC 挖掘出的行為模式在緊湊程度上相差不大。從算法實(shí)驗(yàn)結(jié)果精確度上來(lái)看，本文所提算法STHD 和STTCA 的組合性能最優(yōu)，MTCA 算法由于對(duì)密度不均勻的行為挖掘能力較差，尤其是密度分布較低，軌跡數(shù)量較小的行為往往難以發(fā)現(xiàn)并被認(rèn)定為異常軌跡；K-medoids 算法由于聚類中心隨機(jī)且無(wú)法檢測(cè)異常軌跡，會(huì)將不規(guī)律軌跡判定為某一種規(guī)律性行為，導(dǎo)致準(zhǔn)確率不高；Hausdorff 只能度量軌跡之間的位置信息而無(wú)法度量速度和航向信息，因此造成整體的挖掘算法準(zhǔn)確率不高。從算法運(yùn)行時(shí)間上看，除了K-medoids 聚類迭代消耗大量時(shí)間外，其他的算法時(shí)間消耗主要集中在軌跡相似性度量上，STHD 在時(shí)間復(fù)雜度上低于MFHD和Hausdorff，避免了不必要的信息點(diǎn)距離運(yùn)算，整個(gè)算法的運(yùn)行時(shí)間大大降低。

表1 算法性能比較Table 1 Comparison of algorithm performance

5 實(shí)測(cè)數(shù)據(jù)實(shí)驗(yàn)驗(yàn)證

本實(shí)驗(yàn)選取了2006年1月某天舊金山機(jī)場(chǎng)雷達(dá)檢測(cè)出的所有航班飛行軌跡，經(jīng)過(guò)初步篩選，剔除部分無(wú)效軌跡，總共有1 017 次飛行時(shí)空軌跡，每條時(shí)空軌跡包含x，y和z坐標(biāo)，其中z為飛行高度，以及雷達(dá)信息數(shù)據(jù)點(diǎn)的時(shí)間信息等，所有軌跡如圖9 所示。

利用本文所提算法對(duì)航班飛行軌跡進(jìn)行行為規(guī)律挖掘。采用時(shí)空Hausdorff 距離作為相似性度量，設(shè)置參數(shù)ξ= 5；采用STTCA 算法進(jìn)行軌跡聚類，設(shè)置k最近鄰參數(shù)k= 5 進(jìn)行目標(biāo)行為規(guī)律挖掘?qū)嶒?yàn)。通過(guò)觀察λ-δ決策圖設(shè)置閾值THabnormal=1×104m，剔除異常軌跡，如圖10 所示，紅色圈內(nèi)的軌跡被認(rèn)定為無(wú)規(guī)律軌跡。

圖10 實(shí)測(cè)數(shù)據(jù)λ-δ 決策圖Fig.10 λ-δ decision graph of measured data

通過(guò)觀察決策值降序圖，如圖11 所示，取決策閾值THcenter= 10，圖中紫色虛線所示，提取出12 條中心軌跡。經(jīng)過(guò)聚類和可疑軌跡判定，最終挖掘出航班飛行的12 種行為規(guī)律，如圖12 所示，其中紅色點(diǎn)表示目標(biāo)行為的起點(diǎn)，黑色點(diǎn)表示目標(biāo)行為的終點(diǎn)。實(shí)測(cè)數(shù)據(jù)實(shí)驗(yàn)表明，本文算法在真實(shí)應(yīng)用場(chǎng)景中具有良好的規(guī)律挖掘性能，在智能監(jiān)視任務(wù)中具有較好的應(yīng)用前景。

圖11 實(shí)測(cè)數(shù)據(jù)決策值示意圖Fig.11 Plot of decision value of measured data

圖12 挖掘出的行為規(guī)律在三維和二維空間中的中心軌跡Fig.12 Plot of central trajectories of excavated behavior rules in three and two dimensional spaces

6 結(jié) 論

本文面向預(yù)警監(jiān)視需求，提出了時(shí)空軌跡多維特征融合的行為規(guī)律挖掘算法，進(jìn)行了實(shí)驗(yàn)分析和驗(yàn)證。

1） 針對(duì)目標(biāo)行為規(guī)律挖掘算法存在的多維特征信息融合效果不佳的問(wèn)題，提出了時(shí)空Hausdorff 距離度量算法，可有效度量時(shí)空軌跡多維特征差異。

2） 針對(duì)現(xiàn)有軌跡聚類算法參數(shù)設(shè)置復(fù)雜以及對(duì)軌跡數(shù)據(jù)集行為密度分布敏感的問(wèn)題，結(jié)合k最近鄰距離和密度峰值聚類中決策圖的思想，采用時(shí)空Hausdorff 距離作為相似性度量，提出多維特征融合的時(shí)空軌跡聚類算法，可從海量軌跡數(shù)據(jù)中有效挖掘目標(biāo)行為規(guī)律。

3） 分別在仿真飛行器軌跡和實(shí)測(cè)雷達(dá)軌跡數(shù)據(jù)對(duì)算法進(jìn)行實(shí)驗(yàn)分析和驗(yàn)證，結(jié)果表明本文算法在復(fù)雜度、精確度以及運(yùn)行時(shí)間上要優(yōu)于現(xiàn)有算法，在一定程度上解決了現(xiàn)有算法存在的問(wèn)題。

4） 在接下來(lái)的工作中，將進(jìn)一步研究目標(biāo)行為規(guī)律在線挖掘方法，提升態(tài)勢(shì)感知的實(shí)效性。