面向車輛目的地推測的時空搜索優化

韓 磊,於志勇,2,3,朱偉平,於志文

(1.福州大學 數學與計算機科學學院,福州 350116; 2.福建省網絡計算與智能信息處理重點實驗室,福州 350116;3.空間數據挖掘與信息共享教育部重點實驗室,福州 350002; 4.西北工業大學 計算機學院,西安 710072)

0 概述

隨著我國城市化進程的不斷加快,城市建設取得了巨大成就,但是,城市人口密度大、人員流動性強的狀況也引起了一些公共安全問題,車輛目的地推測對解決城市公共安全問題具有重要意義。警察獲知目標車輛某時刻從某地出發,其需要盡可能準確地掌握該車輛的目的地以制定行動計劃。然而,在很多情況下,由于數據丟失、隱私保護等原因,使得準確推測該車輛的目的地十分困難。此時,警察可以通過已知的目標車輛位置信息來推測其目的地,但是由于已知車輛信息太少(在通常情況下,警察只知道車輛的出發時刻和出發位置),其目的地推測的準確率通常不高。

目前,在城市道路中分布著大量進行全天錄像的攝像頭,可通過這些視頻數據來獲取更多關于目標車輛的途經信息,進而提高車輛目的地推測的準確率。從視頻中識別目標車輛的途徑信息,需要一定的人工和機器成本,且攝像頭數量規模龐大,通過所有的視頻數據進行全時全域搜索時難度巨大。因此,通過盡可能少的時空搜索(通過搜索城市攝像頭視頻數據來查看某個時刻目標車輛是否途經某個位置)來準確推測出目標車輛的目的地,引起了研究人員的廣泛關注。

本文研究面向目的地推測的時空搜索優化問題,通過對道路攝像頭的所有視頻錄像進行時空搜索以獲取車輛的途經信息,從而提高車輛目的地推測的準確率。在此基礎上,使用基于概率的單一指標、基于概率和基尼指數的復合指標[1]以及基于概率和信息增益的復合指標[2]來評價時空搜索方法的性能。

1 相關工作

針對目標搜索問題,文獻[3]提出并建立了一種海上立體搜尋全局優化模型,文獻[4]就飛機發生事故失去動力后黑匣子落水點的位置問題進行了研究,文獻[5]以馬航事件為背景,基于貝葉斯方法提出一種針對特定區域的失蹤目標搜索算法。

基于已知車輛位置信息判斷車輛目的地是移動預測的目標,針對該問題,文獻[6]提出了一種基于移動性近似的目的地預測算法,該算法關注軌跡本身的運動行為以尋找潛在目的地,然后利用移動梯度下降法來確定目標的目的地。文獻[7]研究了個人社會信息和出行信息對出行目的地選擇行為的影響。文獻[8]通過調查GPS數據,建立利用Markov模型進行目的地預測的概率模型。文獻[9]根據人類日常移動路線表現出的時間和空間的規律性,使用拓展的連續路徑模式挖掘算法從軌跡中提取運動模式,并從該運動模式中構建模式樹以進行目的地預測。此外,在歷史信息中(如道路狀況、駕駛習慣[10]和軌跡長度[11-13]等)加入外部信息也可以提高預測的準確率。文獻[14]提出了SMLP算法,該算法在Markov模型的基礎上利用網絡內用戶的相關性對位置進行預測。

主動感知指智能體采取一定行為以獲取更多環境相關信息。在機器視覺[15]和機器人學領域,主動感知已經被廣泛應用于定位和導航任務[16]。此外,主動感知還在同步定位和映射[17]、越野駕駛[18]、機器人探索[19]、雷達目標追蹤、聲吶和光電探測器[20]等方面得到應用。基于車輛起始位置,通過時空搜索獲取更多車輛途經信息以提高車輛目的地預測準確率的思想與主動感知[21]相似。在一個主動感知過程中,系統會根據環境狀態主動執行感知行為[22]以對環境進行認知。

