（海軍航空大學(xué) 煙臺(tái) 264001）

1 引言

目標(biāo)行為規(guī)律是指目標(biāo)在以往執(zhí)行具體任務(wù)時(shí)表現(xiàn)出來(lái)的相似或相同的行為特征，例如目標(biāo)在以往執(zhí)行偵察任務(wù)時(shí)的相同或相似的航線、速度、航向等行為特征。在信息融合領(lǐng)域，基于歷史數(shù)據(jù)庫(kù)中積累的大量歷史目標(biāo)航跡數(shù)據(jù)，利用數(shù)據(jù)挖掘技術(shù)中的無(wú)監(jiān)督聚類(lèi)技術(shù)，通過(guò)對(duì)目標(biāo)航跡數(shù)據(jù)的聚類(lèi)分析，可以挖掘出目標(biāo)的行為規(guī)律。國(guó)內(nèi)外很多學(xué)者在時(shí)間序列聚類(lèi)［1］和軌跡聚類(lèi)［2～3］方面進(jìn)行了大量的研究，對(duì)數(shù)據(jù)挖掘領(lǐng)域中不同的聚類(lèi)技術(shù)進(jìn)行了概述［4］。根據(jù)研究方法不同，常見(jiàn)的軌跡聚類(lèi)方法基本可分為基于距離的軌跡聚類(lèi)［5～7］、基于模型的軌跡聚類(lèi)［8］和基于劃分的軌跡聚類(lèi)［9］等。

目前，大多數(shù)的軌跡聚類(lèi)方法都是將空間位置相近的軌跡聚為同一類(lèi)，沒(méi)有充分考慮多維目標(biāo)航跡的速度、航向、屬性和類(lèi)型等多維特征。部分子軌跡聚類(lèi)方法考慮了軌跡段的方向、速度和角度信息，但不適用于對(duì)整個(gè)軌跡進(jìn)行聚類(lèi)分析的應(yīng)用場(chǎng)景，且現(xiàn)有軌跡聚類(lèi)方法都沒(méi)有充分考慮目標(biāo)的屬性和類(lèi)型信息。因此，本文針對(duì)海上復(fù)雜環(huán)境，基于目標(biāo)的多為航跡特征，提出一種目標(biāo)軌跡聚類(lèi)方法，利用改進(jìn)的DBSCAN密度聚類(lèi)算法完成對(duì)目標(biāo)航跡的無(wú)監(jiān)督聚類(lèi)。

2 海上目標(biāo)多維航跡數(shù)據(jù)

在進(jìn)行海上態(tài)勢(shì)分析的過(guò)程中，目標(biāo)航跡數(shù)據(jù)通常是由多維航跡數(shù)據(jù)點(diǎn)組成的多維序列［10］，包括時(shí)間、位置、速度、航向、敵我屬性、類(lèi)別等多維信息。

設(shè)目標(biāo)海域內(nèi)的航跡樣本數(shù)據(jù)集為

其中，TR為全部航跡樣本集合，i∈[1，n]為樣本編號(hào)，n為樣本數(shù)據(jù)集總數(shù)；每條目標(biāo)航跡TRi(i=1，2，…，n)中含有m個(gè)按時(shí)間順序排列的多維數(shù)據(jù)點(diǎn)，即

其中，TRi(j)為第i條航跡樣本中的第j個(gè)多維航跡數(shù)據(jù)點(diǎn)，j∈[1，m]為航跡數(shù)據(jù)點(diǎn)編號(hào)，m為該航跡樣本中的數(shù)據(jù)點(diǎn)總數(shù)；每個(gè)航跡數(shù)據(jù)點(diǎn)TRi(j)(j=1，2，…，m)中包含q個(gè)多維特征，其表達(dá)式為

其中，向量TRi(j)中含有q個(gè)元素，表示第i條航跡樣本中的第j個(gè)多維航跡數(shù)據(jù)點(diǎn)TRi(j)中包含時(shí)間、位置、速度、加速度、航向、敵我屬性和類(lèi)型等q個(gè)多維特征。

3 目標(biāo)軌跡聚類(lèi)方法

3.1 改進(jìn)的DBSCAN密度聚類(lèi)

聚類(lèi)算法［8］的提出是為了有效解決數(shù)據(jù)集合分類(lèi)問(wèn)題。經(jīng)過(guò)不斷的發(fā)展，當(dāng)前聚類(lèi)算法主要分為劃分聚類(lèi)、密度聚類(lèi)［9，11］、層次聚類(lèi)、模型聚類(lèi)和網(wǎng)格聚類(lèi)［12］五種。DBSCAN是一種典型的無(wú)監(jiān)督、密度聚類(lèi)算法，聚類(lèi)時(shí)以數(shù)據(jù)集在空間分布上的稠密程度為依據(jù)，適合應(yīng)用于沒(méi)有先驗(yàn)知識(shí)的大規(guī)模數(shù)值型數(shù)據(jù)。該算法可發(fā)現(xiàn)任意形狀的聚類(lèi)且抗干擾能力強(qiáng)，在聚類(lèi)的同時(shí)發(fā)現(xiàn)異常點(diǎn)，對(duì)數(shù)據(jù)集中異常點(diǎn)不敏感。

