一種基于軌跡特征劃分的交通軌跡數據分析方法

趙庶旭，屈睿濤，劉昌榮

(蘭州交通大學電子與信息工程學院，甘肅 蘭州 730070)

當前各類數據都處于極其膨脹的狀態，衍生出眾多的數據分析方法，且大都有較為成熟的結果，而在這些成熟結果的背后，數據劃分作為一個重要步驟，為其做出了很大的貢獻。

很多情況下，車輛的軌跡數據都是通過車載GPS裝置采集獲得，導致這些數據的空間位置任意分布。因此，要想對這些數據進行快速準確的研究，就需要先對數據空間進行劃分。面對交通軌跡數據劃分問題，出發點大都從其屬性方面進行研究，即從加速度、時間、轉角、起始位置點、經緯度等這些明顯特征點方面入手，并沒有考慮將特征點劃分與空間劃分相結合。因此，軌跡數據劃分效果還存在較大的優化空間。

基于特征點的交通軌跡數據劃分方法現已有多種，最終可歸為兩大類：軌跡點劃分、軌跡段劃分。而對于交通軌跡數據基于空間的劃分方法包括以下幾個：按屏幕像素劃分、按均勻網格劃分、按行政區域劃分和按照數據本身的屬性進行劃分[1]。文獻[2—6]主要描述了基于軌跡段的劃分。其中，文獻[2]按照最小描述邏輯對復雜的軌跡數據進行劃分，將軌跡劃分為軌跡段的形式，但造成了軌跡局部特征丟失的現象。文獻[4]借鑒文獻[3]提出的拐點檢測算法對文獻[2]進行了改進，從轉角方面入手，對軌跡數據進行了劃分，將整段軌跡劃分成更小片段來處理，同時也提高了軌跡聚類的精度，但未考慮軌跡數據的空間屬性。文獻[5—6]利用軌跡數據的位置與幾何特性對軌跡進行了切分，考慮了軌跡數據分布的空間屬性，但特征點較為單一，劃分效果并不理想。文獻[7—13]主要描述了基于軌跡點的劃分。其中，文獻[7—10]提出了基于起始點到終點位置點的軌跡數據分析方法，對城市移動軌跡模式進行了研究，用來揭示城市不同區域間的關系，考慮了區域和軌跡數據分布的聯系，提高了數據劃分的速度，但劃分點單一，遇到道路情況較為復雜時，劃分效果不明顯。文獻[11—13]將位置信息、時間信息、速度、加速度特征運用到軌跡數據劃分中，把這些特征歸為點來處理，形成簇，然后以可視化的形式展現出來。本文方法與其略有相似，但在特征點的尋找及點群的組建方面要優于以上方法。

基于此，本文充分考慮了軌跡數據分布的空間任意性，結合軌跡數據的位置關系，提出基于軌跡數據特征點與空間劃分相結合的劃分方法。將某一時間段內的軌跡數據與相應的道路路網進行匹配[14]，然后利用高效的α-Shapes去噪方法進行軌跡數據去噪，得到多個車輛軌跡關鍵點。在基于點的劃分方面，除軌跡數據原因特征點外，再提取車輛行駛軌跡的其他特征點，與其組成點群。在空間劃分方面，將道路緩沖區視為軌跡數據分布的空間，采用Voronoi方法對軌跡數據進行劃分。該方法提高了基于軌跡段劃分時因數據特征點單一，且未考慮軌跡數據的空間屬性而導致效果不明顯的缺陷，改善了空間劃分時，由于信息采樣不足而導致的信息不具代表性問題。將其應用于交通擁堵、交通規劃、出行方式建議等方面，收到了良好的效果。

1 軌跡數據預處理

1.1 道路信息獲取

交通軌跡數據維度較高，但是采集的原始的基于GPS的數據在一般情況下缺乏道路信息，需要通過一定的處理方法，獲取到原始GPS數據中的道路信息。

對于得到的原始數據，首先要根據已有的經緯度信息建立緩沖區，其次將原始數據與本文所建立的緩沖區進行相交，得到所在道路的信息。如圖1所示，本文利用淄博市張店區的魯山大道、魯泰大道和309國道在16：00—17：00時間段內的GPS數據，建立該路段的緩沖區后利用地圖匹配算法，把3條道路交匯處(由于交匯區域采集到的GPS數據較豐富，具有代表性)GPS點和路網數據匹配，從而得到圖1所示的GPS點在3條道路交匯處的分布結果，方便了后續工作的開展。

