基于DBSCAN算法的城市交通擁堵區(qū)域發(fā)現(xiàn)

劉暢　李治軍　姜守旭

摘 要：現(xiàn)階段我國車輛的數(shù)目不斷增加，這必然會導(dǎo)致現(xiàn)有的交通條件等不再能夠滿足現(xiàn)在的交通狀況。因時空數(shù)據(jù)蘊(yùn)含豐富的信息，本文將通過分析車輛的時空軌跡數(shù)據(jù)，即GPS軌跡數(shù)據(jù)，并利用DBSCAN算法挖掘出城市中交通最擁堵的城市區(qū)域，并將得到的結(jié)果映射到城市路網(wǎng)上，使得相關(guān)部門能夠清楚的了解問題，并制定一系列相應(yīng)措施，如調(diào)整道路規(guī)劃等，保證該區(qū)域的問題能夠迅速得到解決。本文的實(shí)驗(yàn)結(jié)果清晰地標(biāo)明了城市中具體的擁堵區(qū)域，本文下一步將根據(jù)城市擁堵區(qū)域的發(fā)現(xiàn)結(jié)果預(yù)測區(qū)域的下一次擁堵的時間。

關(guān)鍵詞 ： DBSCAN算法；時空軌跡數(shù)據(jù)；城市擁堵區(qū)域

中圖法分類號： TP39 文獻(xiàn)標(biāo)識碼： A

Discovery of Heavy Traffic Areas based on DBSCAN Algorithm

LIU Chang， LI Zhijun， JIANG Shouxu

（School of Computer Science and Technology， Harbin Institute of Technology， Harbin 150001， China）

Abstract： At present， the number of vehicles is increasing in our country. This will inevitably cause that the existing road and so on would no longer able to meet the current traffic conditions. Because the spatio-temporal data contain rich information， this paper will analyze the GPS data of the vehicle. This paper will mining the heaviest traffic congestion areas in a city by using the DBSCAN algorithm， and the mining result will be mapped to the city road network so that the relevant departments can clearly understand where the problems are. The departments also can develop a series of measures to solve those problems， such as adjusting the road planning and so on. This will ensure that the problems can be resolved quickly， and the experiment results of this paper clearly indicate the specific congestion areas in a city. The next work is the time prediction of congestion areas.

Key words： DBSCAN Algorithm； Spatio-temporal Data； Heavy Traffic Area

0 引 言

我國現(xiàn)階段經(jīng)濟(jì)迅速發(fā)展，私家車、公交車、出租車等的數(shù)量正與日激增，這一態(tài)勢必將導(dǎo)致現(xiàn)有的部分地區(qū)交通道路已經(jīng)難以滿足不斷增長的運(yùn)營與運(yùn)力需求，所以如何做好城市交通道路規(guī)劃即已歸作城市建設(shè)中需要重點(diǎn)解決的關(guān)鍵問題之一[1]，一個科學(xué)、合理的交通道路規(guī)劃則是建造一座現(xiàn)代智能城市的基礎(chǔ)必備技術(shù)手段。

時空軌跡數(shù)據(jù)[2]蘊(yùn)含非常豐富的地理信息、語義信息，連續(xù)的軌跡數(shù)據(jù)還能反映出其移動規(guī)律以及相應(yīng)變化。通過相同種類大量不同對象的軌跡數(shù)據(jù)，規(guī)劃團(tuán)隊(duì)還可以迅速了解某一種類對象的特點(diǎn)特性。而當(dāng)規(guī)劃者使用城市中的車輛軌跡數(shù)據(jù)時，這些數(shù)據(jù)的動態(tài)分布則能實(shí)時有效地反映城市的交通變化[3]，這就為城市交通道路規(guī)劃提供了極其重要的信息，并使得城市的交通道路能夠進(jìn)一步做出相應(yīng)的調(diào)整。本文的目的即是找出潛在不能滿足交通需求的區(qū)域，并且因?yàn)槌鲎廛嚨慕煌〝?shù)據(jù)在一定程度上更能代表全市的交通狀況，而且比較容易實(shí)現(xiàn)采集，由此本文所用的數(shù)據(jù)即為北京市12 000輛出租車一個月的GPS數(shù)據(jù)，該數(shù)據(jù)存儲在TXT文件中[4]。

