基于交通指數(shù)聚類的路網(wǎng)區(qū)域動態(tài)劃分

侯軍軍， 龍佰超， 王洪鈺， 肖建力

（上海理工大學 光電信息與計算機工程學院，上海 200093）

現(xiàn)有的交通狀態(tài)預報方法通常以較小空間尺度的路段作為研究對象。例如，高德地圖和百度地圖顯示的交通狀態(tài)就是以路段的不同顏色來表示。然而，在某些情形下，大空間尺度的路網(wǎng)交通狀態(tài)預報往往更為重要，特別是對宏觀路網(wǎng)區(qū)域交通狀態(tài)的預報。例如，假設需要選擇一個交通狀態(tài)良好的區(qū)域舉辦一場演唱會，選擇徐家匯還是人民廣場區(qū)域，此時，需要對區(qū)域的交通狀態(tài)進行評價。然而，對區(qū)域交通狀態(tài)進行評價，首先必須產(chǎn)生路網(wǎng)區(qū)域。因此，本文主要關注路網(wǎng)區(qū)域劃分方法的研究。

早期的城市路網(wǎng)區(qū)域劃分主要根據(jù)行政區(qū)域及土地性質(zhì)等因素來進行[1]。該方法主要用于研究區(qū)域的演變及其空間格局的變化，其特點是將鄉(xiāng)鎮(zhèn)街道的變化等因素融入路網(wǎng)區(qū)域劃分的研究中。近年來，路網(wǎng)交通狀態(tài)的預報對路網(wǎng)區(qū)域劃分的目標提出了更高的要求，需要進行路網(wǎng)區(qū)域劃分后得到的區(qū)域盡量能夠反映本區(qū)域的交通特性，如果仍然基于之前的思路進行劃分，顯然已無法滿足現(xiàn)代路網(wǎng)區(qū)域劃分的要求[2]。國內(nèi)外學者對此展開了深入的研究。

目前，國內(nèi)學者對城市路網(wǎng)區(qū)域劃分的研究，大體上可以分為兩種思路：一種是以路網(wǎng)內(nèi)交叉口的交通特性作為劃分標準，將交通特性相近的交叉路口劃分為同一個交通區(qū)域，這種路網(wǎng)劃分方法稱為聚類分析方法[3]；第二種是考慮交通路網(wǎng)中所有路段的交叉口，再通過已經(jīng)規(guī)定好的搜索規(guī)則，對符合搜索規(guī)則的交叉口路段統(tǒng)一考慮后劃入同一個區(qū)域，這種路網(wǎng)劃分方法稱為遍歷搜尋法[4]。Moore等[5]提出兩步劃分法，將路網(wǎng)劃分分成兩步：初次劃分時依據(jù)交叉路口的流量大小以及信號控制參數(shù)作為劃分的標準，通過聚類分析完成初次的區(qū)域劃分；然后加入最大綠波帶優(yōu)化模型，并以信號配時優(yōu)化為目標，在初次劃分的結果上對路網(wǎng)區(qū)域?qū)崿F(xiàn)二次劃分。Geroliminis等[6]提出了宏觀基本圖的概念，通過應用示例數(shù)據(jù)區(qū)交通流進行數(shù)據(jù)分析，發(fā)現(xiàn)城市路網(wǎng)中均存在“回滯環(huán)”的現(xiàn)象，即宏觀基本圖客觀存在且具有不隨時間變化的共性，這為城市路網(wǎng)區(qū)域劃分提供了新的研究思路。

總體來看，現(xiàn)有的路網(wǎng)區(qū)域劃分方法的研究還是不夠成熟，不能夠適應現(xiàn)代路網(wǎng)區(qū)域劃分的要求。為此，本文提出了基于交通指數(shù)聚類的路網(wǎng)區(qū)域動態(tài)劃分方法。為驗證城市路網(wǎng)區(qū)域劃分方法的性能，采用基于k-means++聚類算法[7]的路網(wǎng)區(qū)域劃分方法進行區(qū)域劃分，并與其他聚類方法進行對比。結果表明，本文提出的路網(wǎng)區(qū)域劃分方法的精度要優(yōu)于其他對比方法，且具有良好的穩(wěn)定性。

