高 軼，王 鵬

(1.海軍裝備部信息系統(tǒng)局，北京 100841；2.中國電子科技集團公司第五十四研究所，河北 石家莊 050081)

0 引言

對于目標活動行為，傳統(tǒng)的處理方法多注重于實時態(tài)勢的展示[1]，用于目標行為信息的實時反映，保障信息數(shù)據(jù)處理的時效性，對于積累的大量目標活動歷史信息數(shù)據(jù)并沒有過多關注，而目標的行為規(guī)律則只有通過對長時間的歷史數(shù)據(jù)進行分析才有可能獲得。面向積累的海量目標活動數(shù)據(jù)，單憑人工方式來發(fā)現(xiàn)這些規(guī)律是不現(xiàn)實的，因此通過數(shù)據(jù)挖掘方法對海量數(shù)據(jù)進行挖掘，對于掌握目標行為規(guī)律具有非常重要的意義。目前，國內外已經展開了相關研究，如軌跡聚類[2-4]、活動規(guī)律分析[5-7]和軌跡相似性計算[8-9]。其中，文獻[5]利用地理網格技術劃分港口水域，并對每個地理單元格上的傳播行為進行統(tǒng)計分析來揭示整個海域船舶行為規(guī)律，但并未考慮某船舶行為在時間維度上的連續(xù)性；文獻[6]采用混合高斯模型和主成分分析模型對目標軌跡行為進行了分析，并對異常行為進行識別；文獻[7]采用序列模式挖掘方法對潛在的多個目標間的出現(xiàn)規(guī)律進行了分析，但并非針對某個目標的活動規(guī)律進行挖掘。針對目標的行為規(guī)律發(fā)掘問題，本文提出了一種基于數(shù)據(jù)挖掘的目標行為規(guī)律分析算法，對目標軌跡進行預處理以提高數(shù)據(jù)質量，利用地理網格技術對感興趣區(qū)域進行柵格化處理并利用柵格編號表示目標位置，利用目標多次運動軌跡按照時間排序構建觀測序列，利用序列關聯(lián)分析算法對觀測序列進行挖掘和分析，用以提取一段時間內的目標行為規(guī)律，實現(xiàn)目標活動信息的掌握，達到有效支持輔助決策的目的。

1 數(shù)據(jù)挖掘概念

數(shù)據(jù)挖掘是指對大量的、不完全的、有噪聲的、模糊的、隨機的數(shù)據(jù)進行分析以提取隱含的、可信的、新穎的和有效的信息處理過程[10]。其意義在于能夠從大量的數(shù)據(jù)中提取事先未知的、不可預料的知識和信息，這些信息對于決策人員可能是非常有用的。數(shù)據(jù)挖掘任務主要包括分類預測任務和描述任務兩大類[11]，其中預測任務是指根據(jù)其他屬性的值來預測特定屬性的值，而描述任務的目標則是實現(xiàn)對數(shù)據(jù)中潛在聯(lián)系的模式(相關、趨勢、聚類、軌跡和異常)進行概括。本文所涉及的問題就屬于描述任務的范疇，主要是通過對積累的歷史數(shù)據(jù)進行分析，實現(xiàn)目標行為規(guī)律的挖掘，采用的數(shù)據(jù)挖掘方法主要涉及關聯(lián)分析算法。

1.1 關聯(lián)分析的概念

關聯(lián)分析是數(shù)據(jù)挖掘的經典方法，用以描述一場交易中物品之間同時出現(xiàn)的規(guī)律的知識模式，并用關聯(lián)規(guī)則或頻繁項集的形式進行表示，用以揭示事物之間的聯(lián)系，其基本概念和定義如下[12]：

設I={i1，i2，…，im}是項的集合，事務數(shù)據(jù)庫D={t1，t2，…，tn}是由一系列具有唯一標志的事務組成，事務ti={Ii1，Ii2，…，Iik}對應I上的一個子集，即ti?I。關聯(lián)分析就是從大量的數(shù)據(jù)中發(fā)現(xiàn)項集之間的關聯(lián)和相關關系，實現(xiàn)對項集中某些項同時出現(xiàn)規(guī)律或模式的發(fā)掘，獲得形如X?Y的蘊涵式(關聯(lián)規(guī)則)，其中，X、Y表示項集，且滿足X?ti，Y?ti，X∩Y=?。

