姜喬文，劉瑜，丁自然，孫順，簡濤

海軍航空大學(xué) 信息融合研究所，煙臺 264001

在預(yù)警監(jiān)視領(lǐng)域，隨著衛(wèi)星、雷達(dá)、ADS-B（Automatic Dependent Surveillance-Broadcast）、AIS（Automatic Identification System）、聲吶以及高清攝像機(jī)等目標(biāo)探測技術(shù)的快速發(fā)展，覆蓋天基、空基、岸基、海上甚至水下的多層次預(yù)警監(jiān)測體系已經(jīng)基本形成［1-3］。監(jiān)視場景下的運(yùn)動目標(biāo)得到了清晰準(zhǔn)確的檢測、跟蹤和關(guān)聯(lián)，形成不斷更新的目標(biāo)時空信息，最終以時空軌跡的形式記錄下來。海量的時空軌跡數(shù)據(jù)在航空電子系統(tǒng)等目標(biāo)信息處理中心不斷存儲和積累，其中隱含著大量規(guī)律性的信息和知識?；跀?shù)據(jù)挖掘中的聚類技術(shù)可以從海量的歷史數(shù)據(jù)中挖掘出目標(biāo)的頻繁行為模式［4-6］，但離線的數(shù)據(jù)分析不具備時效性，難以適用于態(tài)勢實(shí)時更新的預(yù)警監(jiān)視場景。在預(yù)警監(jiān)視系統(tǒng)中，實(shí)時地對未知身份目標(biāo)的時空軌跡行為進(jìn)行預(yù)測和判定是實(shí)現(xiàn)態(tài)勢感知的有效途徑。當(dāng)前，行為判定多以人工處理方式為主，這不僅要求情報處理人員具備大量的先驗(yàn)知識，同時消耗大量的時間和精力，效率低且準(zhǔn)確性差。因此，如何實(shí)現(xiàn)系統(tǒng)智能化在線分析目標(biāo)行為是當(dāng)下預(yù)警監(jiān)視領(lǐng)域亟待解決的問題，這對于提升信息處理效率、及時分析和預(yù)測目標(biāo)行為意圖、輔助指揮員決策部署以及實(shí)現(xiàn)智能化態(tài)勢感知具有重要的現(xiàn)實(shí)意義。

近年來，國內(nèi)外科研人員在目標(biāo)行為模式分類方面開展了大量的研究工作［7-11］。趙竹珺和吉根林［12］對時空軌跡分類研究進(jìn)展進(jìn)行了詳細(xì)的總結(jié)，針對現(xiàn)有的軌跡分類算法的特點(diǎn)，從數(shù)據(jù)來源、分類器、特征提取方式等方面進(jìn)行了對比分析，并對設(shè)計增量式學(xué)習(xí)算法建立軌跡分類器提出了展望。潘新龍等［13］針對預(yù)警監(jiān)視和指揮決策需求，對現(xiàn)有的目標(biāo)行為模式在線分類技術(shù)進(jìn)行了總結(jié)與展望。曹衛(wèi)權(quán)等［14］基于運(yùn)動目標(biāo)的區(qū)域分布，采用核密度估計和最大似然判決的方法對軌跡段進(jìn)行分類。崔彤彤等［15］結(jié)合卷積神經(jīng)網(wǎng)絡(luò)和長短期記憶網(wǎng)絡(luò)優(yōu)勢學(xué)習(xí)船舶AIS軌跡特征，實(shí)現(xiàn)了船舶軌跡和類型的分類。Owens 和Hunter［16］針對視頻監(jiān)控系統(tǒng)中檢測到的目標(biāo)行為自動分類問題，采用自組織映射神經(jīng)網(wǎng)絡(luò)對正常的軌跡特征進(jìn)行學(xué)習(xí)，實(shí)現(xiàn)無模型軌跡分類和異常檢測。Bolbol 等［17］基于支持向量機(jī)構(gòu)建分類推理框架，來解決GPS 數(shù)據(jù)在不同交通方式（汽車、步行、自行車、地鐵、火車和公共汽車）中的分類問題。Saini 等［18］采用粒子群算法融合軌跡的全局和局部特征，并基于圖方法對軌跡進(jìn)行分類。Pan 等［19］采用多因素Hausdorff 作為軌跡相似性度量，通過構(gòu)造一致性多類分類器對預(yù)警監(jiān)視區(qū)域的頻繁行為模式進(jìn)行在線分類。

雖然目前軌跡分類領(lǐng)域已有大量的研究，但現(xiàn)有方法依然存在以下幾點(diǎn)局限性：場景設(shè)置理想化，沒有考慮到離群軌跡對在線分類器的影響；分類模型復(fù)雜，導(dǎo)致時間消耗大，實(shí)時性有待提升；僅從空間位置信息度量軌跡相似性，忽略了航向和速度等特征。