本文針對城市中的目標車輛搜索問題,提出一種面向目的地推測的時空搜索優化算法,該算法主要包括移動預測和主動感知2個部分。傳統目的地預測方法無車輛途經點搜索過程,本文算法增加了這一過程,以獲取更多車輛途經信息。

2 問題定義

為了更好地定義面向目的地推測的時空搜索優化問題,本文定義如下符號:令攝像頭視頻集合D={d1,d2,…,d|D|},位置集合L={l1,l2,…,l|L|},行程集合N={n1,n2,…,n|N|},行程時間序列T=,車輛集合C={c1,c2,…,c|C|},車輛行程軌跡集合TR={tr(cr,nu)},其中,tr(cr,nu)=<(t1,lt1),(t2,lt2),…>|cr,nu。已知車輛cr的出發時間t1和出發位置lt1后,搜索時刻為tk,搜索位置為li,時空搜索結果為q(cr,tk,li),當目標車輛cr在tk時刻出現在位置li時,q(cr,tk,li)=1;否則記為q(cr,tk,li)=0,如式(1)所示。

(1)

IInterval表示搜索時刻與車輛起始出發時刻的差值,即IInterval=tk-t1。最后,本文將q(cr,tk,li)實例化后的tk、li稱為time-location,需要考慮(t|T|-t1)×|L|個候選time-location。

在一般情況下,車輛到達目的地后就無法通過城市道路攝像頭搜索到該車輛,因此,本文假設車輛當前行程結束后短時間內將無法通過攝像頭視頻數據再次搜索到該車輛的蹤跡。此外,查詢視頻錄像的成本(包括人力和機器成本)遠大于模型訓練和目的地推測的計算成本,因此,完成車輛目的地推測任務的代價可通過時空搜索次數N來預估,使用AAccuracy作為模型性能的評估度量,AAccuracy表示車輛cr在行程nu中目的地lx的推測準確率,計算公式如下:

(2)

其中,#tr()表示軌跡條數。

問題(面向目的地推測的時空搜索優化)給出車輛的歷史行程軌跡集合T′R、車輛cr行程nu的起始時刻t1、起始位置lt1,以及當天可供時空搜索使用的道路攝像頭視頻錄像數據dj。優化目標是在N次時空搜索q(cr,tk,li)的條件下最大化車輛cr行程nu的目的地lx推測的準確率AAccuracy。優化問題表達式如下:

givecr,nu,(t1,lt1),T′R,N,q(cr,ti,lk)indj

returnlx,s.t.maxAAccuracy

(3)

3 車輛目的地推測

假設已知車輛歷史行程軌跡T′R,在僅知道車輛某時刻從某地出發的情況下推測該車輛的目的地,方法有以下2種:根據車輛的起始位置信息推測出車輛目的地;通過時空搜索獲取車輛途經信息,再結合車輛的起始位置信息推測車輛目的地。

對于第1種方法,本文基于簡單一階Markov模型進行實現,其推測車輛目的地的流程如圖1所示。

圖1 基于簡單一階Markov模型的車輛目的地推測

設車輛位置轉移概率(簡稱M)表示車輛從一個位置移動到另一個位置的概率,M計算公式如下:

(4)

(5)

對于第2種方法,本文基于引入時空搜索的一階Markov模型進行實現,其推測車輛目的地的流程如圖2所示。

圖2 基于改進一階Markov模型的車輛目的地推測

Fig.2 Vehicle destination inference based on improved first-order Markov model

此時車輛位置轉移概率計算如下:

(6)

(7)

由于車輛軌跡信息不足(只知車輛出發位置和出發時刻),基于簡單一階Markov模型推測車輛目的地時的準確率不高,因此本文基于改進一階Markov模型來推測車輛目的地。在時空搜索方式的選擇上,本文提出基于概率的單一指標、基于概率和基尼指數的復合指標以及基于概率和信息增益的復合指標來評估不同時空搜索方式的性能,并基于3種指標分別實現算法CFMM-MidQuery、CFMM-UtilityQuery-Gini和CFMM-UtilityQuery-Info。

