移動目標關聯共現規則挖掘算法研究

謝 , , ,,

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

0 概述

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

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

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

移動目標間活動數據越相似,或協同行為越規律,則兩者存在關聯共現的可能性越高。基于此,本文基于傳統的時間戳和地點的關聯模型,加入任務屬性信息,對關聯共現進行定義,提出一種基于序列模式和關聯規則的移動目標共現行為挖掘算法。

1 關聯共現的相關定義

關聯共現規律發現是以移動目標在空間上的共同出現模式為基準,進一步分析時間上的頻繁度而得到。本文將移動目標間的關聯共現規律稱作對象關聯共現,而單移動目標會存在自身地點關聯。在計算中,時間上的頻繁度是以天為單位進行計算的。

1.1 對象關聯共現

定義1對于2個移動目標A和B,若1 d內,存在移動目標A和B的活動數據,則稱移動目標A和移動目標B共同出現了一次,記SAB=1。若1 d內移動目標間對象關聯的共同出現的次數大于1,SAB仍為1。在選定時間段D=[ds,de]內,若移動目標A和B共同出現次數SAB大于閾值SΔ,則稱SAB為移動目標A和B在選定時間段內對象關聯的共現次數,即:

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

定義2定義tAB為移動目標A和B的共同出現時長。若1 d內,移動目標A和B存在共同出現的情況,對于tAB則有:

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

其中,tABi為移動目標A和B在從ds開始第i天的共同出現時長。

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

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

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

對于對象關聯共現中的共同出現,存在2類情況,f(x)為判斷函數:

1)移動目標A和B間,共同出現的次數、時長、間隔距離都存在,即:

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

該種情況稱為存在三參的共同出現。

2)移動目標A和B間,僅存在共同出現的次數,而時長、間隔距離均不存在,即:

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

該種情況稱為存在一參的共同出現。

當且僅當在選定時間段D=[ds,de]內,對移動目標A和B的三參與一參共同出現結果進行累加與合并,若共現次數SAB>sΔ,共現時長TAB>tΔ,間隔距離disAB>disΔ均滿足,則稱此時間段內,移動目標A和移動目標B存在對象關聯共現。

定義4定義φ為對象關聯共現強度,ξi為對象關聯共現中第i種關聯度的分配權重,αi為第i種關聯度的度量值,則三者之間存在關系:

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

在選定時間段D=[ds,de]內,若αi為共現次數關聯度度量值,則有:

若α2為共現時長關聯度度量值,則有:

若α3為共現間隔距離關聯度度量值,則有:

1.2 對象自身地點關聯

定義5移動目標A在選定時間段D=[ds,de]內的活動軌跡數據集為Q={q1,q2,…,qn},每條軌跡qi對應移動目標A的一條活動區域轉移序列。

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

2 移動目標關聯共現行為模式挖掘算法

本文算法是基于原始的軌跡和活動數據,提取關鍵屬性,并對移動目標之間的共現參數進行計算。算法由移動目標對象關聯共現挖掘與移動目標自身地點關聯挖掘2個子算法構成。

2.1 移動目標對象關聯共現挖掘算法

對象關聯共現挖掘算法是在傳統的軌跡序貫模式挖掘的基礎上,從含有{時間戳-地點-任務}三要素的關聯模型中,依據2個移動目標在時間上的頻繁度以及空間上的距離進行共現模式挖掘。設計思路為:對歷史時間段內的軌跡數據進行初始化,將其處理為統一的數據格式。然后根據定義,計算移動目標間的關聯度度量值,對其進行加權求和,從而得到兩兩移動目標間的對象關聯共現強度,構建共現模式鏈。此時鏈表中保存的是完整的對象關聯共現模式集合,在實際需求中,還需要根據用戶的篩選條件,將關聯度度量值及對象關聯共現強度與閾值進行比較,判斷其是否滿足設定的時空頻繁度,再進行輸出展示,從而輔助用戶從模式鏈中獲取滿足條件的對象關聯共現模式集。

算法分為2步:

1)計算任意2個移動目標間的對象關聯共現參數。以天為單位,計算兩兩移動目標在不同區域的共現參數,并將結果數據寫入對象關聯共現參數表中。

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

構建對象關聯共現參數表的具體步驟為:

1)初始化軌跡數據集,將數據格式處理成{軌跡信息唯一標識符,移動目標,任務,出現時間,出現經度,出現緯度,消失時間,消失經度,消失緯度,經過區域,經過區域時間}的格式。

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

3)對tidi進行兩兩匹配,這里以目標A對應的tid1和目標B對應的tid2為例。

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

