基于語義行為的車輛軌跡停留點(diǎn)提取算法

陶 健，王 睿，秦曉安，殷西祥

隨著車載智能終端設(shè)備、定位技術(shù)和存儲(chǔ)技術(shù)的快速發(fā)展，車輛軌跡數(shù)據(jù)的收集存儲(chǔ)得以實(shí)現(xiàn).如何有效分析利用這些軌跡數(shù)據(jù)，成為數(shù)據(jù)挖掘者研究的熱點(diǎn)問題［1-3］.其中，停留點(diǎn)作為車輛軌跡中隱含的重要信息，表示用戶經(jīng)常出沒的、帶有重要語義信息的地區(qū)，如餐館、景點(diǎn)等；提取停留點(diǎn)能為車主日常出行、位置信息搜索、觀光瀏覽等提供輔助決策，同時(shí)也是構(gòu)建位置服務(wù)個(gè)性化推薦系統(tǒng)的基礎(chǔ).

軌跡數(shù)據(jù)挖掘的早期研究主要針對(duì)時(shí)間、幾何特性，并未考慮空間特性；其中有關(guān)停留點(diǎn)提取的算法大致分為三類：基于時(shí)間的聚類算法、基于密度的聚類算法，以及分割聚類算法.

關(guān)于時(shí)間聚類算法，KANG［4］根據(jù)軌跡點(diǎn)的時(shí)間連續(xù)特性，通過時(shí)間閾值和距離閾值設(shè)計(jì)了基于時(shí)間的聚類算法；LV 等人［5］考慮到由于高樓遮擋造成GPS 信號(hào)損失使得軌跡不連續(xù)問題，在時(shí)間聚類算法上增加容忍距離閾值對(duì)形成的相鄰聚類區(qū)域進(jìn)行判斷是否需要合并；MONTOLIU 等人［6］考慮連續(xù)位置點(diǎn)缺失造成停留點(diǎn)誤判問題，在時(shí)間聚類算法上增加時(shí)間差閾值對(duì)相鄰位置點(diǎn)進(jìn)行聚類判別；侯穎超等人［7］考慮車輛行駛在戶外，且不存在長時(shí)間信號(hào)缺失現(xiàn)象的問題，在時(shí)間聚類算法上增加速度閾值對(duì)候選停留點(diǎn)進(jìn)行過濾.雖然時(shí)間聚類算法能夠發(fā)現(xiàn)長時(shí)間停留的停留點(diǎn)，但是對(duì)時(shí)間閾值要求較高，而車輛軌跡中出租車軌跡更多的是短暫停留，這極易造成停留點(diǎn)的丟失.

基于密度的聚類算法，是從軌跡的幾何特性出發(fā)，對(duì)位置點(diǎn)稠密區(qū)進(jìn)行聚類來發(fā)現(xiàn)任 意 形 狀 停 留 點(diǎn)，如SmoT［8］、CB-SMoT［9］、DJ-Cluster［10］等，但難以解決行駛在路網(wǎng)上的車輛軌跡的停留點(diǎn)提取，容易將十字路口、立交橋等誤判為停留點(diǎn).

關(guān)于分割聚類算法，ASHBROOK 等人［11］利用K-Means 的算法思想設(shè)計(jì)了基于切割聚類的停留點(diǎn)提取方法；HUANG 等人［12］通過切割聚類的思想，提出一種停留穩(wěn)定性的概念，進(jìn)而對(duì)軌跡進(jìn)行切割劃分，將停留穩(wěn)定性高于切割標(biāo)準(zhǔn)的子軌跡聚類作為停留點(diǎn).分割聚類算法雖然能夠發(fā)現(xiàn)停留時(shí)間較短的停留點(diǎn)，但并沒有針對(duì)車輛軌跡行駛在路網(wǎng)的特征，會(huì)將十字路口等地誤判為停留點(diǎn).

不同的應(yīng)用場景決定了空間軌跡特點(diǎn)不同，車輛軌跡一般通過車載智能終端設(shè)備采集所得，設(shè)備在行車期間一直保持供電，且長期行駛在戶外，一般不會(huì)產(chǎn)生信號(hào)缺失問題，且軌跡位置點(diǎn)時(shí)間間隔較為恒定.但車輛軌跡被路網(wǎng)嚴(yán)格約束，行車中會(huì)遭遇大量紅綠燈路口、立交橋等，如圖1 所示.先前的停留點(diǎn)提取方法［3-12］會(huì)造成停留點(diǎn)誤判問題，將十字路口或立交橋的偽停留點(diǎn)（Pseudo stay point，PSP）誤判為對(duì)某地感興趣停留點(diǎn).