本文針對上述軌跡分類方法的幾點(diǎn)局限性展開，主要貢獻(xiàn)如下：① 提出了歸納式一致性多類預(yù)測器（Inductive Conformal Multi-class Predictor， ICMP），兼顧分類和離群樣本檢測功能，并提高了訓(xùn)練和在線檢測的效率；② 提出了時空Hausdorff 距離（Spatio-Temporal Hausdorff Distance， STHD）和定向時空Hausdorff 最近鄰不一致性度量函數(shù)（Directed Spatiotemporal Hausdorff Nearest Neighbor Nonconformity Measure， DSHNN-NCM），可以有效區(qū)分空間位置相似但運(yùn)動速度和方向不同的軌跡；③ 提出了序貫時空Hausdorff 最近鄰歸納式一致性多類預(yù)測器（Sequential Spatiotemporal Hausdorff Nearest Neighbor Inductive Conformal Multi-class Predictor， SSHNN-ICMP），對預(yù)警監(jiān)視場景下目標(biāo)頻繁出現(xiàn)的行為進(jìn)行在線學(xué)習(xí)和預(yù)測；④ 通過仿真和實(shí)測數(shù)據(jù)實(shí)驗(yàn)證明了算法在目標(biāo)行為在線分類準(zhǔn)確性和實(shí)時性上的優(yōu)勢。

1 一致性預(yù)測

1.1 一致性多分類器

一致性預(yù)測［20-21］（Conformal Predictor，CP）（算法1）是一種基于Kolmogorov 隨機(jī)性理論轉(zhuǎn)導(dǎo)推理的域預(yù)測機(jī)器學(xué)習(xí)算法，該算法的前提是假設(shè)樣本是獨(dú)立和同分布的。首先在對測試樣本進(jìn)行預(yù)測之前設(shè)定一個置信水平，然后對訓(xùn)練樣本集和待測樣本序列進(jìn)行隨機(jī)性檢驗(yàn)，通過不一致性度量函數(shù)（Nonconformity Measure，NCM）計算待測樣本序列與訓(xùn)練樣本集不一致程度的定量估計，最后將所有隨機(jī)性檢驗(yàn)值超過置信水平的所有類別標(biāo)簽作為域預(yù)測的結(jié)果。一致性預(yù)測算法的預(yù)測風(fēng)險可控，但是預(yù)測結(jié)果可能不唯一。為了保證預(yù)測過程對每個測試樣本的獨(dú)立性，一致性預(yù)測過程采用在線學(xué)習(xí)方法，對于不同的測試樣本，訓(xùn)練樣本集不斷更新。對于第k+1 個測試數(shù)據(jù)，前k個測試樣本已經(jīng)被添加到訓(xùn)練樣本集中，以此來在線擴(kuò)展訓(xùn)練樣本集。

算法1 一致性預(yù)測（CP）算法輸入：訓(xùn)練數(shù)據(jù)集{z1，z2，…，zl}，測試數(shù)據(jù)xl+1，不一致性度量函數(shù)A，置信水平ε輸出： 對測試數(shù)據(jù)xl+1 的預(yù)測標(biāo)簽集合yεl+1 01.yεl+1 ←?02.for all y ∈{1，2，…，c}03.zl+1 ←(xl+1，y)04.for i ←1 to l+1 do 05. αi ←A({z1，z2，…，zl+1}zi，zi)06. end for 07. p ←|{i ∈{1，2，…，l l，+l+1 1 }|αi ≥αl+1}|08. if p ＞ε then 09. yεl+1 ←yεl+1 ∪{y}10. end if 11.end for 12.{z1，z2，…，zl}←{z1，z2，…，zl}∪xl+1

在給定的置信水平ε的前提下，一致性預(yù)測器能夠預(yù)測可控風(fēng)險下的類別。然而，對于同一個測試樣本，一致性多分類器可能得到幾個不同的類別標(biāo)簽；除此之外，ε的取值對一致性預(yù)測結(jié)果至關(guān)重要，在很多應(yīng)用中選擇合適的ε值是非常困難的，需要通過專家經(jīng)驗(yàn)來嘗試，不具有魯棒性，這在預(yù)警監(jiān)視應(yīng)用中是不能接受的。為了解決上述問題，Pan 等［19］提出了一致性多類分類器（Conformal Multi-class Classifier， CMC）（算法2）。該分類器可以保證預(yù)測的唯一性，而且在分類時不需要ε，解決了ε取值困難的問題，具有較強(qiáng)的魯棒性。

算法2 一致性多類分類器（CMC）算法輸入：訓(xùn)練數(shù)據(jù)集{z1，z2，…，zl（}按類別標(biāo)簽分為c 個子集{z1，z2，…，zl1}，…，{z1，z2，…，zlc}，l1+l2+…+lc=l），測試數(shù)據(jù)zl+1，不一致性度量函數(shù)A輸出： 對測試數(shù)據(jù)zl+1 的預(yù)測標(biāo)簽yl+1 01.for all y ∈{1，2，…，c} do 02.zl+1 ←(xl+1，y)03.for i ←1 to ly 04. αyi ←A({z1，z2，…，zly，zl+1}zi，zi)05.end for 06.αl+1 ←A({z1，z1，…，zly}，zl+1)|||||{i ∈{1，2，…，ly，l+1 }|αyi ≥αl+1}|||||07.pyl+1 ←ly+1 08.end for 09.pcl l+ass1 ←max{p1l+1，p2l+1，…，pcl+1}，class ∈{1，2，…，c}10.yl+1 ←class 11.{z1，z2，…，zlclass}←{z1，z2，…，zlclass，zl+1}