3.1 CFMM-MidQuery算法

設車輛cr行程的起始時間為t1,起始位置為li,首先確定車輛cr在tmid時刻的N個可能性最大的位置,表示為lq[1],lq[2],…,lq[j],…,lq[N]。然后執行時空搜索q(cr,tmid,lq[j]),得到N個返回結果,這些結果可能包含一個1(即確定了目標車輛cr在tmid時刻的位置為lq[j])或者所有結果都是0(即tmid時刻在lq[1],lq[2],…,lq[j],…,lq[N]這些位置均未找到目標車輛cr),然后將q(cr,tmid,lq[j])的返回結果作為條件訓練一階Markov模型。該過程為CFMM-MidQuery算法過程,其偽代碼如下。

算法1CFMM-MidQuery算法

輸入T′R(車輛歷史行程軌跡),(cr的起始時刻和位置),tmid(搜索時刻),N(時空搜索次數)

輸出車輛cr的終點位置

1.根據T′R計算t1時刻位置為lt1的車輛在tmid時刻的位置分布概率LSm

2.遍歷向量LSm,返回N個概率最大的位置編號索引:lq[1],lq[2],…,lq[j],…,lq[N]

3.執行時空搜索q(cr,tmid,lq[j])

4.根據T′R、和時空搜索結果計算終點位置分布概率LSc

5.根據LSc返回概率最大的位置

6.END

3.2 CFMM-UtilityQuery算法

CFMM-MidQuery算法需要先指定搜索時刻,其不能說明哪個搜索時刻是最佳選擇,而在CFMM-UtilityQuery算法中,按照效益值大小將不同的候選time-location進行排序,選擇效益大的time-location執行時空搜索,然后將返回結果作為條件訓練模型(模型構建過程與CFMM-MidQuery相同)。在此基礎上,本文分別實現基于概率和基尼指數復合評估指標的CFMM-UtilityQuery-Gini算法與基于概率和信息增益復合評估指標的CFMM-UtilityQuery-Info算法。

3.2.1 CFMM-UtilityQuery-Gini算法

假設目標車輛cr的起始時間為t1,起始位置為lt1。首先,基于概率和基尼指數復合評估指標計算tk時刻搜索位置ls對于推測車輛cr目的地的效用,計算公式如式(8)所示。

(1-ggini(tk,ls))

(8)

式(8)由兩部分組成:p(lt1,ls)|(t1→tk)表示q(cr,tk,ls)=1的概率,(1-ggini(tk,ls))用于評估以q(cr,tk,ls)=1作為條件篩選訓練數據后車輛cr終點位置分布的混亂程度。若終點位置分布概率為P={p1,p2,…,pk,…,pM},則原始基尼指數計算公式如式(9)所示。

(9)

因此,本文基尼指數計算公式如式(10)所示。

ggini(tk,ls)=ggini{p(lt1,lx)|(t1→t|T|),

q(cr,tk,ls)=1}

(10)

CFMM-UtilityQuery-Gini算法偽代碼如下:

算法2CFMM-UtilityQuery-Gini算法

輸入T′R(車輛歷史行程軌跡),(車輛cr的起始時刻和位置),N(時空搜索次數)

輸出車輛cr的終點位置

1.FOR tmid←t1TO t|T|

2.根據T′R計算t1時位置為lt1的車輛在tmid時刻的位置分布概率LSm

3.FOR lmid←l1TO l|L|

4.根據T′R計算t1時刻位置為lt1、tmid時刻位置為lmid的車輛終點位置分布概率LSme

5.END FOR

7.END FOR

,,…,,…,

9.執行時空搜索q(cr,ti,lq[i])并且返回搜索結果

10.根據T′R、和時空搜索結果計算終點位置分布概率LSe

11.返回LSe中概率最大的位置

12.END