圖1 十字路口的偽停留

針對(duì)上述問題，本文提出一種基于語義行為的車輛軌跡停留點(diǎn)提?。⊿emantic behavior-based vehicle trajectory stay point extraction，SPE）算法，該算法從語義行為分析的角度，利用軌跡進(jìn)行空間路網(wǎng)建模，將車輛行駛中產(chǎn)生的偽停留點(diǎn)有效剔除，提高了停留點(diǎn)的提取精度，為車輛用戶語義行為的分析打下基礎(chǔ).

1 車輛軌跡停留點(diǎn)提取

1.1 相關(guān)定義及描述

本文令VT={Tr1,Tr2,…,Trn} 為車輛軌跡數(shù)據(jù)集合，按照一天的時(shí)間間隔劃分，一條軌跡Tri為一輛車行駛一天的位置點(diǎn)集合，其詳細(xì)描述如定義1 所示.

定義1（車輛軌跡）車輛軌跡是包含時(shí)間的有限位置點(diǎn)序列，用符號(hào)表示為Tri=1≤i≤n，其 中，idi表示車輛唯一標(biāo)識(shí)；表示二維地理空間中位置點(diǎn)的緯度與經(jīng)度，其數(shù)據(jù)是在WGS-84坐標(biāo)系下采集所得；ti為位置點(diǎn)的時(shí)間戳信息，且?1

定義2（曼哈頓距離）已知兩個(gè)連續(xù)經(jīng)緯度位置點(diǎn)pi(lati,loni)和pi+1(lati+1,loni+1)，通過坐標(biāo)轉(zhuǎn)換工具將其轉(zhuǎn)換為二維平面空間坐標(biāo)，即pi(xi,yi)和pi+1(xi+1,yi+1)，則連續(xù)位置點(diǎn)的曼哈頓距離為：

其中：xi和yi分別是對(duì)應(yīng)緯度lati和經(jīng)度loni轉(zhuǎn)換的二維平面空間坐標(biāo)點(diǎn).

定義3 （停留穩(wěn)定性）相鄰位置點(diǎn)pi和pi+1之間的停留穩(wěn)定性表示為：

其 中：Δti=ti+1-ti是 相 鄰 位 置點(diǎn)pi和pi+1之間的時(shí)間間隔，Δdi=len(pi,pi-1)為相鄰位置點(diǎn)的曼哈頓距離且不為零.

為了便于理解，本文根據(jù)路網(wǎng)基本都是東西、南北走向，且采用出租車數(shù)據(jù)集，相比傳統(tǒng)歐式距離的計(jì)算方法［12］，采用曼哈頓距離方法計(jì)算相鄰位置點(diǎn)距離更為合理且效率更高，具體如表1 給出的舊金山出租車軌跡的相鄰位置點(diǎn)停留穩(wěn)定性計(jì)算實(shí)例.

表1 相鄰位置點(diǎn)停留穩(wěn)定計(jì)算實(shí)例

其中經(jīng)緯度坐標(biāo)位置點(diǎn)通過坐標(biāo)轉(zhuǎn)換工具轉(zhuǎn)換為二維平面空間坐標(biāo)點(diǎn)，位置點(diǎn)時(shí)間為Unix 時(shí)間戳格式，根據(jù)公式（1）和公式（2）進(jìn)行計(jì)算，得其停留穩(wěn)定性為：Sstab(pi,pi+1)= 0.042 5.

定義4（平均停留穩(wěn)定性）結(jié)合停留穩(wěn)定性的公式，一條軌跡Tri的平均停留穩(wěn)定性如公式（3）所示：

其中：A、B是軌跡Tri的第一個(gè)位置點(diǎn)和最后一個(gè)位置點(diǎn)，n是A、B間相鄰位置點(diǎn)的間隔數(shù)量.

定義5 （候選停留點(diǎn)）軌跡Tri的部分連續(xù)位置點(diǎn){pa,pa+1,…,pb}構(gòu)成的子軌跡Trab聚類成為候選停留點(diǎn)，當(dāng)且僅當(dāng)該子軌跡的所有相鄰位置點(diǎn)的停留穩(wěn)定性都高于切割線cut，該子軌跡Trab構(gòu)成的候選停留點(diǎn)表示形式為：