下面給出DBSCAN算法相關(guān)參數(shù)的定義。

Definition 1ε鄰域：對(duì)于樣本數(shù)據(jù)集中任意兩個(gè)數(shù)據(jù)點(diǎn)p和q，點(diǎn)q屬于點(diǎn)p的ε鄰域當(dāng)且僅當(dāng)兩點(diǎn)之間的距離不大于ε，即點(diǎn)p的ε鄰域Nε(p)可以定義為

其中，dist(p，q)表示p、q兩點(diǎn)間的距離。

Definition 2最小近鄰點(diǎn)數(shù)量MinPts：為用戶(hù)指定閾值，用于定義簇中一點(diǎn)的鄰域密度，即該點(diǎn)的ε鄰域內(nèi)至少應(yīng)有MinPts個(gè)點(diǎn)。

結(jié)合相關(guān)定義，簡(jiǎn)述DBSCAN算法思想如下：

綜合上述DBSCAN算法思想，結(jié)合海上目標(biāo)多維航跡特征，改進(jìn)如下：

給定兩條目標(biāo)航跡TRA、TRB，取j∈[1 ，m] 時(shí)刻對(duì)應(yīng)的兩個(gè)目標(biāo)航跡數(shù)據(jù)點(diǎn)PA、PB，即有PA=TRA(j)、PB=TRB(j)。首先分析當(dāng)前戰(zhàn)場(chǎng)環(huán)境下目標(biāo)航跡的多維屬性特征，分配適合的屬性權(quán)重；而后，計(jì)算PA、PB兩點(diǎn)間的多維度歐式距離，作為航跡數(shù)據(jù)點(diǎn)間的多維度相似性度量。其中，定義兩點(diǎn)間的多維度歐式距離mfdist(PA，PB)為

式中，dist(PA，PB)表示PA、PB兩點(diǎn)間位置特征的歐式距離；與表示PA、PB兩點(diǎn)的速度大小，表示PA、PB兩點(diǎn)的航向大??；wd、wv、wθ分別表示位置、速度和航向特征的權(quán)重因子，各屬性權(quán)重的取值取決于多因素距離的應(yīng)用場(chǎng)景，且滿(mǎn)足條件wd+wv+wθ=1；aPA、aPB表示PA、PB兩點(diǎn)的敵我屬性值，f(aPA，aPB)用于判斷PA、PB兩點(diǎn)的敵我屬性是否相同，若相同，則有f(aPA，aPB)=1，否則，f(aPA，aPB)=∞ 。然后，輸入?yún)?shù)ε和MinPts，基于定義的多因素歐式距離，對(duì)目標(biāo)航跡數(shù)據(jù)點(diǎn)進(jìn)行DBSCAN密度聚類(lèi)。

3.2 目標(biāo)軌跡聚類(lèi)方法流程

基于上述改進(jìn)的DBSCAN密度聚類(lèi)算法，設(shè)計(jì)目標(biāo)軌跡聚類(lèi)方法的流程如下。

步驟1：取目標(biāo)航跡樣本數(shù)據(jù)集TR中，每條目標(biāo)航跡樣本的第j個(gè)數(shù)據(jù)點(diǎn)，形成樣本數(shù)據(jù)集j∈[1，m]。

步驟2：對(duì)樣本數(shù)據(jù)集TR(j)進(jìn)行改進(jìn)的DBSCAN密度聚類(lèi)。

輸入：1.目標(biāo)航跡數(shù)據(jù)點(diǎn)集合TR(j)

2.閾值參數(shù)ε和MinPts

輸出：航跡數(shù)據(jù)點(diǎn)簇集合C(j)={C1，C2，…，Cs}，s為生成簇的個(gè)數(shù)

1.repeat；

2.從樣本數(shù)據(jù)集TR(j)中隨機(jī)抽取一個(gè)未訪問(wèn)的航跡數(shù)據(jù)點(diǎn)TRi(j)，i∈[1，n]；

3.if|Nε(pi)|≥MinPts，即點(diǎn)TRi(j)為核心點(diǎn)（Core Point）；

