移動目標(biāo)關(guān)聯(lián)共現(xiàn)規(guī)則挖掘算法研究

謝 , , ,,

(1.南京理工大學(xué) 計算機科學(xué)與工程學(xué)院,南京 210094; 2.中國電子科技集團公司第三十二研究所,上海 201808)

0 概述

在計算機及網(wǎng)絡(luò)普遍應(yīng)用的信息化時代,人們已經(jīng)習(xí)慣在任何時空環(huán)境下自然地與計算設(shè)備進行交互,具有位置感知功能的計算設(shè)備更是無時無刻地處于運轉(zhuǎn)狀態(tài),記錄著人、車輛等移動目標(biāo)的行為軌跡[1-2]。隨著衛(wèi)星通信、無限傳感器等信息采集設(shè)備的快速發(fā)展和廣泛應(yīng)用,移動目標(biāo)的軌跡數(shù)據(jù)和行為信息可以被更實時、有效地記錄下來[3]。這些移動目標(biāo)跟蹤數(shù)據(jù)包含了大量時間信息、空間信息及行為信息,為挖掘移動目標(biāo)的活動規(guī)律和行為模式提供了有力支撐[4]。同時,這些活動規(guī)律和行為模式在城市規(guī)劃[5-6]、位置服務(wù)[7]、國防軍事[8]等方面也具有非常重要的研究和應(yīng)用價值。

移動目標(biāo)活動規(guī)律是根據(jù)目標(biāo)軌跡數(shù)據(jù)進行分析的。通過統(tǒng)計、關(guān)聯(lián)分析等手段,對時空軌跡數(shù)據(jù)加以分析,可以得到移動目標(biāo)的一些活動模式,如頻繁活動路線、頻繁停留地點等[9]。早期的移動目標(biāo)行為規(guī)律研究僅考慮單一時刻移動目標(biāo)的行為特征,如文獻[10]提出的最長持續(xù)群體模式,要求某時刻至少有m個移動目標(biāo)在同一區(qū)域內(nèi)保持相同的移動狀態(tài)。該算法為群體行為挖掘提供了研究思路,但嚴格限制移動目標(biāo)須在持續(xù)時間內(nèi)同時移動,不能適用于實際應(yīng)用。文獻[11]為了解決這一問題,提出了更加通用化的模型,對于移動目標(biāo)的活動,在時間上不要求連續(xù)性,且不局限于活動區(qū)域的形狀。在頻繁模式挖掘方面,文獻[12]對軌跡進行分割預(yù)處理后,利用最小支持度挖掘移動目標(biāo)的頻繁軌跡,該方法忽略了移動目標(biāo)軌跡數(shù)據(jù)與興趣區(qū)域的關(guān)聯(lián)性。文獻[13]對軌跡數(shù)據(jù)進行了聚類預(yù)處理,對其中符合預(yù)設(shè)區(qū)域的數(shù)據(jù)進行分段提取,從而進一步針對移動目標(biāo)在興趣區(qū)域內(nèi)的行為規(guī)律進行分析?，F(xiàn)有的頻繁模式挖掘研究多基于傳統(tǒng)Apriori算法或樹結(jié)構(gòu),加入時序特征后,針對不同應(yīng)用場景分別對算法進行優(yōu)化[14-15]。

現(xiàn)行的移動目標(biāo)活動規(guī)律側(cè)重于空間或時間單一維度,且忽略目標(biāo)的行為,并且多集中于單目標(biāo)的活動規(guī)律分析[16]。而考慮到在類似于軍情分析等場景中,用戶除了需要了解敵方裝備活動的地點關(guān)聯(lián)性,也需要獲取敵我兩方以及敵方裝備間在時空上的協(xié)同出現(xiàn)規(guī)律,以提前制定應(yīng)對策略。

移動目標(biāo)間活動數(shù)據(jù)越相似,或協(xié)同行為越規(guī)律,則兩者存在關(guān)聯(lián)共現(xiàn)的可能性越高。基于此,本文基于傳統(tǒng)的時間戳和地點的關(guān)聯(lián)模型,加入任務(wù)屬性信息,對關(guān)聯(lián)共現(xiàn)進行定義,提出一種基于序列模式和關(guān)聯(lián)規(guī)則的移動目標(biāo)共現(xiàn)行為挖掘算法。

