基于交通指數聚類的路網區域動態劃分

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

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

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

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

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

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

1 城市路網區域動態劃分方法

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

圖1 路網區域動態劃分方法流程Fig.1 Flowchart of the dynamic division method of traffic road network area

1.1 地圖網格劃分

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

1.2 網格交通指數計算

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

一個路網區域的交通指數可由式（1）計算得到，即

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

1.3 網格特征提取

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

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

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

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

1.4 樣本特征矩陣聚類

a. 初始聚類。

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

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

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

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

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

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

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

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

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

b. 奇異網格標簽的修正。

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

圖1（d）展示了中心網格的四連通和八連通區域內的奇異網格。可以看到奇異網格與四連通和八連通區域內絕大多數網格的顏色明顯不同。為便于后續論述，先給出四連通與八連通區域的基本概念。

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

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

圖2 奇異網格示意圖Fig.2 Examples of singular grids

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

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

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

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

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

1.5 產生路網區域

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

2 相關實驗

2.1 數據來源

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

2.2 交通指數顏色映射

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

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

2.3 聚類算法精度評價指標

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

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

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

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

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

式中：N表示城市路網中的區域總數；Pk表示第k個區域的劃分精度；Pave指標用來衡量整個城市路網劃分的平均精度。

2.4 實驗驗證

實驗部分根據如下思路進行組織：實驗1分別對不同的路網區域劃分方法的精度進行定性和定量分析，實驗2對不同的路網區域劃分方法的穩定性進行驗證。

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

a.方法精度驗證。

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

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

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

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

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

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

b. 方法穩定性驗證。

如圖7（a）～（i）所示，對基于k-means++聚類算法的路網區域劃分方法在不同時間段上的穩定性進行驗證，選取的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。縱觀整個路網區域，劃分結果會隨著不同時間段的交通指數發生一定的變化。但是，總體上同一區域的劃分結果不會發生太大的空間區域變化。實驗結果證實了基于k-means++聚類算法的路網區域劃分方法其穩定性較為良好。

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

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

3 結論

提出了一種基于交通指數聚類的路網區域動態劃分方法，該方法能夠對城市路網區域實現動態劃分，并具有良好的劃分精度和穩定性。本文創新性地提出了衡量不同城市路網區域劃分方法的精度衡量指標，使對路網區域劃分方法的精度進行定量分析成為可能。通過將基于k-means++聚類算法的路網區域劃分方法與其他3種方法進行實驗對比，實驗結果表明，基于k-means++聚類算法的路網區域劃分方法相比于其他3種方法具有更好的劃分精度和穩定性。在今后的研究中，可以將性能更加優越的聚類算法引入到城市路網區域劃分中，進一步提高路網區域劃分的性能。