顧及時空“點-線”關(guān)聯(lián)特征的出行軌跡描述模型

林 艷，賀日興，陳 軍，李佳田，張文宇

1. 中國人民公安大學(xué)信息網(wǎng)絡(luò)安全學(xué)院，北京 100038； 2. 首都師范大學(xué)資源環(huán)境與旅游學(xué)院，北京 100048； 3. 國家基礎(chǔ)地理信息中心，北京 100830； 4. 昆明理工大學(xué)國土資源工程學(xué)院，昆明 650093

關(guān)聯(lián)出行反映了出行目標之間的時空交互，是時空認知研究的基礎(chǔ)問題之一[1-3]，也是城市規(guī)劃、交通出行、傳染病防控、犯罪偵查等領(lǐng)域的研究熱點。以往研究多從宏觀層面，采用公眾出行、出租車等軌跡數(shù)據(jù)，結(jié)合關(guān)聯(lián)的POI、土地利用類型等數(shù)據(jù)，揭示出行數(shù)據(jù)所蘊含的道路交通狀態(tài)、城市居民出行規(guī)律、城市結(jié)構(gòu)及其他社會問題[4-8]。近年來，隨著疫情防控、特殊車輛監(jiān)測、犯罪偵查等精細化需求，很多學(xué)者從微觀層面研究個體目標之間的接觸、同行/伴隨等關(guān)聯(lián)出行行為：如通過分析出行軌跡在時間和空間上的鄰近性，檢測COVID_19病例的密切接觸者[9]；通過分析出行個體共處的時間長短、次數(shù)等，檢測交通個體的潛在同行人員[10]；通過分析刷卡時間間隔和地點，判斷高校學(xué)生是否存在社會網(wǎng)絡(luò)關(guān)系[11]；基于時間和空間約束關(guān)系，分析出租車、運鈔車等特殊車輛的可疑伴隨模式[12-15]；針對反恐情報時空軌跡數(shù)據(jù)，挖掘涉恐群體中的伴隨模式等[16-17]。

然而，出行軌跡作為人的主觀選擇結(jié)果，蘊含著出行個體更復(fù)雜的主觀意圖。以犯罪分子為代表的某些特殊目標，如犯罪分子A在旅館等待犯罪分子B，接頭后二者共同去往某地，等待被害人C出現(xiàn)后實施犯罪，關(guān)注犯罪團伙、犯罪分子與被害人之間的時空特征規(guī)律并識別接頭、等待等關(guān)聯(lián)出行行為，是案件偵查、犯罪防控的重要理論基礎(chǔ)。

當(dāng)前的軌跡關(guān)聯(lián)分析研究是以識別接觸、同行/伴隨關(guān)系中的某一種模式為目的，主要包括3種方法：①基于線模型的軌跡相似度判斷：對原始軌跡化簡后，表示為線要素，基于距離、時間度量計算同行軌跡的相似度[18-20]，從而判斷出行是否存在關(guān)聯(lián)。②基于序列點模型的時空約束關(guān)系判斷[12-17,21-22]：將軌跡表示為序列點要素，判斷在某段時間上連續(xù)、且在空間上處于特定范圍內(nèi)的軌跡點，能夠識別出共同停留點/接觸點、同行路段兩種關(guān)聯(lián)出行模式。③基于Stop/Move點模型的拓撲關(guān)系計算[23-25]：采用Stop/Move模型描述軌跡數(shù)據(jù)中的停留點和移動點[23-24]，在此基礎(chǔ)上，根據(jù)空間拓撲關(guān)系，得到軌跡與周邊地理要素之間共13種關(guān)聯(lián)關(guān)系[25]。

本質(zhì)上，上述研究分別采用點要素或線要素來描述個體出行軌跡，導(dǎo)致在此基礎(chǔ)上的關(guān)聯(lián)出行分析要么關(guān)注“細節(jié)點”、要么關(guān)注“整體線”，從而只能識別“共點”或“共線”兩種關(guān)聯(lián)出行類型，而無法區(qū)分和描述共點和共線關(guān)系中的“等待、接頭”等更復(fù)雜的關(guān)聯(lián)出行模式。為此，本文首先提出一種顧及“點-線”特征的出行軌跡描述模型；然后，在此基礎(chǔ)上，基于時空拓撲關(guān)系提出關(guān)聯(lián)出行的軌跡判別方法，能夠描述19種不同的關(guān)聯(lián)出行模式；最后，通過試驗對比，表明本文方法能夠更清晰地識別關(guān)聯(lián)出行軌跡所隱含的犯罪主觀意圖。