1 關(guān)聯(lián)共現(xiàn)的相關(guān)定義

關(guān)聯(lián)共現(xiàn)規(guī)律發(fā)現(xiàn)是以移動目標(biāo)在空間上的共同出現(xiàn)模式為基準(zhǔn),進一步分析時間上的頻繁度而得到。本文將移動目標(biāo)間的關(guān)聯(lián)共現(xiàn)規(guī)律稱作對象關(guān)聯(lián)共現(xiàn),而單移動目標(biāo)會存在自身地點關(guān)聯(lián)。在計算中,時間上的頻繁度是以天為單位進行計算的。

1.1 對象關(guān)聯(lián)共現(xiàn)

定義1對于2個移動目標(biāo)A和B,若1 d內(nèi),存在移動目標(biāo)A和B的活動數(shù)據(jù),則稱移動目標(biāo)A和移動目標(biāo)B共同出現(xiàn)了一次,記SAB=1。若1 d內(nèi)移動目標(biāo)間對象關(guān)聯(lián)的共同出現(xiàn)的次數(shù)大于1,SAB仍為1。在選定時間段D=[ds,de]內(nèi),若移動目標(biāo)A和B共同出現(xiàn)次數(shù)SAB大于閾值SΔ,則稱SAB為移動目標(biāo)A和B在選定時間段內(nèi)對象關(guān)聯(lián)的共現(xiàn)次數(shù),即:

其中,i∈{1,2,…,|D|},ds和de分別為選定時間段的開始日期和結(jié)束日期,SABi∈{0,1}為移動目標(biāo)A和B在從ds開始第i天的共同出現(xiàn)次數(shù)。

定義2定義tAB為移動目標(biāo)A和B的共同出現(xiàn)時長。若1 d內(nèi),移動目標(biāo)A和B存在共同出現(xiàn)的情況,對于tAB則有:

在選定時間段D=[ds,de]內(nèi),若移動目標(biāo)A和B共同出現(xiàn)時長TAB大于閾值tΔ,則稱TAB為移動目標(biāo)A和B在選定時間段內(nèi)的共現(xiàn)時長,即:

其中,tABi為移動目標(biāo)A和B在從ds開始第i天的共同出現(xiàn)時長。

定義3定義disAB為移動目標(biāo)A和B共同出現(xiàn)的間隔距離。若1 d內(nèi),移動目標(biāo)A和B存在共同出現(xiàn)的情況,具能夠測得共同出現(xiàn)的時長,則對其共同出現(xiàn)的時間段等分取樣,計算同時刻,移動目標(biāo)A和B之間的歐氏距離,并求和取平均,對于disAB即有:

其中,xj、yj分別為移動目標(biāo)A和B在第j個取樣點的位置信息,n為同時刻采樣點的對數(shù)。在選定時間段D=[ds,de]內(nèi),若移動目標(biāo)A和B共同出現(xiàn)時的間隔距離dAB小于閾值disΔ,則稱dAB為移動目標(biāo)A和B在選定時間段內(nèi)的間隔距離,即:

其中,xj、yj為移動目標(biāo)A和B在從ds開始第i天的間隔距離,SAB為在選定時間段D內(nèi),移動目標(biāo)A和B的共同出現(xiàn)次數(shù),此處距離均以千米為單位。

對于對象關(guān)聯(lián)共現(xiàn)中的共同出現(xiàn),存在2類情況,f(x)為判斷函數(shù):

1)移動目標(biāo)A和B間,共同出現(xiàn)的次數(shù)、時長、間隔距離都存在,即:

f((SAB>0)& & (TAB>0)& & (dAB≠∞))=true

該種情況稱為存在三參的共同出現(xiàn)。

2)移動目標(biāo)A和B間,僅存在共同出現(xiàn)的次數(shù),而時長、間隔距離均不存在,即:

