陳 勇

(中國電子科技集團(tuán)公司第五十四研究所，河北石家莊050081)

0 引言

目標(biāo)航跡數(shù)據(jù)聚類挖掘分析能夠從紛雜的航跡數(shù)據(jù)中發(fā)現(xiàn)目標(biāo)的潛在運(yùn)動軌跡，可以用于態(tài)勢數(shù)據(jù)挖掘、目標(biāo)行為意圖分析和空中交通流量分析等領(lǐng)域［1-5］?，F(xiàn)有的航跡數(shù)據(jù)挖掘算法大多數(shù)是針對整個(gè)航跡設(shè)計(jì)的，但在實(shí)際數(shù)據(jù)中，整條航跡具有相似性的情況不多，大多數(shù)情況是不同航跡之間在部分航跡線段上具有相似性，以整條航跡為研究對象的聚類算法往往不能發(fā)現(xiàn)局部航跡線段的聚集特性［6，7］。本文給出一種新的目標(biāo)航跡數(shù)據(jù)聚類分析算法，以航跡線段為對象設(shè)計(jì)聚類挖掘算法，并按照垂直距離、平行距離和角度距離計(jì)算航跡線段之間的距離，這種方法既能發(fā)現(xiàn)局部的航跡線段聚集特征，也能發(fā)現(xiàn)全局的航跡聚集特征。

1 問題描述

借助傳感器偵察手段，能夠獲取受關(guān)注區(qū)域內(nèi)移動目標(biāo)運(yùn)動軌跡的海量信息，這些信息中隱含著目標(biāo)運(yùn)動的特征規(guī)律，特征規(guī)律表現(xiàn)為相同或相似目標(biāo)運(yùn)動軌跡的反復(fù)出現(xiàn)，這些軌跡規(guī)律有助于推測目標(biāo)的行為意圖，但這些軌跡規(guī)律往往被淹沒在大量的噪聲航跡點(diǎn)數(shù)據(jù)中，不易被覺察發(fā)現(xiàn)，需要設(shè)計(jì)相關(guān)聚類分析算法幫助人們進(jìn)行分析。

一組待聚類分析的航跡可以表示為T={t1，t2，…，tn}。Ti(1≤i≤n)表示一條航跡，ti=p1p2…pm，pi(1≤i≤m)表示一個(gè)航跡點(diǎn)。聚類結(jié)果表示為R={C1，C2，…CN}，R 中包含了若干個(gè)簇，一個(gè)簇表示為 Ci(1≤i≤N)，Ci={L1，L2，…Lo}，Ci中包含了若干個(gè)航跡線段，一個(gè)航跡線段表示為Li(1≤i≤o)，Li?ti。

2 算法分析

運(yùn)動目標(biāo)航跡聚類分析方法用于對一批累積目標(biāo)航跡數(shù)據(jù)進(jìn)行聚類分析，將相似航跡線段聚在一起，從雜亂無章的眾多航跡線中發(fā)現(xiàn)目標(biāo)運(yùn)動潛在的運(yùn)動模式。

本文提出了一種目標(biāo)航跡聚類分析算法，其輸入包括:

輸入 1:航跡集合 T={t1，t2，t3，……tnum}，其中，ti(i=1，2，…，num)代表目標(biāo)航跡;

輸入2:指定ε(輻射距離)和support(輻射距離范圍內(nèi)的線段數(shù))2個(gè)參數(shù)。

其輸出為航跡(線段)聚類結(jié)果，算法具體執(zhí)行步驟描述如下:

第1步:對T中整條航跡按照航跡點(diǎn)進(jìn)行分割處理，航跡被分割成若干航跡線段，所有航跡線段組成集合D;

第2步:利用算法Line-Segment-Clustering算法對航跡段進(jìn)行分析，得到航跡段聚類結(jié)果。其中，Line-Segment-Clustering算法描述為:

①設(shè)置變量clusterID初始值為0;

②初始時(shí)，將集合D中每條航跡線段都標(biāo)記為“未分簇”，即未做歸簇處理;

③對于集合D中的每一條航跡線段Li(Li∈D)逐個(gè)進(jìn)行處理，首先判斷航跡線段Li是否已被歸到某個(gè)簇，具有了簇標(biāo)識，若航跡線段已有了簇標(biāo)識，則不做處理，若沒有簇標(biāo)識，則進(jìn)行如下處理過程;

④計(jì)算航跡線段Li鄰域范圍內(nèi)與其距離小于閾值ε的航跡線段的集合Nε(Li)所含航跡線段的數(shù)量，|Nε(Li)|={Lj∈D|dist(Li，Lj)≤ε};

⑤如果Li鄰域范圍的航跡線段數(shù)量大于或等于閾值support，則將集合Nε(Li)中的每一個(gè)線段都分配一個(gè)簇標(biāo)識clusterID;否則，直接轉(zhuǎn)到第⑨步;

⑥將Nε(Li)中的成員線段放入隊(duì)列Q中;

⑦利用擴(kuò)展處理函數(shù)(見表2的說明文字)對Q進(jìn)行處理;