1 出行軌跡描述模型

出行軌跡描述是關(guān)聯(lián)行為分析的前提和基礎(chǔ)。在犯罪團伙、犯罪分子與被害人之間的關(guān)聯(lián)分析中，接頭、等待等關(guān)聯(lián)行為需要關(guān)注軌跡中的停留地點，而同行等關(guān)聯(lián)行為需要關(guān)注移動的路線，因此，出行軌跡描述模型需要同時兼顧軌跡的細節(jié)“點特征”和完整“線特征”，為此，本節(jié)首先介紹顧及“點-線”特征的出行軌跡描述模型。

1.1 軌跡點及其時空特征

如圖1所示，在三維空間中，繪制任意一條出行軌跡，如黑色線條。該軌跡由一系列有序結(jié)點構(gòu)成〈p1,p2,…，pn〉，這些點的類型包括停留點(簡記為P′)、移動點(簡記為P)兩種。即對于任意軌跡結(jié)點p，其軌跡點類型Type(p)={P、P′}。

圖1 軌跡點的時空特征Fig.1 The spatio-temporal characteristics of trajectory points

1.2 軌跡線的時空特征及基本單元

基于線的軌跡描述不是簡單地將所有點順序連接，而是從微觀層面，分析最小的線單元，這是因為在對兩條軌跡進行時空拓撲關(guān)聯(lián)計算時，前提是要在統(tǒng)一的時間尺度和粒度下進行比較和分析。而不同的數(shù)據(jù)獲取方式直接決定了軌跡數(shù)據(jù)的時間采樣粒度，如采用GPS獲取監(jiān)控目標的位置時，每隔十幾秒便可得到一個時空位置信息，因此，本文以軌跡數(shù)據(jù)的時間采樣間隔(Δt)作為最小的時間分析粒度。

在采樣時刻Δt對應(yīng)的點類型可能為P或P′兩種，則下一個時間采樣時刻2Δt，對應(yīng)的點類型也可能為P或P′兩種，則理論上可以組合4種軌跡線的基本單元：〈P′P〉，〈PP′〉，〈PP〉，〈P′P′〉。如圖2所示，軌跡線基本單元對應(yīng)的時空特征分別為：〈P′P〉表示目標在P′處停留后移動到P；〈PP′〉表示從P移動到P′并停留；〈PP〉表示目標從P移動到P；〈P′P′〉表示目標從停留點P′移動到下一個停留點P′。

圖2 軌跡線的4種基本單元Fig.2 Four basic types of trajectory lines

2 關(guān)聯(lián)出行的軌跡判別與描述

本質(zhì)上，兩條軌跡的時間、空間屬性同時存在交集，才會存在時空關(guān)聯(lián)，在此前提下，“等待、接頭、同行”等行為蘊含了軌跡之間不同的時空拓撲關(guān)系，為此，本節(jié)基于點、線時空拓撲關(guān)系提出關(guān)聯(lián)出行的軌跡判別與描述方法。

關(guān)聯(lián)出行判別的總體思路可分為3個層次。首先，判斷空間交集部分的幾何要素類型(Shape(I))，能夠區(qū)分出公共節(jié)點、公共線段兩種類型，此為一級規(guī)則判別。當(dāng)交集為點時，進行二級判別：判斷公共節(jié)點所在原軌跡的軌跡點類型(Type(I))，從而區(qū)分出“接頭模式”“等待模式”“共處模式”；在此基礎(chǔ)上，進行三級判別：判斷公共節(jié)點部分的時間拓撲關(guān)系，進一步對接頭、等待、共處3種模式進行細化。當(dāng)交集為線時，認為出行軌跡存在同行路段，得到“同行模式”，對同行路段的起訖點是否存在等待行為進行二級判別。下文具體介紹關(guān)聯(lián)出行的軌跡三級判別規(guī)則及其結(jié)果描述。