f((SAB>0)& & (TAB==0)& & (dAB==∞))=true

該種情況稱為存在一參的共同出現(xiàn)。

當(dāng)且僅當(dāng)在選定時間段D=[ds,de]內(nèi),對移動目標(biāo)A和B的三參與一參共同出現(xiàn)結(jié)果進行累加與合并,若共現(xiàn)次數(shù)SAB>sΔ,共現(xiàn)時長TAB>tΔ,間隔距離disAB>disΔ均滿足,則稱此時間段內(nèi),移動目標(biāo)A和移動目標(biāo)B存在對象關(guān)聯(lián)共現(xiàn)。

定義4定義φ為對象關(guān)聯(lián)共現(xiàn)強度,ξi為對象關(guān)聯(lián)共現(xiàn)中第i種關(guān)聯(lián)度的分配權(quán)重,αi為第i種關(guān)聯(lián)度的度量值,則三者之間存在關(guān)系:

其中,i∈{1,2,3}。

在選定時間段D=[ds,de]內(nèi),若αi為共現(xiàn)次數(shù)關(guān)聯(lián)度度量值,則有:

若α2為共現(xiàn)時長關(guān)聯(lián)度度量值,則有:

若α3為共現(xiàn)間隔距離關(guān)聯(lián)度度量值,則有:

1.2 對象自身地點關(guān)聯(lián)

定義5移動目標(biāo)A在選定時間段D=[ds,de]內(nèi)的活動軌跡數(shù)據(jù)集為Q={q1,q2,…,qn},每條軌跡qi對應(yīng)移動目標(biāo)A的一條活動區(qū)域轉(zhuǎn)移序列。

現(xiàn)尋找Q中出現(xiàn)頻繁度sup(qj)大于頻繁度閾值supΔ的最長子序列FFS={fs1,fs2,…,fsm},其中,n為目標(biāo)A在選定時間段內(nèi)的活動軌跡總數(shù),m為找到的頻繁子序列總數(shù),且有m≤n,fsi?qj,i∈{1,2,…,m},j∈{1,2,…,n}。FFS即為移動目標(biāo)A在選定時間段D內(nèi)的對象自身地點關(guān)聯(lián)結(jié)果集。

2 移動目標(biāo)關(guān)聯(lián)共現(xiàn)行為模式挖掘算法

本文算法是基于原始的軌跡和活動數(shù)據(jù),提取關(guān)鍵屬性,并對移動目標(biāo)之間的共現(xiàn)參數(shù)進行計算。算法由移動目標(biāo)對象關(guān)聯(lián)共現(xiàn)挖掘與移動目標(biāo)自身地點關(guān)聯(lián)挖掘2個子算法構(gòu)成。

2.1 移動目標(biāo)對象關(guān)聯(lián)共現(xiàn)挖掘算法

對象關(guān)聯(lián)共現(xiàn)挖掘算法是在傳統(tǒng)的軌跡序貫?zāi)Ｊ酵诰虻幕A(chǔ)上,從含有{時間戳-地點-任務(wù)}三要素的關(guān)聯(lián)模型中,依據(jù)2個移動目標(biāo)在時間上的頻繁度以及空間上的距離進行共現(xiàn)模式挖掘。設(shè)計思路為:對歷史時間段內(nèi)的軌跡數(shù)據(jù)進行初始化,將其處理為統(tǒng)一的數(shù)據(jù)格式。然后根據(jù)定義,計算移動目標(biāo)間的關(guān)聯(lián)度度量值,對其進行加權(quán)求和,從而得到兩兩移動目標(biāo)間的對象關(guān)聯(lián)共現(xiàn)強度,構(gòu)建共現(xiàn)模式鏈。此時鏈表中保存的是完整的對象關(guān)聯(lián)共現(xiàn)模式集合,在實際需求中,還需要根據(jù)用戶的篩選條件,將關(guān)聯(lián)度度量值及對象關(guān)聯(lián)共現(xiàn)強度與閾值進行比較,判斷其是否滿足設(shè)定的時空頻繁度,再進行輸出展示,從而輔助用戶從模式鏈中獲取滿足條件的對象關(guān)聯(lián)共現(xiàn)模式集。