在關聯(lián)規(guī)則中，用支持度和置信度對關聯(lián)規(guī)則的強度進行描述。在關聯(lián)規(guī)則X?Y中，支持度是指事務數(shù)據(jù)庫中包含X∪Y的事務占事務數(shù)據(jù)庫D的百分比，用以描述當前項集的頻繁程度，形式如下：

(1)

式中，n表示事務數(shù)據(jù)庫D所包含事務的個數(shù)。置信度是指事務數(shù)據(jù)庫中包含X∪Y的事務數(shù)與包含X的事務數(shù)之比，用于對當前規(guī)則的可靠性進行度量。置信度越高，則表明Y在包含X的事務中出現(xiàn)的可能性就越大，形式如下：

(2)

式中，σ(X)=|{ti|X?ti，ti∈T}|表示項集X的支持度計數(shù)，即當前數(shù)據(jù)庫中包含特定項集的事務個數(shù)。

1.2 關聯(lián)規(guī)則挖掘典型流程

目前，大多數(shù)關聯(lián)規(guī)則挖掘算法采用的策略是將關聯(lián)規(guī)則挖掘的任務分為以下2個步驟：

① 頻繁項集的產生，其目標是發(fā)現(xiàn)滿足設定的最小支持度閾值的所有項集，稱之為頻繁項集，常用的頻繁項集挖掘算法包括Apriori[13]，F(xiàn)P-Growth[14]等算法；

② 規(guī)則的產生，其目標是從步驟①中發(fā)現(xiàn)的頻繁項集中提取所有高置信度的規(guī)則，稱之為強規(guī)則。

1.3 序列模式挖掘

軌跡數(shù)據(jù)存在固有的序列特征，而以上所討論的關聯(lián)規(guī)則都只強調同時發(fā)生，忽略了數(shù)據(jù)中的時間信息。在不同時間點上收集到的目標位置數(shù)據(jù)反映了目標隨時間的變化狀態(tài)，構成了軌跡數(shù)據(jù)，也稱之為時間序列。若需要分析軌跡數(shù)據(jù)中的序列特征，就需要利用序列模式挖掘。通過序列模式挖掘可以發(fā)現(xiàn)時間序列數(shù)據(jù)之間的信息，獲取蘊含在軌跡數(shù)據(jù)中的目標行為規(guī)律。

序列模式的發(fā)現(xiàn)就是在給定的序列數(shù)據(jù)集和設定的最小支持度閾值條件下，找出滿足條件的所有序列，其步驟主要包括排序、頻繁項集產生、轉換和序列產生等階段，常用的算法主要包括2類：一類是基于候選產生測試的Apriori算法以及衍生的如AprioriAll[15]，GSP[16]等相關算法；另一類是基于分而治之的數(shù)據(jù)庫投影模式的PrefixSpan算法[17]以及相關類似算法。

2 目標行為規(guī)律分析算法

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

數(shù)據(jù)預處理的主要目的是提高數(shù)據(jù)集的質量和降低數(shù)據(jù)的復雜度。為提高數(shù)據(jù)集質量，本文采用去重、中值濾波、平滑濾波等方法對數(shù)據(jù)中存在的重復點、異常點進行剔除。為降低數(shù)據(jù)的復雜度并方便后續(xù)數(shù)據(jù)分析工作，本文采用地理網格技術對感興趣區(qū)域進行柵格化處理，并利用柵格編號對目標位置進行表示。

2.1.1 異常點剔除

異常點也稱離群點，是指屬性值明顯偏離期望的屬性值。本文異常點是指由于受到被動偵測特點或其他環(huán)境因素影響所引起的明顯偏離目標正常運動規(guī)律的軌跡點，可采用中值濾波、均值濾波[18]、卡爾曼濾波[19]和粒子濾波[20]等方法進行異常點過濾，每種算法都具有其適用性[21]。

本文采用中值濾波方法進行異常點去除的效果如圖1所示。其中，圖1(a)為原始目標軌跡，圖1(b)為預處理后的目標軌跡。從圖中可以發(fā)現(xiàn)，本文待處理的軌跡數(shù)據(jù)存在大量的異常點，經過預處理，可以有效剔除目標軌跡中的異常點，使得目標運動軌跡更加平滑，有效地提高了軌跡數(shù)據(jù)的質量。