1 城市路網(wǎng)區(qū)域動態(tài)劃分方法

圖1呈現(xiàn)了基于聚類的路網(wǎng)區(qū)域劃分方法的流程，其具體步驟為：第一步，對整個城市區(qū)域進行網(wǎng)格劃分，路網(wǎng)中的路段被網(wǎng)格切分成不同的子路段，每個子路段都從屬于某個特定的網(wǎng)格；第二步，計算每個網(wǎng)格的交通指數(shù)；第三步，對每個網(wǎng)格提取特征，建立樣本特征矩陣；第四步，對樣本特征矩陣進行聚類，得到初始聚類標簽；第五步，對奇異網(wǎng)格的標簽進行修正，得到網(wǎng)格的最終標簽，同時對面積過小的區(qū)域進行合并；最后，將具有相同標簽的網(wǎng)格組成一個路網(wǎng)區(qū)域，對城市路網(wǎng)區(qū)域劃分的結果進行可視化，得到最終的劃分結果。

圖1 路網(wǎng)區(qū)域動態(tài)劃分方法流程Fig.1 Flowchart of the dynamic division method of traffic road network area

1.1 地圖網(wǎng)格劃分

本文提出的路網(wǎng)區(qū)域動態(tài)劃分方法，其主要思路是先將整個路網(wǎng)區(qū)域劃分成相同大小的網(wǎng)格，然后對網(wǎng)格進行聚類，從而得到路網(wǎng)區(qū)域。要實現(xiàn)這一想法，首先需要對整個城市區(qū)域進行網(wǎng)格劃分。先選定整個城市的路網(wǎng)區(qū)域，該區(qū)域為一個矩形區(qū)域。然后，將其劃分為N×N的網(wǎng)格，其中，N為矩形區(qū)域的長或?qū)挼牡确謹?shù)且N為正整數(shù)。在本文的研究中，將整個上海區(qū)域劃分成50×50的網(wǎng)格。自然地，一條長的路段會被網(wǎng)格切分成不同的子路段，每個子路段將從屬于一個唯一的網(wǎng)格。得到網(wǎng)格后，在接下來的小節(jié)中將為每個網(wǎng)格計算交通指數(shù)。

1.2 網(wǎng)格交通指數(shù)計算

交通暢通指數(shù)[8]被定義為在給定時間段內(nèi)，城市路網(wǎng)或區(qū)域的總體暢通程度的相對數(shù)，它是一個無量綱的量。交通暢通指數(shù)的區(qū)間為[0，100]，數(shù)值大小與暢通程度成正比，即數(shù)值越大表示狀態(tài)越暢通，數(shù)值越小則越擁堵[9]。本文將交通暢通指數(shù)簡稱為交通指數(shù)。

一個路網(wǎng)區(qū)域的交通指數(shù)可由式（1）計算得到，即

式中：TFI表示一個網(wǎng)格的交通指數(shù)；i代表當前路網(wǎng)區(qū)域中的第i條子路段；r代表當前區(qū)域?qū)儆诘趓種路網(wǎng)；t代表當前時間屬于第t個時間段；vi為路段實際交通流速度；vfr為不同路網(wǎng)下的路段的自由流車速，根據(jù)路網(wǎng)為快速路、地面主干道、次干道、支路以及高速公路取不同的值；li為路段i的里程長度；ki為路段的車道數(shù)；wt為時間權重系數(shù)，按高峰時段和平峰時段取不同的權重；wr為路網(wǎng)權重系數(shù)，根據(jù)路網(wǎng)屬于快速路、地面主干道、地面次干道、地面支路、高速公路取不同的權重。

1.3 網(wǎng)格特征提取

為了后續(xù)對網(wǎng)格進行聚類，必須先對每個網(wǎng)格進行特征提取。可以由網(wǎng)格連續(xù)一段時間內(nèi)的交通指數(shù)以及網(wǎng)格的坐標來構造該網(wǎng)格的特征向量。例如，取一個小時內(nèi)網(wǎng)格的交通指數(shù)，由于指數(shù)的計算周期是10 min/次，即一共取6組交通指數(shù)加入到網(wǎng)格的特征向量中。對于第i個網(wǎng)格，其特征向量可以表示為