1.2 帶有離群檢測的歸納式一致性多分類預(yù)測器

CMC 作為一種在線預(yù)測器，最突出的問題是在線計算的效率。在計算測試樣本集中每個樣本的不一致性度量值時，CMC 需要反復(fù)訪問和存儲樣本的相似度度量矩陣，耗時較長，因此僅適用于數(shù)據(jù)規(guī)模較小和低實(shí)時性要求的應(yīng)用。除此之外，在實(shí)際預(yù)警監(jiān)視場景中，目標(biāo)的行為并不是都遵循已知的行為模式，會不斷出現(xiàn)無規(guī)則的離群軌跡。當(dāng)采用CMC 對目標(biāo)行為進(jìn)行預(yù)測時，不論在哪一類型為模式中，離群軌跡經(jīng)過不一致性度量會得到一個很小的p值，由于算法未對p值進(jìn)行有效限制，從而導(dǎo)致將離群軌跡強(qiáng)行預(yù)測為某一種行為模式，這在預(yù)警監(jiān)視應(yīng)用中是不能接受的。針對上述問題，結(jié)合歸納式一致性 預(yù) 測［22］（Inductive Conformal Predictor，ICP） 和一致性異常檢測［23］（Conformal Anomaly Detector， CAD）的思想，提出了帶有離群檢測的歸納式一致性多分類預(yù)測器（Inductive Conformal Multi-class Predictor with outlier detector， ICMP）（ 算法3）。

算法3 ICMP 算法輸入：訓(xùn)練數(shù)據(jù)集{z1，z2，…，zl（}按類別標(biāo)簽分為c 個子集{z1，z2，…，zl1}，…，{z1，z2，…，zlc}，l1+l2+…+lc=l，每個子集分為壓縮樣本集{z1，z2，…，zu1}，…，{z1，z2，…，zuc}和檢驗(yàn)樣本集{zu1+1，zu1+2，…，zl1}，…，{zuc+1，zuc+2，…，zlc}），不一致性度量函數(shù)A，風(fēng)險水平ε 訓(xùn)練集{z1，z2，…，zl（}分為壓縮樣本集{z1，z2，…，zu}和檢驗(yàn)樣本集{zu+1，zu+2，…，zl}），測試數(shù)據(jù)zl+1，不一致性度量函數(shù)A，風(fēng)險水平ε輸出： 對測試數(shù)據(jù)zl+1 的預(yù)測標(biāo)簽yl+1 01.for all y ∈{1，2，…，c} do 02.for i ←uy+1 to ly 03. αyi ←A({z1，z2，…，zuy}，zi)04. end for 05.end for 06.for all y ∈{1，2，…，c} do 07.zl+1 ←(xl+1，y)09. αl+1 ←A({z1，z2，…，zuy}，zl+1)|||||{i ∈{uy+1，uy+2，…，ly，l+1 }|αyi ≥αl+1}|||||10.pyl+1 ←ly-uy+1 11.end for 12.pcll+ass1 ←max{p1l+1，p2l+1，…，pcl+1}，class ∈{1，2，…，c}13. if pcl l+ass1 ＜ε then 14. yl+1 ←0（Outlier）15.else 16. yl+1 ←class 17.{z1，z2，…，zlclass}←{z1，z2，…，zlclass，zl+1}

第一，針對在線計算效率的問題，基于歸納式一致性預(yù)測的思想來改善一致性多分類器的在線學(xué)習(xí)的實(shí)時性。將每一類訓(xùn)練樣本集{z1，z2，…，zl1}，…，{z1，z2，…，zlq}，…，{z1，z2，…，zlc}劃 分 為 壓 縮 樣 本 集{z1，z2，…，zu1}，… ，{z1，z2，…，zuq}，…，{z1，z2，…，zuc}和檢驗(yàn)樣本集{zu1+1，zu1+2，…，zl1}，…，{zuq+1，zuq+2，…，zlq}，…，{zuc+1，zuc+2，…，zlc}。壓縮樣本集是一個固定的集合，用來學(xué)習(xí)構(gòu)建一個規(guī)則模型，不隨檢測樣本的更新而改變；只有檢驗(yàn)樣本集隨檢測樣本的更新而改變，這樣既可以實(shí)時更新測試數(shù)據(jù)，又保證了計算效率。檢驗(yàn)樣本集中樣本的不一致性度量值通過壓縮樣本集計算，對于第q類檢驗(yàn)樣本集{zuq+1，zuq+2，…，zlq}中的樣本，其不一致性度量值

對于測試樣本zl+1，其不一致性度量值

每一類樣本中隨機(jī)性檢驗(yàn)值的估計為