算法分為2步:

1)計算任意2個移動目標(biāo)間的對象關(guān)聯(lián)共現(xiàn)參數(shù)。以天為單位,計算兩兩移動目標(biāo)在不同區(qū)域的共現(xiàn)參數(shù),并將結(jié)果數(shù)據(jù)寫入對象關(guān)聯(lián)共現(xiàn)參數(shù)表中。

2)在用戶點擊查詢后,直接從生成的結(jié)果表中查找數(shù)據(jù),進行計算得出最后結(jié)果。

構(gòu)建對象關(guān)聯(lián)共現(xiàn)參數(shù)表的具體步驟為:

1)初始化軌跡數(shù)據(jù)集,將數(shù)據(jù)格式處理成{軌跡信息唯一標(biāo)識符,移動目標(biāo),任務(wù),出現(xiàn)時間,出現(xiàn)經(jīng)度,出現(xiàn)緯度,消失時間,消失經(jīng)度,消失緯度,經(jīng)過區(qū)域,經(jīng)過區(qū)域時間}的格式。

2)以天為單位,從歷史數(shù)據(jù)第一天起,截取當(dāng)天所有的軌跡記錄,找到所有移動目標(biāo)的軌跡信息唯一標(biāo)識符tidi。

3)對tidi進行兩兩匹配,這里以目標(biāo)A對應(yīng)的tid1和目標(biāo)B對應(yīng)的tid2為例。

4)找出tid1包含的經(jīng)過區(qū)域集合area1,tid2包含的經(jīng)過區(qū)域集合area2,然后對area1、area2中包含的區(qū)域及對應(yīng)的經(jīng)過區(qū)域時間進行兩兩匹配。

5)例如,area1={區(qū)域1,區(qū)域2},area2={區(qū)域3}。tid1對應(yīng)的經(jīng)過區(qū)域1的時間是Tin1,Tout1為在Tin1時刻,目標(biāo)A進入?yún)^(qū)域1,在Tout1時刻,目標(biāo)A離開區(qū)域1。tid2對應(yīng)的經(jīng)過區(qū)域3的時間是Tin2、Tout2。

此時,比較Tin1與Tin2的大小,以較晚時間點為基準(zhǔn),記作Tin,即:

Tin=max{Tin1,Tin2}

同樣,比較Tout1與Tout2的大小,以較早時間點為基準(zhǔn),記作Tout,即:

Tout=max{Tout1,Tout2}

判斷Tin與Tout的關(guān)系,若Tout≤Tin,說明目標(biāo)A和B的活動沒有重合時間,則當(dāng)天一參共同出現(xiàn)的次數(shù)記為1,寫入對象關(guān)聯(lián)共現(xiàn)參數(shù)表,并標(biāo)注共同出現(xiàn)標(biāo)示為1,回到步驟4),對下一種區(qū)域匹配情況進行計算。

若TouttΔ,跳轉(zhuǎn)到步驟7),并在此打上斷點breakpoint,若返回值flag=true,則當(dāng)天三參共同出現(xiàn)次數(shù)記為1,寫入對象關(guān)聯(lián)共現(xiàn)參數(shù)表,并標(biāo)注共同出現(xiàn)標(biāo)示為3。如果返回值flag=false,則不統(tǒng)計?；氐讲襟E4),對下一種區(qū)域匹配情況進行計算。

6)若當(dāng)前時刻,在tid1包含的經(jīng)過區(qū)域集合area1和tid2包含的經(jīng)過區(qū)域area2中,所有區(qū)域均已遍歷,跳轉(zhuǎn)到步驟9)。

7)對tid1和tid2的共同出現(xiàn)開始時間點Tin、共同出現(xiàn)結(jié)束時間點Tout等分出5個時間點,提取tid1和tid2對應(yīng)的相應(yīng)時間點的軌跡點信息各5條。

8)計算讀取到的相同時間點的軌跡點的經(jīng)緯度歐式距離,并求取平均值,得到d。如果d