定義6（停留點(diǎn)）某一時(shí)間區(qū)域或空間區(qū)域內(nèi)車輛用戶產(chǎn)生某種感興趣語義行為，如對(duì)公園、餐館等感興趣而停留的點(diǎn).

1.2 數(shù)據(jù)清洗

一般在進(jìn)行軌跡停留點(diǎn)提取之前，由于人為或機(jī)器問題，會(huì)造成車輛軌跡數(shù)據(jù)中大量位置冗余，需要對(duì)原始軌跡進(jìn)行數(shù)據(jù)清洗［13］實(shí)現(xiàn)數(shù)據(jù)可用性的目的.

圖2 數(shù)據(jù)清洗實(shí)例

圖2 所示的舊金山出租車軌跡數(shù)據(jù)樣本，框里的為冗余數(shù)據(jù).本文將TXT 格式的樣本數(shù)據(jù)導(dǎo)入到MySQL 數(shù)據(jù)庫中，應(yīng)用MySQL 的“去重語句”，將其中的冗余數(shù)據(jù)進(jìn)行清洗，僅保留其中一條，為后續(xù)停留點(diǎn)的提取提高精度.

1.3 停留點(diǎn)提取算法

在SPE 算法中，為了提高停留點(diǎn)實(shí)用性，從語義行為的角度對(duì)停留點(diǎn)進(jìn)行精煉，其過程主要分為兩個(gè)階段：采用基于停留穩(wěn)定性切割聚類（Cutting clustering based on stay stability，CSS）算法將停留穩(wěn)定性高的子軌跡聚類作為候選停留點(diǎn).采用基于十字路口過濾（Filtering based on intersection，F(xiàn)BOI）算法將位于十字路口的那些偽停留點(diǎn)進(jìn)行過濾得到符合車輛用戶對(duì)某地感興趣的停留點(diǎn).

基于停留穩(wěn)定性切割聚類算法.現(xiàn)實(shí)生活中，車輛用戶每當(dāng)遇到一個(gè)感興趣的地方，不會(huì)瞬間停止，而是緩慢地到達(dá)目的地；此外，對(duì)有些地方可能只是短暫的停留，如出租車用戶.應(yīng)用CSS 算法可以不依賴停留時(shí)間的長短，而發(fā)現(xiàn)在某地短暫停留的情況，具體如算法1 所示.

為了更好解釋該算法，給出CSS 算法的一個(gè)應(yīng)用實(shí)例，如圖3 所示.

圖3 基于CSS 算法的應(yīng)用實(shí)例

圖3 （a）所示的是出租車在舊金山城區(qū)行駛一天的三維立體軌跡圖例，其中A 點(diǎn)是行駛中的第一個(gè)位置點(diǎn)，B 點(diǎn)是出租車最后停止的位置點(diǎn)，從圖3（a）中可以發(fā)現(xiàn)運(yùn)動(dòng)軌跡和目的地具有極大的隨機(jī)性.

圖3（b）所示的是這條軌跡進(jìn)行CSS 算法后的一個(gè)切割實(shí)例圖，該條軌跡在進(jìn)行公式（3）計(jì)算后得到平均停留穩(wěn)定性為AveSstab(A,B) =0.546 5；當(dāng)切割系數(shù)Ncoef= 1.0，即切割線cut= 0.546 5 時(shí)，位于切割線以上的穩(wěn)定性子軌跡為16 條，調(diào)用算法的第4 步，得到候選停留點(diǎn)為16 個(gè).

基于十字路口過濾.車輛在行駛過程中會(huì)遭遇大量十字路口而被迫停留，這些偽停留點(diǎn)并不是車輛用戶感興趣的語義行為，故提出基于十字路口過濾算法來對(duì)候選停留點(diǎn)進(jìn)行精煉，如算法2 所示.

同時(shí)，Semantic MediaWiki還支持將語義查詢代碼內(nèi)嵌入內(nèi)容文檔中，這樣就可以根據(jù)需要，直接引用并顯示檢索的內(nèi)容，并與原文檔內(nèi)容進(jìn)行有機(jī)的整合，既簡化了編輯步驟，又增加了知識(shí)文檔的共享程度。例如創(chuàng)建一個(gè)內(nèi)容文檔頁面如下：