設(shè)犯罪分子A、B，其軌跡線段類型為上述4種基本單元之一。在某時間段n·Δt(n=1,2,…,n)內(nèi)，SA、SB分別為A、B的空間屬性。設(shè)I=SA∩SB，I表示A、B的空間交集,當(dāng)I為非空的情況下：

一級判別規(guī)則為：判斷I的幾何類型，將其記為Shape(I)。

分析可知，4種軌跡線的基本單元相交，其交集的幾何類型可能為點或線目標，即Shape(I)∈{Point,Line}。

規(guī)則1當(dāng)Shape(I)=point時，表示A、B軌跡在空間上存在公共點。此時二維平面存在一個公共點I，A、B兩目標在I處停留還是移動，決定了二者之間是否存在等待行為，因此，進一步判斷Type(I)的類型。

二級判別規(guī)則為：判斷Type(I)的類型。

將該公共點在A、B中的位置分別記為IA、IB，由軌跡點的類型和特征可知，Type(IA)、Type(IB)的點類型取值均存在兩種可能{P、P′}，則其組合可能存在4種情況：{PP,P′P,PP′,P′P′}，其中P′P、PP′順序無關(guān)可歸為一種，即Type(I)∈{PP,P′P/PP′,P′P′}。

規(guī)則1.1當(dāng)Type(I)=PP時，即Type(IA)=P且Type(IB)=P，表示“A、B存在交點、且交點所在的原軌跡中均為移動點”，該模式為“接頭模式”。

接頭模式的判斷規(guī)則、圖示及語義解釋見表1，對應(yīng)的現(xiàn)實意義為A、B在移動中接頭，且沒有停留。

表1 接頭模式Tab.1 Meeting pattern

規(guī)則1.2當(dāng)Type(I)=P′P/PP′，即Type(IA)=Pand Type(IB)=P′或Type(IA)=P′ and Type(IB)=P，表示AB存在交點、且交點是一條軌跡的停留點，是另一條的移動點，該模式為“等待模式”。

將交點處的時刻記為T(I)，設(shè)等待方的等待時間為T(P′)，交點時間在等待時間中的位置決定了“等待、接頭后共同離開”還是“等待、接頭后繼續(xù)停留”等不同的關(guān)聯(lián)行為，為此，需要進一步區(qū)分T(I)、T(P′)之間的關(guān)系，設(shè)時間點和時間線段間的拓撲關(guān)系Topology[T(I),T(P′)]。

三級判別規(guī)則為：判斷Topology[T(I),T(P′)]。

時間軸上，接頭時間點T(I)與等待方的時間段T(P′)之間存在3種：點在時間線段起點、點在時間線段終點、點在時間線段中間。

規(guī)則1.2.1當(dāng)T(I)=T(P′).start，表示“接頭時間在等待方的時間段起點”。

規(guī)則1.2.2當(dāng)T(I)=T(P′).end，表示“接頭時間在等待方的時間段終點”。

規(guī)則1.2.3當(dāng)T(P′).start

由判別規(guī)則1.2.1至1.2.3將等待模式細分為3種子類型，其判斷規(guī)則、圖示及語義解釋見表2。

表2 等待模式的細分Tab.2 Subdivision of waiting patterns

規(guī)則1.3當(dāng)Type(I)=P′P′，即Type(IA)=P′ and Type(IB)=P′，表示A、B存在交點、且交點是兩條軌跡的停留點，即A、B在各自停留期間在某段時間內(nèi)共處一地，該模式為“共處模式”。

進一步對共處時間進行區(qū)分，可以區(qū)分“同時抵達”或者“同時離開”等不同的關(guān)聯(lián)出行類型。將A、B的停留時間分別記為TA、TB，二者為有向時間線段、且存在交集。設(shè)Topology[TA,TB]表示A、B的時間拓撲關(guān)系，

三級判斷規(guī)則為：判斷Topology[TA,TB]。

根據(jù)現(xiàn)有研究[26,27]，選取存在交集的時間拓撲關(guān)系共6種：meet、overlap、start&contain、during、finish&contain、equals。

