基于GPS軌跡的城市擁堵區域挖掘與分析

武興業，吳 悅，岳曉冬

(上海大學 計算機工程與科學學院，上海 200444)

基于GPS軌跡的城市擁堵區域挖掘與分析

武興業，吳 悅，岳曉冬

(上海大學 計算機工程與科學學院，上海 200444)

隨著世界城市化進程的發展，以及機動車保有量的飛速增長，交通擁堵問題日益嚴峻，城市道路交通擁堵問題已成為研究熱點。傳統的擁堵檢測手段一般采用視頻監控或傳感器檢測，雖然可以實時有效地反映擁堵狀態，但無法挖掘城市擁堵規律，更無法有效分析擁堵原因和擁堵影響。文中提出基于DENCLUE的擁堵區域挖掘算法，對車輛GPS數據預處理，計算出擁堵點，然后對擁堵點進行DENCLUE聚類來確定擁堵區域。實驗證明，該算法可以有效找出擁堵區域，并將擁堵劃分等級，得到城市區域擁堵狀態，反映城市擁堵情況。此外，使用斯皮爾曼等級相關系數計算區域間擁堵程度相關系數，結合實際地理位置分析擁堵區域的擁堵原因及影響。

擁堵點；擁堵區域挖掘；DENCLUE；相關系數；擁堵分析

0 引 言

隨著世界城市化進程的發展，城市交通問題日益嚴重和普遍，而城市交通與城市規劃互相影響，合理的城市規劃會促進交通狀況，而錯誤的城市規劃將導致嚴重的交通問題。因此，需要將城市交通與城市規劃有效結合以促進問題的解決[1]。目前我國正處于高速城市化時期，城市和城市交通的發展正處于挑戰和機遇并存的關鍵歷史階段，同時也是交通治理轉型的關鍵時期。像北京這種大城市的交通問題是不可避免的，雖然修建公路和地鐵可以緩解，但并不是長久之計[2]。智能交通系統(Intelligent Transportation System，ITS)[3]是將先進的科學技術(信息技術、數據通信技術、傳感器技術、電子控制技術、數據處理技術等)有效地綜合運用于地面運輸管理體系，加強車輛、道路、使用者三者之間的聯系，從而形成一種保障安全、提高效率、改善環境、節約能源的綜合運輸系統，是當前研究與應用的熱點。所以大城市都大力發展ITS作為城市交通問題的重要解決途徑之一。其中，大規模交通數據管理、整合和挖掘是一項關鍵技術。大數據時代，智能交通系統已經積累了巨量而復雜的道路交通數據信息，比如車輛的GPS信息，這些交通數據信息為智能交通的研究提供了重要的數據基礎。

數據挖掘作為目前最強有力的一種數據分析工具，為道路交通數據的處理提供了新的分析手段，如何設計有效的數據挖掘算法將特定的交通規律挖掘出來是當前智能交通數據挖掘研究的關鍵。城市擁堵區域挖掘是智能交通領域研究的一個關鍵問題，具有非常重要的現實意義。通過空間數據挖掘技術挖掘出擁堵區域，分析擁堵區域之間的相關性，就能發現擁堵原因，給城市建設提供科學依據，解決城市發展中的很多問題。

文中使用北京10 357輛出租車一周的GPS軌跡數據做實驗，提出一種基于DENCLUE擁堵區域挖掘算法，和一套用于分析擁堵區域原因及影響的方法。

1 相關工作

1.1 城市規劃

微軟研究院鄭宇博士等，通過分析和融合城市中的各種大數據，實現了一系列關于智能交通、城市規劃的實際案例。比如文獻[4]利用高速和環路等主干道將城市分割成區域，然后分析大規模車流軌跡數據在不同區域之間行駛的一些特征，便可找到連通性較差的區域對，從而發掘現有城市道路網的不足之處。通過對比連續兩年的檢測結果，可以驗證一些已經設施的規劃(如新建道路和地鐵)是否真的有效。

1.2 交通異常分析