3.2.2 CFMM-UtilityQuery-Info算法

假設目標車輛cr的起始時間為t1,起始位置為lt1。首先,基于概率和信息增益復合評估指標計算tk時刻搜索位置ls對于推測車輛cr目的地的效用,其計算公式如式(11)所示。

(11)

其中,Iinfo(tk,ls)評估q(cr,tk,ls)=1作為條件篩選訓練數據后車輛終點位置分布的混亂程度。若終點位置分布概率為P={p1,p2,…,pk,…,pM},則熵計算公式如式(12)所示。

(12)

因此,本文信息增益計算公式如式(13)所示。

Iinfo(tk,ls)=E{p(lt1,lt|T|)|(t1→t|T|)}-

E{p(lt1,lt|T|)|(t1→t|T|),

q(cr,tk,ls)=1}

(13)

CFMM-UtilityQuery-Info算法偽代碼如下:

算法3CFMM-UtilityQuery-Info算法

輸入TR′(車輛歷史行程軌跡),(車輛cr的起始時刻和位置),N(時空搜索次數)

輸出車輛cr的終點位置

1.根據T′R計算t1時刻位置為lt1的車輛終點位置分布概率LSse

2.根據LSse和式(12)計算熵E1

3.FOR tmid←t1TO t|T|

4.根據T′R計算t1時位置為lt1的車輛在tmid時刻的位置分布概率LSm

5.FOR lmid←l1TO l|L|

6.根據T′R計算t1時刻位置為lt1、tmid時刻位置為lmid的車輛終點位置分布概率LSme

7.根據LSme和式(12)計算熵E2

8.END FOR

10.END FOR

12.執行時空搜索q(cr,ti,lq[i])

13.根據T′R、和時空搜索結果計算終點位置分布概率LSe

14.返回LSe中概率最大的位置

15.END

4 實驗結果與分析

4.1 原始數據描述