式中：fi表示第i個網(wǎng)格的特征向量；（x,y）表示第i個網(wǎng)格的坐標；TFIi,1表示第i個網(wǎng)格的第1個計算周期的交通指數(shù)，其余的5個交通指數(shù)以此類推。

對所有網(wǎng)格均作類似處理，可以得到由所有網(wǎng)格的特征向量組成的樣本特征矩陣。由于本文中路網(wǎng)劃分是按照50×50來進行劃分的，即一共有2 500個網(wǎng)格。于是，樣本特征矩陣可表示為

可以將樣本特征矩陣F表示為列向量的形式，即有

1.4 樣本特征矩陣聚類

a. 初始聚類。

得到樣本特征矩陣后，需要對其進行聚類，從而產(chǎn)生初始的聚類標簽。一些常見的聚類算法都可以用來執(zhí)行聚類任務，例如，k-means聚類算法[10]、k-means++聚類算法、Birch聚類算法[11]和AGNES聚類算法[12]等。本文采用k-means++聚類算法進行樣本特征矩陣的聚類。

在k-means++聚類算法中，數(shù)據(jù)點與聚類中心之間的最近距離用D(x)表示，其中μo(o=1,2,···,n)表示n個聚類中心點，D(x)的具體計算公式[13]如下：G={g1,g2,···,gk}，則聚類中心的數(shù)學表達式可以表示為[13]

k-means++聚類算法在聚類中心點的選取過程中引入了概率的思想：將每一個被選中的樣本數(shù)據(jù)點概率與距其最近的已選中心點的距離相互聯(lián)系，這樣距離越大被選中的概率就越大。選取好k-means++聚類中心點后，還需要對選定的聚類中心點進行不斷更新，直到聚類中心點不再發(fā)生變化。假定類別數(shù)為k，則聚類中心G可以表示為

式中：gk表示第k類樣本簇的中心點；|Gk|表示第k類樣本簇的樣本總數(shù)；Ak表示第k類樣本簇的樣本集合；xi表示第k類樣本簇的第i個樣本。kmeans++聚類算法的具體步驟如下：

步驟1從輸入的樣本特征數(shù)據(jù)F={x1,x2,···,xn}中隨機選擇一個數(shù)據(jù)點作為第一個聚類中心點μ1；

步驟2對于數(shù)據(jù)點xi，計算數(shù)據(jù)點與第一個聚類中心點的最近距離；

步驟3選擇新的數(shù)據(jù)點作為新的聚類中心點，其中選取的原則為D（x）中距離較大的點，其被選為聚類中心點的概率較大；

步驟4重復上述步驟2和步驟3，選出k個聚類中心點，然后對其更新，直到滿足所有條件，輸出聚類標簽。

通過k-means++聚類算法對樣本特征矩陣進行初始的聚類后，可以得到網(wǎng)格的聚類標簽。圖1（b）為網(wǎng)格數(shù)為10、類別數(shù)為6的帶有聚類標簽的可視化效果圖，數(shù)字代表每個小網(wǎng)格的聚類標簽。注意，該圖只是一個示意圖，為給讀者一個直觀的展示。

b. 奇異網(wǎng)格標簽的修正。

通過初始聚類得到聚類標簽，然后對具有相同類別標簽的網(wǎng)格著上同一種顏色，得到初始聚類的可視化結果圖，如圖1（c）所示。為了更清楚地觀察到初始聚類可視化結果圖中存在的奇異網(wǎng)格，對圖1（c）進行局部放大，結果如圖1（d）所示。對其中存在的部分奇異網(wǎng)格用紅色方框標識出來。所謂奇異網(wǎng)格是指其標簽（即顏色）與周圍鄰域內(nèi)網(wǎng)格的絕大多數(shù)標簽存在明顯差異的網(wǎng)格。奇異網(wǎng)格的標簽可能是錯誤的，因此，需要采用正確的方法對奇異網(wǎng)格的標簽進行修正。