文獻[5-8]通過分析北京3萬多輛出租車的軌跡來發現城市中的異常事件。其主要思想是當異常事件發生時，附近的交通流將出現一定程度的紊亂。文獻[6]試圖用具體的交通線路來進一步解釋異常出現的原因。有時候，兩個區域之間出現了交通流異常，但問題本身可能并不在這兩個區域，而在于遠處的車流必須通過這兩個區域前往另一個目的地，這些車流才是問題的根源。文獻[7]根據司機們路線選擇方式的改變來捕捉交通異常，并進一步從相關的微博中提取關鍵詞來解釋異常的原因，如婚博會、道路坍塌等。

2 基于DENCLUE的擁堵區域挖掘算法

2.1 擁堵點

2.1.1 擁堵點的基本定義

2.1.2 擁堵點的計算方法

(1)根據GPS數據集和城市交通狀況確定Sthreshold、tthreshold、vthreshold和n。

2.2 DENCLUE聚類算法

2.2.1 密度聚類算法

聚類是按照屬性值把一組對象劃分成一系列有意義的子集的描述性任務。它的目的是揭示樣本點之間最本質的“抱團”性質。密度聚類算法根據數據周圍密度的不斷增長聚類，將密度足夠高的區域內數據對象劃分為簇，具有快速識別任意形狀簇和處理數據對象中的噪聲點的優點[10]。DENCLUE[11]就是一種典型的密度聚類算法。

2.2.2 DENCLUE

密度估計是基于密度的聚類算法的核心問題，DENCLUE就是一種泛化的基于核密度估計的聚類算法。DENCLUE(DENsity-based CLUstEring，基于密度的聚類)是Hinneburg等提出的，是一種基于一組密度分布函數的聚類算法。其核心思想是每一個空間數據點通過事先影響函數對空間產生影響，影響值可以疊加，從而在空間形成一曲面，曲面的局部極大值點為一密度吸引子，該吸引子的吸引域形成一類[12]。將DENCLUE應用于交通數據挖掘，密度吸引子為擁堵區域的中心，吸引域為擁堵區域。

2.2.3 DENCLUE的一些基本定義

定義1：基本影響函數。

(1)方波影響函數。

(2)高斯影響函數。

定義2：局部密度函數。

定義4：密度吸引子。

定義5：中心確定的聚類。

定義6：任意形狀的聚類。

對于密度吸引子集合X，如果存在子集C?D，使得：

則稱C為由X確定的(關于ξ，σ的)任意形狀聚類。

2.2.4 爬山算法

2.3 擁堵區域挖掘算法步驟

1)軌跡預處理[13]。

由于采集到的GPS數據極易受到噪聲、缺失值和不一致數據的侵擾，并且低質量的數據將導致低質量的挖掘結果，所以必須對GPS數據進行軌跡預處理。數據預處理的技術有很多，比如數據清理、數據過濾、數據集成、數據變換等，文中主要采用以下兩種數據預處理技術：

(1)數據清理：GPS設備剛啟動或故障等原因會造成采集到大量為0的數據，而且GPS定位的誤差會導致在某一時刻定位錯誤后，在接下來的整個時間段采集的數據都是錯誤的。對于這兩種數據完全刪除。

(2)數據過濾：GPS傳感器的噪聲會造成采集到的個別數據存在誤差，稱為異常值(outliers)。對于個別異常值采用中值濾波器(Median Filters)進行過濾(或者糾正)，即對于檢測到的異常值，取其附近n個點的中值替換該異常值。

2)計算擁堵點。

根據過濾后的數據計算擁堵點，得到候選擁堵點GPS數據。

3)擁堵點聚類。

(1)對候選擁堵點GPS數據D以2σ(σ為設定的寬度閾值)為寬度進行網格劃分，決定非空的網格集Cp，每個網格c中數據數記為Nc。

4)擁堵區域后處理。

3 擁堵區域相關性分析

3.1 相關系數計算方法的選擇

相關性指標的選擇對相關性分析的結果有重要影響[14-15]。線性相關系數有皮爾遜積矩相關系數、斯皮爾曼等級相關系數、肯德爾等級相關系數等幾種，其中斯皮爾曼等級相關系數適用范圍最廣。