為了證明ICMP 在計算效率上的優(yōu)勢，分析ICMP 和CMC 對其不一致性度量算法A的復(fù)雜度。當(dāng)A應(yīng)用于一個包含l個訓(xùn)練數(shù)據(jù)和s個測試數(shù)據(jù)的數(shù)據(jù)集時，算法的整體復(fù)雜度可以表示為

式中：Atrain(l)表示A生成其通用規(guī)則所需的時間；Aapply表示將該通用規(guī)則應(yīng)用到一個新測試數(shù)據(jù)所需的時間［22］。CMC 每完成一個測試樣本后都需要更新訓(xùn)練樣本集，且不一致性度量值在每次測試時也需要不斷更新，其復(fù)雜度表示為

式中：c表示類別數(shù)；lq表示第q類訓(xùn)練樣本集的樣本個數(shù)。而ICMP 通過固定的壓縮樣本集歸納得到檢驗(yàn)樣本集和測試樣本的不一致性度量值，而且只需要訓(xùn)練一次，不需要隨著測試樣本的更新而改變，其復(fù)雜度為

因此，當(dāng)測試樣本規(guī)模很大時，ICMP 計算效率要遠(yuǎn)優(yōu)于CMC。

第二，針對一致性多分類器對離群樣本不敏感的問題，基于一致性異常檢測的思想，對算法增加了風(fēng)險評估。首先設(shè)定一個風(fēng)險水平ε，當(dāng)最終的隨機(jī)性檢驗(yàn)值確定后，將其與風(fēng)險水平ε比較。當(dāng)＜ε時，則把測試樣本zl+1判定為離群樣本；當(dāng)時，則對測試樣本zl+1進(jìn)行正常的分類預(yù)測。這樣就很好地避免了離群軌跡對目標(biāo)行為分類準(zhǔn)確性的影響。

2 不一致性度量函數(shù)

2.1 時空Hausdorff 距離

時空軌跡數(shù)據(jù)是由若干個目標(biāo)位置信息按時間順序構(gòu)成的序列。在一段時間內(nèi)預(yù)警監(jiān)視系統(tǒng)中積累目標(biāo)的所有時空軌跡集合表示為

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

其中：pi，k表示第i條軌跡中的第k個時空信息數(shù)據(jù)點(diǎn)；m表示軌跡tri中時空信息點(diǎn)總數(shù)，通常情況下，不同軌跡的時空信息點(diǎn)總數(shù)m不盡相同。

pi，k是一個包含目標(biāo)時間和空間位置信息的向量，pi，k=[ti，k，li，k]。其中時間信息用ti，k表示，滿足ti，k＜ti，k+1；空間位置信息用li，k表示，li，k既可以是二維空間中的位置點(diǎn)(xi，k，yi，k)，也可以是三維空間中的位置點(diǎn)(xi，k，yi，k，zi，k)。

Hausdorff 距離［24-25］（Hausdorff Distance，HD）是一種廣泛應(yīng)用的軌跡相似性度量方法，它的優(yōu)點(diǎn)在于可以度量整條軌跡的全局特征，當(dāng)軌跡不完整時依然可以很好地進(jìn)行相似性度量。傳統(tǒng)的軌跡Hausdorff 距離度量基于軌跡的空間位置信息，對于2 條軌跡tri和trj，定向Hausdorff距離的意義為軌跡tri中的位置信息點(diǎn)到trj中的位置信息點(diǎn)的最近距離中的最大值，表示為

式中：dist(li，k，lj，k)表示兩點(diǎn)之間的歐氏距離。在二維空間中，

在三維空間中，

傳統(tǒng)的軌跡相似性度量方法，如歐氏距離［26］、DTW［27］、Hausdorff 距離等，都是基于目標(biāo)運(yùn)動空間中的位置信息，未能有效地將目標(biāo)的位置、速度、航向等多維特征信息進(jìn)行融合，因此很難區(qū)分位置相近而運(yùn)動特征存在較大差異的目標(biāo)軌跡。而事實(shí)上，目標(biāo)在運(yùn)動過程中的位置信息是目標(biāo)的速度、航向等特征在時間上積累的結(jié)果，盡管在空間維度中位置相近，但在時間維度上，運(yùn)動特征不同的軌跡卻有著很高的區(qū)分度。因此，我們在目標(biāo)運(yùn)動空間的基礎(chǔ)上引入時間維度，在時空域中基于Hausdorff 距離度量軌跡的相似性，提出了時空Hausdorff 距離（Spatio-Temporal Hausdorff Distance， STHD） 。

在時空域中，空間維中的量綱是距離單位，時間維中的量綱是時間單位，兩者量綱的不同導(dǎo)致無法直接利用歐氏距離進(jìn)行度量?？紤]到距離的量綱與時間的量綱之間相差一個速度量綱，因此只需要在時間維度上乘上一個具有速度量綱的參量即可。設(shè)定該參量為整個數(shù)據(jù)集中目標(biāo)運(yùn)動的平均速度

式中：count(pi，k)表示軌跡tri中信息點(diǎn)的總數(shù)。

于是tri中每個軌跡信息點(diǎn)在時空域中的坐標(biāo)就可以表示為