規(guī)則1.3.1TA.meetTB，表示“A、B相遇出現(xiàn)”。

規(guī)則1.3.2TA.overlapTB，表示“A、B部分同時出現(xiàn)”。

規(guī)則1.3.3TA.start&containTB，表示“A、B同時出現(xiàn)且B提前離開”。

規(guī)則1.3.4TA.duringTB，表示“A出現(xiàn)期間，B出現(xiàn)并提前離開”。

規(guī)則1.3.5TA.finish&containTB，表示“B在A出現(xiàn)過程中出現(xiàn)且同時離開”。

規(guī)則1.3.6TA.equalsTB,表示“A、B完全同時出現(xiàn)”。

在上述6種時間關(guān)系中，本文關(guān)注的是A、B之間的時間關(guān)聯(lián)類型，而不關(guān)注A、B的出現(xiàn)順序，即規(guī)則中的A、B順序可換。如規(guī)則1.3.3中，既描述“A、B同時出現(xiàn)且B提前離開”，也能描述“A、B同時出現(xiàn)且A提前離開”。下文規(guī)則2也同此。

由判別規(guī)則1.3.1至1.3.6將共處模式分為6種子類型，其判斷規(guī)則、圖示及語義解釋見表3。

表3 共處模式的細分Tab.3 Subdivision of coexistence patterns

續(xù)表3

規(guī)則2當(dāng)Shape(I)=line，表示A、B軌跡在空間上存在公共線段，即A、B在該軌跡線段上同行，稱為“同行模式”。

此時二維平面存在公共軌跡線段I，判斷I的拓撲特征類型，可以進一步區(qū)分“同行起訖點是否存在等待”等主觀意圖。

二級判別規(guī)則為：判斷交集線段I的拓撲特征，記為Type(I)。

公共軌跡線段I來自A、B原軌跡，在AB中的軌跡線段類型分別有4種{p′p,pp′,pp,p′p′}，則重疊組合后I的類型可能有16種，去掉與順序無關(guān)的類型，共存在9種公共軌跡線段類型，即Type(I)∈{[P′P′,P′P′],[P′P′,PP],[P′P′,P′P]/[P′P′,PP′],[PP,PP],[PP,P′P′],[PP,P′P]/[PP,PP′],[P′P,PP′]/[PP′,P′P]/[P′P,P′P]/[PP′,PP′],[P′P,P′P′]/[PP′,P′P′],[P′P,PP]/[PP′,PP]}。

規(guī)則2.1當(dāng)Type(I)=[P′P′,P′P′]，表示“A、B共處→同行→共處→分開”。

規(guī)則2.2當(dāng)Type(I)=[P′P′,PP]，表示“A、B共處→同行→分開”。

規(guī)則2.3當(dāng)Type(I)=[P′P′,P′P]/[P′P′,PP′]：表示“A、B共處→同行→A停留B離開”或“A、B共處→同行→A離開B停留”。

規(guī)則2.4當(dāng)Type(I)=[PP,PP]，表示“A、B接頭→同行→分開”。

規(guī)則2.5當(dāng)Type(I)=[PP,P′P′]，表示“A、B接頭→同行→A、B共處”。

規(guī)則2.6當(dāng)Type(I)=[PP,P′P]/[PP,PP′]，表示“A、B接頭→同行→A停留B離開”或“A、B接頭→同行→A離開B停留”。

規(guī)則2.7當(dāng)Type(I)=[P′P,PP′]/[PP′,P′P]/[P′P,P′P]/[PP′,PP′]，表示“A等待B→接頭后同行→A離開B停留”或“B等待A→接頭后同行→A停留B前行”或“A等待B→接頭后同行→A停留B前行”或“B等待A→接頭后同行→A離開B停留”。

規(guī)則2.8當(dāng)Type(I)=[P′P,P′P′]/[PP′,P′P′]，表示“A等待B→接頭后同行→AB共處”或“B等待A→接頭后同行→AB共處”。

規(guī)則2.9當(dāng)Type(I)=[P′P,PP]/[PP′,PP]，表示“A等待B→接頭后同行→A、B分開前行”或“B等待A→接頭后同行→A、B分開前行”。