5)例如,area1={區域1,區域2},area2={區域3}。tid1對應的經過區域1的時間是Tin1,Tout1為在Tin1時刻,目標A進入區域1,在Tout1時刻,目標A離開區域1。tid2對應的經過區域3的時間是Tin2、Tout2。

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

Tin=max{Tin1,Tin2}

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

Tout=max{Tout1,Tout2}

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

若TouttΔ,跳轉到步驟7),并在此打上斷點breakpoint,若返回值flag=true,則當天三參共同出現次數記為1,寫入對象關聯共現參數表,并標注共同出現標示為3。如果返回值flag=false,則不統計?；氐讲襟E4),對下一種區域匹配情況進行計算。

6)若當前時刻,在tid1包含的經過區域集合area1和tid2包含的經過區域area2中,所有區域均已遍歷,跳轉到步驟9)。

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

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

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

10)將同一天內,兩兩移動目標匹配關系相同的數據進行合并,寫入臨時結果表。

11)對臨時結果表進行再次處理,將兩兩移動目標匹配關系相同的數據進行合并,同時對不同的共同出現標示進行合并,寫入最終的對象關聯共現參數表中。

12)根據用戶篩選條件,計算用戶選定時間段內的共同出現次數、共同出現時長以及對應的間隔距離,判斷是否屬于對象關聯共現,若關聯度度量值符合定義中的閾值,則進行輸出展示;若不符合,則略去。

目標對象關聯共現規律挖掘算法流程如圖1所示。

圖1 目標對象關聯共現規律挖掘算法流程

2.2 移動目標自身地點關聯挖掘算法

移動目標的自身地點關聯就是針對單一目標挖掘活動的頻繁序列,即對目標以天為單位的活動區域集合使用頻繁序列挖掘算法,在符合支持度閾值的條件下,找出目標經常活動的、有時間先后順序的活動區域[17]。此處采用序列模式算法中的PrefixSpan算法[18]。

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

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

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

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

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

基于以上對于PrefixSpan算法的理解,利用PrefixSpan算法挖掘移動目標自身地點關聯步驟如下:

步驟1掃描歷史軌跡數據,根據用戶選擇的移動目標、時間范圍、所屬任務,篩選出符合條件的軌跡信息。一條軌跡的出現時間只要在用戶所選的時間范圍內,那么這條軌跡的時間和用戶選擇的時間范圍條件就是相符的。

步驟2對于每一條軌跡信息,經過區域屬性下所包含的區域轉移信息,已經是按照時間升序排列的了。此時,以目標的軌跡信息唯一標識符tidi為單位,記錄符合條件的目標,對用戶篩選時間段內所有的經過區域信息,記作該目標的一條活動序列Qij。

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

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

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

目標自身地點關聯規律挖掘算法流程如圖2所示。

圖2 目標自身地點關聯規律挖掘算法流程

3 實驗結果與分析

對軌跡數據進行對象關聯共現和自身地點關聯分析,得到任意兩兩移動目標間的對象關聯共現參數值,以及任意移動目標自身頻繁執行的軌跡序列。進一步地,根據這些數據,可以判斷任意一段時間內,兩兩移動目標間的關聯強度,以及單移動目標自身的活動規律,從而據此針對各個移動目標建立監控和反應機制。

本文描述的軌跡數據集包括軌跡唯一標識符、移動目標名稱、任務、出現時間、出現經度、出現緯度、消失時間、消失經度、消失緯度、經過區域、經過區域時間共11個屬性,具體數據格式如表1所示。

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

分析得到的目標自身地點關聯結果數據包括自身地點關聯唯一標識符、移動目標名稱、任務、頻繁經過區域、日期、經過次數,共6個屬性,具體數據格式如表3所示。

表1 軌跡數據集數據格式

表2 對象關聯共現結果數據集數據格式

表3 對象自身地點關聯結果數據集數據格式

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

以移動目標A為例,通過對其原始軌跡的分析,如表4所示,可以發現,在該時間軸上,移動目標A總是傾向于出現在區域a、區域b和區域c,并且經常由區域b進入區域a,同時執行普通任務。若設置閾值為20%,則移動目標A的頻繁活動序列為區域a、區域b、區域b->a,以及區域b->a->b->a。而在實驗中,通過本文提出的對象自身關聯規律挖掘算法,可以得到移動目標A的頻繁活動序列為b->a->b->a,出現次數為2。算法的實驗結果與實際情況相符。

圖3 對象關聯共現結果可視化展示

表4 移動目標A簡化后的軌跡信息

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

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

4 結束語

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