其中，式（13）用來表示二維空間中的運(yùn)動目標(biāo)，式（14）用來表示三維空間中的運(yùn)動目標(biāo)。

然后，在時空域中定義軌跡tri和trj之間的定向時空Hausdorff 距離為

定向時空Hausdorff 距離也不具備對稱性，因此定義兩者的較大值為時空Hausdorff 距離

如圖1 所示，盡管在空間維度上3 個運(yùn)動速度和航向相異的目標(biāo)軌跡Hausdorff 距離相近，但是在時空域中，可以準(zhǔn)確地將運(yùn)動特征不同的目標(biāo)軌跡區(qū)分開。

圖1 STHD 示意圖Fig.1 Schematic diagram of STHD

2.2 時空Hausdorff 最近鄰不一致性度量函數(shù)

不一致性度量函數(shù)（Nonconformity Measure， NCM）是一致性預(yù)測算法的一個重要組成部分，用來計算待測樣本序列與訓(xùn)練樣本集不一致程度的定量估計。不一致性度量函數(shù)的構(gòu)造通?；跈C(jī)器學(xué)習(xí)的分類算法，其中應(yīng)用最廣泛的是K 近鄰算法［24］

式中：表示測試樣本zi到與它同類別訓(xùn)練樣本中第j近的距離；表示測試樣本zi到與它不同類別訓(xùn)練樣本中第j近的距離。該定義假設(shè)具有相同標(biāo)簽的樣本彼此很接近，而具有不同標(biāo)簽的樣本彼此距離較遠(yuǎn)。

由于ICMP 本質(zhì)上還是一種多類分類器，因此并不需要考慮到其他類的距離。為了描述時空維度中目標(biāo)軌跡的不一致性，我們結(jié)合STHD和K 最近鄰（K Nearest Neighbor， KNN）的思想，提出了定向時空Hausdorff 最近鄰不一致性度量函數(shù)（Directed Spatiotemporal Hausdorff Nearest Neighbor Nonconformity Measure，DSHNN-NCM）

式中：{tri，tri+1，…，trn}表示目標(biāo)時空軌跡組成的壓縮樣本集；N (tri，{tri，tri+1，…，trn} ri，K)表示時空軌跡tri到與它同類別訓(xùn)練樣本中定向時空Hausdorff 距離第K近的時空軌跡。在預(yù)警監(jiān)視場景的應(yīng)用中，K的值通?？梢匀?、3、4 或5。

3 目標(biāo)行為模式在線預(yù)測方法

基于1.2 節(jié)提出的ICMP 和2.2 節(jié)提出的DSHNN-NCM，提出了帶有離群檢測的序貫時空Hausdorff 最近鄰歸納式一致性多類預(yù)測器（Sequential Spatiotemporal Hausdorff Nearest Neighbor Inductive Conformal Multi-class Predictor with outlier detector， SSHNN-ICMP），用于對預(yù)警監(jiān)視場景下目標(biāo)頻繁出現(xiàn)的行為模式進(jìn)行在線學(xué)習(xí)和預(yù)測，主要流程如圖2 所示，具體實(shí)現(xiàn)步驟（算法4）如下：

圖2 SSHNN-ICMP 流程圖Fig.2 Flow chart of SSHNN-ICMP

輸入

2） 測試軌跡trl+1，以按時間順序輸入的時空信息點(diǎn)更新trl+1，m為時空軌跡長度。

3） 最近鄰參數(shù)K。

4） 風(fēng)險水平ε。

算法4 SSHNN-ICMP輸入 訓(xùn)練集C1，C2，…，C（r分為壓縮樣本集C1c，C2c，…，Crc 和檢驗(yàn)樣本集C1t，C2t，…，Crt），測試軌跡trl+1，最近鄰參數(shù)K，時空Hausdorff 距離向量μ1，μ2，…，μr，零向量h1，h2，…，hr，Q 風(fēng)險水平ε輸出 更新所有pslt+1，k 后軌跡trl+1 的預(yù)測行為標(biāo)簽集yεl+1 01.for k ←1 to m do 02.for all y ∈{1，2，…，r} do 03. for i ←uy+1 to ly do 04. αyi ←μiy-uy 05. end for 06. for g ←1 to uy do 07. hqg ←max{hst( pslt+1，k，trg)，hqg}08. if g ≤K then 09. Q.insertElement(hqg)10. else if Q.maxElement()＞hqg then 11. Q.removeMaxElement()12. Q.insertElement(hqg)13. end if 14. end if 15. end for 16. αl+1 ←Q.maxElement()17. Q.removeAllElements()|||||{i ∈{uy+1，uy+2，…，ly，l+1 }|αyi ≥αl+1}|||||18.pyl+1 ←ly-uy+1 19.end for 20.pcll+ass1 ←max{p1l+1，…，pql+1，…，prl+1}21.if pcl l+ass1 ＜ε then 22. ylε+1，k ←0 23.else 24. yl ε+1，k ←class 25.end for 26.yεl+1 ←{ylε+1，1，…，ylε+1，k，…，ylε+1，m}27.Cy tl ε+1，m ←Cy tl ε+1，m ∪trl+1 28.Update μ1，…，μq，…，μr