由判別規(guī)則2.1至2.9將同行模式分為9種子類型，其判斷規(guī)則、圖示及語義解釋見表4。

綜上，基于該三級判別規(guī)則，能夠區(qū)分和描述“接頭模式”“等待模式”“共處模式”“同行模式”4種基本的關(guān)聯(lián)出行軌跡模式，并可進一步描述共19種不同的關(guān)聯(lián)出行子類型(表1—表4)。

表4 同行模式的細分Tab.4 Subdivision of companion patterns

一級判別規(guī)則Shape(I)二級判別規(guī)則Type(I)關(guān)聯(lián)圖示語義解釋2.Line2.5[PP,P'P']A、B接頭后同行→A、B共處→各自分開2.6[PP,P'P]/[PP,PP']A、B接頭后同行→A停留B離開/A、B接頭后同行→A離開B停留2.7[P'P,PP']/[PP',P'P]/[P'P,P'P]/[PP',PP']A等待B→接頭后同行→A離開B停留/B等待A→接頭后同行→A停留B前行/A等待B→接頭后同行→A停留B前行/B等待A→接頭后同行→A離開B停留2.8[P'P,P'P']/[PP',P'P']A等待B→B抵達后同行→AB共處→各自分開前行/B等待A→A抵達后同行→AB共處→各自分開前行2.9[P'P,PP]/[PP',PP]A等待B→接頭后同行→到達某地后各自分開前行/B等待A→接頭后同行→到達某地后各自分開前行

3 試驗與分析

本文采用某案件相關(guān)的車輛軌跡數(shù)據(jù)進行試驗。2014年某日凌晨3時左右，某市公安局接到報警：在該市碼頭有人遭到一伙戴口罩、持棍棒的不明身份人員毆打，作案后違法犯罪嫌疑人員全部逃竄。偵查人員分析嫌疑人很有可能自帶交通工具，并發(fā)現(xiàn)牌號為皖**車輛在案發(fā)時段有過活動軌跡，通過視頻監(jiān)控平臺軌跡分析，發(fā)現(xiàn)該車在案發(fā)當(dāng)日凌晨3時前后均在中心現(xiàn)場附近出現(xiàn)過，并在多個記錄點發(fā)現(xiàn)同行嫌疑車輛，但由于車牌號碼遮擋，無法區(qū)分，因此，需要進行同行車輛分析，以便還原犯罪團伙的作案過程。

提取案發(fā)前后1 h內(nèi)該路段附近攝像頭的車輛數(shù)據(jù)，結(jié)合人工判斷，提取4輛相關(guān)車輛的軌跡。為消除GPS測量誤差導(dǎo)致同行模式下的軌跡線偏離，進一步將所有軌跡點匹配到統(tǒng)一的道路線上，并進行數(shù)據(jù)加密，預(yù)處理后的該4輛車的時空軌跡如圖3所示。

圖3 預(yù)處理后的4車輛時空軌跡Fig.3 Spatio-temporal trajectories of the four vehicles after preprocessing

采用文獻[12]常見的車輛伴隨模式挖掘方法，得到車輛的關(guān)聯(lián)出行模式為共同停留點和同行路段兩類，a車與b車在時間段t1共同停留在路口1；a車、b車、c車、d車在時間段t2于隋煬東路同行；a車、b車、c車、d車在時間段t3共同停留在路口2；a車與c車在時間段t4于學(xué)士東路同行；b車與d車在時間段t4于隋煬東路同行；a車、b車、c車、d車在時間段t5于瘦西湖路同行；a車與c車在時間段t6于瘦西湖路同行；b車與d車在時間段t6于黃金壩路同行；a車、b車、c車、d車在時間段t7于瘦西湖路同行(表5)。圖4為標注結(jié)果的地圖。

圖4 車輛伴隨模式分析結(jié)果Fig.4 Results of companion pattern mining

表5 文獻[12]方法挖掘的車輛伴隨模式Tab.5 Companion pattern mining based on reference [12]