本文的實驗數據來自滴滴出行平臺(https://gaia.didichuxing.com),原始數據為成都市部分區域的滴滴訂單數據,采集區域的面積大小約為8.37 km×8.35 km,采集日期范圍為2016年11月1日—2016年11月30日,原始數據信息如表1所示。

表1 原始數據信息

4.2 實驗數據預處理

在數據集中,不同車輛的GPS點是無序的,需要對數據集中車輛訂單ID和時間使用二級排序算法生成出租車的GPS點序列。由于原始數據時間精度為3 s,如果同一行程軌跡相鄰兩GPS點的時間相差超過3 s,則認為該軌跡數據部分缺失,按照3 s的時間精度補全缺失數據。如果缺失時長不超過60 s,則在該段缺失時間內車輛被認為是勻速直線行駛;若缺失時間超過60 s,則認為該軌跡缺失嚴重,將其舍棄。

在排好序的出租車GPS點序列中,每輛車每分鐘包括若干個GPS坐標點,且不同分鐘內GPS點的個數不同,因此,本文以分鐘為單位將時間離散化,每分鐘僅取時間最小的一條位置數據表示車輛在該時間的位置。最后根據數據范圍將該區域劃分成大小約為0.93 km×0.93 km的方格[23](共計81個網格),將車輛的軌跡數據投影到網格中,一個網格就代表一個位置區域。

4.3 結果分析

本文基于相同的實驗數據集,測試不同階Markov模型推測車輛目的地的準確率,結果如圖3所示。從圖3可以看出,當Markov模型階數達到3時,車輛目的地推測的準確率達到最高(2階Markov模型和3階Markov模型在推測車輛目的地時的準確率基本一致),然后隨著模型階數的增加其推測準確率逐漸降低,因此,當有多個時空搜索返回結果為1時,本文僅選擇一個time-location參與模型的訓練與預測。

圖3 不同階數Markov模型的推測性能對比

Fig.3 Comparison of inference performance of Markov models with different orders

為研究相同數據集下車輛目的地推測準確率與IInterval的關系,本文基于二階Markov模型改變IInterval(固定起始時間,改變中間搜索時刻),測試模型推測準確率,結果如圖4所示。從圖4可以看出,隨著IInterval的增大,車輛目的地推測的準確率也逐漸提高。因此,當有多個時空搜索返回結果為1時,本文僅選擇IInterval最大的time-location參與模型的訓練與預測。

圖4 不同IInterval時的二階Markov模型推測準確率

Fig.4 Inference accuracy of second-order Markov model with differentIInterval

圖5所示為不同行程時長下的軌跡統計情況,由圖5可以看出,隨著時長的增加,大于該時長的軌跡比例逐漸減小,即在搜索時刻逐漸增大時,通過攝像頭視頻錄像找到車輛的可能性將降低。

圖5 不同行程時長下的軌跡統計情況

由圖4可以看出,隨著IInterval的增大,車輛目的地推測的準確率逐漸提高;由圖5可以看出,隨著搜索時刻的增大,行程時長大于該搜索時刻的軌跡比例逐漸減小。因此,CFMM-MidQuery算法很難選擇合適的中間搜索時刻。本文基于二階Markov模型,測試相同搜索次數下不同中間搜索時刻時車輛目的地推測的準確率,結果如圖6所示,從圖6可以看出,在相同搜索次數下,IInterval為5 min時,CFMM-MidQuery算法推測車輛目的地的準確率最高。

圖6 不同搜索時刻下CFMM-MidQuery算法推測準確率

Fig.6 Inference accuracy of CFMM-MidQuery algorithm at different search times

由圖6可以看出,當搜索時刻為5 min時,CFMM-MidQuery算法的性能較好,因此,將CFMM-MidQuery算法的搜索時間定為5 min,本文將之稱為CFMM-MidQuery-5算法。比較CFMM-MidQuery-5、CFMM-UtilityQuery-Info、CFMM-UtilityQuery-Gini 3種算法,結果如圖7所示。從圖7可以看出,當N較小時,CFMM-UtilityQuery-Gini和CFMM-MidQuery-5算法推測車輛目的地的準確率沒有太大區別,且2種算法略優于CFMM-UtilityQuery-Info算法;當N進一步增大時,CFMM-UtilityQuery算法推測車輛目的地的準確率明顯高于CFMM-MidQuery-5算法,而CFMM-UtilityQuery-Info、CFMM-UtilityQuery-Gini 2種算法在推測車輛目的地的準確率方面無明顯區別。基于概率單一指標的方法只考慮當前時空搜索找到目標車輛的概率,不考慮當前時空搜索對車輛目的地推測的效用,并且該指標需要指定搜索時刻,限制了時空搜索范圍,導致時空搜索次數較高時無法執行更合適的時空搜索;信息增益和基尼指數都是評價車輛位置分布混亂程度的度量,都能在客觀上反映車輛位置的概率分布情況,因此,這2種復合指標在推測車輛目的地的準確率方面無明顯區別。

圖7 不同搜索次數下3種算法車輛目的地推測準確率對比

Fig.7 Comparison of inference accuracy of vehicle destination using 3 algorithms under different search times

5 結束語

獲取目標車輛更多的行程途經信息可以提高車輛目的地推測的準確率。本文提出基于概率和基尼指數的復合指標與基于概率和信息增益的復合指標,不僅考慮當前時空搜索下找到目標車輛的可能性,還兼顧當前時空搜索對目的地推測的長期效用。復合指標無需指定搜索時間,可以將不同時間下的空間搜索進行比較,解決了概率單一指標需要指定搜索時間的問題。實驗結果表明,在高搜索次數條件下,復合指標的評估效果明顯優于概率單一指標。

本文假設車輛行程結束后短時間內無法通過視頻數據再次搜索到該車輛的蹤跡,該假設過于理想,下一步將基于車輛一天中的完整軌跡在給定時刻進行車輛位置搜索,以解決上述假設的局限性問題。