如圖4 所示，由于駕駛員的行車偏好，車輛軌跡在路網(wǎng)之上分布極不均勻，算法2 中首先通過車輛軌跡對(duì)空間路網(wǎng)進(jìn)行建模［14］獲得十字路口，不僅可以快速對(duì)整個(gè)路網(wǎng)進(jìn)行十字路口提取，而且更有利于車輛軌跡在空間上的近似化分析，更適用于任何城區(qū)的十字路口提取研究.

圖4 車輛行駛軌跡可視化圖示

1.4 停留點(diǎn)實(shí)用性

為了驗(yàn)證本文提出的SPE 算法的有效性，文獻(xiàn)［6］給出停留點(diǎn)提取的指標(biāo)，包括準(zhǔn)確率、召回率和調(diào)和平均值.

本文中準(zhǔn)確率指的是正確停留點(diǎn)數(shù)量與發(fā)現(xiàn)停留點(diǎn)數(shù)量的比值，如公式（4）所示.

其中：|{correct}|為正確停留點(diǎn)數(shù)量，據(jù)微軟研究者所述［15］，當(dāng)發(fā)現(xiàn)的停留點(diǎn)和車輛用戶記憶中的停留位置距離不超過50 m，則該停留點(diǎn)為正確停留點(diǎn)；|{discovered}|為經(jīng)過SPE 算法發(fā)現(xiàn)的停留點(diǎn)數(shù)量.

召回率指的是正確停留點(diǎn)數(shù)量與出租車司機(jī)記憶點(diǎn)數(shù)量的比值，如公式（5）所示.

其中：|{remembered}|為車輛用戶記憶中停留位置點(diǎn)，本文中的記憶點(diǎn)為出租車上下客位置點(diǎn)，即車輛軌跡屬性中狀態(tài)位由0 變1 和由1 變0 的相應(yīng)位置點(diǎn).

調(diào)和平均值是準(zhǔn)確率和召回率的平衡指標(biāo)，被作為停留點(diǎn)提取的實(shí)用性指標(biāo)，具體如公式（6）所示.

2 實(shí)驗(yàn)及分析

2.1 實(shí)驗(yàn)設(shè)置

實(shí)驗(yàn)環(huán)境是在Windows7 32 位操作系統(tǒng)上使用Java 語言開發(fā)，并運(yùn)行在一臺(tái)配置為2.83G Intel 雙核CPU，內(nèi)存為3G 的PC 機(jī)上，通過My Eclipse 軟件進(jìn)行Java 語言的編寫與調(diào)試，并將結(jié)果通過Origin 軟件進(jìn)行量化.本實(shí)驗(yàn)采用的車輛軌跡數(shù)據(jù)是PIORKOWSKI 等人［16］提供的包括500 輛出租車于2008 年5 月17 日至6 月10 日在舊金山城區(qū)行駛近一個(gè)月的真實(shí)出租車軌跡數(shù)據(jù)集，該數(shù)據(jù)集已經(jīng)應(yīng)用于學(xué)術(shù)研究的多個(gè)領(lǐng)域，具有真實(shí)可靠性，具體如表2 所示.

表2 舊金山出租車軌跡數(shù)據(jù)集

2.2 參數(shù)值的選取

本文提出的SPE 算法中，每一個(gè)子算法的參數(shù)值都會(huì)影響停留點(diǎn)提取的效果，接下來詳細(xì)闡述算法中用到的參數(shù)值的選取.

（1）ρ和N的選取.根據(jù)城市道路交通的車道規(guī)定［14］，將圓形區(qū)域設(shè)定值ρ的取值為直徑50 m.通過舊金山出租車1 011 條軌跡數(shù)據(jù)的Δα處理，得到轉(zhuǎn)向點(diǎn)67 480 個(gè)，結(jié)合舊金山城區(qū)的特點(diǎn)，并經(jīng)過數(shù)次測(cè)試，選取最小轉(zhuǎn)向點(diǎn)數(shù)為N= 30，得到十字路口數(shù)量為|INS|= 352.圖5 是投影到Google Earth 上的局部十字路口可視化圖，其中圓形圖標(biāo)代表十字路口.

圖5 局部十字路口可視化示例

（2）Ncoef和DIns的選取.首先從舊金山軌跡數(shù)據(jù)集中隨機(jī)選取一條軌跡，其包含位置點(diǎn)1 152 個(gè)，根據(jù)軌跡屬性 中status的0，1 變化，對(duì)上下客位置點(diǎn)進(jìn)行提?。?7］，得到車輛用戶記憶中的停留點(diǎn)42 個(gè).