1 本文所采用的GPS數(shù)據(jù)介紹

本文所采用的GPS數(shù)據(jù)采集頻率約為一分鐘，解壓之前為13.1G，解壓之后約為50G[4]。其具體內(nèi)容主要如下：有車輛標(biāo)識，由6位數(shù)字字符串組成；觸發(fā)事件，對應(yīng)為一位整數(shù)，共有5種情況，其中“0”代表“空車”，“1” 代表“載客”，“2”代表“設(shè)防”，“3”代表“撤防”，“4”代表“其他”；運(yùn)營狀態(tài)，共5種情況，其中“0”代表“空車”，“1” 代表“載客”，“2”代表“駐車”，“3”代表“停運(yùn)”，“4”代表“其他”；GPS時間，是一個數(shù)字字符串，代表年月日時分秒；GPS經(jīng)度，為浮點(diǎn)數(shù)，小數(shù)點(diǎn)后保留6位有效數(shù)字；GPS緯度，也為浮點(diǎn)數(shù)，小數(shù)點(diǎn)后保留6位有效數(shù)字；GPS速度、GPS方向，其對應(yīng)的單位為角度單位“度”；GPS狀態(tài)，共2種狀態(tài)，分別為“有效”、“無效”。各項(xiàng)數(shù)據(jù)之間以逗號相隔，一組GPS數(shù)據(jù)以“回車符”與“換行符”結(jié)束。

首先，對GPS數(shù)據(jù)文件中的數(shù)據(jù)進(jìn)行時間上的分割，設(shè)置時間片為一分鐘，將每一分鐘采樣的出租車數(shù)據(jù)存放于一個txt文件中，并以采集數(shù)據(jù)的發(fā)生時刻命名該文件，每個文件大小約為1 400KB左右。數(shù)據(jù)采樣的時間約為一分鐘，但該頻率并不確定，對數(shù)據(jù)進(jìn)行時間片處理后，每個文件中均會存在同一輛出租車重復(fù)數(shù)據(jù)采樣的問題，此時需對重復(fù)數(shù)據(jù)展開進(jìn)一步處理，即去掉對同一輛車的重復(fù)采樣數(shù)據(jù)，處理完成的數(shù)據(jù)文件仍儲存在txt文件中。

2 基于DBSCAN算法的城市擁堵區(qū)域發(fā)現(xiàn)

2.1 DBSCAN算法相關(guān)定義

針對每個時間片上的數(shù)據(jù)，本文進(jìn)行基于密度聚類（DBSCAN），也就是以數(shù)據(jù)集在空間分布上的稠密程度為依據(jù)進(jìn)行聚類，每個時間片上的群體則可稱為快照集群。文中，DBSCAN算法中涉及的一些定義[5]現(xiàn)表述如下：

R區(qū)域：以數(shù)據(jù)對象為圓心、R為半徑的圓稱為數(shù)據(jù)對象的R區(qū)域，半徑R即為數(shù)據(jù)對象之間距離的最大閾值，本文中計算兩數(shù)據(jù)對象a、b時使用以下公式：

，此處的x、y為緯度和經(jīng)度的弧度數(shù)。通過將兩數(shù)據(jù)對象由經(jīng)緯度坐標(biāo)轉(zhuǎn)換到直角坐標(biāo)系中，求出兩數(shù)據(jù)對象相對地心的弧長，即為對象a、b的距離[6] （本文中地球半徑r取為6 378 137.0米）；

數(shù)量閾值Min：數(shù)據(jù)對象R領(lǐng)域中包含其他數(shù)據(jù)對象的數(shù)量最小閾值為數(shù)量閾值Min；

核心數(shù)據(jù)對象：若數(shù)據(jù)對象的R領(lǐng)域中所包含的其他數(shù)據(jù)對象數(shù)量超過閾值Min，則稱該數(shù)據(jù)對象為核心數(shù)據(jù)對象；

直接密度可達(dá)：一個核心數(shù)據(jù)對象a的R區(qū)域中所有其他的數(shù)據(jù)對象…，數(shù)據(jù)對象…從該核心數(shù)據(jù)對象a直接密度可達(dá)；