采用本文關(guān)聯(lián)出行分析方法，判斷四車均存在時空關(guān)聯(lián)，關(guān)聯(lián)出行模式的描述如圖5所示。其中，a車與b車的關(guān)聯(lián)類型為：a車在路口1等待b車→b車到達后共處→b車離開→于路口1接頭→于隋煬東路同行→于路口2共處→于路口2同行→各自離開→于瘦西湖路接頭→各自離開。a車與c車的關(guān)聯(lián)類型為：于路口1接頭→于隋煬東路同行→于路口2共處→于路口2同行→于學(xué)士東路同行→于瘦西湖路同行。a車與d車的關(guān)聯(lián)類型為：于路口1接頭→于隋煬東路同行→于路口2共處→于路口2同行→各自離開→于瘦西湖路接頭→各自離開。b車與c車的關(guān)聯(lián)類型為：于路口1接頭→于隋煬東路同行→于路口2共處→于路口2同行→各自離開→于瘦西湖路接頭→各自離開。b車與d車的關(guān)聯(lián)類型為：于路口1接頭→于隋煬東路同行→于路口2共處→于路口2同行→于隋煬東路同行→于瘦西湖路同行→于黃金壩路同行→于瘦西湖路同行。c車與d車的關(guān)聯(lián)類型為：于路口1接頭→于隋煬東路同行→于路口2共處→于路口2同行→各自離開→于瘦西湖路接頭→各自離開，詳細說明見表6。

圖5 涉案車輛的關(guān)聯(lián)出行模式類型Fig.5 Types of spatio-temporal association patterns of vehicles involved in the case

相比文獻[12]只能區(qū)分共同停留點和同行路段2種關(guān)聯(lián)出行類型，本文方法能夠進一步區(qū)分和描述19種不同的帶有碰頭、等待等主觀意圖的關(guān)聯(lián)出行行為，包括共點模式中的“接頭模式”“等待模式”“共處模式”3種基本類型，其中，接頭模式包含1種子類型、等待模式可細分為3種子類型、共處模式可細分為6種子類型；并能區(qū)分和描述共線模式中9種不同的同行子類型。如表5中時間段t1，a車與b車共同停留在路口1，對應(yīng)表6中可進一步描述為“a車抵達后等待b，共處某時間段后b提前離開”；表5中時間段t2，a車、b車、c車、d車在隋煬東路同行，對應(yīng)表6中可進一步描述為“a車、b車、c車、d車接頭后同行→到達路口2后共處”。相比簡單的共點、共線模式，本文方法能夠更細致地描述犯罪嫌疑人“接頭、等待”等復(fù)雜的主觀意圖，對于案件偵查中還原作案團伙的作案動機、作案軌跡等關(guān)鍵信息具有重要作用。

表6 本文方法挖掘的車輛關(guān)聯(lián)出行模式Tab.6 Association pattern mining based on this paper

其原因在于，現(xiàn)有的軌跡模式挖掘方法是基于軌跡點要素模型，計算時間和空間兩個因素的交集，故而只能發(fā)現(xiàn)共同的停留點或行駛路線；而本文基于“點-線”特征的出行軌跡描述方法，不僅能對軌跡點的關(guān)聯(lián)類型進行分析計算，也能從軌跡線的角度，分析點與線、線與線之間的時空拓撲關(guān)系，從而能夠區(qū)分等待、接頭等更多的關(guān)聯(lián)出行類型。

4 結(jié) 論

本文針對現(xiàn)有的共點、共線描述方法無法區(qū)分更多的犯罪關(guān)聯(lián)模式，首先提出了顧及“點-線”特征的出行軌跡描述方法，能夠較好地兼顧軌跡的細節(jié)點特征和完整線特征；然后，在此基礎(chǔ)上，基于時空拓撲關(guān)系提出了關(guān)聯(lián)出行軌跡的三級判別方法，能夠描述“接頭”“等待”“共處”“同行”4種基本的關(guān)聯(lián)出行軌跡模式，并可進一步細分為19種更詳細的子類型?；谶@些出行軌跡關(guān)聯(lián)模式，能夠在時空背景下解析人員復(fù)雜的互動關(guān)聯(lián)，對犯罪防控、案件偵查等有重要的幫助意義，并可為時空關(guān)聯(lián)分析、時空行為建模等提供思路和方法。