圖1 異常軌跡點剔除結果

2.1.2 軌跡擬合

未擬合的目標軌跡數(shù)據(jù)以及經過多項式擬合后的軌跡數(shù)據(jù)如圖2所示。從圖2中可以看出，未經擬合處理的軌跡數(shù)據(jù)存在明顯的不連續(xù)處。而經過多項式擬合，可以有效補充軌跡點之間的缺失部分。此外，不同手段或同一手段不同時間獲取的目標軌跡數(shù)據(jù)采樣基準可能不一致，采用擬合方法還可以通過控制因變量實現(xiàn)采樣基準的一致性。

受被動偵測以及其他環(huán)境因素影響，目標軌跡可能存在不連續(xù)的情況，如圖2中原始軌跡點所示。此外，同一目標軌跡數(shù)據(jù)可能由多種手段獲取，并不能保證其采樣基準一致。為解決以上2個問題，本文對剔除異常點后的軌跡進行擬合，常用的擬合方法包括多項式擬合、三次樣條插值等方法。

圖2 軌跡擬合結果

2.1.3 目標位置柵格化

目標軌跡是目標位置按照時間排序的結果，其位置信息通常以經緯度的形式表示，因此，目標軌跡是時間—經度—緯度的三維表示，復雜度較高，并且不利于后續(xù)數(shù)據(jù)挖掘分析。為降低數(shù)據(jù)復雜度，并進一步消除測向定位引起的位置誤差，本文對感興趣區(qū)域運用地理網格技術進行柵格化處理，利用網格編號替代經緯度實現(xiàn)目標位置的唯一表示，將目標軌跡由時間—經度—緯度的三維表示簡化為時間—網格編號的二維表示。本文對感興趣區(qū)域進行柵格化處理的示意圖如圖3所示，每個網格的大小為0.1°×0.1°，網格的大小可以根據(jù)位置精度及其他需求進行綜合考慮。

圖3 目標位置柵格化示意

2.2 行為規(guī)律挖掘

對經過預處理的軌跡數(shù)據(jù)進行序列模式挖掘以得到該目標的行為規(guī)律，詳細步驟如下：

① 構建目標行為序列數(shù)據(jù)：將經過預處理的一個目標的多次觀測按照觀測時間排序構造形成目標行為序列數(shù)據(jù)S={s1，s2，…，sm}，其中，si代表該目標的一次觀測軌跡，m表示該目標觀測軌跡的數(shù)量；

② 設定參數(shù)：設置頻繁序列支持度為T，設置頻繁序列的長度N；

③ 單元素頻繁序列挖掘：對目標行為序列數(shù)據(jù)中的軌跡點位置編號進行去重得到序列中包含的元素，通過計算得到滿足支持度T的單元素頻繁序列C1；

④ 對得到的單元素頻繁序列C1進行遍歷，得到所有可能的兩元素組合，計算判斷滿足頻繁序列支持度T的兩元素組合，得到兩元素頻繁序列C2；

⑤ 根據(jù)單元素頻繁序列C1、兩元素頻繁序列C2，通過添加新的元素構建新的三元素備選序列，計算判斷滿足多元素頻繁序列支持度T的三元素組合，得到三元素頻繁序列C3；

⑥ 依此類推，重復步驟⑤，得到滿足長度為N的頻繁序列；若參數(shù)N為空，則得到所有長度的頻繁序列，直至頻繁序列集合不再增加為止；

⑦ 輸出集合C1、C2，...，CN，至此得到滿足參數(shù)T，N的所有頻繁序列。

3 仿真實驗

為驗證所提算法的有效性，進行了計算機仿真實驗。仿真實驗數(shù)據(jù)共包含5組同一目標的真實軌跡觀測數(shù)據(jù)，如圖4所示?？梢园l(fā)現(xiàn)，雖然5次軌跡數(shù)據(jù)長度、運動方向等并不完全相同，但存在共同的運動趨勢，并經過相同的位置，即該目標的行為存在一定的規(guī)律。

圖4 目標軌跡數(shù)據(jù)

按照2.1節(jié)中方法進行預處理后，5條軌跡可以表示為：