密度可達(dá)：在所有數(shù)據(jù)對象中，若存在一串?dāng)?shù)據(jù)對象為a，…，c，并且有對象從對象a直接密度可達(dá)，對于，對象從直接密度可達(dá)，對象c從對象直接密度可達(dá)，則對象c從對象a密度可達(dá)；

密度相連：在同一個密度可達(dá)數(shù)據(jù)集合中的所有數(shù)據(jù)對象，稱作是相互密度相連的；

簇ID：將不同的密度相連的數(shù)據(jù)集合中的數(shù)據(jù)對象用簇ID來標(biāo)記，其中簇ID為-1代表數(shù)據(jù)對象為噪音點(diǎn)，即該數(shù)據(jù)對象沒有滿足密度要求，不屬于任何簇。

2.2 DBSCAN算法描述

首先，掃描整個數(shù)據(jù)集，找到任意一個核心數(shù)據(jù)對象并針對該核心對象進(jìn)行擴(kuò)充。擴(kuò)充的方法是尋找從該核心數(shù)據(jù)對象出發(fā)的所有密度相連的數(shù)據(jù)對象。遍歷該核心數(shù)據(jù)對象的R區(qū)域內(nèi)的所有核心數(shù)據(jù)對象（因?yàn)檫吔鐢?shù)據(jù)對象無法擴(kuò)充，故只遍歷所有核心數(shù)據(jù)對象），尋找與這些數(shù)據(jù)對象密度相連的數(shù)據(jù)對象并將密度相連的數(shù)據(jù)對象標(biāo)記為相同的簇ID，直到?jīng)]有可以擴(kuò)充的數(shù)據(jù)對象為止，最后聚類成簇的邊界點(diǎn)都是非核心數(shù)據(jù)對象。其次，重新掃描未被訪問過的數(shù)據(jù)集，尋找沒有被標(biāo)記的核心數(shù)據(jù)對象，并重復(fù)第一步的步驟，對該核心數(shù)據(jù)對象進(jìn)行擴(kuò)充。以此類推，直至數(shù)據(jù)集中所有的GPS數(shù)據(jù)對象均被訪問過，數(shù)據(jù)集中沒有包含在任何簇中的數(shù)據(jù)點(diǎn)則構(gòu)成噪音點(diǎn)，將其簇ID置為-1。

該算法流程如下：

算法——各時間片GPS數(shù)據(jù)文件基于密度聚類

輸入：時間片分割后的GPS數(shù)據(jù)文件，半徑R，數(shù)量閾值Min；

輸出：所有生成的達(dá)到密度要求的簇。

（1） 初始化文件中每個數(shù)據(jù)對象所屬的簇ID為-1，即不屬于任何簇，數(shù)據(jù)對象是否被訪問的標(biāo)記參數(shù)isVisited設(shè)置為false

（2） 初始化半徑R以及數(shù)量閾值Min

（3） n為文件中數(shù)據(jù)點(diǎn)個數(shù)

（4） For i從1到n

（5） If GPS點(diǎn)i的R區(qū)域內(nèi)的GPS數(shù)據(jù)點(diǎn)數(shù)大于等于閾值Min

（6） 標(biāo)記點(diǎn)i為核心數(shù)據(jù)對象

（7） End if

（8） End for

（9） 初始化簇ID=0

（10） For i從1到n

（11） If GPS點(diǎn)i參數(shù)isVisited=false && GPS點(diǎn)i是核心數(shù)據(jù)對象

（12） 設(shè)置GPS點(diǎn)i所屬簇ID

（13） 設(shè)置GPS點(diǎn)i已被訪問過，即將 isVisited置為true

（14） While GPS點(diǎn)i的R區(qū)域內(nèi)存在未被訪問的數(shù)據(jù)對象

（15） 設(shè)置該數(shù)據(jù)對象已被訪問過， isVisited = true

（16） 設(shè)置該對象所屬簇ID = GPS點(diǎn)i的簇ID

（17） If 該點(diǎn)為核心數(shù)據(jù)對象

（18） 遞歸遍歷其R區(qū)域中的其他未被訪問的GPS點(diǎn)

（19） End if

（20） End while

（21） 簇ID自增1

（22） End if

（23） End for