9)回到步驟1),對下一天所有的軌跡記錄進行計算,直到所有日期都遍歷結(jié)束。

10)將同一天內(nèi),兩兩移動目標(biāo)匹配關(guān)系相同的數(shù)據(jù)進行合并,寫入臨時結(jié)果表。

11)對臨時結(jié)果表進行再次處理,將兩兩移動目標(biāo)匹配關(guān)系相同的數(shù)據(jù)進行合并,同時對不同的共同出現(xiàn)標(biāo)示進行合并,寫入最終的對象關(guān)聯(lián)共現(xiàn)參數(shù)表中。

12)根據(jù)用戶篩選條件,計算用戶選定時間段內(nèi)的共同出現(xiàn)次數(shù)、共同出現(xiàn)時長以及對應(yīng)的間隔距離,判斷是否屬于對象關(guān)聯(lián)共現(xiàn),若關(guān)聯(lián)度度量值符合定義中的閾值,則進行輸出展示;若不符合,則略去。

目標(biāo)對象關(guān)聯(lián)共現(xiàn)規(guī)律挖掘算法流程如圖1所示。

圖1 目標(biāo)對象關(guān)聯(lián)共現(xiàn)規(guī)律挖掘算法流程

2.2 移動目標(biāo)自身地點關(guān)聯(lián)挖掘算法

移動目標(biāo)的自身地點關(guān)聯(lián)就是針對單一目標(biāo)挖掘活動的頻繁序列,即對目標(biāo)以天為單位的活動區(qū)域集合使用頻繁序列挖掘算法,在符合支持度閾值的條件下,找出目標(biāo)經(jīng)?；顒拥摹⒂袝r間先后順序的活動區(qū)域[17]。此處采用序列模式算法中的PrefixSpan算法[18]。

基于前綴投影進行頻繁序列模式挖掘的主要步驟如下:

步驟1找出頻繁單項:掃描數(shù)據(jù)庫,尋找出現(xiàn)次數(shù)大于設(shè)定支持數(shù)的單項(每個單項在一個序列中即使出現(xiàn)多次也只算一次),得到長度為1的頻繁項目集。

步驟2生成投影數(shù)據(jù)庫:為上一步得到的頻繁項目集中所有項目生成投影數(shù)據(jù)庫。

步驟3尋找頻繁序列子集:通過遞歸挖掘投影數(shù)據(jù)庫得到頻繁序列子集。找到以步驟1得到的頻繁項目集中的元素為前綴的頻繁序列,然后為其構(gòu)造投影數(shù)據(jù)庫并挖掘。

步驟4重復(fù)步驟1～步驟3,直到找不出頻繁項目。

基于以上對于PrefixSpan算法的理解,利用PrefixSpan算法挖掘移動目標(biāo)自身地點關(guān)聯(lián)步驟如下:

步驟1掃描歷史軌跡數(shù)據(jù),根據(jù)用戶選擇的移動目標(biāo)、時間范圍、所屬任務(wù),篩選出符合條件的軌跡信息。一條軌跡的出現(xiàn)時間只要在用戶所選的時間范圍內(nèi),那么這條軌跡的時間和用戶選擇的時間范圍條件就是相符的。

步驟2對于每一條軌跡信息,經(jīng)過區(qū)域?qū)傩韵滤膮^(qū)域轉(zhuǎn)移信息,已經(jīng)是按照時間升序排列的了。此時,以目標(biāo)的軌跡信息唯一標(biāo)識符tidi為單位,記錄符合條件的目標(biāo),對用戶篩選時間段內(nèi)所有的經(jīng)過區(qū)域信息,記作該目標(biāo)的一條活動序列Qij。

步驟3對同一個移動目標(biāo)的活動序列構(gòu)建數(shù)據(jù)庫Si,使用PrefixSpan算法分析數(shù)據(jù)庫Si,獲得目標(biāo)的頻繁序列集合Fi,其中,i表示第i個符合用戶篩選條件的移動目標(biāo)。