5） 時空Hausdorff 距離向量μ1，…，μq…，μr，其中μq是一個維度為(lq-uq)×1 的列向量，μiq表示第q類行為模式檢驗(yàn)樣本集中第i條軌跡到壓縮樣本集軌跡中第K近的時空Hausdorff距離。

6） 零向量h1，…，hq，…，hr，其中hq是一個維度為uq×1 的列向量。

7） 空排序集Q。

輸出

每更新一個時空信息點(diǎn)pl+1，k后軌跡trl+1的預(yù)測行為標(biāo)簽集其中表示離群軌跡。

1.2.2 各間隙調(diào)整正確。如秧針與導(dǎo)軌插口側(cè)面的標(biāo)準(zhǔn)間隙為1.3～1.7 mm，秧針和苗箱側(cè)面的標(biāo)準(zhǔn)間隙為1.5～2.5 mm。

步驟1對于軌跡trl+1在tk時刻更新的時空信息點(diǎn)，首先在第1 類行為模式的訓(xùn)練集C1重復(fù)如下操作：

1） 通過時空Hausdorff 距離向量μ1計算檢驗(yàn)樣本集中所有軌跡相對于壓縮樣本集的不一致性度量值

2） 計算更新的時空信息點(diǎn)相對于壓縮樣本集中所有軌跡的有向Hausdorff 距離并與前一個時刻進(jìn)行比較，取兩者中的較大值作為該時刻軌跡trl+1子軌跡相對于壓縮樣本集中所有軌跡的有向時空Hausdorff距離

3） 更新空集Q，當(dāng)Q中的元素個數(shù)超過K時，將所有的存入Q中；當(dāng)g＞K時，將當(dāng)前的與Q中的最大值相比，若小于Q中的最大值，則將Q中最大的元素剔除，并將插入到Q中。

4）Q中最大的元素即為該時刻trl+1子軌跡相對于壓縮樣本集中所有軌跡的K 最近鄰時空Hausdorff 距離，由此計算軌跡trl+1子軌跡的不一致性度量值

之后清空Q中所有元素。

5） 計算的值

步驟2在剩余r-1 類的訓(xùn)練集Cq中重復(fù)步驟1）～4）操作，計算得到

步驟3取中的最大值作為trl+1子軌跡在該時刻的一致性檢驗(yàn)值

步驟4判斷trl+1子軌跡在該時刻的一致性檢驗(yàn)值pl+1與風(fēng)險水平ε的大小關(guān)系。若pl+1＜ε，則判定軌跡trl+1為離群軌跡；若pl+1≥ε，則將trl+1子軌跡在該時刻的行為分類為中最大值所對應(yīng)的行為模式。

步驟5持續(xù)對更新后的trl+1子軌跡進(jìn)行行為判定，直到時空信息點(diǎn)不再更新。獲取trl+1整條軌跡在跟蹤過程中的行為模式標(biāo)簽集

步驟6將存入相應(yīng)類別的行為模式訓(xùn)練集的檢驗(yàn)樣本集中，并更新相應(yīng)的時空Hausdorff距離向量。

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

本實(shí)驗(yàn)?zāi)M了某預(yù)警監(jiān)視區(qū)域中未知飛行器的10 種飛行行為，生成了含有10 種類別標(biāo)簽的時空軌跡，我們在該數(shù)據(jù)集上實(shí)現(xiàn)了SSHNNICMP 算法，研究了算法的性能，并對實(shí)驗(yàn)結(jié)果進(jìn)行詳細(xì)的分析和討論。

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

本節(jié)的時空軌跡數(shù)據(jù)集由Piciarelli 等［28］公開發(fā)表的軌跡模擬程序生成，可以模擬產(chǎn)生帶有類別標(biāo)簽的規(guī)律性軌跡以及隨機(jī)的異常航跡。

用該程序產(chǎn)生二維空間中的目標(biāo)軌跡數(shù)據(jù)，并人為添加信息數(shù)據(jù)點(diǎn)中目標(biāo)的時間信息。該數(shù)據(jù)集共包含1 600 條時空軌跡，其中包括1 500 條規(guī)律性軌跡和100 條無規(guī)律軌跡，所有軌跡如圖3所示。規(guī)律性軌跡包含10 種行為模式，標(biāo)簽1～3的行為模式在同一位置生成，以行為1 為參照，行為2 速度是行為1 的2 倍，行為3 與行為1 運(yùn)動方向相反，每種行為有150 條軌跡；標(biāo)簽4 和5 的行為模式在同一位置生成，行為5 速度是行為4 的2倍，行為4 有200 條軌跡，行為5 有100 條軌跡；標(biāo)簽6 和7 的行為模式在同一位置生成，兩者運(yùn)動方向相反，行為6 有200 條軌跡，行為7 有100 條軌跡；標(biāo)簽8～10 的行為同理標(biāo)簽1～3 生成。如圖4所示，其中箭頭表示目標(biāo)的運(yùn)動方向，相鄰軌跡點(diǎn)間隔的長短表示目標(biāo)的速度大小。