文中分析的是兩個區域中車流量隨時間變化的相關性，對GPS數據以10 min為間隔進行抽樣，得到的是離散數據。當交通出現擁堵時采集到的數據量會出現尖峰，但區域間可能存在軌跡模式[16]，并且車流量也是相關的。如果使用皮爾遜積矩相關系數在交通擁堵時會因尖峰導致相關性減弱，從而削弱可能存在的軌跡模式。而斯皮爾曼等級相關系數對數據條件的要求不是很嚴格，只要兩個變量的觀測值是成對的等級評定數據，或者是由連續變量觀測數據轉化得到的等級數據，不論兩個變量的總體分布形態、樣本容量的大小如何，都可以用斯皮爾曼等級相關來進行研究。所以對于文中的擁堵區域相關程度的相關系數計算，應當使用斯皮爾曼等級相關系數。

3.2 斯皮爾曼等級相關系數

斯皮爾曼等級相關(Spearman’s correlation coefficient for ranked data)主要用于解決稱名數據和順序數據相關的問題。適用于兩列變量，而且具有等級變量性質具有線性關系的資料。由英國心理學家、統計學家斯皮爾曼根據積差相關的概念推導而來，一些人把斯皮爾曼等級相關看作積差相關的特殊形式。

在統計學中，斯皮爾曼等級相關系數以Charles Spearman命名，并經常用希臘字母ρ表示。斯皮爾曼等級相關系數用來估計兩個變量X,Y之間的相關性。假設兩個隨機變量分別為X,Y，它們的元素個數均為n，取兩個隨機變量的第i(1≤i≤n)個值，分別用xi,yi表示。對X,Y進行排序(同時為升序或降序)，得到有序集合X,Y，將有序集合X,Y中的元素對應相減得到一個差分集合D，其中di=xi-yi,1≤i≤n，從而可以使用D計算隨機變量X,Y之間的斯皮爾曼等級相關系數，公式為：

3.3 相關性分析方法

在城市交通中，當一個區域為嚴重擁堵區域時，必定會對周圍區域產生影響。對于相關性較大的擁堵區域與非擁堵區域，應當解決擁堵區域的問題，以避免或緩解其對周圍非擁堵區域的影響。而擁堵區域擁堵的原因可能是兩個擁堵區域互相影響的結果，此時應根據它們的擁堵程度相關性來分析擁堵原因，并提出解決擁堵的方案。

根據斯皮爾曼等級相關系數公式計算出擁堵區域的擁堵程度相關系數；按照三個等級評價擁堵區域之間的相關性，最后集合擁堵區域的實際地理位置做擁堵分析。

4 實驗結果與分析

4.1 擁堵區域挖掘實驗

為了驗證基于DENCLUE的擁堵區域挖掘算法的效果，使用北京市10 357輛出租車一周的GPS軌跡數據作為實驗數據。實驗代碼使用Java語言進行編寫。由于需要使用百度地圖對結果進行展示，實驗需要將原始數據轉換為百度地圖格式的數據。

當車輛經過一個區域的平均速度較小時，認為此區域擁堵，以擁堵點記錄。每個擁堵點對附近擁堵點都有一定的影響，擁堵點的影響函數使用高斯函數進行計算，因此DENCLUE算法中所研究的點可以描述為擁堵點，維數是二維的，即經度和緯度。在尋找高密度網格時，ξ作為擁堵點的網格密度閾值，當網格中擁堵點數量Nc≥ξ時，形成高密度網格，說明附近擁堵點多，可聚類為擁堵區域；如果Nc<ξ，說明擁堵點稀少，不足以聚類構成擁堵區域。將高密度網格連接起來聚類，以爬山算法確定擁堵區域中心點，就得到了如圖1所示的擁堵區域分布圖。

圖1使用百度地圖提供的添加熱力圖API繪制，熱力區域標記黑色的強度區分擁堵程度。對于挖掘出來的擁堵區域，根據擁堵區域的擁堵點數目對擁堵程度進行劃分，越擁堵的區域，擁堵區域的擁堵點數目越多。圖1中根據黑色標記強度的減弱，區域擁堵程度依次遞減，沒標記的地方代表不擁堵或者沒有相關數據。可以看到有少量區域擁堵等級高，為出租車經常發生擁堵的區域。對于這些出租車經常發生擁堵的區域，找出它們的擁堵原因很重要，所以要做區域相關性分析。