圖1（d）展示了中心網(wǎng)格的四連通和八連通區(qū)域內(nèi)的奇異網(wǎng)格?？梢钥吹狡娈惥W(wǎng)格與四連通和八連通區(qū)域內(nèi)絕大多數(shù)網(wǎng)格的顏色明顯不同。為便于后續(xù)論述，先給出四連通與八連通區(qū)域的基本概念。

根據(jù)數(shù)字圖像處理[14]中的相關理論，四連通區(qū)域是指處于中心網(wǎng)格上、下、左、右，緊鄰的4個網(wǎng)格區(qū)域，如圖2（a）所示。共有4個方向，所以稱為四連通區(qū)域，又稱四鄰域。假設中心網(wǎng)格p的坐標為（x,y），則四連通數(shù)學含義可定義為

同理，八連通區(qū)域，是指在中心網(wǎng)格的上、下、左、右、左上、右上、左下、右下，是緊鄰的網(wǎng)格和斜向相鄰的網(wǎng)格區(qū)域組成的全體，共8個方向，所以稱之為八連通區(qū)域或八鄰域，如圖2（b）所示。假設中心網(wǎng)格p的坐標為（x,y），則八連通數(shù)學含義可定義為

圖2 奇異網(wǎng)格示意圖Fig.2 Examples of singular grids

本文提出一種基于八連通多數(shù)投票的奇異網(wǎng)格標簽修正方法，其具體步驟如下：

步驟1輸入初始聚類標簽；

步驟2判斷在中心網(wǎng)格的八連通區(qū)域中是否存在奇異網(wǎng)格，如果存在奇異網(wǎng)格，則將奇異網(wǎng)格聚類標簽修正為八鄰域內(nèi)數(shù)目最多的標簽，同時中心網(wǎng)格右移一個網(wǎng)格，直到所有奇異網(wǎng)格的聚類標簽都得到修正，否則重復步驟1和步驟2；

步驟3輸出修正后的聚類標簽。

經(jīng)過基于八連通多數(shù)投票的奇異網(wǎng)格標簽修正后，即可得到初始的路網(wǎng)區(qū)域劃分，觀察各個區(qū)域，一旦發(fā)現(xiàn)某個區(qū)域的面積過小，且其顏色與周圍面積較大區(qū)域的顏色相近，則將該區(qū)域進行合并。

1.5 產(chǎn)生路網(wǎng)區(qū)域

對于上述步驟得到的區(qū)域，還需要用輪廓線進行標識，具體方法為：通過比較各網(wǎng)格的聚類標簽來畫出城市路網(wǎng)區(qū)域的輪廓線。首先確定輪廓線起點，接下來如果兩個聚類標簽不相同就在兩個聚類標簽中間畫一條直線，相同則不作處理，依次迭代下去，直到將所有聚類簇的輪廓線都畫出來為止。最終得到城市路網(wǎng)區(qū)域劃分結果，如圖1（f）所示。

2 相關實驗

2.1 數(shù)據(jù)來源

本文實驗部分的GPS數(shù)據(jù)來源于上海市交通信息中心，時間為2012年2月1日，一天24 h的GPS數(shù)據(jù)。

2.2 交通指數(shù)顏色映射

為了后續(xù)驗證路網(wǎng)區(qū)域劃分方法的精度，將網(wǎng)格的交通指數(shù)映射為不同的顏色，顏色映射的規(guī)則為：將交通指數(shù)由0到100分別映射為深紅到深綠色，顏色會隨著交通指數(shù)數(shù)值由小到大呈現(xiàn)出不斷漸變的過程[15-16]。其中，某些缺少交通指數(shù)的網(wǎng)格則用白色表示，效果圖如圖3所示。

圖3 交通指數(shù)顏色映射圖Fig.3 Map generated by mapping the traffic indexes into the color space

2.3 聚類算法精度評價指標