圖3 仿真軌跡數(shù)據(jù)集Fig.3 Plot of simulation trajectory dataset

圖4 10 種行為模式Fig.4 Plot of 10 beheavior patterns

4.2 評價指標(biāo)

本文采用精確率（Precision）、召回率（Recall）、F1-score、分類準(zhǔn)確率（Accuracy）以及虛警概率（False Alarm， FA）對算法的性能進(jìn)行評估。Precision、Recall 以及Fl-score 用來衡量一致性預(yù)測器在每一類行為模式上的在線分類性能。其中Precision 表示測試集中某種行為模式正確預(yù)測的軌跡個數(shù)占所有預(yù)測為該種行為模式軌跡總數(shù)的比例；Recall 表示測試集中某種行為模式預(yù)測正確的軌跡個數(shù)占該種行為模式的軌跡總數(shù)的比例；Fl-score 是Precision 和Recall的調(diào)和平均值。False Alarm 表示判定為離群軌跡的時空軌跡中具有正常行為模式標(biāo)簽的時空軌跡的比例。Accuracy 表示所有行為預(yù)測正確的軌跡占測試集所有軌跡總數(shù)的比例，用來衡量在線分類和異常檢測在整個數(shù)據(jù)集上的整體性能。這些性能指標(biāo)的計算方法如下：

4.3 驗(yàn)證與分析

本實(shí)驗(yàn)在仿真數(shù)據(jù)集上實(shí)現(xiàn)SSHNN-ICMP算法，并分別與一致性多分類器CMC 與不一致性度量函數(shù)HD-KNN、STHD-KNN 的組合進(jìn)行對比分析。將整個仿真數(shù)據(jù)集隨機(jī)分成訓(xùn)練集和測試集，每一種行為模式的時空軌跡中75%作為測試集，25% 作為訓(xùn)練集，對于SSHNNICMP 而言，20%作為壓縮樣本集，5%作為檢驗(yàn)樣本集。設(shè)置風(fēng)險水平ε=0.01，K 近鄰參數(shù)K=2，3，4，5，按照上述比例隨機(jī)選取訓(xùn)練集和測試集進(jìn)行20 次重復(fù)實(shí)驗(yàn)。采用Precision、Recall、F1-score、Accuracy、FA 以及訓(xùn)練和測試消耗的總時間對算法的性能進(jìn)行評估，如表1 所示，其中的Precision、Recall 和F1-score 為每次實(shí)驗(yàn)所有行為模式類別間的平均值，表中的所有數(shù)據(jù)均為20 次重復(fù)試驗(yàn)的平均值，表中每項評估值的最優(yōu)結(jié)果用加粗表示。

表1 仿真場景中算法性能比較Table 1 Comparison of algorithm performance in simulation scenario

從表1 中結(jié)果可以看出，SSHNN-ICMP 與CMC 的組合算法相比在Precision、F1-score 以及Accuracy 等評價指標(biāo)上具有明顯的優(yōu)勢，且預(yù)警率保持在較低的水平。STHD 與KNN 的NCM組合整體性能要優(yōu)于HD 與KNN 的NCM 組合，因?yàn)榍罢呔邆浞直婵臻g位置相似而速度和航向不同的行為的能力。在訓(xùn)練和測試消耗的總時間上SSHNN-ICMP 要遠(yuǎn)小于CMC 的組合算法。

為了進(jìn)一步對比兩者在測試軌跡運(yùn)行時間上的差異，將K=3 時SSHNN-ICMP 與STHDKNN-CMC 在每一條測試軌跡上的耗時變化繪制在圖5 中。從圖5 中可以看出，隨著測試軌跡數(shù)目的增加，SSHNN-ICMP 的運(yùn)行時間幾乎保持在一個很低的值不變，而STHD-KNN-CMC隨著測試軌跡數(shù)目的增加運(yùn)行時間幾乎呈線性增長。因此SSHNN-ICMP 的實(shí)時性更強(qiáng)，將更適用于數(shù)據(jù)集規(guī)模大的場景。

圖5 運(yùn)行時間測試軌跡規(guī)模變化對比Fig.5 Comparation of running times dependent on size of test trajectory dataset

由于歸納式一致性預(yù)測的訓(xùn)練集不隨在線檢測更新，因此壓縮樣本集的規(guī)模將決定著預(yù)測性能。為了研究SSHNN-ICMP 分類的整體性能與壓縮樣本集的關(guān)系，保持5%的數(shù)據(jù)集作為檢驗(yàn)樣本集不變，將壓縮樣本集按照每一種行為模式從5%開始等比例增加，采用Accuracy 評估性能，通過多項式擬合的方法繪制曲線，如圖6 所示。

圖6 仿真場景中壓縮樣本集規(guī)模對算法分類準(zhǔn)確率的影響Fig.6 Influence of compressed dataset size on Accuracy of algorithm classification in simulation scenario

