一種基于數(shù)據(jù)挖掘的目標(biāo)行為規(guī)律分析算法

高 軼，王 鵬

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

0 引言

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

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

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

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

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

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

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

(1)

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

(2)

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

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

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

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

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

1.3 序列模式挖掘

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

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

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

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

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

2.1.1 異常點(diǎn)剔除

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

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

圖1 異常軌跡點(diǎn)剔除結(jié)果

2.1.2 軌跡擬合

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

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

圖2 軌跡擬合結(jié)果

2.1.3 目標(biāo)位置柵格化

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

圖3 目標(biāo)位置柵格化示意

2.2 行為規(guī)律挖掘

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

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

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

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

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

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

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

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

3 仿真實(shí)驗(yàn)

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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

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