4.then找出點(diǎn)TRi(j)密度可達(dá)的所有數(shù)據(jù)點(diǎn)集合O(j)，形成一個(gè)航跡數(shù)據(jù)點(diǎn)簇C1；其中，O(j)={TRo(j)|TRo(j)∈TR(j)且TRi(j)到TRo(j)密度可達(dá)}。

5.else點(diǎn)TRi(j)是非核心點(diǎn)（邊緣點(diǎn)或噪聲點(diǎn)），跳出此次循環(huán)，尋找下一個(gè)未訪問(wèn)點(diǎn)TRr(j)，TRr(j)∈TR(j)；

6.util樣本數(shù)據(jù)集TR(j)中所有樣本數(shù)據(jù)點(diǎn)都被處理。

步驟3：循環(huán)執(zhí)行上述步驟m次，使正整數(shù)j遍歷區(qū)間[1，m]，得到m個(gè)航跡數(shù)據(jù)點(diǎn)簇集合C={C(1)，C(2)，…，C(j)，…，C(m)}。

步驟4：由對(duì)目標(biāo)航跡數(shù)據(jù)點(diǎn)的聚類(lèi)，實(shí)現(xiàn)對(duì)目標(biāo)航跡軌跡的聚類(lèi)。設(shè)定比例閾值β，目標(biāo)航跡數(shù)據(jù)集TR中的任兩條航跡TRi和TRj，i，j∈[1，n]，若每條航跡包含的m個(gè)數(shù)據(jù)點(diǎn)中，有a個(gè)數(shù)據(jù)點(diǎn)都屬于對(duì)應(yīng)的同一航跡數(shù)據(jù)點(diǎn)簇，且滿(mǎn)足，則這兩條航跡屬于同一航跡聚類(lèi)簇。

4 實(shí)驗(yàn)驗(yàn)證分析

為了驗(yàn)證本研究提出的目標(biāo)軌跡聚類(lèi)方法性能，在一個(gè)軍用場(chǎng)景的數(shù)據(jù)集上進(jìn)行仿真實(shí)驗(yàn)并對(duì)結(jié)果進(jìn)行分析，通過(guò)仿真的多維航跡數(shù)據(jù)來(lái)模擬戰(zhàn)場(chǎng)目標(biāo)的活動(dòng)情況，對(duì)航跡數(shù)據(jù)進(jìn)行處理。

4.1 數(shù)據(jù)集

目標(biāo)航跡數(shù)據(jù)通常是由多維航跡數(shù)據(jù)點(diǎn)組成的多維序列，通常包括時(shí)間、位置、速度、航向、敵我屬性、類(lèi)別等多維信息。本實(shí)驗(yàn)參考了文獻(xiàn)［11］，利用Piciarelli公開(kāi)的目標(biāo)航跡生成程序［12］，生成含有二維位置信息的目標(biāo)航跡數(shù)據(jù)，然后人為添加目標(biāo)的速度、航向、敵我屬性和類(lèi)型等信息，構(gòu)造出多維目標(biāo)航跡仿真數(shù)據(jù)集。設(shè)仿真目標(biāo)的運(yùn)動(dòng)方向?yàn)橛牲c(diǎn) (xi，yi)到點(diǎn) (xi+1，yi+1)，且同一目標(biāo)航跡中任意兩個(gè)相鄰數(shù)據(jù)點(diǎn)間的時(shí)間間隔t相等。如圖1所示，目標(biāo)的速度vi和航向θi特征可以由式（7）和式（8）計(jì)算得出。

圖1 航跡的速度和航向示意圖

本實(shí)驗(yàn)數(shù)據(jù)集包括代表4種目標(biāo)行為規(guī)律的360條多維航跡數(shù)據(jù)和10條不規(guī)律的目標(biāo)航跡數(shù)據(jù)。構(gòu)造過(guò)程如下：首先，利用目標(biāo)航跡生成程序產(chǎn)生4個(gè)簇的360條規(guī)律目標(biāo)航跡數(shù)據(jù)和10條不規(guī)律目標(biāo)航跡數(shù)據(jù)。然后，根據(jù)每條航跡的起始點(diǎn)位置不同，將目標(biāo)航跡的屬性標(biāo)簽分別設(shè)置為敵方（1）、我方（2）和中立方（0），按目標(biāo)型號(hào)設(shè)置類(lèi)型標(biāo)簽，速度和航向信息可由式（7）、式（8）計(jì)算得出，這樣就生成了370條多維目標(biāo)航跡數(shù)據(jù)。最后，對(duì)修改后的370條航跡隨機(jī)排序，得到了實(shí)驗(yàn)仿真數(shù)據(jù)集。

4.2 實(shí)驗(yàn)分析