圖1 基于DENCLUE的擁堵區域挖掘算法結果

4.2 相關性和擁堵影響分析實驗

一般車輛的活動時間從早上6點到晚上23點為高峰，而晚上23點到早上6點的活動較少，這也符合人們的生活規律，所以實驗選取早上6點到晚上23點的數據作為實驗數據。為了分析區域之間的相關性，以區域之間數據量、平均速度和擁堵密度作為特征進行相關性分析。實驗以10 min為時間間隔(每小時6次抽樣)進行抽樣，樣本為該區域每個時間段計算數據量、平均速度和擁堵密度的加權平均值得到的擁堵程度。根據抽樣得到的擁堵程度樣本數據，求得擁堵區域之間擁堵程度的斯皮爾曼等級相關系數，然后結合區域的實際位置進行分析，實驗如下：

這組實驗選取的是地鐵4號線辟才胡同與靈境胡同附近區域。經過擁堵區域挖掘后，可以得到如圖2

圖2 擁堵區域熱力圖

所示的熱力圖，位置詳情如圖3所示。圖2標記了1、2兩個區域，1號區域為擁堵嚴重且擁堵范圍大的區域，2號區域為十字路口擁堵區域。

圖3 擁堵區域放大詳情圖

根據擁堵區域挖掘結果，可以得到兩個區域的擁堵狀態，其中經度和緯度為密度吸引子的位置，平均速度由車輛總體采樣數據計算得到，密度吸引子密度由高斯密度函數計算得出，擁堵密度由區域的擁堵點計算得到。

為了分析兩個區域的擁堵原因和擁堵影響，對每個區域數據以10 min為時間間隔進行抽樣，將不同時間段的數據量、擁堵密度、平均速度作為擁堵程度的判定條件繪制圖4和5。實驗中的擁堵程度主要由數據量決定，當擁堵密度非常大、平均速度非常小時才考慮其影響。

由圖4和圖5可以明顯看出，從13:00開始，直到20:00，兩個區域的擁堵程度都是比其他時間段嚴重的。經過計算，兩區域整體的斯皮爾曼等級相關系數高達0.821 6，說明兩區域具有很強的擁堵相關性；兩區域從13:00至20:00擁堵程度的斯皮爾曼等級相關系數更是高達0.953 7，說明兩區域在高度擁堵時的擁堵程度相關性極強，兩區域的擁堵會互相影響。由圖3可知，2號區域有很多飯店，此區域是個娛樂區域，這造成了車輛在這里停留過多，導致嚴重擁堵。而兩區域的擁堵程度具有高度相關性，尤其是擁堵時間段，也就是說兩區域擁堵規律高度相關，所以1號擁堵區域的擁堵會直接導致2號十字路口的擁堵。為防止交通惡化，應當在擁堵嚴重的時間段加強交通管制，或者對異常擁堵區域進行重新規劃，將擁堵代價降到最低。

圖4 1號區域分時段擁堵程度抽樣圖

圖5 2號區域分時段擁堵程度抽樣圖

5 結束語

文中提出了基于DENCLUE的擁堵區域挖掘算法。首先將GPS軌跡數據進行預處理，以最小化實驗的誤差；然后通過計算擁堵點，得到候選擁堵點GPS數據；最后使用DENCLUE聚類算法對候選擁堵點GPS數據進行聚類。此算法可以有效找出交通擁堵區域，并對擁堵狀態進行分級。再對嚴重擁堵區域進行了相關性和擁堵原因及影響分析。實驗結果表明，文中提出的擁堵區域挖掘與分析方法可以有效檢測擁堵區域，查明擁堵原因和影響，為城市規劃提供建議。

[1] 王 荻,張冠增.城市軌道交通規劃與城市規劃的互動關系[J].城市軌道交通研究,2007,10(2):1-4.

[2] Li Fengyi,Wang Bing.The death and the life of Beijing-the history,present situation and strategy of urban planning in Beijing[J].Canadian Social Science,2011,7(3):198-201.

[3] Luo Qi.Research on intelligent transportation system technologies and applications[C]//Proc of the workshop on power electronics & intelligent transportation system.[s.l.]:IEEE,2008:529-531.