圖6 給出參數(shù)Ncoef和DIns的不同取值和與其相對(duì)應(yīng)的準(zhǔn)確率和召回率的變化，由于軌跡數(shù)據(jù)是明顯的偏態(tài)分布，從圖6 中可以分析出：隨著兩個(gè)參數(shù)值的改變，準(zhǔn)確率和召回率呈現(xiàn)出一種波動(dòng)的變化.

當(dāng)距離閾值DIns一定的條件下，由于軌跡的平均停留穩(wěn)定性極易遭受數(shù)據(jù)極端值的影響，即在切割系數(shù)Ncoef不斷增大的初期，準(zhǔn)確率和召回率都有明顯地提高，但隨著Ncoef繼續(xù)增大，部分停留點(diǎn)可能會(huì)被割裂丟棄，從圖中可以看出當(dāng)切割系數(shù)Ncoef> 3.0 時(shí)，準(zhǔn)確率和召回率都在不斷降低，即選取切割系數(shù)為Ncoef= 3.0.當(dāng)切割系數(shù)Ncoef一定的條件下，隨著DIns的不斷增大，十字路口附近的停留點(diǎn)會(huì)被過濾，導(dǎo)致準(zhǔn)確率和召回率的降低，當(dāng)DIns>30 m 時(shí)，出現(xiàn)明顯降低；在DIns取值上，若選取太小，不能很好地將十字路口的偽停留點(diǎn)過濾，若DIns取值太大，又會(huì)丟失一些有意義的停留點(diǎn)，結(jié)合生活中行車至十字路口不允許停車的規(guī)定，本文選取距離閾值DIns= 30 m.

圖6 Ncoef 和DIns 的參數(shù)值選取

2.3 實(shí)驗(yàn)結(jié)果及分析

分別將已存在的基于時(shí)間聚類（簡稱為ETC）算法［4］和基于分割聚類（簡稱為OC）算法［12］與本文提出的SPE 算法進(jìn)行比較，實(shí)驗(yàn)中利用舊金山出租車軌跡數(shù)據(jù)分別對(duì)OC 算法和ETC 算法進(jìn)行了多次測(cè)試，選擇最佳的參數(shù)值，其中OC 算法的分割系數(shù)為Ncut=3.0；ETC 算法的最短停留時(shí)間參數(shù)為Tmin= 210 s，最大空間范圍為Dmax= 130 m.

表3 給出了三種算法對(duì)隨機(jī)一條車輛軌跡提取停留點(diǎn)的結(jié)果.

表3 不同算法下的停留點(diǎn)提取表現(xiàn)

從表3 可以發(fā)現(xiàn)：ETC 算法的準(zhǔn)確率要高于另外兩種算法，主要因?yàn)樵撍惴ǖ淖疃掏Ａ魰r(shí)間Tmin的限定，能夠?qū)⑹致房诘哪切┒虝r(shí)間偽停留過濾，但會(huì)將短時(shí)間停留的停留點(diǎn)忽略，造成召回率較低；同時(shí)OC 算法的召回率要優(yōu)于另外兩種算法，因?yàn)榉指钏惴ú粫?huì)被停留時(shí)間所局限，能夠發(fā)現(xiàn)短時(shí)間停留的位置點(diǎn)，但該算法未將十字路口的偽停留進(jìn)行過濾，造成準(zhǔn)確率較低.

本文的SPE 算法在發(fā)現(xiàn)停留點(diǎn)上不會(huì)受停留時(shí)間長短的影響，又能過濾行車過程中被迫停留的偽停留點(diǎn)，故調(diào)和平均值相比另外兩種算法要高出很多，在車輛軌跡的停留點(diǎn)提取上有更好的實(shí)用性.

3 結(jié)語

本文首先深刻剖析行駛在路網(wǎng)之上的車輛軌跡特點(diǎn)，利用車輛軌跡進(jìn)行路網(wǎng)空間建模，從車輛用戶對(duì)某地感興趣的語義行為角度，提出基于語義行為的車輛軌跡停留點(diǎn)提取算法.該算法創(chuàng)新地提出不依賴真實(shí)路網(wǎng)約束的噪點(diǎn)剔除方法，有效地排除十字路口與立交橋等的干擾.此外，通過車輛軌跡分析車輛用戶移動(dòng)行為將是后期的研究方向.