圖1 GPS點與道路緩沖區

1.2 數據去噪

由于從GPS裝置上獲取到的數據存在一定數量的噪聲，通過地圖匹配后，許多數據不一定會落到道路緩沖區內，因此在進行研究前要對這些數據進行去噪，避免造成誤差。本文采用α-Shapes算法對軌跡數據進行噪聲過濾[15-17]。

車輛在行駛過程中，時常出現變道、轉彎、超車等駕駛行為，同時，一些道路樞紐、立交橋、盤旋路及道路交叉口的路況大多為圓形，這些情況就造成車輛行駛路線多為彎曲路線，而α-Shapes算法去噪的原理主要是通過半徑圓的滾動來提取邊緣輪廓，能很好地適應以上描述的車輛行駛路線。因此在交通軌跡數據分析中，將α-Shapes算法應用在道路上的軌跡數據噪聲過濾問題上較為合適。

α-Shapes原理：一般情況下，設有一個離散的點集S，將一個半徑為α的圓在點集外滾動，α取合適的值時，這個圓所圍成的邊界線內的數據即為去噪后的數據，邊界外數據為剔除的數據(噪聲數據)。α-Shapes算法運算速度快，具有一定的自適應性，通過α值的調節可實現一定的過濾功能，可以將數據噪聲和部分小目標過濾掉。

在軌跡數據去噪中，對于邊界的確定，是由GPS點集S和α決定的。對于S，設其由n個GPS點組成，可以連接成n(n-1)/2條線，筆者在S中任意選取2個點P1、P2，繪制半徑為α的圓，圓心的確定根據測繪學中的求交法得到[18]。

令P1和P2的坐標分別為(x1,y1)、(x2,y2)，求圓心(x,y)，如下

(1)

對于α的取值，需要通過多次試驗，最終確定一個合適的值。當α足夠小時，每一個點就可以大致認為是邊界；而α足夠大時，則是S的凸包。筆者對α的取值進行了多次試驗，確定對于相對筆直路段，0.33 m較為符合，對于轉彎路段及道路交叉口，0.1 m較為理想，如圖2所示。

圖2 α-Shapes算法去噪對比

2 基于軌跡特征劃分的數據分析

2.1 軌跡特征點提取

軌跡的特征點包括起點和終點、明顯轉彎點和顯著停止點(運動停頓點)等。若軌跡是一條長直線段，則只需獲取其部分特征點。由于以上所述的特征點對于解決本文描述的問題還存在不足，因此，本文提出了較為全面的獲取軌跡特征點的方法，以更好地適應軌跡數據分布的空間任意性問題。一些軌跡的明顯特征點如圖3所示。

圖3 軌跡明顯特征點

2.1.1 軌跡特征點描述

軌跡T=(xi,yi,ti)，1≤i≤n，n≥2，其中xi和yi為空間坐標，ti為時間，則還需提取的軌跡特征如下。

(1) 最小轉角點：連續軌跡段的方向之間的最小角度，如圖4所示。

圖4 軌跡最小轉角

(2) 最短停留時間點：在大致相同的位置花費的最短停留時間，被視為重要的停留。

(3) 最短距離點：兩者連續的點，之間的距離連續低于其他連續點之間的距離，這兩個點被視為這條軌跡的最短距離點。

圖5 軌跡最短距離點

(4) 最大距離點：兩者連續的點，之間的距離連續大于其他連續點之間的距離，這兩個點被視為這條軌跡的最大距離點。

2.1.2 算法描述

編程采用Java語言，令C為軌跡特征點的集合，提取軌跡特征點的相關步驟算法描述如下：

step1 定義C={(x1，y1，t1)}；inti=1。

step2 intj=i+1。

step3 如果j>n，執行第九步；

否則結束。

step4 計算兩點間的空間距離。

step5 判斷兩點間空間距離是否大于最大距離，則令C=C∪{(xj,yj,tj)}，并執行第2步，否則結束。

step6 執行k=j+1循環，并判斷兩點間的空間距離是否大于最小距離，是則執行第2步；否則結束循環，進行第9步。

step7 計算最短停留時間。

step8 計算最小轉角。

step9 添加所得點到C集合，令C=C∪{(xj,yj,tj)}。

step10 返回C。

通過該方法，可以得到軌跡特征點，將這些特征點與原有軌跡數據特征點相結合，為后續的軌跡數據空間劃分作輔助。