[4] Zheng Y,Liu Y,Yuan J,et al.Urban computing with taxicabs[C]//Proceedings of the 13th international conference on ubiquitous computing.[s.l.]:ACM,2011:89-98.

[5] Liu Wei,Zheng Yu,Chawla S,et al.Discovering spatio-temporal causal interactions in traffic data streams[C]//Proceedings of the 17th ACM SIGKDD international conference on knowledge discovery and data mining.San Diego,CA,USA:ACM,2011:1010-1018.

[6] Pang L X,Chawla S,Liu W,et al.On mining anomalous patterns in road traffic streams[C]//Proceedings of international conference on advanced data mining and applications.Beijing,China:[s.n.],2011:110-118.

[7] Chawla S,Zheng Y,Hu J.Inferring the root cause in road traffic anomalies[C]//Proc of 12th international conference on data mining.[s.l.]:IEEE,2012:141-150.

[8] Pan B,Zheng Y,Wilkie D,et al.Crowd sensing of traffic anomalies based on human mobility and social media[C]//Proceedings of the 21st ACM SIGSPATIAL international conference on advances in geographic information systems.[s.l.]:ACM,2013:344-353.

[9] Zheng Y,Zhang L,Xie X,et al.Mining interesting locations and travel sequences from GPS trajectories[C]//Proc of international conference on world wide web.[s.l.]:[s.n.],2009:791-800.

[10] Tran T N,Drab K,Daszykowski M.Revised DBSCAN algorithm to cluster data with dense adjacent clusters[J].Chemometrics & Intelligent Laboratory Systems,2013,120(2):92-96.

[11] Hinneburg A,Keim D A.An efficient approach to clustering in large multimedia databases with noise[C]//Proceedings of the 4th international conference on knowledge discovery and data mining.New York,USA:[s.n.],1998:58-65.

[12] 張志兵.空間數據挖掘關鍵技術研究[D].武漢:華中科技大學,2004.

[13] Zheng Y.Computing with spatial trajectories[M]//Computing with spatial trajectories.[s.l.]:Springer,2011.

[14] 張堯庭.我們應該選用什么樣的相關性指標?[J].統計研究,2002(9):41-44.

[15] 李秀敏,江衛華.相關系數與相關性度量[J].數學的實踐與認識,2006,36(12):188-192.

[16] Giannotti F,Nanni M,Pinelli F,et al.Trajectory pattern mining[C]//Proceedings of the 13th ACM SIGKDD international conference on knowledge discovery and data mining.[s.l.]:ACM,2007:330-339.

Mining and Analysis of Urban Congestion Region Based on GPS Trajectory

WU Xing-ye，WU Yue，YUE Xiao-dong

(School of Computer Engineering and Science,Shanghai University,Shanghai 200444,China)

With the development of world urbanization,and the rapid growth of motor vehicle,traffic congestion problem is increasingly serious and has become a hot research topic.Traditional congestion detection generally uses the video surveillance or sensors,although they can effectively reflect the real-time congestion,but can’t mine the law of the urban congestion,even fail to analyze the congestion correlation between urban areas.In this paper,the congestion region mining algorithm is proposed based on DENCLUE,first preprocessing the urban taxi GPS data,calculation of the congestion point,then clustering them by DENCLUE to determine the congestion area.It is shown in the experiment that the algorithm can effectively find out congestion areas and grade them,getting the congestion state of the city,reflection of urban congestion.In addition,Spearman rank correlation coefficient is used to calculate the flow of car correlation coefficient between regions,analysis of the congestion causes and effects of severe congestion regions combined with the actual location.

congestion point;congestion region mining;DENCLUE;correlation coefficient;congestion analysis

2015-09-14

2015-12-17

時間：2016-06-22

國家自然科學基金面上項目(61573235)

武興業(1991-)，男，碩士，研究方向為數據挖掘；吳 悅，博士，教授，研究方向為智能信息處理。

http://www.cnki.net/kcms/detail/61.1450.TP.20160622.0842.002.html

TP391.41

A

1673-629X(2016)07-0116-06

10.3969/j.issn.1673-629X.2016.07.025