DBSCAN算法的優(yōu)點(diǎn)是無需限定其將要生成的簇的個數(shù)，并能發(fā)現(xiàn)數(shù)據(jù)集中任意形狀的簇。不過DBSCAN算法仍存在一些缺點(diǎn)，其對區(qū)域半徑R以及數(shù)量閾值Min的設(shè)定很敏感，對此二參數(shù)稍作改動都有可能導(dǎo)致差別較大的結(jié)果。

通過DBSCAN算法可以得到每個時間片上的快照集群，得到每個時間片上快照集群所在城市區(qū)域，即得到各時間片交通擁擠的區(qū)域。記錄各時間片擁擠區(qū)域ID，若擁擠區(qū)域持續(xù)一定的時間，即檢測到城市交通擁堵區(qū)域。若某區(qū)域經(jīng)常出現(xiàn)擁堵情況，則該區(qū)域需要進(jìn)一步作城市交通道路規(guī)劃調(diào)整。

3 實(shí)驗(yàn)結(jié)果與結(jié)論分析

首先，對數(shù)據(jù)進(jìn)行時間片分割，得到每個時間片上的車輛GPS軌跡數(shù)據(jù)。其次，本文針對各個時間片上的GPS數(shù)據(jù)進(jìn)行DBSCAN聚類，其中的部分聚類結(jié)果效果圖如圖1所示，設(shè)圖1的時間片時間為第m個時間片。

（a） 時間片m上的聚類結(jié)果

（a）Result of DBSCAN Algorithm on time slice m

（b） 時間片m+1上的聚類結(jié)果

（b）Result of DBSCAN Algorithm on time slice m+1

（c） 時間片m+2上的聚類結(jié)果

（c）Result of DBSCAN Algorithm on time slice m+2

圖1 連續(xù)時間片的聚類結(jié)果

Fig.1 Result of DBSCAN Algorithm

從圖1（a）和圖1（b）的圓圈處可看到各個時間片上的聚類結(jié)果的變化，各快照集群位置有些細(xì)微變化，某一些簇的邊界或位置已經(jīng)發(fā)生了改變。

將聚類結(jié)果與地圖相映射，某一時刻的城市擁堵區(qū)域檢測結(jié)果如圖2所示。

圖2 城市擁堵區(qū)域在路網(wǎng)上的映射

Fig.2 Heavy Traffic Areas Mapped to The City Road Network

圖2中深色部分為擁堵程度較重的區(qū)域，淺色為擁堵程度次重的區(qū)域。

4 結(jié)束語

本文將得到城市擁堵區(qū)域ID以及其擁堵時間，由于本文所使用的DBSCAN算法對參數(shù)比較敏感，本文將進(jìn)一步找到較為合適的算法參數(shù)。其后的下一研究方向則是結(jié)合本文所得到的結(jié)果，運(yùn)用概率模型，針對地圖區(qū)域，推測出區(qū)域下一次出現(xiàn)群體的時間。這一研究則可為交通指揮人員提供有利信息，使其能夠預(yù)先掌握即將出現(xiàn)交通問題的區(qū)域，并利于其智能型和前瞻性的工作調(diào)度，因而本文研究成果必將具備重大的現(xiàn)實(shí)意義及價值。

參考文獻(xiàn)：

[1] 周曉昌. 城市交通擁堵問題研究[J]. 價值工程， 2014，（28）：86-87.

[2] 單國慧， 程濤， 楊培章，等. 運(yùn)動目標(biāo)軌跡的時空數(shù)據(jù)模型研究[J]. 測繪科學(xué)， 2007， 32（3）：33-35.

[3] ZHENG V W， ZHENG Y， YANG Q. Joint learning user's activities and profiles from GPS data[C]//Proceedings of the 2009 International Workshop on Location Based Social Networks， [S.l.]：ACM， 2009： 17-20.

[4] 某北方城市12000輛出租車GPS位置數(shù)據(jù)（2012年11月）. http：//www.datatang.com/data

/44502，2013-09-16 16：50

[5] BIRANT D， KUT A. ST-DBSCAN： An algorithm for clustering spatial–temporal data[J]. Data & Knowledge Engineering， 2007， 60（1）： 208-221.

[6] VENESS C. Calculate distance， bearing and more between Latitude/Longitude points[J]. not dated， http：//www. movable-type. co. uk/scripts/latlong. html， 2010.