步驟4對第i個移動目標(biāo)計算獲得的頻繁序列集合Fi,去除子集序列,獲得最長頻繁序列集合Li,Li即為該目標(biāo)的頻繁活動序列集。

步驟5跳回步驟3,對下一個符合用戶篩選條件的目標(biāo)計算頻繁序列,直到符合用戶選定條件的所有移動目標(biāo)的頻繁序列都已被挖掘,算法結(jié)束。

目標(biāo)自身地點關(guān)聯(lián)規(guī)律挖掘算法流程如圖2所示。

圖2 目標(biāo)自身地點關(guān)聯(lián)規(guī)律挖掘算法流程

3 實驗結(jié)果與分析

對軌跡數(shù)據(jù)進行對象關(guān)聯(lián)共現(xiàn)和自身地點關(guān)聯(lián)分析,得到任意兩兩移動目標(biāo)間的對象關(guān)聯(lián)共現(xiàn)參數(shù)值,以及任意移動目標(biāo)自身頻繁執(zhí)行的軌跡序列。進一步地,根據(jù)這些數(shù)據(jù),可以判斷任意一段時間內(nèi),兩兩移動目標(biāo)間的關(guān)聯(lián)強度,以及單移動目標(biāo)自身的活動規(guī)律,從而據(jù)此針對各個移動目標(biāo)建立監(jiān)控和反應(yīng)機制。

本文描述的軌跡數(shù)據(jù)集包括軌跡唯一標(biāo)識符、移動目標(biāo)名稱、任務(wù)、出現(xiàn)時間、出現(xiàn)經(jīng)度、出現(xiàn)緯度、消失時間、消失經(jīng)度、消失緯度、經(jīng)過區(qū)域、經(jīng)過區(qū)域時間共11個屬性,具體數(shù)據(jù)格式如表1所示。

設(shè)定對象關(guān)聯(lián)共現(xiàn)中的出現(xiàn)次數(shù)閾值SΔ為1次,時長閾值tΔ為0.2 h,間隔距離閾值disΔ為200 km,對象自身地點關(guān)聯(lián)中的頻繁度閾值為原始軌跡總條數(shù)的20%。針對2017年全年,全部約1 TB的移動目標(biāo)軌跡數(shù)據(jù)進行分析。得到的對象關(guān)聯(lián)共現(xiàn)結(jié)果數(shù)據(jù)包括對象關(guān)聯(lián)共現(xiàn)唯一標(biāo)識符、日期、2個移動目標(biāo)各自的名稱、任務(wù)、所在區(qū)域,2個移動目標(biāo)共同出現(xiàn)的開始時間、共同出現(xiàn)的結(jié)束時間、共同出現(xiàn)的時長、間隔距離,以及出現(xiàn)標(biāo)識、關(guān)聯(lián)強度共14個屬性,具體數(shù)據(jù)格式如表2所示。

分析得到的目標(biāo)自身地點關(guān)聯(lián)結(jié)果數(shù)據(jù)包括自身地點關(guān)聯(lián)唯一標(biāo)識符、移動目標(biāo)名稱、任務(wù)、頻繁經(jīng)過區(qū)域、日期、經(jīng)過次數(shù),共6個屬性,具體數(shù)據(jù)格式如表3所示。

表1 軌跡數(shù)據(jù)集數(shù)據(jù)格式

表2 對象關(guān)聯(lián)共現(xiàn)結(jié)果數(shù)據(jù)集數(shù)據(jù)格式

表3 對象自身地點關(guān)聯(lián)結(jié)果數(shù)據(jù)集數(shù)據(jù)格式

以移動目標(biāo)A和移動目標(biāo)W為例,通過對A和W的原始軌跡的可視化展示,如圖3所示,可以發(fā)現(xiàn),在同一時間軸上,移動目標(biāo)A和W的活動傾向于協(xié)同出現(xiàn),并且距離較近。而在實驗中,通過本文提出的對象關(guān)聯(lián)共現(xiàn)規(guī)律挖掘算法,可以得到移動目標(biāo)A和移動目標(biāo)W存在對象關(guān)聯(lián)共現(xiàn)。因此,算法的實驗結(jié)果與實際情況相符。