本仿真環(huán)境下，每條目標(biāo)航跡TRi(i=1，2，…，n)都由32個(gè)時(shí)刻的數(shù)據(jù)點(diǎn)組成，利用所提方法，確定閾值參數(shù)ε和MinPts的取值。當(dāng)t=j，j∈[1，32]時(shí)，對(duì)所有航跡中對(duì)應(yīng)的j時(shí)刻數(shù)據(jù)點(diǎn)進(jìn)行密度聚類(lèi)，輸出所生產(chǎn)的簇，同時(shí)分離出該時(shí)刻數(shù)據(jù)點(diǎn)樣本集合中的噪聲點(diǎn)。循環(huán)32次后，根據(jù)對(duì)航跡數(shù)據(jù)點(diǎn)的密度聚類(lèi)結(jié)果，實(shí)現(xiàn)對(duì)航跡軌跡的分簇。

需注意，在進(jìn)行t=j時(shí)刻的密度聚類(lèi)時(shí)，少量游離于簇外的數(shù)據(jù)點(diǎn)中，既包含不規(guī)律航跡的數(shù)據(jù)點(diǎn)，又包含行為規(guī)律的航跡中誤差較大的異常點(diǎn)。為了防止因個(gè)別誤差較大的異常點(diǎn)而影響整條目標(biāo)航跡的有效性，通過(guò)對(duì)航跡軌跡的分簇，可有效防止該情況的產(chǎn)生。在本仿真環(huán)境下，確定閾值β的取值為β=0.9，即每條目標(biāo)航跡都由32個(gè)時(shí)刻的數(shù)據(jù)點(diǎn)組成，若每條航跡的32個(gè)數(shù)據(jù)點(diǎn)中有29個(gè)點(diǎn)實(shí)現(xiàn)了對(duì)應(yīng)的分簇，則該航跡即為一條行為規(guī)律的航跡。

本實(shí)驗(yàn)中取wd=0.6、wv=0.2、wθ=0.2來(lái)計(jì)算兩點(diǎn)間的多維度歐式距離，利用改進(jìn)的DBSCAN算法對(duì)一次隨機(jī)生成的目標(biāo)航跡數(shù)據(jù)點(diǎn)樣本集合進(jìn)行密度聚類(lèi)處理。經(jīng)試驗(yàn)驗(yàn)證，取參數(shù)ε=0.017，MinPts=20時(shí)，仿真結(jié)果最優(yōu)。部分時(shí)刻數(shù)據(jù)點(diǎn)的密度聚類(lèi)情況如圖2、圖3、圖4、圖5所示。

圖2 t=2時(shí)刻的航跡數(shù)據(jù)點(diǎn)分布情況

圖3 t=2時(shí)刻的數(shù)據(jù)點(diǎn)實(shí)際分類(lèi)結(jié)果

圖4 t=26時(shí)刻的航跡數(shù)據(jù)點(diǎn)分布情況

圖5 t=26時(shí)刻的數(shù)據(jù)點(diǎn)實(shí)際分類(lèi)結(jié)果

本實(shí)驗(yàn)利用改進(jìn)的DBSCAN算法進(jìn)行目標(biāo)軌跡聚類(lèi)，輸出軌跡聚類(lèi)前、后的戰(zhàn)場(chǎng)目標(biāo)航跡分布圖，結(jié)果如圖6和圖7所示。對(duì)數(shù)據(jù)集中370條航跡進(jìn)行軌跡聚類(lèi)，挖掘其中360條行為規(guī)律的目標(biāo)航跡和10條不規(guī)律的目標(biāo)航跡，實(shí)際檢測(cè)出11條行為不規(guī)律的目標(biāo)航跡。

圖6 軌跡聚類(lèi)前目標(biāo)航跡分布圖

圖7 軌跡聚類(lèi)后目標(biāo)航跡分布圖

5 結(jié)語(yǔ)

本文針對(duì)海上態(tài)勢(shì)生成需求，基于目標(biāo)的多維航跡特征定義了多維度歐式距離，進(jìn)而利用改進(jìn)的DBSCAN算法，設(shè)計(jì)了一種目標(biāo)軌跡聚類(lèi)方法，并在仿真軍事場(chǎng)景上進(jìn)行了實(shí)驗(yàn)分析驗(yàn)證。結(jié)果表明，該方法能夠根據(jù)戰(zhàn)場(chǎng)態(tài)勢(shì)需求，結(jié)合目標(biāo)的位置、速度、航向、敵我屬性和類(lèi)型等多維特征，高效、準(zhǔn)確地從海量歷史數(shù)據(jù)中實(shí)現(xiàn)海洋復(fù)雜環(huán)境下的目標(biāo)軌跡聚類(lèi)，為下一步開(kāi)展海上態(tài)勢(shì)分析奠定基礎(chǔ)。