從圖6 可以看出，當(dāng)壓縮樣本集軌跡數(shù)據(jù)量較小的時候，Accuracy 隨著壓縮樣本集規(guī)模的增加而逐漸升高；當(dāng)壓縮樣本集軌跡數(shù)量達(dá)到一定規(guī)模時，Accuracy 總是保持在一個較高的水平。因此，獲得足夠的壓縮樣本集是保證軌跡行為規(guī)律預(yù)測的準(zhǔn)確性的前提。

5 實(shí)測數(shù)據(jù)實(shí)驗(yàn)分析

5.1 實(shí)測軌跡數(shù)據(jù)集

本實(shí)驗(yàn)選取了2006 年2 月某段時間美國舊金山機(jī)場雷達(dá)檢測出的部分航班飛行軌跡，該實(shí)測數(shù)據(jù)集總計有1 128 條時空軌跡。根據(jù)之前的研究工作［29］對該軌跡數(shù)據(jù)集進(jìn)行規(guī)律挖掘并標(biāo)記標(biāo)簽，其中包括14 種行為模式和57 條離群軌跡。所有軌跡如圖7 所示，不同行為模式的軌跡用不同的顏色表示，離群軌跡用黑色表示。圖8展示了該場景下目標(biāo)的14 種不同的行為模式。

圖7 真實(shí)軌跡數(shù)據(jù)集Fig.7 Plot of real trajectory dataset

圖8 14 種行為模式Fig.8 Plot of 14 beheavior patterns

5.2 實(shí)驗(yàn)與分析

本實(shí)驗(yàn)在實(shí)測數(shù)據(jù)集上實(shí)現(xiàn)了SSHNNICMP 算法，并分別與一致性多分類器CMC 與不一致性度量函數(shù)HD-KNN、STHD-KNN 的組合進(jìn)行對比分析。將整個仿真數(shù)據(jù)集隨機(jī)分成訓(xùn)練集和測試集，每一種行為模式的時空軌跡中25%作為測試集，75%作為訓(xùn)練集，對于ICP 而言，20%作為壓縮樣本集，5%作為檢驗(yàn)樣本集。設(shè)置風(fēng)險水平ε=0.01，K 近鄰參數(shù)K=3，按照上述比例隨機(jī)選取訓(xùn)練集和測試集進(jìn)行20 次重復(fù)實(shí)驗(yàn)。采用Precision、Recall、F1-score、Accuracy、FA 以及訓(xùn)練和測試消耗的總時間對算法的性能進(jìn)行評估，如表2 所示，其中的Precision、Recall 和F1-score 為每次實(shí)驗(yàn)所有行為模式類別間的平均值，表中的所有數(shù)據(jù)均為20 次重復(fù)試驗(yàn)的平均值，表中每項評估值的最優(yōu)結(jié)果用加粗表示。

表2 真實(shí)場景中算法性能比較Table 2 Comparison of algorithm performance in measured scene

圖9 展示了隨著壓縮樣本集規(guī)模增大Accuracy 的變化，通過多項式擬合的方法繪制曲線。從圖中可以看出，當(dāng)壓縮樣本集軌跡數(shù)據(jù)量較小時，Accuracy 隨著壓縮樣本集規(guī)模的增加而逐漸升高；當(dāng)壓縮樣本集軌跡數(shù)量接近一定數(shù)量時，Accuracy 總是保持在一個較高的水平。因此，在實(shí)際應(yīng)用場景中，當(dāng)壓縮樣本集軌跡數(shù)量足夠且適量時，即可保證算法具備良好的準(zhǔn)確性和實(shí)時性。

圖9 真實(shí)場景中壓縮樣本集規(guī)模對算法分類準(zhǔn)確率的影響Fig.9 Influence of compressed dataset size on Accuracy of algorithm classification in measured scenario

6 結(jié) 論

本文針對實(shí)時預(yù)警監(jiān)視需求，提出了基于時空軌跡信息的目標(biāo)行為模式在線分析方法，進(jìn)行了實(shí)驗(yàn)分析和驗(yàn)證，創(chuàng)新性工作包括幾個方面：

1） 提出了ICMP，解決了CMC 實(shí)時性不強(qiáng)、對離群軌跡不敏感等問題。

2） 提出了時空Hausdorff 距離概念，并結(jié)合KNN 構(gòu)造了DSHNN-NCM，可以有效區(qū)分位置、航向以及速度特征不同的目標(biāo)行為。

3） 提出了SSHNN-ICMP，可以在預(yù)警監(jiān)視場景下對目標(biāo)頻繁出現(xiàn)的行為進(jìn)行在線學(xué)習(xí)和預(yù)測。

4） 分別在仿真飛行器軌跡和實(shí)測雷達(dá)軌跡數(shù)據(jù)中實(shí)現(xiàn)了SSHNN-ICMP，結(jié)果表明本文算法與CMC 的組合算法相比在Precision、F1-score 以及Accuracy 等評價指標(biāo)上具有明顯的優(yōu)勢，且實(shí)時性顯著提高。

基于上述創(chuàng)新工作，下一步將重點(diǎn)研究無監(jiān)督條件下的目標(biāo)行為模式在線分析方法。