s1={133，138，142，143，147，152，157，162，166，167，171，176，181}；

s2={19，24，29，34，39，49，53，54，59，64，73，78，83，88，93，98，103，108，113，118，123，128，133，137，138，142，147，152，157，162，166，167，171，176，181，186}；

s3={4，9，14，24，29，34，44，49，54，59，73，78，83，88，93，98，103，108，113，118，123，128，133，143，148，153，158，163，167，168，172，176，177，181，186}；

s4={34，44，49，54，59，64，69，74，78，79，83，88，103，108，113，118，123，128，133，138，143，148，153，158，162，167，172，176，181}；

s5={9，24，29，34，39，44，49，54，59，64，69，74，78，79，83，88，93，98，103，108，113，118，123，128，133，138，143，148，153，158，163，167，168，172，176，177，181}。

按照2.2節(jié)中目標行為規(guī)律挖掘方法對上述軌跡數(shù)據(jù)進行分析，設定頻繁序列支持度T=4時，得到的頻繁序列為{34，49，54，59，78，88，103，108，113，123，128，133，167，176，181}；而當設定多元素頻繁序列支持度閾值為T=5時，得到的頻繁序列為{133，167，176，181}。

上述挖掘得到的頻繁序列的含義是，對當前積累的該目標的歷史活動軌跡進行目標行為規(guī)律分析可得，有80%的概率按照支持度為4時的軌跡運動，而有100%的概率按照支持度為5時的軌跡運動。通過觀察圖4或者上文陳列的5條目標軌跡編號可以發(fā)現(xiàn)，支持度為4時的頻繁序列出現(xiàn)在軌跡2、軌跡3、軌跡4和軌跡5中；而支持度為5的頻繁序列出現(xiàn)在所有的軌跡中。這是因為軌跡1(圖4箭頭所指軌跡)并無其他目標軌跡數(shù)據(jù)的前半部分，與頻繁序列挖掘結果相一致，說明了上述挖掘結果的正確性與有效性。

此外，通過對比挖掘的序列模式結果與預處理后的軌跡數(shù)據(jù)網格編號可以發(fā)現(xiàn)，挖掘得到的頻繁序列在時間先后順序上與原始軌跡相一致。這就說明，本文算法可以實現(xiàn)目標行為規(guī)律的發(fā)掘。

另一方面，為驗證算法的有效性，同樣采用上述軌跡數(shù)據(jù)，在配置為i7處理器、8 G內存的計算機上對不同參數(shù)下算法的運行時間進行了統(tǒng)計，結果如下：

當設定頻繁序列支持度T=5、長度N缺省時，共挖掘得到該數(shù)據(jù)集的單元素頻繁序列14項，多元素頻繁序列4項，平均運行時間約為0.16 s(10次平均值)；

當設定頻繁序列支持度T=4、長度N缺省時，共挖掘得到該數(shù)據(jù)集的單元素頻繁序列19項，多元素頻繁序列 86 924項，平均運行時間約為35.21 s(10次平均值)；

當設定頻繁序列支持度T=3、長度N缺省時，共挖掘得到該數(shù)據(jù)集的單元素頻繁序列30項，多元素頻繁序列6 723 383項，平均運行時間約為4 800 s(10次平均值)。

通過以上結果可以看出，隨著算法參數(shù)設置的不同，其運行時間發(fā)生急劇變化，說明頻繁序列支持度需要根據(jù)當前數(shù)據(jù)情況進行設定，當目標的軌跡數(shù)據(jù)較為相似時，頻繁序列支持度的閾值不宜過低，否則可能會帶來維度災難。

4 結束語

針對目標行為規(guī)律分析問題提出了一種基于序列模式挖掘的分析方法，并利用真實軌跡數(shù)據(jù)進行了異常點去除、軌跡擬合、行為規(guī)律挖掘等仿真實驗，實現(xiàn)了目標活動規(guī)律的挖掘，對于目標異常行為識別、目標屬性輔助判證等應用具有重要意義。

此外，在仿真實驗中發(fā)現(xiàn)，數(shù)據(jù)的預處理效果直接影響后續(xù)分析算法的性能，需要設計能夠適應更加復雜場景的預處理算法是后續(xù)研究的重點方向。