將城市路網(wǎng)區(qū)域劃分結果圖1（f）疊加到圖3中得到圖4。在圖4中紅色線段所框出來的區(qū)域中，組成區(qū)域的網(wǎng)格主要由兩部分組成，主基色網(wǎng)格以及輔基色網(wǎng)格。所謂主基色網(wǎng)格是指一個區(qū)域內(nèi)顏色接近且網(wǎng)格數(shù)目占絕大多數(shù)的網(wǎng)格，輔基色網(wǎng)格則是指區(qū)域內(nèi)除了主基色網(wǎng)格之外的其他顏色網(wǎng)格。一般而言，輔基色網(wǎng)格的顏色與主基色網(wǎng)格顏色不同，且其網(wǎng)格數(shù)量占該區(qū)域的少數(shù)。區(qū)域面積則可由該區(qū)域內(nèi)的網(wǎng)格總數(shù)來表示，也即主基色網(wǎng)格數(shù)量和輔基色網(wǎng)格數(shù)量的總和。

圖4 路網(wǎng)區(qū)域及區(qū)域中的主基色網(wǎng)格和輔基色網(wǎng)格Fig. 4 Traffic road network areas and the major color grids and minor color grids in these areas

為了評價不同城市路網(wǎng)區(qū)域劃分方法的精度，創(chuàng)新性地提出了一個衡量某個區(qū)域劃分精度的指標P，其計算公式為

式中：P表示當前區(qū)域的劃分精度，P值越小表示劃分精度越好，P值越大表示劃分精度越不理想；H表示路網(wǎng)區(qū)域中的主基色網(wǎng)格數(shù)量；hi為第i種輔基色網(wǎng)格的數(shù)目，n為輔基色顏色的總數(shù)，表示路網(wǎng)區(qū)域中輔基色網(wǎng)格總數(shù)；S表示當前區(qū)域的面積大小，即當前區(qū)域內(nèi)網(wǎng)格的總數(shù)。

為了衡量整個路網(wǎng)劃分的精度，可以計算P的平均值Pave，即有

式中：N表示城市路網(wǎng)中的區(qū)域總數(shù)；Pk表示第k個區(qū)域的劃分精度；Pave指標用來衡量整個城市路網(wǎng)劃分的平均精度。

2.4 實驗驗證

實驗部分根據(jù)如下思路進行組織：實驗1分別對不同的路網(wǎng)區(qū)域劃分方法的精度進行定性和定量分析，實驗2對不同的路網(wǎng)區(qū)域劃分方法的穩(wěn)定性進行驗證。

將k-means++聚類算法與k-means聚類算法、AGNES聚類算法以及Birch聚類算法4種方法對比驗證。k-means聚類算法流程如下：首先設置聚類的類別數(shù)k，然后從樣本數(shù)據(jù)中隨機選取k個樣本作為初始的聚類中心，通過計算聚類中心與樣本數(shù)據(jù)點之間的距離，把每個數(shù)據(jù)點分配到距離它最近的聚類中心；再將同一類別的所有樣本數(shù)據(jù)特征取平均值，并將平均后所得的數(shù)據(jù)點作為新的聚類中心；最后，重復上述步驟直到聚類中心滿足終止條件，輸出聚類標簽。AGNES聚類算法采取自下而上的聚類思想。首先將樣本數(shù)據(jù)作為一個聚類簇，然后根據(jù)一定的相似性度量將這些聚類簇逐漸合并成一個大的聚類簇，直到達到初始設定的類別數(shù)為止。Birch聚類算法引入聚類特征和聚類特征樹兩個新的概念來概括對聚類的描述。其中，聚類特征樹概括了聚類中的有用信息，占用的空間比原來的數(shù)據(jù)集要小，這節(jié)約了內(nèi)存空間，提升了Birch算法在大型數(shù)據(jù)集上的聚類速度[17-20]。

a.方法精度驗證。

分別選取以下4個時間段：04:00—04:20、17:40—18:00、08:00—08:20、00:40—01:00，通過定性分析和定量計算驗證基于k-means++聚類算法的路網(wǎng)區(qū)域劃分方法的精度。