⑧讓變量clusterID增加1;

⑨如果Li鄰域范圍的航跡線段數(shù)量小于閾值support，則將Li標(biāo)記為噪聲;

⑩經(jīng)過上述步驟之后，集合D中的每一個(gè)元素都被賦予了簇標(biāo)識;

[11] D中的航跡線段按照其簇標(biāo)識分配到相應(yīng)的簇中;

[12]對于每一個(gè)簇，通過線段與原始航跡之間的映射關(guān)系，找出cluster中包含的原始航跡數(shù)量，如果航跡數(shù)量大于某一個(gè)預(yù)定值，則保留這個(gè)簇，否則，刪除這個(gè)簇。

算法的偽代碼如表1所示。

表1 算法描述

擴(kuò)展處理函數(shù)的算法描述為:

① 接收參數(shù)Q，clusterID，ε 和support，以循環(huán)方式對Q中的每一個(gè)成員航跡線段進(jìn)行處理;

②計(jì)算Q中成員線段M的領(lǐng)域線段集合Nε(M);

③如果Nε(M)所含線段數(shù)量大于或等于support，則把集合Nε(M)中的每一個(gè)未分簇或噪聲線段都標(biāo)識為clusterID;否則，什么都不做，進(jìn)入下一次循環(huán)，處理Q中的下一個(gè)成員線段。

擴(kuò)展處理算法的偽代碼如表2所示。

表2 擴(kuò)展處理函數(shù)描述

3 實(shí)驗(yàn)計(jì)算結(jié)果分析

采用仿真數(shù)據(jù)對航跡聚類分析算法進(jìn)行了測試，仿真數(shù)據(jù)分為6組，分別包含了2 000、4 000、6 000、8 000、15 000和25 000個(gè)航跡點(diǎn)，每個(gè)航跡點(diǎn)關(guān)聯(lián)了目標(biāo)出現(xiàn)時(shí)間、位置經(jīng)度和位置緯度信息。

在一臺配置為Pentium CPU 3.00 GHz、2 GB內(nèi)存、250 GB硬盤的PC上開展了航跡聚類分析實(shí)驗(yàn)。聚類分析的執(zhí)行時(shí)間如圖1所示，聚類算法的執(zhí)行時(shí)間隨著航跡中所含航跡點(diǎn)的數(shù)量增大而增加。

圖1 航跡聚類算法執(zhí)行時(shí)間

航跡聚類結(jié)果如圖2所示，圖中淺灰色細(xì)線段是通過傳感器觀測到的飛機(jī)運(yùn)動形成的航跡線段，黑色粗線段是聚類生成的航跡簇的標(biāo)識性線段。實(shí)驗(yàn)結(jié)果表明算法能排除零星散布航跡線段的干擾，準(zhǔn)確地將鄰近密集分布的航跡線段歸為一簇。

圖2 航跡聚類結(jié)果

4 結(jié)束語

本文以運(yùn)動目標(biāo)航跡聚類為研究目標(biāo)，針對航跡中的航跡線段設(shè)計(jì)了聚類算法，依據(jù)垂直距離、平行距離和角度距離量度線段之間的距離，通過對實(shí)際航跡數(shù)據(jù)的聚類分析試驗(yàn)，實(shí)驗(yàn)結(jié)果表明，該算法能夠排除零散航跡的影響，從目標(biāo)航跡數(shù)據(jù)中發(fā)現(xiàn)目標(biāo)的運(yùn)動軌跡特征。該算法可以應(yīng)用到目標(biāo)行為意圖分析、目標(biāo)行為異常檢測等領(lǐng)域。

［1］ 王濤波，黃寶軍.基于4D航跡的模糊聚類分析［J］.交通信息與安全，2013，31(180):38-42.

［2］ 王潔寧，孫 禾，趙元棣.基于時(shí)間—空間的進(jìn)場航跡聚類分析［J］.科學(xué)技術(shù)與工程，2013，13(33):10 078-10 081.

［3］ 王 超，徐肖豪，王 飛.基于航跡聚類的終端區(qū)進(jìn)場程序管制適用性分析［J］.南京航空航天大學(xué)學(xué)報(bào)，2013，45(1):130-139.

［4］ 王 超，王明明，王 飛.基于改進(jìn)的模糊C-Means航跡聚類方法研究［J］.中國民航大學(xué)學(xué)報(bào)，2013，31(3):14-18.

［5］ 楊詠建，祝勝強(qiáng).態(tài)勢標(biāo)繪系統(tǒng)設(shè)計(jì)分析［J］.無線電通信技術(shù)，2012，38(1):52-55.

［6］ 王增福，潘 泉，郎 林，等.基于減法聚類的動態(tài)航跡聚類算法［J］.系統(tǒng)仿真學(xué)報(bào)，2009，21(16):5 240-5 246.

［7］ ACHTERT E，B?OHM C，KRIEGEL H-P，et al.Deriving Quantitative Models for Correlation Clusters［C］∥ 12th ACM SIGKDD Int'l Conf.on Knowledge Discovery and Data Mining，Philadelphia，Pennsylvania，2006:4-13.