以移動目標(biāo)A為例,通過對其原始軌跡的分析,如表4所示,可以發(fā)現(xiàn),在該時間軸上,移動目標(biāo)A總是傾向于出現(xiàn)在區(qū)域a、區(qū)域b和區(qū)域c,并且經(jīng)常由區(qū)域b進入?yún)^(qū)域a,同時執(zhí)行普通任務(wù)。若設(shè)置閾值為20%,則移動目標(biāo)A的頻繁活動序列為區(qū)域a、區(qū)域b、區(qū)域b->a,以及區(qū)域b->a->b->a。而在實驗中,通過本文提出的對象自身關(guān)聯(lián)規(guī)律挖掘算法,可以得到移動目標(biāo)A的頻繁活動序列為b->a->b->a,出現(xiàn)次數(shù)為2。算法的實驗結(jié)果與實際情況相符。

圖3 對象關(guān)聯(lián)共現(xiàn)結(jié)果可視化展示

表4 移動目標(biāo)A簡化后的軌跡信息

由實驗結(jié)果可以看出,任意2個移動目標(biāo)之間,對象關(guān)聯(lián)共現(xiàn)的關(guān)聯(lián)強度越高,則說明這2個移動目標(biāo)活動數(shù)據(jù)越相似,協(xié)同行為越規(guī)律。根據(jù)關(guān)聯(lián)強度,對兩兩移動目標(biāo)間的關(guān)聯(lián)度進行多檔劃分,可以對進一步制定的應(yīng)對方案給出決策指導(dǎo)。而對于移動目標(biāo)自身具有的地點關(guān)聯(lián)共現(xiàn)規(guī)律而言,其得到的結(jié)果標(biāo)識了單移動目標(biāo)大概率活動區(qū)域及活動的先后順序,可以輔助用戶深入研究移動目標(biāo)的行為特征,進而輔助預(yù)測分析。

就算法效率而言,對象關(guān)聯(lián)共現(xiàn)規(guī)律挖掘算法采取的是以空間換取時間效率的方式,首先按d將計算結(jié)果存入數(shù)據(jù)庫中,當(dāng)用戶執(zhí)行查詢操作時,將相應(yīng)數(shù)據(jù)從數(shù)據(jù)庫中調(diào)出并進行簡單的低維運算,此時的復(fù)雜度僅為O(n),其中,n表示數(shù)據(jù)庫中的數(shù)據(jù)條數(shù)。這一舉措可以大大降低用戶執(zhí)行操作的耗時,優(yōu)化查詢效率。而在移動目標(biāo)自身地點關(guān)聯(lián)規(guī)律挖掘算法中,相較于傳統(tǒng)的序列挖掘算法,如Apriori算法[19]、GSP算法[20]、SPADE算法[21],本文采取的PrefixSpan算法因其無需保存頻繁序列的候選集,而只需保存投影數(shù)據(jù),可以大幅度減少內(nèi)存的消耗[22],在設(shè)定同等最小支持度閾值的條件下,該算法的耗時更低,且運行良好。

4 結(jié)束語

本文研究了一種基于數(shù)據(jù)挖掘的移動目標(biāo)行為模式挖掘算法,基于傳統(tǒng)的時間戳和地點的關(guān)聯(lián)模型,加入任務(wù)屬性信息,對關(guān)聯(lián)共現(xiàn)進行了定義,分析時空軌跡數(shù)據(jù),獲得2個移動目標(biāo)之間的協(xié)同行為規(guī)律。同時運用序列模式挖掘算法,分析單移動目標(biāo)自身的行為規(guī)律,為針對各個移動目標(biāo)建立監(jiān)控和反應(yīng)機制提供了數(shù)據(jù)基礎(chǔ)。實驗結(jié)果證明,本文所提算法可以有效挖掘移動目標(biāo)間的活動地點關(guān)聯(lián)性以及協(xié)同共現(xiàn)規(guī)律,并且具有較低的算法復(fù)雜度,可以適用于基于海量數(shù)據(jù)的計算和應(yīng)用。