2.2 Voronoi劃分

2.2.1 軌跡點分類

對得到的軌跡特征點進行一個簡單的分類，本文采取的方法是提取點群的質心(平均點)，計算點之間的歐氏距離，距離近的點組成點群，質心點作為Voronoi圖細分的生成元。Voronoi圖細分是指通過添加三角形的方式對一個網絡的三角形進行細分，這些新添加的三角形可以偏移到一個新的位置。本文利用歐氏距離計算方法對軌跡點進行分組

(2)

通過歐氏距離的計算，將距離相近的點分為一組，圖6所示為省級道路與鄉鎮道路上軌跡特征點的分布位置。

圖6 特征點分布

2.2.2 Voronoi劃分定義

Voronoi圖[19-22]是計算幾何領域中非常重要的一種結構，由俄羅斯科學家M.G.Voronoi提出，針對平面內n個離散的點，將平面分成多個區域，所得區域就是本文所要劃分軌跡數據最近點的集合。

設P={P1,P2,…,Pn}?R3為三維歐氏空間內的n個點,d(P,Pi)為P和Pi間的歐氏距離，將由

所給出的對空間的分割稱為以P={P1,P2,…,Pn}?R3為空間點集的Voronoi圖,V(Pi)(i=1,2,…,n)為Voronoi圖的晶胞，Pi(i=1,2,…,n)為Voronoi圖的母點(生成元)，如圖7所示。

圖7 Voronoi圖

2.2.3 Voronoi劃分

進行Voronoi劃分之前，本文首先對特征點數據進行處理，找到特征點群的質心點，然后按照質心點的位置進行Voronoi劃分，其中圓點為母點，母點四周的多邊形為Voronoi劃分的區域，即為劃分后軌跡數據點的集合。

3 基于GPS數據的實例驗證

為進一步說明本文方法，在共同依托項目的城市交通數據可視化平臺上進行驗證[23]，將前文提出的算法與山東省淄博市的出租車GPS數據相結合，然后在與當地路網數據匹配的基礎上，進行實際GPS數據的實例驗證。筆者利用張店區的北京路、魯泰大道、南京路、公園北路、中潤大道的主要車輛行駛路段篩選出16：00—17：00點具有代表性的382條出租車運行軌跡，通過特征提取方法得到了6592個特征點數據進行驗證。首先得到特征點質心分布效果圖，如圖8所示。

圖8 實際特征質心點

3.1 多特征軌跡數據劃分方法的優勢

為說明多特征軌跡數據劃分方法的優越性，筆者利用淄博市張店區(北京路、魯泰大道、南京路、公園北路、中潤大道)的主要車輛行駛路段篩選出16：00—17：00點的數據，利用其他方法進行了試驗，并與本文提出的方法進行了對比，結果見表1。

表1 劃分效果對比

注：空間分布適應性是指劃分后的匹配數據與原始隨機分布數據之間的比例。

從表1中數據可以看出，本文方法在數據劃分點上面明顯多于其他方法，可以很好地適應數據空間分布隨意性的特性。

3.2 實物驗證

為更好地說明多特征劃分方法在適應空間分布隨意性上的優勢，本文選擇表1中基于轉角的數據劃分方法進行驗證，對青銀高速、淄博西樞紐立交、濱萊高速、原山大道、魯泰大道、中潤大道、世紀路，以及周圍車輛行駛較多的縣道、鄉鎮道路的16：00—17：00的軌跡數據進行劃分，并利用共同依托項目的城市交通數據可視化平臺進行驗證，如圖9所示。

圖9 多特征劃分下主要路段GPS數據劃分

從劃分效果圖可以看出，多特征劃分效果明顯優于其他劃分的效果，該方法較好地克服了數據空間分布隨機性問題。

4 結 語

本文對軌跡數據按照其位置關系進行車輛行駛特征點的提取，利用α-Shapes去噪算法，對提取到的特征點按照其分布的幾何相關性，進行簡單分組并形成點群，且利用其空間分布的屬性，按照Voronoi多邊形進行分割，克服了軌跡數據空間分布的任意性缺陷，提高了軌跡數據劃分的效率。最后利用山東省淄博市出租車軌跡數據，依托本課題項目城市交通數據可視化平臺進行實例驗證，取得了良好的效果。后期將會在動態數據分析及可視化方面進行深入研究。