一種基于數據挖掘的目標行為規律分析算法

高 軼，王 鵬

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

0 引言

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

1 數據挖掘概念

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

1.1 關聯分析的概念

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

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

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

(1)

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

(2)

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

1.2 關聯規則挖掘典型流程

目前，大多數關聯規則挖掘算法采用的策略是將關聯規則挖掘的任務分為以下2個步驟：

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

② 規則的產生，其目標是從步驟①中發現的頻繁項集中提取所有高置信度的規則，稱之為強規則。

1.3 序列模式挖掘

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

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

2 目標行為規律分析算法

2.1 數據預處理

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

2.1.1 異常點剔除

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

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

圖1 異常軌跡點剔除結果

2.1.2 軌跡擬合

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

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

圖2 軌跡擬合結果

2.1.3 目標位置柵格化

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

圖3 目標位置柵格化示意

2.2 行為規律挖掘

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

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

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

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

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

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

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

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

3 仿真實驗

為驗證所提算法的有效性，進行了計算機仿真實驗。仿真實驗數據共包含5組同一目標的真實軌跡觀測數據，如圖4所示。可以發現，雖然5次軌跡數據長度、運動方向等并不完全相同，但存在共同的運動趨勢，并經過相同的位置，即該目標的行為存在一定的規律。

圖4 目標軌跡數據

按照2.1節中方法進行預處理后，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節中目標行為規律挖掘方法對上述軌跡數據進行分析，設定頻繁序列支持度T=4時，得到的頻繁序列為{34，49，54，59，78，88，103，108，113，123，128，133，167，176，181}；而當設定多元素頻繁序列支持度閾值為T=5時，得到的頻繁序列為{133，167，176，181}。

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

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

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

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

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

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

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

4 結束語

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

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