定性分析，以圖5（a）～（d）的結果，基于kmeans++聚類算法的路網(wǎng)區(qū)域劃分方法的精度，對其展開定性分析。通過觀察圖5（a）～（d）發(fā)現(xiàn)各個路網(wǎng)區(qū)域中網(wǎng)格的顏色一致性較強，這表明路網(wǎng)區(qū)域劃分的精度較高。

圖5 k-means++聚類算法的精度驗證Fig.5 Accuracy verification of k-means++ clustering algorithm

定量分析，通過對城市路網(wǎng)的各區(qū)域分別計算精度性能評價指標P，然后計算P的均值Pave來評價路網(wǎng)區(qū)域劃分方法的精度，Pave值越小精度越高。選取的交通指數(shù)時間段為17:40—18:00。圖6（a）～（d）分別為基于k-means++，k-means，AGNES，Birch聚類算法的路網(wǎng)區(qū)域劃分方法的劃分結果，由圖6（a）～（d）分別計算各方法劃分結果的Pave值，并總結于表1中。由表1可知，基于k-means++聚類算法的路網(wǎng)區(qū)域劃分方法精度最高。

表1 不同方法的Pave值Tab.1 Pave values of different methods

圖6 不同聚類算法對比圖Fig. 6 Comparison of different clustering algorithms

b. 方法穩(wěn)定性驗證。

如圖7（a）～（i）所示，對基于k-means++聚類算法的路網(wǎng)區(qū)域劃分方法在不同時間段上的穩(wěn)定性進行驗證，選取的9個時間段分別是：12:00—12:20、13:00—13:20、14:00—14:20、15:00—15:20、16:00—16:20、17:00—17:20、18:00—18:20、19:00—19:20和20:00—20:20?？v觀整個路網(wǎng)區(qū)域，劃分結果會隨著不同時間段的交通指數(shù)發(fā)生一定的變化。但是，總體上同一區(qū)域的劃分結果不會發(fā)生太大的空間區(qū)域變化。實驗結果證實了基于k-means++聚類算法的路網(wǎng)區(qū)域劃分方法其穩(wěn)定性較為良好。

圖7 k-means++聚類算法穩(wěn)定性驗證Fig.7 Stability verification of k-means++ clustering algorithm

分別在9個不同時間段的路網(wǎng)區(qū)域劃分結果圖中選取5個空間地理位置接近的區(qū)域，通過觀察這5個區(qū)域在不同時間段上形狀的變化，來定性分析算法的穩(wěn)定性。如圖7（a）～（i）所示，選取的區(qū)域為：區(qū)域No.1、區(qū)域No.2、區(qū)域No.3、區(qū)域No.4和區(qū)域No.5，采用不同顏色的輪廓線對5個區(qū)域進行標注。通過對比9個時間段上的城市路網(wǎng)區(qū)域劃分的結果，發(fā)現(xiàn)在不同的時間段上，5個區(qū)域面積大小、劃分區(qū)域的路網(wǎng)拓撲結構沒有發(fā)生較大變化。這從局部細節(jié)上反映了基于kmeans++聚類算法的路網(wǎng)區(qū)域劃分方法的穩(wěn)定性較為良好。

3 結論

提出了一種基于交通指數(shù)聚類的路網(wǎng)區(qū)域動態(tài)劃分方法，該方法能夠?qū)Τ鞘新肪W(wǎng)區(qū)域?qū)崿F(xiàn)動態(tài)劃分，并具有良好的劃分精度和穩(wěn)定性。本文創(chuàng)新性地提出了衡量不同城市路網(wǎng)區(qū)域劃分方法的精度衡量指標，使對路網(wǎng)區(qū)域劃分方法的精度進行定量分析成為可能。通過將基于k-means++聚類算法的路網(wǎng)區(qū)域劃分方法與其他3種方法進行實驗對比，實驗結果表明，基于k-means++聚類算法的路網(wǎng)區(qū)域劃分方法相比于其他3種方法具有更好的劃分精度和穩(wěn)定性。在今后的研究中，可以將性能更加優(yōu)越的聚類算法引入到城市路網(wǎng)區(qū)域劃分中，進一步提高路網(wǎng)區(qū)域劃分的性能。